2013-04-29 12 views
16

Recentemente ho ascoltato Rich Hickey's interview on Software Engineering Radio. Durante l'intervista, Rich ha detto che le collezioni di Clojure sono implementate come alberi. Spero di implementare strutture dati persistenti in un'altra lingua e mi piacerebbe capire come vengono implementate le altre strutture di dati persistenti di Clojure e di altri.Qual è la struttura dati dietro i set di Clojure?

Che aspetto avrebbe l'albero in ogni punto del seguente scenario?

  1. creare il set {1 2 3}

  2. Creare l'unione di {1 2 3} e {4}

  3. Creare la differenza di {1 2 3 4} e {1}

mi piacerebbe capire come il tre set generati ({1 2 3}, {1 2 3 4} e {2 3 4}) condividono la struttura e come vengono gestite le "eliminazioni".

Mi piacerebbe anche conoscere il numero massimo di rami che un nodo può avere. Rich ha detto nell'intervista che gli alberi sono poco profondi, quindi presumibilmente il fattore di ramificazione è maggiore di due.

+3

Il fattore di diramazione è 32. –

+0

Nota pedante: ho appena ascoltato Rich Hickey _Clojure Data Structures 2_ all'indirizzo http://www.youtube.com/watch?v=sp2Zv7KFQQ0. Non so dove o quando è stato registrato. Le raccolte hanno diverse implementazioni di archiviazione. (predefinito?) i vettori sono alberi poco profondi. Altre raccolte potrebbero avere altre implementazioni. –

+1

Lo fanno. In particolare: hash-set, hash-map e vector hanno 32 figli per nodo; set ordinati e mappa ordinata sono alberi rosso-neri e hanno 2 figli per nodo. – Chouser

risposta

20

Probabilmente hai bisogno di leggere il lavoro di Phil Bagwell. La sua ricerca sulle strutture dati è alla base delle strutture dati persistenti di Clojure, Haskell e Scala.

C'è questo discorso da Phil a Clojure/Conj: http://www.youtube.com/watch?v=K2NYwP90bNs

Ci sono anche alcune carte:

È inoltre possibile leggi Purely Functional Data Structures di Chris Okasaki.Questo post sul blog parla del libro: http://okasaki.blogspot.com.br/2008/02/ten-years-of-purely-functional-data.html

11

Si dovrebbe leggere davvero Clojure Programming, copre questo in grande dettaglio, comprese le immagini. In breve, però, le raccolte sono le prime ricerche di profondità attraverso gli alberi. Siamo in grado di mostrare i tuoi esempi come questo:

(def x #{1 2 3}) 

x 
| 
| \ 
|\ 3 
1 \ 
    2 

(def y (conj x 4)) 

x y 
|/\ 
| \ 4 
|\ 3 
1 \ 
    2 

(def z (difference y #{1})) 

x y 
|/\ 
| \ 4 
|\ 3 
1/\ 
z- 2 

Si noti che queste sono solo indicativi, non sto dicendo che questo è esattamente il layout Clojure usa internamente. È l'essenza però.

8

Mi piacciono i disegni e le spiegazioni di SCdF, ma se stai cercando una maggiore profondità dovresti leggere l'eccellente serie di articoli sulle strutture dati di Clojure allo Higher-Order. Spiega in dettaglio come funzionano le mappe di Clojure e gli insiemi di Clojure sono solo uno strato sottile sopra le sue mappe: #{:a :b} è implementato come un involucro intorno allo {:a :a, :b :b}.

Problemi correlati