2009-08-20 5 views
10

Mi chiedo se non v'è un'implementazione di una mappa che è:Implementazione efficiente della mappa immutabile?

  • Immutabile, in modo che posso utilizzare in programmazione funzionale, e senza sforzo garantire transazioni e la concorrenza.
  • Veloce. Ho controllato gli alberi di ricerca di Binary (RB, AVL) e tentativi, ma nessuno di loro sembrava essere veloce come tabelle hash. Esiste un'implementazione della mappa che supporta il tempo costante per gli aggiornamenti e i recuperi? (O almeno molto veloce tempo logaritmico)

In breve, v'è una struttura di dati funzionale che può confrontare con mappe Hash prestazioni?

risposta

4

Clojure ha mappe immutabili. (link). Non sei sicuro della struttura dei dati sottostanti che sta utilizzando. Il codice sorgente di Clojure ti darà più informazioni!

+0

Grazie mille per la vostra risposta utile. Vado presto a dare un'occhiata a Clojure. – Phil

+2

Le mappe immutabili di Clojure utilizzano tentativi di mappatura con hash array a 32 vie (http://en.wikipedia.org/wiki/Hash_array_mapped_trie). Sono una grande struttura dati, quasi una HashMap mutevole, ma con tutti i vantaggi di essere persistenti e immutabili. – mikera

3

Scala ha anche immutable maps, ma sono più lenti delle tabelle hash. Sospetto che la risposta alla tua domanda sia no, non troverai un'implementazione cartografica immutabile con operazioni di inserimento/interrogazione tempo previsto O (1).

+0

Sì, sto attualmente sperimentando con Scala, e generalmente non sono soddisfatto delle prestazioni. – Phil

1

In ogni caso solo per condividere con le persone, questi sono due interessanti post di blog sull'implementazione di Vettori persistenti in Scala utilizzando Tries. Citano anche l'implementazione di Clojure, così come la nuova IntMap nelle recenti versioni di Scala.

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

Per queste strutture di dati, ho provato con la chiave come numeri interi, ma non ancora le stringhe. Poiché la mia applicazione reale userà le stringhe come chiavi, non sono sicuro che l'implementazione sarà più efficiente di una mappa hash. Cosa succede se utilizzo il codice hash della stringa come chiave, quindi utilizzo un vettore persistente per supportare la mappa? Userò un trie a 32 vie per implementare il vettore persistente. Immagino che la collisione sarebbe molto rara e che la memoria sarebbe spesa solo di conseguenza. Ma non sono sicuro della quantità effettiva necessaria per copiare gli aggiornamenti.

Inserirò presto i miei risultati.

Problemi correlati