¿Qué ajustes de estructura de datos de lista vinculada me darían una búsqueda aleatoria rápida?

Question

Actualmente estoy usando una lista doblemente vinculada (C ++ std::list) para mantener un montón de registros que tienen un identificador entero único. La lista vinculada se crea en orden ordenado de tal manera que en la lista, el siguiente elemento siempre tiene un identificador único más grande que su predecesor.

El problema que me enfrento es que ocasionalmente necesito poder insertar un elemento rápidamente en su posición relativa ordenada y usar una lista vinculada simple significa que esta operación es $ O (n) $ que me está causando problemas de rendimiento. En general, esto significaría que quiero usar algo como un árbol binario (C ++ std::map), sin embargo, también depende de la siguiente función de una lista doblemente vinculada para un buen rendimiento:

• Capacidad para empalmar una sección contigua de una lista vinculada a otra en $ o (1) $ tiempo. (Amortizado $ O (1) $ o $ o ( log log n) $ sería lo suficientemente bueno).

Una característica de mis datos que me gustaría aprovechar es que a menudo tengo largos rangos de registros contiguos donde el entero único de cada uno es exactamente uno más que su predecesor. Al buscar la posición clasificada relativa de un elemento, siempre estaría fuera de los registros contiguos ya que no hay identificadores duplicados.

Me gustaría encontrar una estructura de datos de reemplazo o un aumento en una lista doblemente vinculada que me permita continuar empalmando secciones enteras de una lista a otra en tiempo constante, pero me permita localizar la posición ordenada en la que insertar un nuevo registro en mejor que $ o (n) $ tiempo.

Otras operaciones incluyen iteración hacia adelante y hacia atrás en los elementos. Los índices de registro comienzan en cero y crecen hacia 64 bits, generalmente secuencialmente, y el código funciona bien en tales casos. Ocasionalmente, algunos registros no están disponibles antes de los posteriores, es la inserción de estos registros faltantes lo que causa los problemas de rendimiento ahora.

Un enfoque posible que se me ocurre es almacenar en caché la ubicación de varios índices. El caché se invalidaría cada vez que un empalme elimina elementos que podrían superponerse a las entradas en caché. Con este caché, en lugar de hacer una búsqueda lineal, la búsqueda podría comenzar desde el iterador de punto de caché cuyo índice único es el más cercano a aquel cuya posición se está buscando. Sin embargo, me gustaría utilizar más completamente la característica de los registros contiguos. También pensé en una lista jerárquica vinculada donde tengo una lista de regiones contiguas de nivel superior, donde cada región es una lista vinculada de registros que son consecutivos, pero no vi una forma limpia de adaptar una lista vinculada para proporcionar esto funcionalidad. ¿Quizás se ha hecho algo como esto antes? Encuentro que las listas de omisión están cerca, pero no veo la funcionalidad de empalme (), además de una lista genérica de omisión no aprovechar el hecho de que la inserción nunca ocurre dentro de los registros contiguos.

Answer 1

Un enfoque simple podría ser utilizar una lista doblemente vinculada de extensiones, donde cada extensión representa una secuencia de registros contiguos. Los registros dentro de cada extensión podrían representarse a su vez con una lista doblemente vinculada.

Esto conserva su capacidad de hacer $ o (1) $ $ tiempo de empalme, y ahora la operación de inserción toma $ o (k) $ tiempo, donde $ k $ es el número de extensiones (en lugar de $ o (n) $, donde $ $ n $ es el número de registros). Si tiene muchas menos extensiones que los registros, esta podría ser una mejora parcial.

No sé si esto será mejor que una simple lista de saltos o un árbol binario.

Tenga en cuenta que si usa un árbol binario, aún puede hacer un empalme eficiente. La operación de empalme ya no es $ o (1) $ tiempo, pero se puede hacer en $ o ( log ell) $ tiempo, donde $ ell $ es el número de registros en el segmento empalmado. Esto no es tan rápido como $ O (1) $ TIEMPLE -SPLIMING, pero dependiendo de la frecuencia relativa de sus diferentes operaciones, es otra estructura de datos que podría considerar (por ejemplo, comparación con los conjuntos de datos realistas).

Y, por supuesto, puede combinar estas ideas, por ejemplo, con un árbol binario de extensiones, donde cada extensión a su vez es una lista doblemente vinculada de registros contiguos. Los insertos tomarán $ o ( lg k) $ tiempo, y el empalme se puede hacer en $ o ( lg ell) $ time (los cuales podrían ser mejores que el $ o ( lg n) $ logrado a través de un Árbol binario simple).