Estructura de datos eficiente para acceso aleatorio rápido, búsqueda, inserción y eliminación

Question

Estoy buscando una estructura de datos (o estructuras) que me permita mantener una lista ordenada de enteros, sin duplicados, con índices y valores en el mismo distancia.

Necesito cuatro operaciones principales para ser eficiente, en orden aproximado de importancia:

1. tomando el valor de un índice dado
2. encontrar el índice de un valor dado
3. insertar un valor en una dado índice
4. la eliminación de un valor en un índice dado

Usando una matriz tengo 1 a O (1), pero 2 es O (N) y la inserción y las eliminaciones son costosas (O (N) también, creo).

Una lista vinculada tiene O (1) inserción y eliminación (una vez que tiene el nodo), pero 1 y 2 son O (N), por lo tanto, anula las ganancias.

He intentado mantener dos matrices a [índice] = valor yb [valor] = índice, que convierten 1 y 2 en O (1) pero convierten 3 y 4 en operaciones aún más costosas.

¿Existe una estructura de datos más adecuada para esto?

Answer 1

Yo utilizaría un red-black tree para asignar las claves a los valores. Esto le da O (log (n)) para 1, 3, 4. También mantiene las claves en orden ordenado.

Para 2, utilizaría una tabla hash para asignar valores a las claves, lo que le da un rendimiento O (1). También agrega O (1) sobrecarga para mantener actualizada la tabla hash al agregar y eliminar claves en el árbol rojo-negro.

Answer 2

¿Qué le parece usar una matriz ordenada con búsqueda binaria?

La inserción y borrado es lenta. pero dado el hecho de que los datos son enteros simples podrían optimizarse con llamadas a memcpy() si está usando C o C++. Si conoce el tamaño máximo de la matriz, puede incluso evitar cualquier asignación de memoria durante el uso de la matriz, ya que puede preasignarla al tamaño máximo.

El "mejor" enfoque depende de la cantidad de elementos que necesita almacenar y la frecuencia con la que tendrá que insertar/eliminar en comparación con la búsqueda. Si rara vez inserta o elimina una matriz ordenada con O (1), el acceso a los valores es ciertamente mejor, pero si inserta y elimina elementos con frecuencia, un árbol binario puede ser mejor que la matriz. Para un n suficientemente pequeño, la matriz probablemente sea mejor que el árbol en cualquier caso.

Si el tamaño de almacenamiento es preocupante, la matriz es mejor que los árboles, también. Los árboles también necesitan asignar memoria para cada elemento que almacenan y la sobrecarga de la asignación de memoria puede ser significativa ya que solo almacena valores pequeños (enteros).

Es posible que desee crear un perfil de lo que es más rápido, la copia de los enteros si inserta/elimina de la matriz ordenada o del árbol con sus asignaciones de memoria.

Answer 3

Howabout a Treemap? log (n) para las operaciones descritas.

Answer 4

Me gustan mucho los árboles binarios equilibrados. A veces son más lentos que las tablas hash u otras estructuras, pero son mucho más predecibles; generalmente son O(log n) para todas las operaciones. Sugeriría usar un Red-black tree o un AVL tree.

Answer 5

No sé qué idioma está utilizando, pero si se trata de Java puede aprovechar LinkedHashMap o una colección similar. Tiene todos los beneficios de una Lista y un Mapa, proporciona un tiempo constante para la mayoría de las operaciones y tiene la huella de memoria de un elefante. :)

Si no está utilizando Java, la idea de un LinkedHashMap probablemente sea aún adecuada para una estructura de datos utilizable para su problema.

Answer 6

Si está trabajando en .NET, entonces, de acuerdo a los documentos de MS http://msdn.microsoft.com/en-us/library/f7fta44c.aspx

• SortedDictionary y ambos tienen SortedList O (log n ) para la recuperación
• SortedDictionary ha O (log n ) para operaciones de inserción y eliminación, mientras que SortedList tiene O (n).

Ambos se diferencian por el uso de memoria y la velocidad de inserción/eliminación. SortedList utiliza menos memoria que SortedDictionary. Si SortedList se completa a la vez a partir de datos ordenados, es más rápido que SortedDictionary. Por lo tanto, depende de la situación en cuanto a cuál es realmente la mejor opción para usted.

Además, su argumento para la Lista vinculada no es realmente válido, ya que podría ser O (1) para la inserción, pero debe recorrer la lista para encontrar el punto de inserción, por lo que realmente no es.

Answer 7

¿Cómo conseguir 2 con árboles RB? Podemos hacer que cuenten a sus hijos con cada operación de inserción/eliminación. Esto no hace que estas operaciones duren mucho más. Luego, bajar al árbol para encontrar el elemento i-ésimo es posible en el tiempo de registro n. Pero no veo implementación de este método en java ni stl.

Answer 8

Utilice un vector para acceder a la matriz.

Utilice un mapa como índice de búsqueda del subíndice en el vector.

• dado un subíndice buscar el valor a partir del vector O (1)
• dado una llave, utilizar el mapa para encontrar el subíndice del valor. O (lnN)
• insertar un valor, empujar de vuelta en el vector O (1) amortizado, insertar el subíndice en el mapa O (lnN)
• eliminar un valor, borrar del mapa O (lnN)