C'è un modo per aggiungere elementi unici a un array senza fare un sacco di confronti?

Question

C'è un modo per aggiungere elementi unici a un array senza fare un sacco di confronti?

#1 da (14 voti)
#2 da (6 voti)
#3 da (4 voti)

3

Per favore, spogliati con me, voglio che questo sia il più indipendente possibile dal linguaggio delle lingue con cui lavoro (una delle quali è un linguaggio chiamato PowerOn). Tuttavia, la maggior parte dei linguang supporta i loop e gli array.

Dire che ho il seguente elenco in un aray:

0x  0  Foo
1x  1  Bar
2x  0  Widget
3x  1  Whatsit
4x  0  Foo
5x  1  Bar

Qualsiasi cosa con un 1 dovrebbe essere aggiunta univocamente a un altro array con il seguente risultato:

0x  1  Bar
1x  1  Whatsit

Ricorda che questo è un esempio molto elementare. In realtà, ho a che fare con decine di migliaia di elementi sulla vecchia lista. Ecco cosa ho finora.

Pseudo codice:

For each element in oldlist
 For each element in newlist
  Compare
  If values oldlist.element equals newlist.element, break new list loop
  If reached end of newlist with with nothing equal from oldlist, add value from old list to new list
 End
End

C'è un modo migliore per farlo? Algoritmicamente, c'è spazio per miglioramenti? E come bonus qeustion, qual è la notazione O per questo tipo di algoritmo (se ce n'è uno)?

loops array algorithms

posta Chad Harrison 01.11.2012 - 16:02

fonte

3 risposte

14

Sì, si chiama tabella hash o mappa - non so se la tua lingua li ha incorporati ma è facile codificare. Questo ti permette di verificare se una voce è già presente nello stesso tempo, indipendentemente da quanto è grande l'elenco (quasi).

Se è necessario conservare l'ordine, si utilizzerà una lista collegata ordinata. Quindi è facile trovare (cercando) se la voce è nuova e un elenco collegato ti consente di inserirlo senza spostare tutte le altre voci.

risposta data 01.11.2012 - 16:03

fonte

4

Organizza il secondo array come albero binario . È più semplice dell'implementazione di una tabella hash e verrà eseguito in tempo O (n log n).

risposta data 01.11.2012 - 17:54

fonte

Leggi altre domande sui tag loops array algorithms

Un sacco di classi con un solo metodo statico con lo stesso nome della classe - Codice odore? [duplicare] Confusione GPL! Posso vendere un prodotto con componenti coperti GPL senza rendere disponibile la fonte?

score 6 · Accepted Answer

Se mantieni il newlist ordinato, puoi utilizzare la ricerca binaria per determinare se esiste un duplicato. Questo farà la differenza quando il tuo newlist inizia a diventare grande, quindi se non si allunga mai più di (diciamo) 64 voci potresti non notare alcun miglioramento. Potrebbe anche non funzionare se è costoso inserirlo nel mezzo di un array: il passaggio di tutti gli elementi potrebbe farti risparmiare molto tempo. Potresti mitigarlo in qualche modo mantenendo più elenchi, magari la tua lista di partenza e un elenco separato degli elementi che hai aggiunto. Dovrai cercarli separatamente ma con la ricerca binaria che dovrebbe essere gestibile. Quindi, una volta terminati i loop, unisci i nuovi elementi nella seconda lista.

Un altro miglioramento potrebbe essere quello di attraversare il oldlist dopo aver inserito un nuovo valore in newlist e rimosso eventuali duplicati. Difficile a dirsi, però, senza sapere nulla sui dati.