Е
Вернее, скажем так: в Фибоначчи нету acc
есть, конечно, просто он не аккумулирует данные,
Size: a a a
2020 August 27
Е
ща накидаю
AB
я в этой сомнительной дискуссии могу только отметить, что вчера написал один там depth-first traversal без аккумулятора, и сегодня считаю это очень большой глупостью.
а еще в нем, собственно, присутствует Enum.into в лист, что вообще говоря не дорого, но вызывает некоторок отвращение
LL
Так получается только в одном конкретном случае. И не из-за проблемы с хвостовой рекурсией, а из-за оптимизации для функций
f, возвращающих [some_value | f(args)]Мои сообщения просто игнорируются :/
LL
Фибоначчи пишется хвостовой рекурсией, всё нормально
Е
Проверил. Фибоначчи хвостовая куда шустрее обычной:
defmodule Fib do
def calc(1), do: 1
def calc(2), do: 1
def calc(n), do: calc(n - 2) + calc(n - 1)
end
defmodule FibTail do
def calc(1), do: 1
def calc(2), do: 1
def calc(n), do: calc(n - 2, 1, 1)
def calc(0, _, n2), do: n2
def calc(n, n1, n2), do: calc(n - 1, n2, n1 + n2)
end
#IO.puts Fib.calc(100)
IO.puts FibTail.calc(100)
LL
Проверил. Фибоначчи хвостовая куда шустрее обычной:
defmodule Fib do
def calc(1), do: 1
def calc(2), do: 1
def calc(n), do: calc(n - 2) + calc(n - 1)
end
defmodule FibTail do
def calc(1), do: 1
def calc(2), do: 1
def calc(n), do: calc(n - 2, 1, 1)
def calc(0, _, n2), do: n2
def calc(n, n1, n2), do: calc(n - 1, n2, n1 + n2)
end
#IO.puts Fib.calc(100)
IO.puts FibTail.calc(100)
Конечно быстрее, потому что в обычной банально количество вызовов больше
Е
100 элементов обычной у меня даже не успевает выполниться в онлайн-компилерах
Е
Конечно быстрее, потому что в обычной банально количество вызовов больше
в два раза, а время рассчета во много раз больше отличается
Е
или не в два раза :)
Е
и отличается ли?
LL
в два раза, а время рассчета во много раз больше отличается
Нет, не в два раза
В хвостовой
В обычной
В хвостовой
fib(n) — n вызововВ обычной
fib(n) — 2^n вызововЕ
по одному вызову на каждое число фибоначчи вроде и там и там
ŹR
Алгоритм просто соптимизированный
LL
Алгоритм просто соптимизированный
Что ты имеешь в виду?
ŹR
Ну что так скорости не меряют
ŹR
Один алгоритм тупо быстрее
Е
Нет, не в два раза
В хвостовой
В обычной
В хвостовой
fib(n) — n вызововВ обычной
fib(n) — 2^n вызововА почему 2^n?
ŹR
Он математически соптимизирован, а не компилятором
LL
Один алгоритм тупо быстрее
Вот именно, тут разницу
body vs tail не померять