Как мне написать эту функцию Clojure, чтобы она не уничтожала стек?

Question

Я новичок в Clojure, и я думаю, что мой подход к написанию кода пока не соответствует «Путь Clojure». По крайней мере, я продолжаю писать функции, которые приводят к ошибкам StackOverflow с большими значениями. Я узнал об использовании recur, что стало хорошим шагом вперед. Но как заставить функции, подобные приведенной ниже, работать для таких значений, как 2500000?

(defn fib [i]
  (if (>= 2 i)
    1
    (+ (fib (dec i))
       (fib (- i 2)))))

Эта функция, на мой взгляд, "простая" реализация генератора Фибоначчи. Я видел другие реализации, которые намного более оптимизированы, но менее очевидны с точки зрения того, что они делают. То есть когда вы читаете определение функции, вы не говорите «о, Фибоначчи».

Любые указатели будут с благодарностью!

Answer 1

Вы должны иметь мысленную модель того, как работает ваша функция.Допустим, вы выполняете свою функцию самостоятельно, используя клочки бумаги для каждого вызова.Сначала записка, вы пишете (fib 250000), затем вы видите «о, мне нужно вычислить (fib 249999) и (fib 249998) и, наконец, добавить их», так что вы заметили это и начали два новых записки.Вы не можете выбросить первое, потому что у него все еще есть дела, когда вы закончите другие вычисления.Вы можете себе представить, что для этого расчета понадобится много записок.

Другой способ - начать не сверху, а снизу.Как бы вы сделали это вручную?Вы должны начать с первых чисел, 1, 1, 2, 3, 5, 8…, а затем всегда добавлять последние два, пока не сделаете это i раз.Вы даже можете выбрасывать все числа, кроме последних двух, на каждом шаге, поэтому вы можете повторно использовать большинство записок.

(defn fib [i]
  (loop [a 0
         b 1
         n 1]
    (if (>= n i)
        b
        (recur b
               (+ a b)
               (inc n)))))

Это также довольно очевидная реализация, но из как , а не что .Это всегда кажется довольно элегантным, когда вы можете просто записать определение, и оно автоматически преобразуется в эффективный расчет, но программирование - это преобразование.Если что-то преобразуется автоматически, то эта конкретная проблема уже решена (часто в более общем смысле).

Размышление «как бы я сделал это шаг за шагом на бумаге» часто приводит к хорошей реализации.

Answer 2

Генератор Фибоначчи, реализованный «простым» способом, как в определении последовательности, всегда взорвет ваш стек. Ни один из двух рекурсивных вызовов fib не является хвостовым, такое определение не может быть оптимизировано.

К сожалению, если вы хотите написать эффективную реализацию, работающую для больших чисел, вам придется принять тот факт, что математическая запись не переводит код так же чисто, как нам бы хотелось.

Например, нерекурсивную реализацию можно найти в clojure.contrib.lazy-seqs . Целый ряд различных подходов к этой проблеме можно найти на Haskell wiki . Это не должно быть трудно понять со знанием основ функционального программирования.

Answer 3

 ;;from "The Pragmatic Programmers Programming Clojure"
 (defn fib [] (map first (iterate (fn [[a b]][b (+ a b)])[0N 1N])))
 (nth (fib) 2500000)