Array dinamico con rimozione O (1) di qualsiasi elemento

Question

Questa domanda riguarda una struttura dati a cui ho pensato. È una matrice dinamica, come std :: vector <> in C++, tranne che l'algoritmo di rimozione è diverso.

In una matrice dinamica normale, quando un elemento viene rimosso, tutti gli elementi rimanenti devono essere spostati verso il basso, ovvero O (n), a meno che non sia l'ultimo elemento, che sarà O (1).

In questo, se qualsiasi elemento viene rimosso, viene sostituito dall'ultimo elemento. Questo ovviamente perde l'ordine degli elementi. Ma ora la rimozione di qualsiasi elemento è costante.

Un elenco avrà gli stessi tempi di rimozione, ma questa struttura ha accesso casuale. L'unico avvertimento è che non sai a cosa stai accedendo, dal momento che l'ordine potrebbe essere confuso, quindi a che cosa serve comunque l'accesso casuale. Inoltre una lista non rovinerà alcun puntatore/iteratore agli elementi.

Quindi, questa struttura sembra piuttosto inutile, tranne per il compito molto specifico di camminare rigorosamente attraverso gli elementi e forse rimuoverli lungo il percorso. Un elenco può fare lo stesso, ma questo ha prestazioni di cache migliori.

Quindi, questa struttura strana/inutile ha un nome e ha qualche utilizzo? O solo una bella piccola tempesta cerebrale?

Answer 1

Questa idea è utilizzata in Knuth (Fisher–Yates) shuffle. Un elemento scelto a caso viene sostituito con l'ultimo nell'array. Poiché ciò che vogliamo è una permutazione casuale, comunque, il riordino non ha importanza.

Answer 2

Hm, l'algoritmo ha davvero tempo di rimozione O (1)?

Ciò significherebbe che

1. Trovare l'elemento da rimuovere è O (1)
2. Trovare l'ultimo elemento (che sostituirà l'elemento cancellato) è O (1)
3. Trovare il secondo -to-last-element (il nuovo elemento "last") è O (1)

... che non è possibile in qualsiasi struttura dati che riesco a trovare. Sebbene una lista a doppio collegamento possa soddisfare tutti questi vincoli, dato che hai già un puntatore all'elemento da rimuovere.

Answer 3

Ricordo di aver usato questo metodo un sacco di volte prima. Ma non conosco un nome per questo.

Semplice esempio: in un gioco per computer che si sta iterazione tutti i "cattivi" e calcolando i loro movimenti, ecc Una cosa che può accadere a loro è quello di scomparire (il loro corpo morto finito scomparendo ed è trasparente al 99% ora) . A quel punto lo rimuovi dalla lista come fai tu, e riprendi l'iteratore senza aumentare il contatore di iterazioni.

Qualcosa di simile a questo è fatto in un Binary Heap quando si elimina un elemento, tuttavia il passo successivo è mantenere la regola di heap - O (log n).

Answer 4

Quindi, questa struttura strana/inutile ha un nome e ha qualche utilizzo?

Ho usato qualcosa di simile nelle simulazioni di sistemi multi-processo.

In un programma di pianificazione per i processi implementati come macchine di stato, ogni processo è in attesa di un evento esterno, attivo o completato. Lo scheduler ha una serie di puntatori ai processi.

Inizialmente ogni processo è attivo e lo scheduler ha l'indice dell'ultimo processo in attesa e primo completato, inizialmente zero e la lunghezza dell'array.

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

fare un passo il processo al suo stato successivo, i itera scheduler sopra la matrice e corre ogni processo, a sua volta. Se un processo segnala che è in attesa, viene scambiato con il processo dopo l'ultimo processo di attesa nell'array.

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

Se segnala che è stato completato, viene scambiato con il processo prima del primo array completato.

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

Così come piste e dei processi di pianificazione transizione da attivo in attesa o completato, l'array diventare ordinata con tutti i processi in attesa alla partenza, tutti quelli attivi nel mezzo, e quelli completati alla fine .

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

Dopo sia un certo numero di iterazioni, o quando ci sono processi più attivi, i processi completati vengono puliti dalla matrice e eventi esterni vengono elaborati:

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

Questo è simile a che sta usando lo swap per rimuovere elementi da una collezione, ma sta rimuovendo gli elementi da entrambe le estremità piuttosto e lasciando la "raccolta" nel mezzo.

Answer 5

Si chiama Set.

Answer 6

Non conosco un nome per questo, ma in alcuni casi è meglio di un elenco.

In particolare, questo sarebbe di gran lunga superiore a una lista concatenata o doppiamente collegata per dati molto piccoli. Poiché si memorizza tutto in modo contiguo, non vi è alcun overhead del puntatore in più per elemento.