Come ricorrere rapidamente a un elenco con un solo valore modificato?

Question

Diciamo che ho un elenco di oggetti che sono ordinati da un campo specifico su quell'oggetto. Se uno degli oggetti cambia quella proprietà, la sua posizione nell'elenco ordinato dovrebbe essere aggiornata.

Quale algoritmo di ordinamento o "trucchi" potrei usare per ordinare molto rapidamente questo elenco, dato che non rientra nella selezione di un solo articolo alla volta?

La struttura dati è una matrice e ho accesso diretto all'indice dell'elemento modificato.

Sto usando Scala per questo, ma qualsiasi suggerimento o suggerimento generale sarebbe utile anche.

Answer 1

Si potrebbe fare solo un'iterazione di bubble sort: iniziare dall'inizio della lista e iterare fino a trovare l'elemento fuori servizio. Quindi spostalo nella direzione appropriata finché non cade sul posto. Questo ti darà la peggiore performance 2N.

Answer 2

Spostare l'elemento non differenziati a sinistra oa destra nella lista sembra la soluzione ottimale

Answer 3

Se la lista è ordinata, si può semplicemente rimuovere l'elemento che si sta per cambiare dalla lista, e dopo averlo cambiato, potresti inserire "binario", no? Ciò richiederebbe una media di passi log (n).

Se è possibile, passare da una matrice a una java.util.TreeMap: sia la rimozione che l'inserimento saranno operazioni log (n): che saranno più veloci dell'accesso O (1) + O (n) soluzione di inserimento utilizzando un array.

Answer 4

Rimuovere l'elemento e riaggiungerlo nella posizione corretta. IF si sta facendo solo un articolo, il tempo massimo di esecuzione è N.

Se si sta facendo più di uno, è necessario attendere fino a quando non sono stati completati e quindi ricorrere. Ma dovrai dirci molto di più sul tuo spazio problematico. Quick è controbilanciato dalla memoria e da altri fattori che dovrai determinare per scegliere l'algoritmo giusto.

Answer 5

A seconda che il nuovo valore sia maggiore o minore di quello precedente, è possibile "bollarlo" al suo posto.

La pseudo-codice sarebbe simile a questa:

if new value larger than old value 
    then if new value is larger than next value in collection 
     then swap the value with the next value 
     iterate until value is not larger than next value 
else if new value is smaller than previous value in collection 
    then swap the value with the previous value 
    iterate until value is not smaller than the previous value 

Naturalmente, un modo migliore sarebbe quella di utilizzare la ricerca binaria.

Innanzitutto, individuare il nuovo punto nella raccolta in cui dovrebbe trovarsi l'elemento. Quindi, sposta gli elementi in posizione. Se il nuovo indice spot è maggiore dell'indice spot corrente, spostate gli elementi di un elemento, altrimenti li spostate verso l'alto. Sposti gli elementi a partire dal punto che hai precedentemente occupato, a quello che vuoi occupare. Quindi memorizzi il valore nel punto che hai trovato.

Per esempio, assumere questa collezione:

a b c d e f g h i j 
10 20 30 40 50 60 70 80 90 100 

poi si desidera cambiare il valore dell'elemento f da 60 a 95.

Per prima cosa è capire dove dovrebbe essere.Utilizzando ricerca binaria, abbiamo scoperto che dovrebbe essere tra 90 e 100:

a b c d e f g h i j 
10 20 30 40 50 60 70 80 90 100 
           ^
            +- here 

Poi si sposta gli elementi dalla posizione corrente verso il basso un elemento, in questo modo:

a b c d e f g h i j 
10 20 30 40 50 60 70 80 90 100 <-- from this 
10 20 30 40 50 70 80 90 ?? 100 <-- to this 

E poi si memorizza il valore dentro ?? spazio, che ti dà questa formazione

a b c d e g h i f j 
10 20 30 40 50 70 80 90 95 100 

Answer 6

Se la lista è davvero grande e ci sono un gran numero di operazioni di aggiornamento previsto, un semplice array ad accesso casuale o una lista collegata sarà troppo lento. Se si utilizzano matrici/elenchi collegati, ciascuna operazione di aggiornamento avrà un costo O (n). Con piccoli elenchi e/o un piccolo numero di aggiornamenti questo è adeguato.

Per gli elenchi più grandi, è possibile ottenere gli aggiornamenti O (log (n)) utilizzando una struttura dati O (log (n)) ordinata (alberi AVL/RB, elenchi di capitoli, alberi di segmenti ecc.). Una semplice implementazione può comportare la rimozione dell'elemento da aggiornare, la modifica del valore e il successivo reinserimento. Molte lingue popolari hanno una sorta di struttura dati ordinata nella loro libreria (ad esempio TreeMap/TreeSet in Java, multiset/multimap in STL di C++), oppure puoi facilmente trovare un'implementazione gratuita per la tua lingua.

Answer 7

Per un array, l'inserimento di un elemento nella posizione corretta sarebbe O (n), poiché è necessario copiare gli elementi dell'array per creare spazio per un elemento aggiuntivo. È possibile trovare l'indice che è necessario inserire in uno binary search (O (log n)) o linear search (O (n)). Qualunque sia la scelta che fai, l'algoritmo nel suo complesso sarà O (n).

L'unico modo per fare questo molto rapidamente consiste nell'utilizzare una struttura dati più adatta a questa situazione: a binary search tree. Inserimento sarebbe O (log n) se l'albero rimane decentemente equilibrata (Usare un self-balancing binary search tree per garantire questo, o sperare i suoi dati non saranno inseriti in un ordine molto regolare per approssimare O (log n).)

O (log n) è via più veloce di O (n) per gli elenchi anche moderatamente grandi, quindi se si dispone di elenchi che possono essere quasi arbitrariamente grandi e davvero interessati all'ordinamento delle prestazioni, utilizzare un albero di ricerca binario.