Una lista autoorganizada es una lista que reordena sus elementos basándose en alguna heurística autoorganizada para mejorar el tiempo de acceso promedio . El objetivo de una lista autoorganizada es mejorar la eficiencia de la búsqueda lineal moviendo los elementos a los que se accede con más frecuencia hacia el encabezado de la lista. Una lista autoorganizada logra un tiempo casi constante para acceder a los elementos en el mejor de los casos. Una lista autoorganizada utiliza un algoritmo de reorganización para adaptarse a varias distribuciones de consultas en tiempo de ejecución.
Historia
El concepto de listas autoorganizadas tiene sus raíces en la idea de organización de actividades [1] de registros en archivos almacenados en discos o cintas. Una discusión que se cita con frecuencia sobre listas y archivos autoorganizados es la de Knuth. [2] John McCabe dio los primeros análisis algorítmicos de complejidad de la estrategia Move-to-Front (MTF) en la que un elemento se mueve al principio de la lista después de que se accede a él. [3] Analizó el tiempo promedio necesario para que la lista ordenada al azar se coloque en el orden óptimo. El orden óptimo de una lista es aquel en el que los elementos se ordenan en la lista por la probabilidad con la que se necesitarán, con el elemento más visitado primero. Es posible que el orden óptimo no se conozca de antemano y que también cambie con el tiempo.
McCabe introdujo la estrategia de transposición en la que un elemento al que se accede se intercambia con el elemento que está delante de él en la lista. Hizo la conjetura de que, en el caso medio, la transposición funcionaba al menos tan bien como el MTF para aproximarse al orden óptimo de registros en el límite. Esta conjetura fue probada más tarde por Rivest. [4] McCabe también señaló que con la transposición o la heurística MTF, el orden óptimo de los registros se abordaría incluso si la heurística solo se aplicara cada enésimo acceso, y que se podría elegir un valor de N que reflejara el costo relativo de reubicar registros con el valor de acercarse al pedido óptimo más rápidamente. Se realizaron mejoras adicionales y los investigadores sugirieron algoritmos, entre ellos: Rivest, Tenenbaum y Nemes, Knuth y Bentley y McGeoch (por ejemplo, análisis del peor caso para heurísticas de búsqueda secuencial autoorganizadas).
Introducción
La implementación más simple de una lista autoorganizada es como una lista vinculada y, por lo tanto, aunque es eficiente en la inserción de nodos aleatorios y la asignación de memoria, adolece de accesos ineficaces a nodos aleatorios. Una lista autoorganizada reduce la ineficiencia al reorganizar dinámicamente los nodos en la lista según la frecuencia de acceso.
Ineficiencia de los recorridos de listas vinculadas
Si se va a buscar un nodo en particular en la lista, cada nodo de la lista debe compararse secuencialmente hasta que se alcance el nodo deseado. En una lista vinculada, recuperar el elemento n es una operación O (n). Esto es muy ineficiente en comparación con una matriz, por ejemplo, donde acceder al n- ésimo elemento es una operación O (1).
Eficiencia de listas autoorganizadas
Una lista autoorganizada reorganiza los nodos manteniendo los a los que se accede con más frecuencia al principio de la lista. Generalmente, en una consulta particular, las posibilidades de acceder a un nodo al que se ha accedido muchas veces antes son mayores que las posibilidades de acceder a un nodo al que históricamente no se ha accedido con tanta frecuencia. Como resultado, mantener los nodos a los que se accede habitualmente al principio de la lista reduce el número de comparaciones necesarias en un caso medio para llegar al nodo deseado. Esto conduce a una mayor eficiencia y, en general, a tiempos de consulta reducidos.
Implementación de una lista autoorganizada
La implementación y los métodos de una lista autoorganizada son idénticos a los de una lista enlazada estándar . La lista enlazada y la lista autoorganizada difieren solo en términos de la organización de los nodos; la interfaz sigue siendo la misma.
Análisis de tiempos de ejecución para acceso / búsqueda en una lista
Caso medio
Puede demostrarse que en el caso medio, el tiempo necesario para realizar una búsqueda en una lista autoorganizada de tamaño n es
donde p (i) es la probabilidad de acceder al i-ésimo elemento de la lista, por lo que también se denomina probabilidad de acceso. Si la probabilidad de acceso de cada elemento es la misma (es decir, p (1) = p (2) = p (3) = ... = p (n) = 1 / n) entonces el orden de los elementos es irrelevante y el La complejidad del tiempo promedio viene dada por
y T (n) no depende de las probabilidades de acceso individuales de los elementos de la lista en este caso. Sin embargo, en el caso de búsquedas en listas con probabilidades de acceso a registros no uniformes (es decir, aquellas listas en las que la probabilidad de acceder a un elemento es diferente de otro), la complejidad del tiempo promedio puede reducirse drásticamente mediante el posicionamiento adecuado de los elementos contenidos en el lista.
Esto se hace emparejando i más pequeño con mayores probabilidades de acceso para reducir la complejidad de tiempo promedio general. Esto se puede demostrar de la siguiente manera:
Lista dada: A (0.1), B (0.1), C (0.3), D (0.1), E (0.4)
Sin reorganizar, el tiempo de búsqueda promedio requerido es:
Ahora suponga que los nodos se reorganizan para que los nodos con mayor probabilidad de acceso se coloquen más cerca del frente de modo que la lista reordenada sea ahora:
E (0.4), C (0.3), D (0.1), A (0.1), B (0.1)
Aquí, el tiempo de búsqueda promedio es:
Por tanto, el tiempo medio necesario para buscar en una lista organizada es (en este caso) alrededor de un 40% menos que el tiempo necesario para buscar en una lista organizada de forma aleatoria. Este es el concepto de la lista autoorganizada en el sentido de que la velocidad media de recuperación de datos aumenta reorganizando los nodos de acuerdo con la frecuencia de acceso.
Peor de los casos
En el peor de los casos, el elemento a ubicar está al final de la lista, ya sea una lista normal o autoorganizada, por lo que se deben hacer n comparaciones para llegar a él. Por lo tanto, el peor tiempo de ejecución de una búsqueda lineal en la lista es O (n) independiente del tipo de lista utilizada. Tenga en cuenta que la expresión para el tiempo de búsqueda promedio en la sección anterior es probabilística. Mantener los elementos de acceso común al principio de la lista simplemente reduce la probabilidad de que ocurra el peor de los casos, pero no lo elimina por completo. Incluso en una lista autoorganizada, si se va a acceder a un elemento de menor probabilidad de acceso (obviamente ubicado al final de la lista), se debe recorrer toda la lista para recuperarla. Esta es la búsqueda del peor de los casos.
Mejor caso
En el mejor de los casos, el nodo que se va a buscar es uno al que se ha accedido comúnmente y, por lo tanto, ha sido identificado por la lista y mantenido a la cabeza. Esto resultará en una operación de tiempo casi constante. En notación de oh grande, en el mejor de los casos, acceder a un elemento es una operación O (1).
Técnicas para reorganizar los nodos.
Al ordenar los elementos de la lista, las probabilidades de acceso de los elementos generalmente no se conocen de antemano. Esto ha llevado al desarrollo de varias heurísticas para aproximar el comportamiento óptimo. Las heurísticas básicas utilizadas para reordenar los elementos de la lista son:
Mover al método delantero (MTF)
Esta técnica mueve el elemento al que se accede al encabezado de la lista. Esto tiene la ventaja de que se implementa fácilmente y no requiere memoria adicional. Esta heurística también se adapta rápidamente a cambios rápidos en la distribución de consultas. Por otro lado, este método puede priorizar los nodos a los que se accede con poca frecuencia; por ejemplo, si se accede a un nodo poco común incluso una vez, se mueve al encabezado de la lista y se le da la máxima prioridad incluso si no se va a acceder con frecuencia en la lista. futuro. Estos nodos 'recompensados en exceso' destruyen el orden óptimo de la lista y conducen a tiempos de acceso más lentos para los elementos a los que se accede comúnmente. Otra desventaja es que este método puede volverse demasiado flexible y dar lugar a patrones de acceso que cambian con demasiada rapidez. Esto significa que debido a las memorias muy cortas de los patrones de acceso, incluso una disposición óptima de la lista se puede alterar inmediatamente al acceder a un nodo poco frecuente en la lista.
Si se selecciona el quinto nodo, se mueve al frente
En la t-ésima selección de artículo: si se selecciona el artículo i: mover el elemento i al encabezado de la lista
Método de conteo
En esta técnica, se cuenta el número de veces que se buscó cada nodo, es decir, cada nodo mantiene una variable de contador separada que se incrementa cada vez que se llama. Luego, los nodos se reorganizan de acuerdo con el recuento decreciente. Por tanto, los nodos de mayor recuento, es decir, a los que se accede con mayor frecuencia, se mantienen al principio de la lista. La principal ventaja de esta técnica es que generalmente es más realista al representar el patrón de acceso real. Sin embargo, existe un requisito de memoria adicional, el de mantener una variable de contador para cada nodo de la lista. Además, esta técnica no se adapta rápidamente a cambios rápidos en los patrones de acceso. Por ejemplo: si el recuento del elemento principal dice A es 100 y para cualquier nodo posterior dice B es 40, entonces incluso si B se convierte en el nuevo elemento al que se accede con más frecuencia, aún se debe acceder al menos (100 - 40 = 60 ) veces antes de que pueda convertirse en el elemento principal y así hacer que el orden de la lista sea óptimo.
Si se busca dos veces el quinto nodo de la lista, se intercambiará con el cuarto
init: count (i) = 0 para cada elemento iEn la t-ésima selección de artículo: si se busca el elemento i: contar (i) = contar (i) + 1 reorganizar los elementos según el recuento
Método de transposición
Esta técnica implica intercambiar un nodo al que se accede con su predecesor. Por lo tanto, si se accede a cualquier nodo, se intercambia con el nodo que está al frente, a menos que sea el nodo principal, lo que aumenta su prioridad. Este algoritmo es nuevamente fácil de implementar y eficiente en el espacio y es más probable que mantenga los nodos a los que se accede con frecuencia al principio de la lista. Sin embargo, el método de transposición es más cauteloso. es decir, se necesitarán muchos accesos para mover el elemento al encabezado de la lista. Este método tampoco permite una respuesta rápida a los cambios en las distribuciones de consultas en los nodos de la lista.
Si se selecciona el quinto nodo de la lista, se intercambiará con el cuarto
En la t-ésima selección de elementos: si se selecciona el elemento i: si i no es el encabezado de la lista: intercambiar el artículo i con el artículo (i - 1)
Otros metodos
La investigación se ha centrado en fusionar los algoritmos anteriores para lograr una mejor eficiencia. [5] El algoritmo de Bitner usa MTF inicialmente y luego usa el método de transposición para reordenamientos más finos. Algunos algoritmos son aleatorios e intentan evitar la recompensa excesiva de los nodos a los que se accede con poca frecuencia que puede ocurrir en el algoritmo MTF. Otras técnicas implican reorganizar los nodos basándose en los algoritmos anteriores después de cada n accesos en la lista como un todo o después de n accesos seguidos en un nodo en particular y así sucesivamente. Algunos algoritmos reorganizan los nodos a los que se accede en función de su proximidad al nodo principal, por ejemplo: algoritmos Swap-With-Parent o Move-To-Parent. Se usa otra clase de algoritmos cuando el patrón de búsqueda exhibe una propiedad llamada localidad de referencia por la cual en un intervalo de tiempo dado, es probable que solo se acceda a un subconjunto más pequeño de la lista. Esto también se conoce como acceso dependiente donde la probabilidad de acceso de un elemento particular depende de la probabilidad de acceso de sus elementos vecinos. Estos modelos son comunes en aplicaciones del mundo real, como bases de datos o sistemas de archivos y administración de memoria y almacenamiento en caché. Un marco común para los algoritmos que se ocupan de estos entornos dependientes es reorganizar la lista no solo en función del registro al que se accede, sino también en los registros cercanos. Esto implica efectivamente reorganizar una sublista de la lista a la que pertenece el registro.
Aplicaciones de listas autoorganizadas
Los traductores de idiomas, como los compiladores e intérpretes, utilizan listas autoorganizadas para mantener tablas de símbolos durante la compilación o interpretación del código fuente del programa. Actualmente se está investigando para incorporar la estructura de datos de lista autoorganizada en sistemas integrados para reducir la actividad de transición de bus que conduce a la disipación de energía en esos circuitos. Estas listas también se utilizan en inteligencia artificial y redes neuronales, así como en programas de autoajuste. Los algoritmos utilizados en las listas autoorganizadas también se utilizan como algoritmos de almacenamiento en caché como en el caso del algoritmo LFU.
Los métodos simples Move to Front y transpose también son aplicables en colecciones del mundo real: por ejemplo, organizar un cajón de especias reemplazando artículos usados al frente de un cajón, o transponer un artículo de limpieza con su vecino más al frente cuando se usa.
Notas
- ^ Becker, J .; Hayes, RM (1963), Almacenamiento y recuperación de información: herramientas, elementos, teorías , Nueva York: Wiley
- ^ Knuth, Donald (1998), Clasificación y búsqueda , El arte de la programación informática , Volumen 3 (Segunda ed.), Addison-Wesley, p. 402, ISBN 978-0-201-89685-5
|volume=
tiene texto extra ( ayuda ) - ^ McCabe, John (1965), "On Serial Files with Relocatable Records", Operations Research , 13 (4): 609–618, doi : 10.1287 / opre.13.4.609
- ^ Rivest, Ronald (1976), "Sobre heurística de búsqueda secuencial autoorganizada", Communications of the ACM , 19 (2): 63–67, doi : 10.1145 / 359997.360000
- ^ Amer, Abdelrahman; Oommen, B. John (2006). "Listas en listas: un marco para listas autoorganizadas en entornos con localidad de referencia". Algoritmos experimentales . Apuntes de conferencias en Ciencias de la Computación. 4007 . págs. 109-120. doi : 10.1007 / 11764298_10 . ISBN 978-3-540-34597-8.
Referencias
- Auto organización (PDF) , 2004
- Entrada NIST DADS
- Drozdek, estructuras de datos y algoritmos en Java Tercera edición
- Amer, Abdelrehman; B. John Oommen (2006), Lists on Lists: A Framework for Self-Organing Lists in Environment with Locality of Reference , Lecture Notes in Computer Science, 4007 , doi : 10.1007 / 11764298 , ISBN 978-3-540-34597-8