Lazy Las secuencias que “mirar hacia adelante” para el Proyecto Euler problema 14

Question

Estoy tratando de resolver Proyecto Euler Problema 14 en un perezoso camino. Por desgracia, puede estar tratando de hacer lo imposible: crear una secuencia perezosa que es tanto perezoso, sin embargo, de alguna manera también mira hacia adelante '' para los valores calculados no ha todavía.

La versión no perezoso escribí a la corrección de pruebas fue:

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

Lo que funciona, pero es muy lento. Por supuesto que podría memoize que:

(def memoized-chain
   (memoize
     (fn [n]
       (cond
        (= n 1) 1 
         (odd? n) (+ 1 (memoized-chain (+ 1 (* 3 n))))
         true     (+ 1 (memoized-chain (/ n 2)))))))

Sin embargo, lo que realmente quería hacer era rascarme la comezón para la comprensión de los límites de secuencias perezosos, y escribir una función como esta:

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

Tirando de los elementos de esta provocará un desbordamiento de pila para n> 2, lo cual es comprensible si se piensa en por qué se tiene que buscar 'en el futuro' en n = 3 a conocer el valor del elemento décimo en la lista perezosa porque (+ 1 (* 3 n)) = 10.

Desde listas perezosos tienen mucho menos espacio que los memoization, me gustaría saber si este tipo de cosas es posible de alguna manera a través de la evaluación aún más retardada o colas?

Answer 1

A continuación me da una secuencia perezosa de los valores Collatz. En microbenchmarks en mi máquina, es ligeramente mejor que la solución memoized. En el lado negativo, también recursivamente demasiado profundamente para encontrar 1 millón de longitudes de cadena de Collatz, y la pila se desborda en algún lugar entre el número 100.000 y 1.000.000 elemento, pero que podría resolverse con un poco de trabajo y 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])))

Sin embargo, todavía no es lo que quería: esta misma funcionalidad sin el HashMap. Pensando en excelente comentario de Michal y el concepto de la construcción de un árbol recursivo, supongo que lo que quería aquí no era un perezosa secuencia, sino una recursiva perezoso estructura de datos de algún tipo, probablemente un árbol. Por qué existen tales técnicas de flujo de datos?

Mi idea original era cadenas de generación de 'retrasos' desde el valor desconocido (n) que siguen recursivamente hasta que lleguen a un número conocido (como 1), y luego relajarse, poblar la estructura de datos perezoso con valores reales como la recursividad desenrolla. Si pensamos en una secuencia perezosa como una lista enlazada perezoso, lo que quería era un vector de longitud infinita pereza o árbol que se encuentra a cabo sus dependencias de datos de forma automática utilizando la regla de Collatz. Un HashMap bastó para este problema, pero es en cierto sentido, sólo una aproximación de lo que quería:. Un vector de flujo de datos perezoso con una regla aplica sobre cómo rellenar los elementos en el vector

más duro desafío :? ¿Alguien puede pensar en una forma de fácil representar un árbol / vector tal perezoso y sin el uso de un HashMap

Answer 2

Una ss "mirar hacia el futuro"

Un ejemplo de un cobarde SEC mirar hacia el futuro podría tener este aspecto:

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

(una cookie para el que hace que este simple sin romperlo: -.))

Por supuesto, si la determinación del valor de un elemento podría implicar el examen de un elemento de "futuro" que a su vez depende de un elemento adicional que requiere el cálculo de un elemento aún más distante ..., la catástrofe no se puede evitar.

Euler 14

El problema fundamental con el esquema de "mirar hacia el futuro", el código de los intentos de interrogación para emplear a un lado, este enfoque no soluciona realmente el problema, ya que, si se decide a empezar desde 1 e ir hacia arriba , es necesario tener ramificaciones en cuenta: a 10 en una cadena de Collatz podría llegarse a través de la aplicación de cualquiera de regla (la regla n / 2 aplica a 20 o la regla 3n + 1 partir de 3). Además, si se desea construir sus cadenas hacia arriba, usted debe invertir las reglas y tampoco se multiplica por 2 o 1 restar y dividir por 3 (aplicando, en cada paso, esa regla que produce un número entero - o posiblemente los dos si ambos lo hacen) .

Por supuesto, se podría construir un árbol , en lugar de una lista perezosa, pero eso no se parecía en nada el boceto código en la pregunta y yo esperaría que termina en última instancia, la memoizing cosa.

Lo anterior es para ser calificado con la observación de que es posible que tenga una conjetura en cuanto a que "la construcción de regla de la cadena" es probable que genere la cadena más larga a partir de 1 al tiempo que la estancia de entrada final por debajo del límite dado. Si ese es el caso, probablemente debería demuestras correcta y luego ponerlo en práctica directamente (a través de loop / recur a partir de las 1); sin una prueba, realmente no se puede decir que ha resuelto el problema.

Answer 3

Creo iterate y take-while podrían ser de alguna ayuda (aunque este código no se ve en el futuro):

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