Rimozione elementi di sequenze pigri in una grande struttura ad albero Clojure, evitando ritenzione testa

Question

Problema Descrizione

Per l'elaborazione di grandi strutture di dati in Clojure, sequenze pigri offrono una bella approccio, idiomatica. Bisogna essere prudenti per evitare la ritenzione della testa , però.

ho lotta con l'elaborazione di una grande struttura ad albero simile a questo:

    R           Root 
     __________|____________________ 
     A     B   C, D, E, ...   1st Level Children 
_______|_______  _______|_______ 
X Y Y ... Y X Y  X Y Y ... Y X Y      2nd Level Children 

• Tutti i nodi sono mappe con una chiave :content. Il valore di qualsiasi :content è un seq pigro con tutti i figli di quel nodo.
• L'intero albero non si adatta alla memoria. Ci sono troppi articoli Y al 2 ° livello.
• L'albero intero escluso gli articoli Y si adatta alla memoria.

Dopo aver elaborato l'albero, desidero finire con un nuovo albero, in cui sono stati rimossi tutti Y nodi:

  R 
    ______|__________________ 
    A    B   C, D, E, ... 
_____|___  _____|___ 
X X ... X  X X ... X 

codice di esempio e ulteriori spiegazioni

;; Generating example data 
;;;;;;;;;;;;;;;;;;;;;;;;;; 

(defn root [content] 
    {:tag :root :content content}) 

(defn lazy-elements [n tag content] 
    (lazy-seq (repeat n {:tag tag :content content}))) 

(defn level-1 [content] 
    (lazy-elements 3 :A content)) 

(defn level-2 [n] 
    (concat (lazy-elements 10 :X '(:leaf)) 
      (lazy-elements n :Y '(:leaf)))) 

(defn remove-nodes [node] 
    (remove #(= (:tag %) :Y) node)) 


;; Illustrating usage 
;;;;;;;;;;;;;;;;;;;;; 

;; runs and runs and runs... and eventually returns correctly 
(defn valid-run [] 
    (->> (root (level-1 (level-2 1e8))) 
     :content 
     first 
     :content 
     remove-nodes)) 

;; Does not terminate properly, runs out of memory 
(defn invalid-run [] 
    (->> (root (level-1 (level-2 1e8))) 
     :content 
     (map :content)  ; source of head retention 
     (map remove-nodes))) 

(Gist available on GitHub)

Il secondo esempio si blocca (a seconda della memoria disponibile, potrebbe essere necessario regola il numero di elementi di livello 2). La mappatura su :content di tutti gli articoli di livello 1 introduce un riferimento che causa problemi di ritenzione della testa quando si passa da tutti gli elementi di contenuto a per rimuovere gli elementi indesiderati :Y.

Sono stato in grado di utilizzare i dati da qualcosa come valid-run, metterlo in uno stato mutabile di var holding, facendo ciò per tutti i nodi rilevanti e poi ricucire tutti insieme i dati. Ma sono molto scontento di questo approccio per il fatto di dover dipendere dalla mutabilità e dover utilizzare un codice abbastanza imperativo per unire i dati alla fine (eseguendo, ad esempio, gli indici delle liste).

Domanda

come può essere raggiunto in uno stile dichiarativo funzionale? Idealmente, vorrei evitare di dover usare lo stato mutabile oltre ad essere troppo imperativo (ad esempio cucendo insieme le raccolte usando indici e simili).

Risorse

I seguenti articoli e frammenti sono interessanti letture su aspetti di questo problema:

• XML manipulation in Clojure
• Rich Hickey on incidental complexity of head retention
• Related Clojure documentation
• Head retention funkiness in a nutshell

altro sfondo

Eventualmente ho bisogno di questo per elaborare file XML di grandi dimensioni. Grandi mezzi> 1 GB e l'analisi in un albero non funzioneranno nella memoria disponibile . Da tale XML voglio mettere alcuni elementi nel bucket A (diciamo una tabella del database) e tutto il resto dell'albero XML nel bucket B. La struttura XML, naturalmente, dovrebbe essere mantenuta per i sottotitoli estratti.

Invece di analizzare l'XML in un albero, è anche possibile elaborare l'XML come un flusso di eventi, ad esempio tramite data.xml/source-seq. Tuttavia, significherebbe perdere la semantica dell'albero XML. Funzionerebbe, ma non essere bello. Ma forse ci sono altri approcci per gestire il codice XML in primo luogo.

Answer 1

Il problema è che i vostri nodi level-2 hanno tutti i puntatori alla stessa sequenza pigra in memoria e quindi si esegue il mapping su quella sequenza più volte. Avresti lo stesso problema se hai appena fatto il valid-run process sia sul primo che sul secondo nodo - il numero di nodi non ha molta importanza, perché fai saltare l'heap con due nodi qualsiasi. In una vera applicazione, in cui hai letto questi nodi da un database o da un file o altro, indicheranno oggetti diversi, che potrai gestire pigramente, ognuno a turno.

Se a generare più dati di esempio rappresentativo (cioè, gli stessi dati, ma senza la condivisione strutturale), è possibile GC ogni nodo come si elabora esso:

(defn root' [content] 
    (fn [] 
    {:tag :root :content (content)})) 

(defn lazy-elements' [n tag content] 
    (repeatedly n (fn [] {:tag tag :content (content)}))) 

(defn level-1' [content] 
    (fn [] 
    (lazy-elements' 3 :A content))) 

(defn level-2' [n] 
    (fn [] 
    (concat (lazy-elements' 10 :X (fn [] '(:leaf))) 
      (lazy-elements' n :Y (fn [] '(:leaf)))))) 

(defn remove-nodes [node] 
    (remove #(= (:tag %) :Y) node)) 

(defn run [] 
    (let [root-builder (root' (level-1' (level-2' 1e8)))] 
    (->> (root-builder) 
     :content 
     (map :content)  
     (map remove-nodes)))) 

user> (pprint (run)) 
(({:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)}) 
({:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)}) 
({:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)} 
    {:tag :X, :content (:leaf)})) 

Dal momento stiamo solo la generazione di contenuti ad esempio, Ho adattato tutti i tuoi creatori di nodi, piuttosto che un oggetto su cui dovrebbero essere archiviate N copie, una funzione che dovrebbero chiamare N volte per ottenere N oggetti distinti. E piuttosto che restituire un nodo, restituiscono una funzione che, quando viene chiamata, produce una copia di quel nodo; questo permette loro di comporre altrettanto bene delle versioni originali, ma solo di avere una chiamata di funzione extra al livello esterno. Se in effetti hai già oggetti distinti, come sospetto che faresti in una vera applicazione, puoi semplicemente usare le tue funzioni originali come scritte.