Memoria asignada: algoritmos parcialmente basados ​​en disco

Question

¿Existen buenos recursos o libros para estructuras de datos derramables, es decir, una cola?

Al almacenar objetos grandes podría llenar toda la memoria, pero si puede guardar, por ejemplo, los elementos más utilizados de esa estructura de cola en la memoria y el resto en el disco (algo así como paginación).

De manera similar, esta pregunta se aplica a otras estructuras como listas vinculadas, matrices, tablas hash, etc.

Answer 1

Lo que está buscando podría ser el tema de los algoritmos eficientes de E/S. Una búsqueda en Google no apareció ningún libro para mí, pero este course page contiene una lista de artículos que pueden o no ser relevantes para usted.

También debería echar un vistazo a WikiPedia page for B-trees, especialmente la sección en B-trees in filesystems.

Answer 2

Existe la Buffer Tree (PDF, 0,6 MB):

" ... desarrollado una cola de prioridad y eficiente externa versiones dinámicas por lotes del (unidimensional) árbol gama y el árbol segmento "

y

" ... nos permitirá diseñar algoritmos de memoria externa eficientes de algoritmos internos conocidos de una manera directa, de tal manera que todas las E/S de partes específicas de los algoritmos son oculto en las estructuras de datos. "

es el mencionado como parte de un tratamiento más amplio de la tema en la libre disposición libro en línea "Algorithms and Data Structures for External Memory" por Jeffrey de Scott Vitter (PDF, 1 MB).

Answer 3

¿Quiere decir encontrar análogos basados ​​en disco eficientes a las estructuras de datos basadas en RAM fundamentales (por ejemplo, listas enlazadas, pilas, colas, colas de prioridad, etc.)? Si es así, la respuesta a continuación puede o no ser útil.

---

No estoy del todo seguro de lo que estás tratando de hacer. Por cola, ¿te refieres a una cola FIFO (primero en entrar, primero en salir) o una cola de prioridad?

Para tratar las colas y el registro de FIFO, quizás podría examinar los búferes de anillo y la rotación de registros.

Para tratar con los datos de almacenamiento en caché en la memoria RAM para minimizar el acceso al disco, puede o no ser mejor dejar eso al sistema operativo. A menos que esté desarrollando una aplicación para Windows, es mejor que simplemente lea y escriba desde y hacia archivos de forma ingenua, ya que el sistema operativo debe realizar el almacenamiento en caché de lectura y escritura lo suficientemente bien. Sin embargo, por lo que puedo decir, Windows tiene un almacenamiento en caché de lectura/escritura horrible (puedo estar equivocado).

Tal vez mirar el subsistema VFS en Linux y estudiar http://lxr.linux.no/#linux+v2.6.31/Documentation/filesystems/vfs.txt ayudará, ya que (creo) esta es la parte de Linux que maneja el almacenamiento en caché.

No soy un experto en colas y almacenamiento en caché, pero sé algunas cosas al respecto. Si pudiera proporcionar más detalles sobre lo que está tratando de hacer, quizás alguien pueda ayudarlo a encontrar la solución correcta.