Ленивые последовательности, которые “Смотрят вперед” для решения задачи проекта Эйлера 14

Question

Я пытаюсь решить Проектная задача Эйлера 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)))))

Это работает, но работает очень медленно.Конечно, я мог бы запомнить это:

(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.

Поскольку отложенные списки требуют гораздо меньших накладных расходов, чем запоминание, я хотел бы знать, возможно ли подобное каким-либо образом с помощью еще более отложенной оценки или постановки в очередь?

Answer 1

Следующее дает мне ленивую последовательность значений collatz.Что касается микробенчмарков на моей машине, то это слегка превосходит записанное решение.С другой стороны, он также рекурсирует слишком глубоко, чтобы найти 1 миллион длин цепочки collatz, и стек переполняется где-то между 100 000-м и 1 000 000-м элементами, но это можно решить, немного поработав и recur.

 (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), а затем разматываться, заполняя отложенную структуру данных фактическими значениями по мере разматывания рекурсии.Если мы думаем о ленивой последовательности как о ленивом связанном списке, то мне нужен был ленивый вектор или дерево бесконечной длины, которое автоматически определяло бы зависимости своих данных с помощью правила Collatz.Для решения этой задачи было достаточно хэш-карты, но это в некотором смысле лишь приближение к тому, что я хотел:отложенный вектор потока данных с правилом, применяемым к способу заполнения элементов в векторе.

Сверхтрудный Вызов:Кто-нибудь может придумать способ легко представить такое ленивое дерево / вектор без использования hashmap?

Answer 2

Продолжение "взгляд в будущее"

Пример фанкового продолжения, заглядывающего в будущее, может выглядеть следующим образом:

(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)

(Печенье тому, кто сделает это проще, не ломая его.:-))

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

Эйлер 14

Фундаментальная проблема со схемой "заглядывания в будущее", которую пытается использовать код из вопроса, в стороне, этот подход на самом деле не решает проблему, потому что, если вы решите начать с 1 и идти вверх, вам необходимо учитывать ветвление:a 10 в цепочке Collatz это может быть достигнуто путем применения любого правила ( n / 2 правило, применяемое к 20 или тот 3n + 1 правило, начинающееся с 3).Кроме того, если вы хотите построить свои цепочки по восходящей, вам следует изменить правила на противоположные и либо умножить на 2 или вычтите 1 и разделить на 3 (применяя на каждом шаге то правило, которое выдает целое число - или, возможно, и то, и другое, если оба делают).

Конечно, вы могли бы построить дерево, а не отложенный список, но это не было бы похоже на набросок кода в вопросе, и я бы ожидал, что вы в конечном итоге запомните это.

Вышесказанное следует дополнить замечанием о том, что у вас может быть предположение относительно того, какое "правило построения цепочки", скорее всего, сгенерирует самую длинную цепочку, начиная с 1 при этом итоговая запись остается ниже заданного лимита.Если это так, то вам, вероятно, следует докажите, что это правильно а затем реализовать это напрямую (через loop / recur начиная с 1);без доказательств вы не можете на самом деле утверждать, что решили проблему.

Answer 3

Я думаю , что 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)