Е
В первом варианте вроде одни и теже числа по нескольку раз не вычисляются
Size: a a a
2020 August 27
LL
А почему 2^n?
Подумой
ŹR
В первом варианте вроде одни и теже числа по нескольку раз не вычисляются
Вычисляются конечно же
Е
Да, вы правы
ŹR
Померяй факториал
LL
Померяй факториал
Хвостовой факториал с аккумулятором будет быстрее, я думаю
Е
Ща другой пример накидаю
ŹR
Нереально померять на факториале - одно и то же
Е
Хвостовой факториал с аккумулятором будет быстрее, я думаю
А вот и нихрена :)))))
Е
У меня хвостовая чуть-чуть медленнее
Е
defmodule Fact do
def calc(1), do: 1
def calc(n), do: calc(n-1) * n
end
defmodule FactTail do
def calc(1), do: 1
def calc(n), do: calc(n, 1)
def calc(1, n1), do: n1
def calc(n, n1), do: calc(n - 1, n * n1)
end
Е
но возможно это что-то другое
Е
а так, соточку мгновенно считает
ŹR
Name ips average deviation median 99th %
body 0.164 6.10 s ±0.00% 6.10 s 6.10 s
tco 0.161 6.22 s ±0.00% 6.22 s 6.22 s
Comparison:
body 0.164
tco 0.161 - 1.02x slower +0.115 s
ŹR
На уровне погрешности
Е
:timer.tc(Fact, :calc, [1000])
{708, 402...}
:timer.tc(FactTail, :calc, [1000])
{815, 402...}
Е
подозреваю, что хитрозадый beam оптимизирует таки и обычную рекурсию в случае с факториалом
Е
насчет аккумулятора мапы - допустим просто подсчет количества повторов в списке и запоминание в мапе
%{элемент => кол-во повторов}Е
можно хвостовой, а можно и обычной
ŹR
И как это сделать обычной?