Las estructuras de datos: ¿Qué debo usar para estas condiciones?

Question

Esto no debería ser una cuestión difícil, pero me gustaría simplemente como alguien a rebotar fuera de antes de continuar. Simplemente necesito para decidir qué estructura de datos a utilizar en base a estas actividades que se espera:

1. ¿Se necesita con frecuencia iterar en forma ordenada (comenzando en la cabeza).
2. tendrá que eliminar / restaurar elementos arbitrarios de la / una vista ordenada.
3. Más tarde voy a estar recurriendo con frecuencia los datos y trabajar con múltiples vistas ordenadas.
4. También más adelante voy a estar con frecuencia cambiando la posición de los elementos dentro de sus puntos de vista ordenados.

Esto es en Java, por cierto.

Mi mejor conjetura es que yo tampoco le rodadura alguna costumbre Vinculado Hash Conjunto (para organizar los vínculos en el orden establecido) o, posiblemente, sólo usando un conjunto de árbol. Pero todavía no estoy completamente seguro todavía. Recomendaciones?

Editar:? supongo que debido a la arbitraria remove / restauración, probablemente debería seguir con un conjunto de árbol, a la derecha

En realidad, no necesariamente. Hmmm ...

Answer 1

En teoría, yo diría que la estructura de datos adecuada es un árbol de múltiples - de preferencia algo como un árbol B +. Tradicionalmente, esta es una estructura de datos basada en disco, pero la memoria principal moderna tiene un montón de características similares debido a las capas de la memoria caché y la memoria virtual.

Dentro de la orden de iteración de un árbol B + es muy eficiente debido a que (1) sólo iterar a través de la lista enlazada de nodos hoja -. Rama no son necesarios los nodos, y (2) se obtiene muy buena localidad

Finding, la eliminación y la inserción de elementos arbitrarios es log (n) como con cualquier árbol equilibrado, aunque con diferentes factores constantes.

El recurso dentro del árbol es sobre todo una cuestión de elegir un algoritmo que da un buen rendimiento cuando se opera en una lista enlazada de bloques (los nodos hoja), minimizando la necesidad de nodos hoja de uso - Variantes de clasificación rápida o mergesort parecer como posibles candidatos . Una vez que los elementos se ordenan en los nodos rama, simplemente propagar la parte posterior resumen de información a través de los nodos hoja.

y - pragmática, esto es sólo algo que haría si estás muy seguro de que lo necesite. Las probabilidades son buenas que es mejor usar algún contenedor estándar. algoritmo de optimización de la estructura / datos es el mejor tipo de optimización, pero todavía puede ser prematuro.

Answer 2

Estándar LinkedHashSet o LinkedMultiset de colecciones de Google si desea que su estructura de datos para almacenar los valores no únicos.