In che modo le matrici e le mappe hash sono costanti nel loro accesso?

Question

In particolare: dato un hash (o un indice di array), come fa la macchina a raggiungere i dati in tempo costante?

Mi sembra che anche il passaggio da tutte le altre posizioni di memoria (o qualsiasi altra cosa) richiederebbe una quantità di tempo uguale al numero di posizioni passate (quindi tempo lineare). Un collaboratore ha cercato coraggiosamente di spiegarmelo, ma ha dovuto rinunciare quando siamo scesi in pista.

Esempio:

my_array = new array(:size => 20) 
my_array[20] = "foo" 
my_array[20] # "foo" 

accesso di "foo" in posizione 20 è costante, perché sappiamo che secchio "foo" è in Come siamo magicamente arriva a quel secchio senza passare tutti gli altri sulla strada. ? Per arrivare a casa # 20 su un blocco dovresti comunque passare dall'altro 19 ...

Answer 1

Come siamo magicamente arriva a che secchio senza passare tutti gli altri sulla strada?

"Noi" non "andiamo" al secchio affatto. Il modo in cui la RAM funziona fisicamente è più come trasmettere il numero del bucket su un canale su cui tutti i bucket ascoltano, e quello il cui numero è stato chiamato ti invierà il suo contenuto.

I calcoli si verificano nella CPU. In teoria, la CPU è la stessa "distanza" da tutte le posizioni di memoria (in pratica non lo è, a causa del caching, che può avere un impatto enorme sulle prestazioni).

Se si desidera visualizzare i dettagli più importanti, leggere "What every programmer should know about memory".

Answer 2

Quindi per capire devi vedere come la memoria è organizzata e accessibile. Potrebbe essere necessario esaminare il modo in cui un address decoder funziona. Il fatto è che NON devi passare da tutti gli altri indirizzi per arrivare a quello che vuoi nella memoria. Puoi effettivamente saltare a quello che vuoi. Altrimenti i nostri computer sarebbero davvero molto lenti.

Answer 3

A differenza di una macchina di turing, che dovrebbe accedere alla memoria in modo sequenziale, i computer utilizzano una memoria ad accesso casuale, o RAM, il che significa che se sanno dove inizia l'array e sanno di voler accedere al 20 ° elemento dell'array, sapere quale parte della memoria guardare.

È meno come guidare lungo una strada e più simile a scegliere lo slot di posta corretto per il tuo appartamento in una casella di posta condivisa.

Answer 4

2 cose sono importanti:

1. my_array ha informazioni su dove nel computer di memoria deve saltare per ottenere questo array.
2. indice * sizeof type ottiene offset dall'inizio della matrice.

1 + 2 = O (1) in cui i dati possono essere trovati

Answer 5

Big O non funziona così. Dovrebbe essere una misura di quanto le risorse computazionali vengono utilizzate da un particolare algoritmo e funzione. Non è pensato per misurare la quantità di memoria utilizzata e se stai parlando di attraversare quella memoria, è ancora un tempo costante. Se ho bisogno di trovare il secondo slot di un array, si tratta di aggiungere un offset a un puntatore. Ora, se ho una struttura ad albero e voglio trovare un nodo particolare, ora stai parlando di O (log n) perché non lo trova al primo passaggio. In media ci vuole O (log n) per trovare quel nodo.

Answer 6

Discutiamo di questo in termini C/C++; ci sono alcune cose aggiuntive da sapere sugli array C# ma non è davvero rilevante al punto.

dato un array di valori interi a 16 bit:

short[5] myArray = {1,2,3,4,5}; 

cosa è realmente accaduto è che il computer è assegnato un blocco di spazio nella memoria. Questo blocco di memoria è riservato per quell'array, è esattamente la dimensione necessaria per contenere l'array completo (nel nostro caso 16 * 5 == 80 bit == 10 byte) ed è contiguo. Questi fatti sono dati; se qualcuno o nessuno di essi è vero nel proprio ambiente in un dato momento, si rischia generalmente di causare il blocco del programma a causa di una vializzazione di accesso.

Quindi, data questa struttura, ciò che la variabile myArray è, dietro le quinte, è l'indirizzo di memoria dell'inizio del blocco di memoria. Questo è anche, comodamente, l'inizio del primo elemento. Ogni elemento aggiuntivo è allineato nella memoria subito dopo il primo, in ordine. Il blocco di memoria allocata per myArray potrebbe essere simile:

00000000000000010000000000000010000000000000001100000000000001000000000000000101 
^    ^   ^   ^   ^
myArray([0]) myArray[1]  myArray[2]  myArray[3]  myArray[4] 

È considerato un'operazione costante di tempo per accedere ad un indirizzo di memoria e leggere un numero costante di byte. Come nella figura sopra, è possibile ottenere l'indirizzo di memoria per ognuno se si conoscono tre cose; l'inizio del blocco di memoria, la dimensione della memoria di ciascun elemento e l'indice dell'elemento desiderato. Così, quando si chiede myArray[3] nel codice, tale richiesta è trasformato in un indirizzo di memoria dalla seguente equazione:

myArray[3] == &myArray+sizeof(short)*3; 

Così, con un calcolo costante di tempo, avete trovato l'indirizzo di memoria del quarto elemento (indice 3), e con un'altra operazione a tempo costante (o almeno considerata tale, la complessità di accesso effettiva è un dettaglio hardware e abbastanza veloce da non doversene preoccupare) è possibile leggere quella memoria. Questo è, se vi siete mai chiesti, perché gli indici delle raccolte nella maggior parte dei linguaggi in stile C partono da zero; il primo elemento dell'array inizia nella posizione dell'array stesso, senza offset (sizeof (nulla) * 0 == 0)

In C#, ci sono due differenze notevoli. Gli array C# hanno alcune informazioni di intestazione che sono utili per il CLR. L'intestazione viene prima nel blocco di memoria, e la dimensione di questa intestazione è nota e costante, quindi l'equazione indirizzamento ha una sola differenza fondamentale:

myArray[3] == &myArray+headerSize+sizeof(short)*3; 

C# non consente di fare riferimento direttamente memoria nel suo gestiti ambiente, ma il runtime stesso utilizzerà qualcosa di simile per eseguire l'accesso alla memoria dall'heap.

La seconda cosa, che è comune anche alla maggior parte dei sapori di C/C++, è che determinati tipi vengono sempre gestiti "per riferimento". Qualsiasi cosa tu debba usare la parola chiave new da creare è un tipo di riferimento (e ci sono alcuni oggetti, come le stringhe, che sono anche tipi di riferimento anche se sembrano tipi di valori nel codice). Un tipo di riferimento, se istanziato, viene posto in memoria, non si sposta e solitamente non viene copiato. Qualsiasi variabile che rappresenta quell'oggetto è quindi, dietro le quinte, solo l'indirizzo di memoria dell'oggetto in memoria. Gli array sono tipi di riferimento (ricorda che myArray era solo un indirizzo di memoria). Le matrici di tipi di riferimento sono matrici di questi indirizzi di memoria, quindi l'accesso a un oggetto che è un elemento in un array è un processo in due fasi; per prima cosa si calcola l'indirizzo di memoria dell'elemento nell'array e si ottiene quello.Questo è un altro indirizzo di memoria, che è la posizione dell'oggetto reale (o almeno dei suoi dati mutabili, il modo in cui i tipi composti sono strutturati in memoria è un intero altro che può essere un worm). Questa è ancora un'operazione a tempo costante; solo due passi invece di uno.