Algoritmo de memoria externa
En informática , los algoritmos de memoria externa o algoritmos fuera del núcleo son algoritmos que están diseñados para procesar datos que son demasiado grandes para caber en la memoria principal de una computadora a la vez. Dichos algoritmos deben optimizarse para obtener y acceder de manera eficiente a los datos almacenados en la memoria masiva lenta (memoria auxiliar ), como discos duros o unidades de cinta , o cuando la memoria está en una red informática . [1] [2] Los algoritmos de memoria externa se analizan en el modelo de memoria externa .
Los algoritmos de memoria externa se analizan en un modelo idealizado de computación denominado modelo de memoria externa (o modelo de E/S , o modelo de acceso al disco ). El modelo de memoria externa es una máquina abstracta similar al modelo de máquina RAM , pero con un caché además de la memoria principal . El modelo captura el hecho de que las operaciones de lectura y escritura son mucho más rápidas en un caché que en la memoria principal , y que la lectura de bloques contiguos largos es más rápida que la lectura aleatoria utilizando un cabezal de lectura y escritura de disco . El tiempo de ejecución de un algoritmo.en el modelo de memoria externa se define por el número de lecturas y escrituras requeridas en la memoria. [3] El modelo fue presentado por Alok Aggarwal y Jeffrey Vitter en 1988. [4] El modelo de memoria externa está relacionado con el modelo de memoria caché ajena , pero los algoritmos en el modelo de memoria externa pueden conocer tanto el tamaño del bloque como el tamaño de la caché . Por este motivo, a veces se hace referencia al modelo como modelo con reconocimiento de memoria caché . [5]
El modelo consta de un procesador con una memoria interna o caché de tamaño M , conectado a una memoria externa ilimitada . Tanto la memoria interna como la externa están divididas en bloques de tamaño B. Una operación de entrada/salida o transferencia de memoria consiste en mover un bloque de B elementos contiguos desde la memoria externa a la interna, y el tiempo de ejecución de un algoritmo está determinado por el número de estas operaciones de entrada/salida. [4]
Los algoritmos en el modelo de memoria externa aprovechan el hecho de que recuperar un objeto de la memoria externa recupera un bloque completo de tamaño . Esta propiedad a veces se denomina localidad.
La búsqueda de un elemento entre los objetos es posible en el modelo de memoria externa utilizando un árbol B con factor de ramificación . Usando un árbol B, la búsqueda, la inserción y la eliminación se pueden lograr en el tiempo (en notación Big O ). Información teóricamente , este es el tiempo de ejecución mínimo posible para estas operaciones, por lo que usar un árbol B es asintóticamente óptimo . [4]
La clasificación externa es la clasificación en una configuración de memoria externa. La ordenación externa se puede realizar a través de la ordenación por distribución, que es similar a la ordenación rápida , o a través de una ordenación por combinación de vías . Ambas variantes logran el tiempo de ejecución asintóticamente óptimo para clasificar N objetos. Este límite también se aplica a la transformada rápida de Fourier en el modelo de memoria externa. [2]
