arrays - listas - pilas y colas en java

¿Se anexa una estructura de datos que admite O(1) acceso aleatorio y el peor caso O(1)?

Question

Me doy cuenta de que una colección indexada de tamaño variable que utiliza una matriz para almacenar sus elementos (como List<T> en .NET o ArrayList en Java) tiene amortizado O (1) el tiempo de inserción al final de la colección. Pero luego siempre hay una sola inserción molesta en coyunturas críticas donde la colección acaba de alcanzar su capacidad y la siguiente inserción requiere una copia completa de todos los elementos en la matriz interna a una nueva (presumiblemente el doble).

Un error común (en mi opinión) es ir con una lista vinculada para "arreglar" este problema; pero creo que la sobrecarga de asignar un nodo para cada elemento puede ser bastante inútil, y de hecho empequeñecería el beneficio de una inserción O (1) garantizada en ese raro caso en que la inserción del arreglo es costosa, cuando, de hecho, cada dos la inserción de matriz es significativamente más barata (y más rápida).

Lo que estaba pensando podría tener sentido es un enfoque híbrido que consiste en una lista enlazada de matrices, donde cada vez que la matriz "principal" actual alcanza su capacidad, se agrega una nueva matriz dos veces mayor a la lista enlazada. Entonces no sería necesaria ninguna copia ya que la lista enlazada aún tendría la matriz original. Esencialmente, esto me parece análogo (a mí) al enfoque List<T> o ArrayList , excepto que siempre que haya incurrido en el costo de copiar todos los elementos de la matriz interna, aquí solo incurre en el costo de asignar una nueva matriz más una inserción de un solo nodo.

Por supuesto, esto complicaría otras características si fueran deseables (por ejemplo, insertar / eliminar en / de la mitad de la colección); pero como expresé en el título, realmente estoy buscando una colección de solo agregar (e iterar).

¿Hay alguna estructura de datos ideal para este propósito? O, ¿puedes pensar en uno tú mismo?

Answer 1

Cuando necesito un contenedor como ese, utilizo mi implementación de la estructura descrita en "Matrices reajustables en tiempo y espacio óptimos"

Answer 2

DE ACUERDO. Lo que ha descrito es casi exactamente lo que std::deque encuentra en la biblioteca estándar de C ++. La diferencia es que una matriz (por lo general) se usa para mantener los punteros en las sub-matrices en lugar de usar una lista vinculada.

Answer 3

Hay una hermosa estructura llamada matriz extensible que tiene la peor inserción de O (1) y O (n) sobrecarga de memoria (es decir, es asintóticamente comparable a una matriz dinámica, pero tiene O (1) inserción en el peor de los casos). El truco consiste en adoptar el enfoque que utiliza el vector (doblar y copiar), pero hacer que la copia sea floja. Por ejemplo, supongamos que tienes una matriz de cuatro elementos como este:

[1] [2] [3] [4]

Si desea agregar un número nuevo, digamos 5, comienza asignando una matriz que es el doble de grande:

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

A continuación, inserta 5 en la nueva matriz:

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [5] [ ] [ ] [ ]

Finalmente, despliegue el 4 de la matriz anterior en el nuevo:

[1] [2] [3] [ ]
[ ] [ ] [ ] [4] [5] [ ] [ ] [ ]

A partir de ahora, cada vez que haga una inserción, agregue el elemento a la nueva matriz y despliegue un elemento más de la matriz anterior. Por ejemplo, después de agregar 6, obtendríamos

[1] [2] [ ] [ ]
[ ] [ ] [3] [4] [5] [6] [ ] [ ]

Después de insertar dos valores más, terminamos aquí:

[ ] [ ] [ ] [ ]
[1] [2] [3] [4] [5] [6] [7] [8]

Si ahora necesitamos agregar un elemento más, desechamos el conjunto antiguo ahora vacío y asignamos un conjunto dos veces más grande que el conjunto actual (capaz de contener 16 elementos):

[1] [2] [3] [4] [5] [6] [7] [8]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Y repite este proceso. Al descontar el costo de una asignación de memoria (que generalmente es sublineal en el tamaño de la matriz), hace como máximo O (1) trabajo por inserción.

Las búsquedas siguen siendo O (1), ya que usted solo decide cuál de las dos matrices debe buscar, mientras que las inserciones en el medio son O (n) debido a la mezcla.

Si tiene curiosidad, tengo una implementación Java de esta estructura en mi sitio personal. No sé qué tan útil lo encontrará, pero es más que bienvenido a probarlo.

¡Espero que esto ayude!

EDITAR : Si desea invertir un poco de tiempo leyendo un trabajo de investigación y tratando de implementar una estructura de datos bastante compleja, puede obtener el mismo resultado (apéndice O (1) del peor caso) en exceso de espacio O (√n) (que por cierto es óptimo) usando las ideas de este documento. Nunca llegué a implementar esto realmente, pero ciertamente vale la pena leerlo si la memoria es un recurso muy escaso. Curiosamente, utiliza esta construcción anterior como una subrutina.

Answer 4

Una idea sería crear una lista de algunos elementos, como:

struct item
{
    int data[NUM_ITEMS];
    item *next;
}

En este caso, el inserto tomaría O(1) y si alcanzó el límite, simplemente cree un nuevo bloque y añádalo al final de su lista.