Arreglo dinámico con O (1) eliminación de cualquier elemento

Question

Esta pregunta es sobre una estructura de datos en la que pensé. Es una matriz dinámica, como std :: vector <> en C++, excepto que el algoritmo de eliminación es diferente.

En una matriz dinámica normal, cuando se elimina un elemento, todos los elementos restantes deben desplazarse hacia abajo, que es O (n), a menos que sea el último elemento, que será O (1).

En este caso, si se elimina algún elemento, se reemplaza por el último elemento. Esto, por supuesto, pierde el orden de los elementos. Pero ahora la eliminación de cualquier elemento es un tiempo constante.

Una lista tendrá los mismos tiempos de eliminación, pero esta estructura tiene acceso aleatorio. La única advertencia es que no sabes a qué estás accediendo, ya que el orden puede ser complicado, así que de todos modos el uso es de acceso aleatorio. Además, una lista no confundirá ningún puntero/iterador con elementos.

Así que, esta estructura parece bastante inútil a excepción de la tarea muy específica de caminar estrictamente a través de los elementos y tal vez eliminarlos en el camino. Una lista puede hacer lo mismo, pero esto tiene un mejor rendimiento de caché.

Entonces, ¿esta estructura extraña/inútil tiene un nombre, y tiene algún uso? ¿O solo una pequeña tormenta cerebral?

Answer 1

Esta idea se utiliza en Knuth (Fisher–Yates) shuffle. Un elemento elegido al azar se reemplaza con el último en la matriz. Como lo que queremos es una permutación aleatoria de todos modos, el reordenamiento no importa.

Answer 2

Hm, ¿ese algoritmo realmente tiene O (1) tiempo de eliminación?

Eso significaría que

1. Encontrar el elemento a eliminar es O (1)
2. Encontrar el último elemento (que sustituirá al elemento suprimido) es O (1)
3. Encontrar el segundo -al último elemento (el nuevo "último" elemento) es O (1)

... que no es posible en ninguna estructura de datos que se me ocurra. Aunque una lista de doble enlace podría cumplir estas restricciones, dado que ya tiene un puntero al elemento para eliminar.

Answer 3

Recuerdo haber usado este método muchas veces antes. Pero no sé un nombre para eso.

Ejemplo simple: estás iterando a todos los "tipos malos" y calculando sus movimientos, etc. Una cosa que les puede pasar es desaparecer (su cuerpo muerto terminó desapareciendo y ahora es 99% transparente) . En ese punto lo eliminará de la lista como lo hace, y reanudará el iterador sin aumentar el contador de iteraciones.

Algo similar a esto se hace en un Binary Heap al eliminar un elemento; sin embargo, el siguiente paso es mantener la regla del montón: O (log n).

Answer 4

Entonces, ¿esta estructura extraña/inútil tiene un nombre, y tiene algún uso?

He usado algo similar en las simulaciones de sistemas multiproceso.

En un programador para procesos implementados como máquinas de estado, cada proceso está esperando un evento externo, activo o completado. El planificador tiene una matriz de punteros a los procesos.

Inicialmente, cada proceso está activo, y el planificador tiene el índice de la última espera y el primer proceso completado, inicialmente cero y la longitud de la matriz.

V-- waiting 
[ A-active, B-active, C-active, D-active ] 
          completed --^ 
^- run 

Para paso, el proceso a su siguiente estado, los itera planificador sobre la matriz y se ejecuta cada proceso a su vez. Si un proceso informa que está esperando, se intercambia con el proceso después del último proceso de espera en la matriz.

  V-- waiting 
[ A-waiting, B-active, C-active, D-active ] 
           completed --^ 
      ^- run 

Si informa que se ha completado, se intercambia con el proceso antes de la primera matriz completa.

  V-- waiting 
[ A-waiting, D-active, C-active, B-completed ] 
        completed --^ 
      ^- run 

Así como carreras y procesos del planificador de transición de activo a la espera o completado, la matriz convertido ordenada con todos los procesos en espera en el inicio, todos los activos en el medio, y los terminados los al final .

     V-- waiting 
[ A-waiting, C-waiting, D-active, B-completed ] 
        completed --^ 
         ^- run 

Después de cualquiera de un cierto número de iteraciones, o cuando hay procesos no más activos, los procesos completados se limpian fuera de la matriz y los acontecimientos externos se procesan:

     V-- waiting 
[ A-waiting, C-waiting, D-completed, B-completed ] 
      completed --^ 
         ^- run == completed so stop 

Esto es similar en que está utilizando el intercambio para eliminar elementos de una colección, pero está eliminando elementos de ambos extremos y dejando la 'colección' en el medio.

Answer 5

Se llama Set.

Answer 6

No se el nombre, pero en algunos casos es mejor que una lista.

En particular, esto sería muy superior a una lista simple o doblemente vinculada para datos muy pequeños. Debido a que almacena todo de manera contigua, no hay una sobrecarga de puntero adicional por elemento.