Qual è la differenza tra la funzione Clojure (nth [coll index]) e la composizione (last (take index coll))

Sto provando a lavorare con il libro di programmazione Clojure di Stuart Halloway. Tutta questa roba funzionale è molto nuova per me.Qual è la differenza tra la funzione Clojure (nth [coll index]) e la composizione (last (take index coll))

Capisco come

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

genera la sequenza di Fibonacci pigramente. Non capisco il motivo per cui

(last (take 1000000 (fibo)))

opere, mentre

(nth (fibo) 1000000)

genera OutOfMemoryError. Qualcuno potrebbe spiegare come queste due espressioni differiscono? È (ennesimo) in qualche modo aggrappato al capo della sequenza?

Grazie!

fonte

2011-12-15 Josh

Nessuno di questi lavori per me su tryclj.com dato che il numero è così grande da causare un overflow. AFAICT non tieni alcun riferimento a qualcosa, quindi non credo che nulla sia "trattenuto sulla testa". Sei sicuro che non è solo perché il numero è così stravolgente? –

L'implementazione dell'ultima è un'attuazione ricorsiva in avanti di tipo O (n), e non regge a nulla. nth è implementato in Java e sono abbastanza sicuro che non trattiene nulla. Pertanto, entrambe le sequenze dovrebbero funzionare bene (in teoria). L'unica cosa a cui riesco a pensare, anche se non sono chiaro su questo influenza il risultato, è che la tua ennesima chiamata calcola effettivamente 1 oggetto in più rispetto alla tua ultima chiamata. n ° 1000000 = 1000001st oggetto (0 indicizzazione) – vedang

@vedang Grazie ... Non avrei catturato quell'importante distinzione. Non era la fonte del mio problema, anche se non mi ero reso conto che l'argomento da prendere fosse la dimensione della sequenza, mentre l'argomento di ennesima era l'indice. – Josh

Penso che tu stia parlando del problema discusso in google group e Rich Hickey fornito patch che ha risolto il problema. E il libro, che è stato pubblicato più tardi, non ha trattato questo argomento.

In clojure 1.3 l'esempio nth funziona con piccoli miglioramenti nella funzione fibo. Ora, a causa delle modifiche nella versione 1.3, è necessario contrassegnare esplicitamente M per utilizzare la precisione arbitraria, oppure cade con throwIntOverflow.

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

E con questi cambiamenti

(nth (fibo) 1000000)

avere successo (se si dispone di memoria sufficiente)

fonte

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

Stavo usando una versione di istantanea distribuita con il libro, 1.1.0-alpha-SNAPSHOT. Passare alla versione 1.3.0 funzionante. Sto indovinando la versione in cui avevo contenuto il bug a cui ti riferisci ... vale a dire che "Un recente tentativo di ottimizzazione ha introdotto un salto per la testa in RT.nth" – Josh

La "M" però non era richiesta. Clojure sembra convertirsi a BigInt quando necessario, almeno con 1.3.0. – Josh

@Josh, non sulla mia macchina. Vedi la mia risposta. –

Quale versione Clojure stai usando? Prova (versione clojure) su un repl. Ottengo risultati identici per entrambe le espressioni in 1.3.0, vale a dire un overflow intero.

Per

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

ottengo risultati corretti per entrambe le espressioni (davvero un grande intero ...).

fonte

2011-12-15 17:00:05

Penso che si può essere colpire un limite di memoria specifica per la vostra macchina, e non una vera differenza in funzione.

Guardando il codice sorgente per en ° https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java non sembra che l'ennesimo o il take mantengano la testa.

Tuttavia, l'ennesimo utilizza l'indicizzazione basata su zero, piuttosto che un conteggio per numero di articolo. Il tuo codice con ennesima seleziona l'elemento 1000001st della sequenza (quella all'indice 1000000). Il codice con take restituisce l'elemento finale in una sequenza di elementi 1000000. Questo è l'oggetto con l'indice 999999. Dato quanto cresce la fib rapida, quell'ultimo oggetto potrebbe essere quello che ha rotto la schiena del cammello.

Inoltre, stavo controllando la fonte 1.3.0. Forse le versioni precedenti avevano implementazioni diverse. Per ottenere il vostro fibo per funzionare correttamente in 1.3.0 è necessario utilizzare le funzioni aritmetiche che promuoveranno i numeri per bignum:

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

fonte

2011-12-15 18:39:40

Qual è la differenza tra la funzione Clojure (nth [coll index]) e la composizione (last (take index coll))

risposta

Problemi correlati