Accesso casuale (lettura / scrittura) nelle strutture dati

1

Certe strutture dati, come il dizionario di Python, sono non ordinate / a lettura / scrittura casuale. Poiché la programmazione in python è iterativa (e la programmazione in generale è?), Come funzionano queste datastrutture non ordinate?

Comprendo che il dizionario di Python è essenzialmente un hashtable. Ma ho capito che la struttura dei dati viene immagazzinata nella memoria per ordine di inserimento, e viene quindi letta, quando si esegue l'iterazione sull'intera infrastruttura dati, in un ordine simile. Ma questo non è il caso.

Oltre a non capire come funziona, mi chiedo anche il beneficio di questo. Ma potrebbe essere fin troppo chiaro quando capisco come funziona:)

ps. Non pensavo che fosse una domanda StackOverflow, quindi mettila qui ...

    
posta puredevotion 16.12.2013 - 04:02
fonte

2 risposte

1

Dizionari / hash vengono spesso implementati come una matrice di elenchi collegati.

La chiave viene prima sottoposta a hash per assegnare un indice per l'array che punta alla prima voce di un elenco collegato. Quindi viene eseguita la ricerca nell'elenco collegato per verificare se esiste una voce con la chiave.

Quindi per qualsiasi dizionario abbastanza grande ci sarà un array ordinato a caso, di liste collegate. Ogni lista collegata verrà ordinata per sequenza di inserimento.

    
risposta data 16.12.2013 - 06:45
fonte
0

Una tabella hash contiene alcune parti ordinate, come l'elenco di bucket, ma raramente le accedi in quell'ordine perché quell'ordine ha poca o nessuna correlazione con nessuna parte utile dei tuoi dati.

Supponiamo di voler archiviare molte stringhe. Se il tuo obiettivo è quello di estrarre efficientemente la stringa 73 (o altra scelta arbitrariamente), allora potresti usare un array, che è ordinato. Quindi ottenere la 73ª stringa è questione di fare riferimento direttamente all'elemento 73rd dell'array.

Tuttavia, il tuo obiettivo è determinare in modo efficiente se una determinata stringa è presente nel tuo set. Se si dispone di un array non ordinato, è necessario cercare tra tutte le stringhe. Se si dispone di un array ordinato, è necessario ordinare il log (n) delle stringhe, che è meglio ma non eccezionale. Quindi la soluzione è una tabella hash.

Ingenuità ... Si crea una matrice con 256 voci (ciascuna che rappresenta un carattere), ciascuna che punta a un elenco o una serie di stringhe che iniziano con quel carattere. Ora, se vuoi scoprire se "Bob" è nel tuo set di stringhe, salta immediatamente al bucket "B" e guarda solo attraverso quelle stringhe.

Ovviamente, questo esempio significa ancora che le stringhe vengono fuori in ordine alfabetico, il che suona bene, ma nel mondo reale si usa una funzione di hash più complessa di "il primo carattere", preferibilmente una che distribuisce le stringhe in modo uniforme il più possibile tra i tuoi secchi. Il risultato è che semplicemente leggendo la tua tabella hash in ordine darai un ordine pseudo-casuale delle tue stringhe.

    
risposta data 16.12.2013 - 04:13
fonte

Leggi altre domande sui tag