È possibile una memoria di tutte le possibili permutazioni di un blocco di kilobyte e dei puntatori?

Ci sono 2 ⁸¹⁹² possibili blocchi 1K diversi. Memorizzandoli tutti occorrerebbero 2 ⁸²⁰² bit di memoria. Poiché l'universo contiene solo circa 10 particelle ⁸⁰ (o ~ 2 ²⁶⁶ ), è sicuro che non è possibile memorizzarle tutto, e non ti devi chiedere se sarebbe un risparmio di tempo o meno.

Ma c'è, in effetti, un modo più interessante di rispondere a questo. Stai suggerendo di creare un indice in un enorme pool di costanti. Ma come sapresti quale indice dereferenziare? Immagina per un argomento che vuoi archiviare solo blocchi di 1 carattere: a , b , c ... Presumibilmente i tuoi indici sarebbero 0, 1, 2 ecc., Poiché è il più efficiente layout di memorizzazione di quei blocchi.

Hai notato qualcosa riguardo alla sistemazione? Il tuo indice è, infatti, una rappresentazione codificata dei dati memorizzati ! In altre parole, non è necessario effettuare il dereferenziamento, è sufficiente trasformare l'indice nei dati desiderati.

Quando memorizzi tutti i possibili valori di qualcosa in una tabella, ciò accade sempre: il tuo indice diventa semplicemente una versione codificata dei dati stessi, quindi la memorizzazione dei dati diventa inutile in primo luogo. Questo è il motivo per cui nel mondo reale gli indici sono utili solo per dati sparsi (ad esempio tutte le pagine web che hai visitato, non tutte le pagine web che potrebbero esistere , o anche tutte quelle che fanno > esiste).

Come altri hanno già sottolineato, hai 2 ^ 8192 possibilità per un blocco di 1k. Ciò significa che avresti bisogno di 8192 bit per codificare l'indirizzo di un blocco se tutti gli indirizzi dei blocchi sono codificati con la stessa quantità di bit, quindi i tuoi indirizzi sarebbero 1 k lungo. Non avresti guadagnato nulla se non aggiungendo uno strato di riferimento indiretto in modo da non ottenere alcuna prestazione.

Se vuoi avere degli indirizzi più corti, dovresti codificare alcuni blocchi con un indirizzo breve e alcuni con quelli più lunghi e fare in modo che quelli lunghi non compaia spesso, e ora stai semplicemente comprimendo i dati (probabilmente con qualcosa come un codice Huffman ). Ciò richiederebbe la conoscenza dei dati che stai memorizzando prima di memorizzarli o cambiamenti regolari nella codifica. Probabilmente sarebbe anche meno efficiente di altri algoritmi di compressione che usano blocchi di lunghezza variabile.

Ci sono due problemi con questo.

Primo, "tutte le possibili permutazioni binarie di un kilobyte" è una quantità enorme di dati. 1024 byte * 8 bit per byte = 8192 bit in un kilobyte. Tutte le possibili permutazioni sarebbero 2 ^ 8192. Questo è circa 1.09e+2466 kilobyte! (A scopo di confronto, un'unità da 1 TB è 1e09 kilobyte.)

In secondo luogo, anche se disponevi di una tabella così enorme e ci indicassi con i puntatori, cosa faresti se volessi fare riferimento a dati più piccoli di esattamente 1 KB?

Come altri segnalatori hanno sottolineato, a un certo punto, la dimensione del puntatore necessario per indicizzare l'elenco di tutti i valori possibili annulla il tuo guadagno.

Tuttavia, alcune lingue usano una versione limitata di ciò che suggerisci per ottimizzare l'utilizzo della memoria. Python utilizza la stringa "interning" per ridurre il numero di stringhe duplicate in memoria. Puoi trovare ulteriori informazioni cercando "python string intern".