¿Qué tipo de estructura de datos se usa para los mapas inmutables?

Sé cómo funcionan los mapas mutables normales (usando hashtables), y sé cómo funcionan las listas inmutables (listas recursivas vinculadas) y su ventaja sobre las listas mutables (tiempo constante que se agrega sin estropear el original) pero ¿cómo se hacen los mapas inmutables (por ejemplo, Scala) ¿trabajo?¿Qué tipo de estructura de datos se usa para los mapas inmutables?

Conozco la ventaja de no jugar con el mapa original al generar nuevos mapas, pero ¿cómo funciona la estructura de datos subyacente y qué tipo de características de rendimiento tienen, por ejemplo, en comparación con las tablas hash variables? ¿Hay alguna estructura de datos estándar que las personas usen para implementar estas, que podría buscar en CLRS/wikipedia?

Fuente

2012-01-29 Li Haoyi

CLRS, y casi todos los demás libros de texto estructura de datos/algoritmo están fuertemente * * sesgados hacia la mutabilidad y la impureza. Chris Okasaki * literalmente * escribió el libro sobre las estructuras de datos funcionales, que se basa en una extensión de su trabajo de tesis anterior. Otras obras que deberías mirar son de Phil Bagwell y Rich Hickey. –

persistente Hash mapas se implementan utilizando una estructura llamada Hash trie. Era originally proposed by Phil Bagwell (quien es miembro del grupo Scala en EPFL) pero en realidad fue implementado por Clojure primero. Se golpeó Scala cuando 2,8 salió en 2010.

Hay una great talk on functional data structures por Dan Spiewak donde la mecánica del trie de hash se explican muy lúcidamente (junto con otras cosas tales como colas bancarias)! También explica muy bien la actuación asintótica de big-O en la charla.

El pasado mes de octubre Phil dio otra charla en el London scala Lift Off, esta vez en estructuras de datos paralelas persistentes.

mapas ordenados persistentes se implementan a través de un Red-Black tree

Fuente

2012-01-29 16:22:21

En general, las estructuras de datos persistentes se basan en el * intercambio estructural * (por ejemplo, las listas de contras persistentes comparten sus colas). Normalmente, usas árboles para eso. Si entiendes cómo funcionan las listas de contras persistentes, estás a medio camino: después de todo, una lista es simplemente un árbol degenerado con una sola rama en todas partes. (O bien, un árbol es una generalización de una lista, donde cada celda puede tener más de un sucesor.) –

Creo que la información interesante es cómo conectar ese entendimiento con la forma en que se relaciona con el acceso basado en hash. –

Podría ser un árbol (rojo-negro) o un mapa hash. Sus características de acceso dependen de la implementación subyacente. Un árbol es O (log n) para acceso de lectura; un mapa hash es O (1).

Fuente

2012-01-29 16:13:31 duffymo

¿Qué tipo de estructura de datos se usa para los mapas inmutables?

Respuesta

Cuestiones relacionadas