Incrocio tra funzionalità "dotimes" e "for"?

Question

Mi capita spesso di voler eseguire in modo efficiente una funzione Clojure più volte con un indice intero (come "dotimes") ma anche ottenere i risultati come sequenza/lista già pronta (come "for").

cioè mi piacerebbe fare qualcosa di simile:

(fortimes [i 10] (* i i)) 

=> (0 1 4 9 16 25 36 49 64 81) 

Chiaramente sarebbe possibile fare:

(for [i (range 10)] (* i i)) 

Ma vorrei evitare di creare e buttare via la temporanea elenco di intervalli se possibile.

Qual è il modo migliore per ottenere questo in Clojure?

Answer 1

ho scritto una macro di iterazione che può fare questo e di altri tipi di iterazione in modo molto efficiente. Il pacchetto si chiama clj-iterate, sia su github che sui clojars. Ad esempio:

user> (iter {for i from 0 to 10} {collect (* i i)}) 
(0 1 4 9 16 25 36 49 64 81 100) 

Questo non creerà un elenco temporaneo.

Answer 2

Generare un intervallo in un ciclo for, come mostrato nel secondo esempio, è la soluzione idiomatica per risolvere questo problema in Clojure.

Poiché Clojure è basato sul paradigma funzionale, la programmazione in Clojure, per impostazione predefinita, genererà strutture di dati temporanee come questa. Tuttavia, poiché sia ​​il comando "range" che il comando "for" operano con sequenze pigri, la scrittura di questo codice non forza l'intera struttura di dati dell'intervallo temporaneo a esistere nella memoria contemporaneamente. Se usato correttamente, c'è un sovraccarico di memoria molto basso per i seq pigri come in questo esempio. Inoltre, l'overhead computazionale per il tuo esempio è modesto e dovrebbe crescere solo in modo lineare con le dimensioni dell'intervallo. Questo è considerato un overhead accettabile per il tipico codice Clojure.

Il modo appropriato per evitare completamente questo sovraccarico, se l'elenco di intervalli temporaneo è assolutamente, positivamente inaccettabile per la situazione, è quello di scrivere il codice utilizzando atomi o transitori: http://clojure.org/transients. Lo fai, tuttavia, rinuncerai a molti dei vantaggi del modello di programmazione Clojure in cambio di prestazioni leggermente migliori.

Answer 3

Non sono sicuro del motivo per cui si tratta di "creare e buttare via" la sequenza lenta creata dalla funzione range. L'iterazione limitata effettuata da dotimes è probabilmente più efficiente, poiché rappresenta un incremento in linea e viene confrontato con ogni passaggio, ma è possibile che si paghi un costo aggiuntivo per esprimere la propria concatenazione di elenchi.

La soluzione Lisp tipica è quella di anteporre nuovi elementi a una lista che si costruisce mentre si procede, quindi di invertire la lista costruita in modo distruttivo per ottenere il valore restituito. Altre tecniche per consentire l'aggiunta a un elenco in tempo costante sono ben note, ma non sempre si dimostrano più efficienti rispetto all'approccio anteporre-retro-inverso.

In Clojure, è possibile utilizzare transitori per arrivarci, basandosi sul comportamento distruttivo della funzione conj!:

(let [r (transient [])] 
    (dotimes [i 10] 
    (conj! r (* i i))) ;; destructive 
    (persistent! r)) 

che sembra funzionare, ma the documentation on transients avverte che non si dovrebbe usare conj! a " valori bash in atto "— vale a dire contare su comportamenti distruttivi invece di prendere il valore restituito. Quindi, quel modulo deve essere riscritto.

Al fine di associare nuovamente r sopra al nuovo valore dato da ogni chiamata a conj!, avremmo bisogno di utilizzare un atom per introdurre più di un livello di indirezione.A quel punto, però, stiamo solo combattendo contro lo dotimes, e sarebbe meglio scrivere il tuo modulo usando loop e recur.

Sarebbe bello poter preallocare il vettore in modo che abbia le stesse dimensioni del limite di iterazione. Non vedo un modo per farlo.

Answer 4

(defmacro fortimes [[i end] & code] 
    `(let [finish# ~end] 
    (loop [~i 0 results# '()] 
     (if (< ~i finish#) 
     (recur (inc ~i) (cons ~@code results#)) 
     (reverse results#))))) 

esempio:

(fortimes [x 10] (* x x)) 

dà:

(0 1 4 9 16 25 36 49 64 81) 

Answer 5

Hmm, non riesco a rispondere al tuo commento perché non ero registrato. Tuttavia, clj-iterate utilizza PersistentQueue, che fa parte della libreria di runtime, ma non è esposto attraverso il lettore.

È fondamentalmente un elenco su cui è possibile associare alla fine.