1. Inicio
  2. Pregunta y respuesta
  3. Implementación eficiente de mapas inmutables?

Implementación eficiente de mapas inmutables?

2009-08-20 9 views
10

Me pregunto si hay una implementación de un mapa que es:Implementación eficiente de mapas inmutables?

  • Inmutable, de modo que pueda utilizarlo en programación funcional, y sin esfuerzo garantizar transacciones y concurrencia.
  • Rápido. Revisé Binary Search Trees (RB, AVL) y Tries, pero ninguno parecía tan rápido como Hash Tables. ¿Hay una implementación de mapa que admita el tiempo constante para actualizaciones y recuperaciones? (O al menos muy rápido tiempo logarítmica)

En pocas palabras, ¿hay una estructura de datos funcional que pueda compararse con Hash Maps en el rendimiento?

Fuente

2009-08-20 Phil

Respuesta

4

Clojure tiene mapas inmutables. (link). No estoy seguro de qué estructura de datos subyacente está utilizando. ¡El código fuente de Clojure le dará más información!

Fuente

2009-08-20 10:15:18

+0

Muchas gracias por su útil respuesta. Voy a ver a Clojure pronto. – Phil

+2

Los mapas inmutables de Clojure usan intentos mapeados en matriz de hash de 32 vías (http://en.wikipedia.org/wiki/Hash_array_mapped_trie). Son una gran estructura de datos, casi tan rápida como un HashMap mutable, pero con todas las ventajas de ser persistente e inmutable. – mikera

3

Scala también tiene immutable maps, pero son más lentos que las tablas hash. Sospecho que la respuesta a su pregunta es no, no encontrará una implementación de mapa inmutable con O (1) operaciones esperadas de inserción/consulta de tiempo.

Fuente

2009-08-20 13:44:55

+0

Sí, actualmente estoy experimentando con Scala, y generalmente no estoy satisfecho con el rendimiento. – Phil

1

De todos modos solo para compartir con la gente, estas son dos entradas de blog interesantes sobre la implementación de vectores persistentes en Scala utilizando Tries. También mencionan la implementación de Clojure, así como el nuevo IntMap en los últimos lanzamientos de Scala.

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis

Por estas estructuras de datos, he probado con llave como enteros, pero no todavía cuerdas. Debido a que mi aplicación real va a usar cadenas como claves, no estoy seguro si la implementación será más eficiente que un Hash Map. ¿Qué pasa si uso el HashCode of the String como una clave, y luego uso un Vector persistente para apoyar el mapa? Usaré un trie de 32 vías para implementar el Vector persistente. Supongo que la colisión sería muy rara, y la memoria solo se gastaría en consecuencia. Pero no estoy seguro de la cantidad real necesaria para copiar en las actualizaciones.

Voy a publicar mis resultados pronto.

Fuente

2009-08-20 15:24:45 Phil

Cuestiones relacionadas

 Cuestiones relacionadas