Memoria mappata - algoritmi parzialmente basati su disco

Question

Esistono buone risorse o libri per strutture di dati spillabili, vale a dire una coda?

Quando si memorizzano oggetti di grandi dimensioni, potrebbe riempire tutta la memoria, ma se è possibile mantenere, ad esempio, gli elementi più utilizzati di quella struttura di coda in memoria e il resto su disco (una sorta di impaginazione simile).

Analogamente, questa domanda si applica ad altre strutture come elenchi collegati, matrici, hashtables e così via.

Answer 1

Quello che stai cercando potrebbe essere l'argomento degli algoritmi I/O efficienti. Una ricerca Google non ha generato alcun libro per me, ma questo course page contiene un elenco di articoli che potrebbero essere o non essere rilevanti per te.

Si dovrebbe anche dare un'occhiata allo WikiPedia page for B-trees, in particolare la sezione B-trees in filesystems.

Answer 2

C'è la Buffer Tree (PDF, 0.6 MB):

" ... sviluppato una coda efficiente esterna di priorità e versioni dinamiche dosati del (unidimensionale) albero gamma e l'albero segmento ".

e

" ... ci permettono di progettare algoritmi esterni efficiente della memoria da algoritmi interni noti in modo semplice, tale che tutte le parti di I/O specifiche degli algoritmi sono nascosto nelle strutture dati. "

E 'il menzionato come parte di un trattamento più ampia della soggetto nella liberamente disponibile on-line libro "Algorithms and Data Structures for External Memory" da Jeffrey Scott Vitter (PDF, 1 MB).

Answer 3

Significa trovare efficienti analoghi basati su disco per le strutture di dati fondamentali basate su RAM (ad esempio, elenchi collegati, stack, code, code di priorità, ecc.)? In tal caso, la risposta potrebbe non essere utile o meno.

---

Non sono del tutto sicuro di quello che stai cercando di fare. Per coda, intendi una coda FIFO (first in first out) o una coda prioritaria?

Per la gestione delle code FIFO e della registrazione, è possibile esaminare i buffer delle suonerie e la rotazione dei registri.

Per la gestione dei dati di memorizzazione nella cache nella RAM per ridurre al minimo l'accesso al disco, è possibile o meno lasciare questo al sistema operativo. A meno che tu non stia sviluppando un'applicazione per Windows, potresti stare meglio leggendo e scrivendo da e verso i file in modo ingenuo, dal momento che il sistema operativo dovrebbe eseguire una lettura e scrittura nella cache abbastanza buona. Tuttavia, per quanto posso dire, Windows ha una cache di lettura/scrittura orribile (potrei sbagliarmi).

Forse guardare il sottosistema VFS in Linux e studiare http://lxr.linux.no/#linux+v2.6.31/Documentation/filesystems/vfs.txt aiuterà, poiché (penso) questa è la parte di Linux che gestisce la cache.

Non sono un esperto di code e memorizzazione nella cache, ma so alcune cose a riguardo. Se potresti fornire maggiori dettagli su ciò che stai cercando di fare, forse qualcuno può aiutarti a trovare la giusta soluzione.