Implementazioni rapide delle mappe hash di ricerca

0

Sto implementando un linguaggio di programmazione su LLVM. Per il mio sistema polimorfico, sto cercando suggerimenti per un dizionario ultra-veloce. Non mi interessa il tempo di inserimento, in quanto queste mappe sono scritte solo una dozzina di volte. Ma sto cercando una ricerca super veloce.

Ho fatto qualche ricerca sull'implementazione di dict per l'indirizzamento aperto in Python, e sembra piuttosto veloce (alcuni turni e maschere di bit nel migliore dei casi). Tuttavia, voglio fare la mia ricerca. Qualcuno sa di un super dizionario veloce / implementazione di hashmap?

In questo caso i miei dati saranno probabilmente puntatori come chiavi e puntatori come valori. O se funziona meglio, potrei probabilmente cavarmela con numeri interi come chiavi. Qualsiasi documento o discussione sull'argomento sarebbe fantastico.

    
posta Timothy Baldridge 26.03.2013 - 00:51
fonte

1 risposta

2

Puoi dare un'occhiata veloce a "Cuckoo hashing" - se funziona, ti è garantito un tempo di ricerca costante (in contrasto con la maggior parte degli schemi di hashing, come l'indirizzamento aperto). Certo, non è senza i suoi problemi, ma potrebbe valerne la pena, considerando le preferenze di inserimento / ricerca.

Articolo su wiki: link

E anche se lo avresti considerato, anche la Proear lineare ha la sua parte di vantaggi: contrariamente all'OA, la scansione della memoria è sequenziale, il che è ovviamente molto più rapido dell'accesso casuale di OA (ma naturalmente, altri fattori influenzano anche questo).

Infine, esistono schemi per creare tabelle di hash perfette, che in genere sono molto lente da costruire, ma garantiscono ricerche costanti nel tempo.

Non collegherò a documenti o articoli, ma cercherò google per: hashing del cuculo, sondaggio lineare, hashing perfetto

    
risposta data 26.03.2013 - 01:00
fonte

Leggi altre domande sui tag