Ленивые Последовательности, которые “Смотрят вперед” для Euler проблемы Проекта 14
Я пытаюсь решить Euler проблему Проекта 14 ленивым способом. К сожалению, я могу пытаться сделать невозможное: создайте ленивую последовательность, которая оба ленива, все же также так или иначе 'смотрит вперед' для значений, которые она еще не вычислила.
Неленивая версия, которую я записал для тестирования правильности, была:
(defn chain-length [num]
(loop [len 1
n num]
(cond
(= n 1) len
(odd? n) (recur (inc len) (+ 1 (* 3 n)))
true (recur (inc len) (/ n 2)))))
Который работает, но является действительно медленным. Конечно, я мог memoize что:
(def memoized-chain
(memoize
(fn [n]
(cond
(= n 1) 1
(odd? n) (+ 1 (memoized-chain (+ 1 (* 3 n))))
true (+ 1 (memoized-chain (/ n 2)))))))
Однако то, что я действительно хотел сделать, было поцарапать мою жажду понимания пределов ленивых последовательностей и записать функцию как это:
(def lazy-chain
(letfn [(chain [n] (lazy-seq
(cons (if (odd? n)
(+ 1 (nth lazy-chain (dec (+ 1 (* 3 n)))))
(+ 1 (nth lazy-chain (dec (/ n 2)))))
(chain (+ n 1)))))]
(chain 1)))
Получение по запросу элементов от этого вызовет переполнение стека для n> 2, который понятен, если Вы думаете о том, почему это должно 'изучить будущее' в n=3 для знания значения десятого элемента в ленивом списке потому что (+ 1 (* 3 n)) = 10.
Так как ленивые списки имеют намного меньше служебный, чем memoization, я хотел бы знать, возможна ли такого рода вещь так или иначе через еще более задержанную оценку или организацию очередей?
3 ответа
Следующее дает мне ленивую последовательность значений collatz. На микробенчмарках на моей машине это слегка превосходит мемоизированное решение. С другой стороны, он также подвергается слишком глубокой рекурсии, чтобы найти длину цепочки в 1 миллион коллатц, и стек переполняется где-то между 100 000-м и 1 000 000-м элементом, но это может быть решено с небольшой работой и повторяется .
(defn collatz [n cache]
(if-let [v (cache n)]
[v cache]
(let [[p cache] (if (odd? n)
(collatz (+ 1 (* 3 n)) cache)
(collatz (/ n 2) cache))]
[(inc p) (assoc cache n (inc p))])))
(def lazy-collatz
(map first (iterate (fn [[v cache n]]
(concat (collatz n cache) [(inc n)]))
[1 {1 1} 2])))
Тем не менее, это все еще не то, что я хотел: та же самая функциональность без хэш-карты. Думая о превосходном комментарии Михала и концепции построения рекурсивного дерева, я полагаю, что я хотел здесь не ленивую последовательность, а какую-то ленивую рекурсивную структуру данных , возможно, дерево .Существуют ли такие методы потока данных?
Моя первоначальная идея заключалась в том, чтобы построить цепочки «задержек» из неизвестного значения (n), которые продолжаются рекурсивно, пока не достигнут известное число (например, 1), а затем разворачиваются, заполняя ленивую структуру данных. с фактическими значениями по мере развертывания рекурсии. Если мы думаем о ленивой последовательности как о ленивом связанном списке, то мне нужен был ленивый вектор или дерево бесконечной длины, которое автоматически обнаруживало бы свои зависимости данных с помощью правила Коллатца. Для этой проблемы было достаточно хэш-карты, но в некотором смысле это лишь приближение того, что я хотел: вектор ленивого потока данных с правилом, применяемым к тому, как заполнять элементы в векторе.
Сверхсложная задача : Может ли кто-нибудь придумать способ легко представить такое ленивое дерево / вектор без использования хэш-карты?
Последовательность «заглядывая в будущее»
Пример напуганной последовательности, смотрящей в будущее, может выглядеть так:
(def funky-seq
(let [substrate (atom ())]
(letfn [(funk [n] (delay (if (odd? n) n @(nth @substrate (inc n)))))]
(reset! substrate (map funk (range))))
(map deref @substrate)))
user> (take 10 funky-seq)
(1 1 3 3 5 5 7 7 9 9)
(Файл cookie для тех, кто делает это проще, не нарушая его.: -))
Конечно, если определение значения элемента может включать рассмотрение элемента «будущего», который сам зависит от другого элемента, который требует вычисления еще более удаленного элемента ..., с катастрофой ничего не поделать.
Эйлер 14
Фундаментальная проблема со схемой «заглядывания в будущее» код из вопроса пытается использовать в стороне, этот подход на самом деле не решает проблему, потому что, если вы решите начать с 1 и двигаясь вверх , необходимо принять во внимание ветвление: 10 в цепочке Коллатца может быть получено посредством применения любого правила ( n / 2 Правило применяется к 20 или к правилу 3n + 1 , начиная с 3 ). Кроме того, если вы хотите построить свои цепочки вверх, вы должны изменить правила и либо умножить на 2 , либо вычесть 1 и разделить на 3 (применимо, при каждый шаг, то правило, которое дает целое число - или, возможно, оба, если оба делают).
Конечно, вы могли бы построить дерево , а не ленивый список, но это не будет похоже на набросок кода в вопросе, и я ожидаю, что вы в конечном итоге запомните эту вещь .
Сказанное выше должно быть дополнено замечанием о том, что у вас может быть предположение относительно того, какое «правило построения цепочки», вероятно, сгенерирует самую длинную цепочку, начиная с 1 , при этом последняя запись останется ниже данный лимит. Если это так, вам, вероятно, следует доказать его правильность , а затем реализовать его напрямую (с помощью цикла / повторения , начиная с 1 ) ; без доказательства вы не можете утверждать, что проблема решена.
Я думаю, что iterate и take-while могут немного помочь (хотя этот код не смотрит в будущее):
(defn next-collatz [n]
(cond
(= n 1) 1
(odd? n) (+ 1 (* 3 n))
true (/ n 2)))
(defn collatz-seq [n]
(iterate next-collatz n))
(defn collatz [n]
(take-while #(not (= % 1)) (collatz-seq n)))
user> (collatz 100)
=> (100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2)