Задача из проекта Эйлера 2 в Clojure


Я нахожусь в процессе обучения в Clojure. Я довольно новыми для функционального программирования, и хотел бы знать, если мой код попахивает или если есть какие-либо последствия для производительности с моим подходом.

; Returns the the given sequence with the given item appended to it.
(defn snoc [xs x] (concat xs [x]))

; Returns the Fibonacci sequence up to the highest number less than max.
(defn fib [max] 
  (loop [a 1, b 1, acc [1]] 
    (if (> b max) 
      acc
      (recur b (+ a b) (snoc acc b)))))

; Project Euler Problem 2: Attempt A
(defn pe2a []
  (reduce +
    (filter even? (fib 4000000))))

Для справки:

Каждый новый термин в Фибоначчи последовательность генерируется путем добавления два предыдущих условия. Начиная с 1 и 2, первые 10 условия будут:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

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



Комментарии
2 ответа

(defn snoc [xs x] (concat xs [x]))

Есть повод snoc не определен по умолчанию в Clojure: с добавлением в конец однонаправленного списка занимает o(n) времени, это фактически довольно дорого. Когда создание неленивый списки хвост-рекурсивно в функциональном языке, вы часто строят списка по неверному пути (через минусы вместо snoc), а затем обратить его в конце, чтобы избежать затрат.

Однако в этом случае существует на самом деле лучше так: с помощью ленивой последовательности, а не строгий список, мы можем избежать необходимости для петли/рецидивирует и сэкономить на стоимости строительства до списка. Мы можем также разделить логику создания числа Фибоначчи от логики, которая решает, сколько номеров мы хотим сначала создать ленивый последовательность, содержащую все числа Фибоначчи, а затем, используя взять-а взять эти меньше заданного максимального. Это приведет к следующим кодом:

;; A lazy sequence containing all fibonacci numbers
(def fibs
(letfn
[(fibsrec [a b]
(lazy-seq (cons a (fibsrec b (+ a b)))))]
(fibsrec 1 1)))

;; A function which returns all fibonacci numbers which are less than max
(defn fibs-until [max]
(take-while #(<= % max) fibs))

13
ответ дан 27 января 2011 в 07:01 Источник Поделиться

Я не уверен, если это в качестве комментария здесь, но я построил свое решение на Clojure, а также. Числа Фибоначчи создаются в виде бесконечной последовательности как в "Программирование Хэлоуэй это в Clojure" С. 136. Тогда я сумму, используя список осмысления

;;Programming in Clojure p. 136

(defn fibo [] (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

(defn proj-euler2 []
(reduce + (for [x (fibo) :when (even? x) :while (< x 4000000)] x)))

5
ответ дан 3 февраля 2011 в 06:02 Источник Поделиться