¿Cuál es la diferencia entre la función de Clojure (nth [índice coll]) y la composición (última (tomar índice coll))

Estoy tratando de trabajar con el libro de Stuart Halloway Programming Clojure. Todo este material funcional es muy nuevo para mí.¿Cuál es la diferencia entre la función de Clojure (nth [índice coll]) y la composición (última (tomar índice coll))

entiendo cómo

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

genera la sucesión de Fibonacci con pereza. No entiendo por qué

(last (take 1000000 (fibo)))

obras, mientras que

(nth (fibo) 1000000)

lanza un OutOfMemoryError. ¿Podría alguien explicar por qué estas dos expresiones son diferentes? ¿Está (nth) de alguna manera aferrándose a la cabeza de la secuencia?

Gracias!

Fuente

2011-12-15 Josh

Ninguno de estos me funciona en tryclj.com ya que el número es tan grande que causa un desbordamiento. AFIRMEMOS que no mantienes una referencia a nada, así que no creo que nada esté "agarrado a la cabeza". ¿Estás seguro de que no es solo porque el número es tan grande? –

La implementación de la última es una implementación recta recursiva O (n), y no se sostiene en nada. nth está implementado en Java y estoy bastante seguro de que no se aferra a nada tampoco. Por lo tanto, ambas secuencias deberían funcionar bien (en teoría). Lo único que se me ocurre, aunque no estoy seguro de que esto afecte el resultado, es que su enésima llamada realmente calcula 1 elemento más que su última llamada. enésimo 1000000 = 1000001er artículo (0 indexación) – vedang

@vedang Gracias ... No habría captado esa importante distinción. No fue la fuente de mi problema, aunque no me había dado cuenta de que el argumento a seguir es el tamaño de la secuencia, mientras que el argumento de nth es el índice. – Josh

Creo que estás hablando del problema que se discutió en google group y Rich Hickey proporcionó patch que resolvió el problema. Y el libro, que fue publicado más tarde, no cubrió este tema.

En clojure 1.3 su ejemplo nth funciona con pequeñas mejoras en la función fibo. Ahora, debido a cambios en 1.3, debemos marcar explícitamente M para usar precisión arbitraria, o cae con throwIntOverflow.

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

Y con estos cambios

(nth (fibo) 1000000)

tienen éxito (si tiene suficiente memoria)

Fuente

2011-12-15 17:02:39 4e6

Estaba usando una versión de instantánea distribuida con el libro, 1.1.0-alpha-SNAPSHOT. Cambiando a 1.3.0 trabajado. Supongo que la versión que tenía contenía el error al que se refiere ... es decir que "Un intento de optimización reciente introdujo un salto de retención de cabeza en RT.nth" – Josh

Sin embargo, la "M" no era necesaria. Clojure parece estar convirtiendo a BigInt cuando sea necesario, al menos con 1.3.0. – Josh

@Josh, no en mi máquina. Ver mi respuesta –

¿Qué versión de Clojure estás utilizando? Pruebe (clojure-version) en una réplica. Obtengo resultados idénticos para ambas expresiones en 1.3.0, es decir, un desbordamiento de enteros.

Para

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

puedo obtener resultados correctos para ambas expresiones (realmente un gran número entero ...).

Fuente

2011-12-15 17:00:05

creo que se le puede golpear a un límite de memoria específica para su máquina, y no una diferencia real en función.

Al observar el código fuente de nth en https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java, no parece que ni enésima ni la toma retienen el encabezado.

Sin embargo, nth usa indexación basada en cero, en lugar de contar por número de artículo. Su código con nth selecciona el elemento 1000001 de la secuencia (el del índice 1000000). Tu código con take devuelve el elemento final en una secuencia de elemento 1000000. Ese es el artículo con el índice 999999. Dado lo rápido que crece fib, ese último artículo podría ser el que rompió la espalda del camello.

Además, estaba revisando la fuente 1.3.0. Quizás las versiones anteriores tenían implementaciones diferentes. Para hacer que su fibo funcione correctamente en 1.3.0 necesita usar las funciones aritméticas que promocionarán números a bignums:

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

Fuente

2011-12-15 18:39:40

¿Cuál es la diferencia entre la función de Clojure (nth [índice coll]) y la composición (última (tomar índice coll))

Respuesta

Cuestiones relacionadas