La migliore struttura dati per i seguenti vincoli?

Question

Ecco alcuni vincoli per una struttura dati di cui ho bisogno. Sembra che nessuna delle strutture dati comuni (menzionerò quelle che ho pensato di seguito) si adattano bene a tutto questo. Qualcuno può suggerire uno che forse non ho pensato?

1. Devo essere in grado di eseguire ricerche con chiavi integer senza segno.
2. Gli elementi da memorizzare sono strutture definite dall'utente.
3. Questi indici saranno sparsi, in genere estremamente. Gli array regolari sono fuori.
4. La frequenza di ciascun indice avrà una distribuzione non uniforme, con indici piccoli molto più frequenti di quelli di grandi dimensioni.
5. N di solito sarà piccolo, probabilmente non più grande di 5 o 10, ma non voglio fare affidamento su quello troppo pesantemente perché potrebbe a volte essere molto più grande.
6. Il termine costante conta molto. Ho bisogno di ricerche davvero veloci quando N è piccolo. Ho già provato tabelle hash generiche e, empiricamente, sono troppo lente, anche quando N = 1, ovvero nessuna collisione, probabilmente a causa della quantità di indirezione implicata. Tuttavia, sarei aperto a suggerimenti su tabelle hash specializzate che sfruttano altri vincoli citati.
7. Il tempo di inserimento è non importante finché il tempo di recupero è veloce. Anche il tempo di inserimento di O (N) è abbastanza buono.
8. L'efficienza dello spazio non è molto importante, anche se è abbastanza importante non utilizzare solo array regolari.

Answer 1

Quando N è piccolo un semplice array o lista collegata singola con tasto + valore payload è molto efficiente. Anche se non è il massimo quando N diventa più grande.

Si ottiene O (N) tempo di ricerca che significa che le ricerche richiedono il tempo k * N. Una ricerca O (1) richiede un tempo costante K. Quindi ottieni migliore prestazione con O (N) per N < K/k. Qui k è molto piccolo, quindi puoi ottenere valori interessanti di N. Ricorda che la notazione Big O descrive solo il comportamento per grandeN s, non quello che stai cercando. Per tavoli di piccole dimensioni

void *lookup(int key_to_lookup) 
{ 
    int n = 0; 
    while (table_key[n] != key_to_lookup) 
    n++; 
    return table_data[n]; 
} 

può essere difficile da battere.

Esegui il benchmark delle tabelle hash, dell'albero bilanciato e dell'elenco di array/link semplice e vedi a quali valori di N iniziano a essere migliori. Allora saprai quale è meglio per te.

Ho quasi dimenticato: tenere i tasti a cui si accede frequentemente all'inizio dell'array. Data la tua descrizione, significa che manterrai l'ordine.

Answer 2

Si potrebbe provare a combinare il meglio di entrambi i mondi: se la chiave è piccola, inserirla in una struttura dati simile a una matrice che non diventa più grande di una chiave massima predefinita. Se la chiave è grande, inseriscila in una tabella hash.

Answer 3

Una ricerca tabella di hash è circa veloce come può essere:

L'unica cosa che la distingue da una normale ricerca array è il calcolo dell'hash e (se il vostro hashfunction è abbastanza buono, o si spende tempo sufficiente per generare una funzione hash ottimale durante l'inserimento, che renderebbe il tuo inserimento prendere O (N)) quindi essenzialmente una ricerca di array.

Essenzialmente poiché potrebbe accadere (a meno che non si usi una funzione di hash ottimale) che si debba ripetere o seguire un elenco molto piccolo.

Poiché la maggior parte delle funzioni di hash utilizzate per le tabelle hash sono di k * c_1% c_2, la differenza rispetto a una ricerca di matrice in una tabella hash piuttosto sparsa e/o ottimale consiste in un riferimento indiretto, due moltiplicazioni, una sottrazione e una divisione (un'efficiente implementazione del modulo che utilizza le capacità di cpus potrebbe ridurlo con una sottrazione e una moltiplicazione e la ricerca di array.

Semplicemente non diventa più veloce di così.

Answer 4

Considererei una tabella hash che gestisce le collisioni hash con un albero binario autobilanciato invece di un semplice concatenamento. Dovresti essere in grado di ottenere O (1) una ricerca ammortizzata su tutte le chiavi e la ricerca nel caso peggiore di O (logN). Poiché la distribuzione delle chiavi è distorta, è probabile che si verificheranno collisioni con valori bassi dell'indice e la ricerca della struttura sarà davvero redditizia.

Answer 5

Questo consiglio assume le CPU moderna con:

• cache veloci
• la latenza di memoria molto più lento rispetto alla velocità di clock.
• previsione ragionevole ramo (veramente sorprendente negli ultimi processori desktop/server)

Vorrei suggerire che le strutture ibride può ben vincenti un'unica struttura.

Utilizzo di coppie di valori chiave basati su array semplici con accesso O (N) come fattori costanti ma molto bassi e comportamento di caching estremamente buono. Questa struttura iniziale dovrebbe essere piccola (probabilmente non più grande di 16 e possibilmente 8 valori) per evitare di andare oltre una singola linea della cache. Purtroppo è un parametro che dovresti sintonizzare.

Una volta superato tale numero, si vorrebbe ricorrere a una struttura con un comportamento O (N) migliore, suggerirei di provare una tabella hash decente per iniziare, poiché ciò probabilmente sarà ragionevole dal 16 - diverse migliaia intervallo e se si tende a cercare valori simili più spesso tenderà a rimanere nelle cache più veloci.

Se anche rimuovere e inserire è necessario fare attenzione a non battere avanti e indietro tra i due stati. Richiedere che il conteggio si riduca a metà del cut-off per "upgrading" alla struttura secondaria dovrebbe impedire questo, ma ricorda che qualsiasi comportamento di crossover deterministico sarà suscettibile all'input del caso peggiore.
Questo potrebbe essere un problema se si sta tentando di difendersi da dati di input dannosi. In tal caso, l'utilizzo di un fattore di casualità nella decisione protegge contro di esso. È probabile che non ti interessi per questo, dal momento che non ne hai parlato.

Se si desidera provare a rendere ordinato l'array primario iniziale, consentendo una ricerca binaria che è O (log (N)) ma a costo di un codice di ricerca più complesso.Penserei che il semplice array walk in realtà lo batterà, ma vorresti fare un benchmark per i diversi valori di N, potrebbe permetterti di rimanere con un array primario più a lungo, ma penserei che questa sia una funzione della dimensione della dimensione della linea della cache più del comportamento O (N).

Altre opzioni includono:

• Trattare tutti i valori di chiave < 256 diverso e loro memorizzazione in una coppia struct byte -> di array di risparmiare spazio sui tasti (e potenzialmente permettendo loro di rimanere lì quando si cambia a la struttura secondaria) potrebbe non funzionare a causa della necessità di decomprimere l'array al volo alla lunghezza della parola nativa.
• utilizzando una struttura simile a un byte alla volta della chiave. Dubito che la complessità di questo comporterà un buon risultato nella pratica

Ancora una volta ripeterò l'ottimo consiglio di kmkaplan. Benchmark evitando accuratamente i microbenchmarks. In questa sorta di analisi i numeri reali possono essere sorprendentemente diversi dalla teoria ...

Answer 6

Si potrebbe provare un hash con indirizzo aperto con interrogazione quadratica invece di concatenazione separata, se la N di solito è piccola. Avresti bisogno di riallocare da, diciamo, una dimensione iniziale di 32 a larghezze maggiori se ottieni il raro caso N che lo riempie eccessivamente. Il sondaggio lineare o l'hashing del cuculo offrono buone prestazioni se riesci a far rientrare l'intera struttura in poche righe della cache.

Onestamente sono sorpreso che anche un normale hash table ti stia comportando in modo così miserabile. Forse potresti inserire un profilo per vedere cosa lo rende così lento - se è la stessa funzione hash, usarne uno semplice come un modulo power-of-two (ad esempio, il tasto & (N-1) dove N è noto per essere 2^x) che favorirà comunque le distribuzioni centrate attorno allo 0. Se è la mancanza di dcache di inseguire la catena separata, scrivi un'implementazione che memorizza i primi quattro elementi in ciascun bucket nel bucket stesso in modo che tu li possa ottenere almeno rapidamente. Quanto è lento N = 1?

Vorrei archiviare i puntatori alle strutture piuttosto che le strutture stesse nelle catene del secchio: se le strutture sono grandi, quindi camminare su una catena di esse avrà molti errori di cache. D'altra parte, è possibile adattare circa 16 coppie chiave/puntatore su una singola linea di cache, e pagare solo per perdere quando si trova l'elemento corretto.

Answer 7

L'unica spiegazione che posso vedere per il problema descritto è che la funzione di hash è troppo complessa. Sarei propenso a un approccio a due fasi:

1) Per i tasti di piccole dimensioni, una semplice matrice di puntatori. Nessun hash o niente.

2) Per le chiavi che sono più grandi rispetto alle dimensioni della tabella si alloca:

Che ne dite di una semplice funzione di hash che si diffonderà fuori le chiavi cluster:

La sinistra-order 5 bit (Sto assumendo interi a 32 bit, se è 64-bit quindi aggiungo un altro bit.) Sono il numero di bit che contengono effettivamente dati, il resto è semplicemente la somma (scartata) della chiave originale tagliata in blocchi di molti bit che stai utilizzando per lo scopo e aggiunti insieme.

Si noti che il numero di bit significativi può essere parzialmente calcolato in precedenza - creare una tabella 64k con valori di bit elevati. Se la parola di ordine superiore è diversa da zero, utilizzarla come indice per la tabella e aggiungere 16, altrimenti utilizzare la parola di ordine inferiore come indice. Per gli interi a 64 bit, ovviamente, devi usare 4 passi invece di due.

Answer 8

si potrebbe considerare Judy Arrays:

Judy è una libreria C che fornisce uno stato-of-the-art tecnologia base che implementa un array dinamico sparso. Gli array Judy sono dichiarati semplicemente con un puntatore nullo . Una matrice Judy consuma memoria solo quando popolato, tuttavia può crescere per sfruttare tutte memoria disponibile se desiderato ... Judy può sostituire molti dati comuni strutture, ad esempio matrici, sparsi matrici, tabelle hash, Alberi B, alberi binari , liste lineari, skiplists, altri algoritmi di ordinamento e ricerca e conteggio.

Answer 9

Ecco un'idea generale per una funzione di hashing. Hai detto che gli inserti possono essere costosi.

Hash la chiave, che è un numero intero, con un semplice modulo, memorizzato con ogni istanza di una tabella hash

se un inserto causerebbe una collisione, ri-ottimizzare il hashtable calcolando il numero di collisioni ciò avverrebbe per ciascun modulo in un intervallo ragionevole, ad esempio il numero di elementi nella mappa attraverso un multiplo costante di quello.

ovviamente, i tuoi inserti diventano effettivamente piuttosto costosi, attorno a O (n^2) se minimizzi le allocazioni, ma probabilmente sarai in grado di ottenere ricerche con una singola divisione intera e un puntatore indiretto a un solo puntatore, e sai, perché l'hai calcolato al momento dell'insediamento, quale sarà la ricerca del caso peggiore.

Answer 10

Vorrei raccomandare uno Skip list qui. Il pacchetto java.util.concurrent ha una buona implementazione se ci sei.