Come gestire un ampio elenco di numeri distinti

-2

Ho una lista di circa 2 miliardi di numeri distinti memorizzati in memoria per alcuni calcoli. Attualmente, ogni volta che ho bisogno di aggiungere una nuova voce devo cercare l'intero elenco per un potenziale duplicato.

Ho 18 cifre, 2 miliardi di numeri da conservare in memoria. Alcuni dei numeri sono ripetuti. Quindi, voglio caricare il nuovo numero nella memoria e ignorarlo se il numero esiste già. In questo momento, aggiungo il numero nell'elenco se non esiste già.

Questo processo di scansione lineare del numero già esistente richiede molto tempo. Cosa posso fare per aggirare questo problema di prestazioni?

    
posta Saurabh 26.01.2015 - 11:39
fonte

3 risposte

2

Potresti usare una tabella hash usando il numero stesso come chiave.

Ciò significa che le ricerche e gli inserimenti saranno entrambi costanti nel tempo. Se sai di avere circa due miliardi di record, puoi pre-allocare molto spazio in anticipo, quindi ridimensionare non è un problema.

    
risposta data 26.01.2015 - 23:02
fonte
1

La ricerca lineare di 2 miliardi di numeri sarà dolorosa. In media, analizzerete quasi un miliardo di numeri prima di trovare quello che volete. Anche se i numeri sono in memoria, ci vuole un po 'di tempo.

Un approccio migliore consiste nell'ordinare quei numeri mentre li carichi in memoria e quindi utilizzare un algoritmo Ricerca binaria per velocizzare trova il numero desiderato in O (log n) ora.

Non ripeterò qui l'eccellente algoritmo di Wikipedia dell'algoritmo, ma l'idea generale è di campionare il centro dell'elenco e confrontarlo con il numero che stai cercando. Se il tuo numero è più alto, puoi immediatamente scartare la metà più piccola dell'elenco e riprovare con ciò che è rimasto.

  • Il tuo primo campione potrebbe trovare il numero o eliminare 1 miliardo di numeri.
  • Il tuo secondo campione potrebbe trovare il numero o eliminare 500 milioni di numeri
  • Il tuo terzo campione potrebbe trovare il numero o ridurre la ricerca impostata su 250 milioni di numeri.

... e così via. Come puoi vedere, questo converge su una soluzione (o il numero è stato trovato o sai che non è lì) molto rapidamente. C'è un sovraccarico nell'ordinare inizialmente i numeri, ma sono le noccioline rispetto al tempo che salverete nella ricerca.

Se riesci a memorizzare i numeri sul disco ordinato, sarai anche molto più avanti al gioco.

    
risposta data 26.01.2015 - 18:26
fonte
0

Utilizza un set .

Ha molte proprietà semantiche di list , ma memorizza solo valori univoci. Per essere onesti, non sono sicuro che eseguirà ragionevolmente miliardi di elementi, ma è supportato da tabelle hash e l'ho usato con successo per creare unioni e intersezioni di insiemi con oltre 10 milioni di voci.

    
risposta data 27.01.2015 - 01:00
fonte

Leggi altre domande sui tag