data structures - ¿Cuál es la estructura de datos detrás de los conjuntos de Clojure?

data-structures immutability

Question

Recientemente escuché la entrevista de Rich Hickey en Radio de Ingeniería de Software . Durante la entrevista, Rich mencionó que las colecciones de Clojure se implementan como árboles. Espero implementar estructuras de datos persistentes en otro idioma, y ​​me gustaría entender cómo se implementan los conjuntos y otras estructuras de datos persistentes de Clojure.

¿Cómo se vería el árbol en cada punto en el siguiente escenario?

1. Crea el set {1 2 3}

2. Crea la unión de {1 2 3} y {4}

3. Crea la diferencia de {1 2 3 4} y {1}

Me gustaría entender cómo los tres conjuntos generados ( {1 2 3} , {1 2 3 4} y {2 3 4} ) comparten la estructura, y cómo se manejan las "eliminaciones".

También me gustaría saber el número máximo de sucursales que puede tener un nodo. Rich mencionó en la entrevista que los árboles son poco profundos, por lo que presumiblemente el factor de ramificación es mayor que dos.

Answer 1

Aquí hay un punto de partida: https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashSet.java

Puedes ver que está implementado en términos de PersistentHashMap.

Answer 2

Debería leer la programación de Clojure , ya que cubre esto con gran detalle, incluidas las imágenes. Brevemente, sin embargo, las colecciones son profundas en las primeras búsquedas a través de los árboles. Podemos mostrar sus ejemplos como este:

(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

Tenga en cuenta que estos son solo indicativos, no estoy diciendo que este es exactamente el diseño que Clojure usa internamente. Aunque es la esencia.

Answer 3

Me gustan los dibujos y explicaciones de SCdF, pero si está buscando más profundidad, debería leer la excelente serie de artículos sobre las estructuras de datos de Clojure en Higher-Order . Explica en detalle cómo funcionan los mapas de Clojure, y los conjuntos de Clojure son solo una capa delgada en la parte superior de sus mapas: #{:a :b} se implementa como un ajuste alrededor de {:a :a, :b :b} .

Answer 4

Probablemente necesites leer el trabajo de Phil Bagwell. Su investigación en estructuras de datos es la base de las estructuras de datos persistentes de Clojure, Haskell y Scala.

Hay una charla de Phil en Clojure / Conj: http://www.youtube.com/watch?v=K2NYwP90bNs

También hay algunos papeles:

• Listas funcionales rápidas, listas de hash, deques y matrices de longitud variable
• Árboles de hash ideales
• Más de Phil aquí

También puede leer Estructuras de datos puramente funcionales de Chris Okasaki. Esta publicación del blog habla sobre el libro: http://okasaki.blogspot.com.br/2008/02/ten-years-of-purely-functional-data.html