Algoritmica complessità di Data.Hashtable

Question

Sto tentando di scrivere una funzione che utilizza hash (per un'implementazione di A *).

Dopo un po 'di ricerca, ho trovato che lo standard defacto è Data.Map.

Tuttavia, leggendo la documentazione API, ho trovato che: O(log n). Find the value at a key.

https://downloads.haskell.org/~ghc/6.12.2/docs/html/libraries/containers-0.3.0.0/Data-Map.html

Infatti documentazione suggerisce generalmente volte grandi O significativamente inferiori al O (1) di un hash standard.

Quindi ho trovato Data.HashTable. https://hackage.haskell.org/package/base-4.2.0.2/docs/Data-HashTable.html Questa documentazione non menziona direttamente la grande O, portandomi a credere che probabilmente soddisfi le mie aspettative.

Ho diverse domande: 1) È corretto? O (lookupInDataHashTable) = O (1)? 2) Perché dovrei voler usare Data.Map data la sua inefficienza? 3) Esiste una libreria migliore per le mie esigenze di struttura dei dati?

Answer 1

Perché dovrei mai voler utilizzare Data.Map data la sua inefficienza?

Può non essere efficiente, ma supporta qualsiasi tipo di chiave con un'istanza Ord, anche quelli che non possono essere hashing ad un numero intero.

è O (lookupInDataHashTable) = O (1)?

Generalmente sì. Il flusso di lavoro di "lookupInDataHashTable" e le prestazioni corrispondenti in notazione O grande sono:

1. Hash the key. per intero: O (1), per stringa: O (lunghezza della stringa)
2. Accedere a un IOArray con l'hash, ottenere un elenco contenente tutte le coppie chiave-valore che hanno lo stesso hash. O (1)
3. Cercare la chiave nell'elenco. O (lunghezza della lista)

Quindi, a meno che non si abbiano stringhe molto lunghe come chiavi, la funzione di ricerca garantisce prestazioni O (1).

Esiste una libreria migliore per le esigenze della struttura dati?

Dipende dal tipo di chiave. Per gli interi distinti Data.IntMap bests, per altri tipi hash Data.HashMap mostra prestazioni decenti, altrimenti non hai scelta se non Data.Map.

Answer 2

Data.HashTable è stato deprecato e non lo troverete nell'attuale base.

E 'stato dichiarato obsoleto perché ha funzionato male rispetto a hashtables.

Tuttavia, hashtables e Data.HashTable sono entrambe le implementazioni mutevoli, mentre Data.Map e Data.HashMap sono immutabili.

Le hashmap mutabili in Haskell sono simili all'array-of-bucket o alle soluzioni di indirizzamento aperte in altre lingue. Le mappe immutabili sono basate su alberi o tentativi. In generale, i contenitori associativi immutabili non possono essere implementati con la modifica O (1).

Allora perché usare mappe immutabili?

In primo luogo, l'API è molto più comoda in Haskell. Non possiamo usare le mappe mutabili nelle funzioni pure, solo nelle azioni IO o ST.

In secondo luogo, le mappe immutabili possono essere condivise in modo sicuro tra i thread, che è spesso una caratteristica cruciale.

In terzo luogo, in pratica, la differenza di prestazioni tra mappe mutevoli e immutabili può essere insignificante, i. e. non ha un impatto significativo sulle prestazioni generali del programma. O (log n) è anche limitato dalla memoria disponibile, quindi non otteniamo spettacolari differenze asintotiche rispetto a O (1). In particolare, Data.HashMap utilizza un trie a 16 diramazioni, quindi la profondità non può essere più realisticamente di 6 o 7.

Quarta, le mappe immutabili possono essere semplicemente più veloci per ragioni che non comprendo completamente (più ottimizzato librerie? ottimizzazione migliore da GHC?); Ho provato un paio di volte a sostituire Data.HashMap con le mappe mutabili da hashtables, ma le prestazioni sono state sempre un po 'peggiorate in seguito.