Lista autoorganizada | Serie 1 (Introducción)

El tiempo de búsqueda en el peor de los casos para una lista enlazada ordenada es O(n). Con un árbol de búsqueda binario equilibrado, podemos omitir casi la mitad de los Nodes después de una comparación con la raíz. Para una array ordenada, tenemos acceso aleatorio y podemos aplicar la búsqueda binaria en las arrays.

Una idea para hacer que la búsqueda de listas enlazadas sea más rápida es Saltar lista . Otra idea (que se discute en esta publicación) es colocar los elementos a los que se accede con más frecuencia más cerca de la cabeza. . Puede haber dos posibilidades. fuera de línea (conocemos la secuencia de búsqueda completa de antemano) y en línea (no conocemos la secuencia de búsqueda).
En caso de estar fuera de línea, podemos colocar los Nodes de acuerdo con las frecuencias de búsqueda decrecientes (el elemento que tiene el número máximo de búsquedas se coloca primero). Para muchas aplicaciones prácticas, puede ser difícil obtener la secuencia de búsqueda por adelantado. Una lista autoorganizadareordena sus Nodes en función de las búsquedas que se realizan. La idea es utilizar la localidad de referencia (en una base de datos típica, el 80% de los accesos son al 20% de los elementos). Las siguientes son diferentes estrategias utilizadas por las listas autoorganizadas.

1) Método Move-to-Front : Cualquier Node buscado se mueve al frente. Esta estrategia es fácil de implementar, pero puede recompensar en exceso los elementos a los que se accede con poca frecuencia, ya que siempre mueve el elemento al frente.

2) Método de recuento : cada Node almacena el recuento del número de veces que se buscó. Los Nodes están ordenados por número decreciente. Esta estrategia requiere espacio adicional para almacenar el conteo.

3) Método de transposición : cualquier Node buscado se intercambia con el Node anterior. A diferencia de Move-to-front, este método no se adapta rápidamente a patrones de acceso cambiantes.

Análisis competitivo:
La complejidad temporal en el peor de los casos de todos los métodos es O(n). En el peor de los casos, el elemento buscado es siempre el último elemento de la lista. Para el análisis de casos promedio , necesitamos una distribución de probabilidad de secuencias de búsqueda que no está disponible muchas veces.
Para estrategias y algoritmos en línea como los anteriores, tenemos una forma totalmente diferente de analizarlos llamada análisis competitivo.donde el rendimiento de un algoritmo en línea se compara con el rendimiento de un algoritmo fuera de línea óptimo (que puede ver la secuencia de requests por adelantado). El análisis competitivo se utiliza en muchos algoritmos prácticos como almacenamiento en caché, paginación de disco, computadoras de alto rendimiento. Lo mejor del análisis competitivo es que no necesitamos asumir nada sobre la distribución de probabilidad de entrada. El método Move-to-front es 4-competitivo, lo que significa que nunca hace más de un factor de 4 operaciones que el algoritmo fuera de línea (vea la videoconferencia del MIT como prueba).

Pronto discutiremos la implementación y la prueba del análisis dado en la video conferencia.

Referencias:
http://en.wikipedia.org/wiki/Self-organizing_list
MIT Video Lecture
http://www.eecs.yorku.ca/course_archive/2003-04/F/2011/2011A/DatStr_071_SOLists.pdf
http:/ /en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm)

Este artículo ha sido compilado por Abhay Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.