Algoritmo per il rilevamento di duplicati in un set di dati che è troppo grande per essere completamente caricato in memoria

Question

Esiste una soluzione ottimale a questo problema?

Descrivere un algoritmo per la ricerca di duplicati in un file di un milione di numeri di telefono. L'algoritmo, quando è in esecuzione, avrebbe solo due megabyte di memoria disponibili, il che significa che non è possibile caricare tutti i numeri di telefono in memoria contemporaneamente.

La mia soluzione "ingenua" sarebbe una soluzione O (n^2) che esegue l'iterazione dei valori e carica semplicemente il file in blocchi anziché in una volta sola.

Per i = 0 a 999.999

string currentVal = get the item at index i 

for j = i+1 to 999,999 
    if (j - i mod fileChunkSize == 0) 
    load file chunk into array 
    if data[j] == currentVal 
    add currentVal to duplicateList and exit for 

Ci deve essere un altro scenario dove si può caricare l'intero set di dati in un modo davvero unico e di verificare se un numero è duplicato. Qualcuno ne ha uno?

Answer 1

Se è possibile memorizzare file temporanei, è possibile caricare il file in blocchi, ordinare ogni blocco, scriverlo in un file e quindi scorrere tra i blocchi e cercare i duplicati. Puoi facilmente capire se un numero è duplicato confrontandolo con il numero successivo nel file e il numero successivo in ciascuno dei blocchi. Quindi passa al numero più basso successivo di tutti i blocchi e ripeti fino a quando non finisci i numeri.

Il runtime è O (n log n) a causa dell'ordinamento.

Answer 2

Dividere il file in blocchi M, ognuno dei quali è abbastanza grande da essere ordinato in memoria. Ordinali in memoria

Per ogni set di due pezzi, saremo quindi effettuare l'ultimo passo di Mergesort su due pezzi per fare un pezzo più grande (c_1 + c_2) (+ C_3 c_4) .. (c_m c_m-1 +)

Punta al primo elemento su c_1 e c_2 su disco e crea un nuovo file (lo chiameremo c_1 + 2).

se l'elemento point-to di c_1 è un numero inferiore rispetto all'elemento point-to di c_2, copiarlo in c_1 + 2 e puntare all'elemento successivo di c_1.
Altrimenti, copia l'elemento puntato di c_2 in e punta all'elemento successivo di c_2.

Ripetere il passaggio precedente finché entrambi gli array non sono vuoti. Hai solo bisogno di usare lo spazio nella memoria necessaria per contenere i due numeri a punta. Durante questo processo, se incontri c_1 e c_2 a parità di elementi puntati, hai trovato un duplicato - puoi copiarlo due volte e incrementare entrambi i puntatori.

Gli array m/2 risultanti possono essere ricombinati in modo ricorsivo nello stesso modo - prenderà log (m) di questi passaggi di unione per generare l'array corretto. Ogni numero verrà confrontato tra loro in modo tale da trovare i duplicati.

In alternativa, una soluzione rapida e sporca, come accennato da @Evgeny Kluev, è creare un filtro di fioritura che sia il più ampio possibile in memoria. È quindi possibile creare un elenco dell'indice di ciascun elemento che non riesce a filtrare e ripetere il ciclo del file una seconda volta per testare questi membri per la duplicazione.

Answer 3

Mi piace la soluzione di @airza, ma forse c'è un altro algoritmo da considerare: forse un milione di numeri di telefono non possono essere caricati in memoria in una volta perché sono espressi in modo inefficiente, cioè utilizzando più byte per numero di telefono del necessario.In tal caso, potresti essere in grado di avere una soluzione efficiente tagliando i numeri di telefono e memorizzando gli hash in una tabella (hash). Le tabelle hash supportano le operazioni del dizionario (come in) che consentono di trovare facilmente i duplicati.

Per essere più concreti, se ogni numero di telefono è di 13 byte (ad esempio una stringa nel formato (NNN)NNN-NNNN), la stringa rappresenta uno dei miliardi di numeri. Come numero intero, questo può essere memorizzato in 4 byte (anziché 13 nel formato stringa). Potremmo quindi essere in grado di memorizzare questo "hash" a 4 byte in una tabella hash, perché ora i nostri numeri di hash da 1 miliardo occupano lo spazio di 308 milioni di numeri, non un miliardo. Escludere numeri impossibili (tutto nei prefissi telefonici 000, 555, ecc.) Potrebbe consentire di ridurre ulteriormente la dimensione dell'hash.

Answer 4

Credo che la soluzione di Airza si sta dirigendo verso una buona direzione, ma dal momento che l'ordinamento non è ciò che si vuole, ed è più costoso è possibile effettuare le seguenti operazioni da combinare con l'approccio di angelatlarge:

prendere un pezzo C che si adatta nella memoria della taglia M/2.

Prendi il pezzo C _i

1. Scorrere _i e patate ogni elemento in un hash-table. Se l'elemento esiste già, sai che è un duplicato e puoi contrassegnarlo come duplicato. (aggiungi il suo indice in una matrice o qualcosa del genere).

2. Ottieni il blocco successivo C _{i + 1} e verifica se esiste già una chiave nella tabella hash. Se esiste un elemento, contrassegnarlo per la cancellazione.

3. Ripetere con tutti i pezzi fino a quando si sa che non contengono duplicati dal pezzo C _i

4. Ripetere i passaggi 1,2 con pezzo C _{i + 1}

5. eliminati tutti gli elementi contrassegnato per la cancellazione (potrebbe essere fatto durante, qualunque sia più appropriato, potrebbe essere più costoso eliminarne uno alla volta se devi spostare tutto il resto).

Viene eseguito in O ((N/M) * | C |), dove | C | è la dimensione del blocco. Nota che se M> 2N, allora abbiamo solo un pezzo, e questo viene eseguito in O (N), che è ottimale per l'eliminazione dei duplicati. Semplicemente li cancelliamo e ci assicuriamo che tutte le collisioni siano cancellate.

Modifica: Per richiesto, sto fornendo dettagli: * N è il numero di telefono.

• La dimensione del blocco dipenderà dalla memoria, dovrebbe essere della dimensione M/2. Questa è la dimensione della memoria che caricherà un blocco del file, poiché l'intero file è troppo grande per essere caricato in memoria.

• Questo lascia un altro M/2 byte per mantenere la tabella di hash , e/o un elenco duplicato .

• Quindi, devono essere presenti blocchi N/(M/2), ciascuno della dimensione | C | = M/2

• Il tempo di esecuzione sarà il numero di blocchi (N/(M/2)), moltiplicato per le dimensioni di ogni blocco | C | (o M/2). Nel complesso, questo dovrebbe essere lineare (più o meno l'overhead di cambiare da un pezzo all'altro, che è il motivo per cui il modo migliore per descriverlo è O ((N/M) * | C |)

. una Caricamento di un pezzo C _iO. (| C |).
b iterare ogni elemento, prova e impostare se non ci O (1) saranno hashing in cui inserimento e ricerca dovrebbero prendere.
c. Se l'elemento è già presente, è possibile eliminarlo.
d. Ottenere il prossimo ch Lo Zio, sciacquare e ripetere (pezzi 2N/M, quindi O (N/M))

Rimozione di un elemento potrebbe costare O (N), a meno che non teniamo una lista e rimuoverli tutti in una volta , evitando di spostare tutti gli elementi rimanenti ogni volta che viene rimosso un elemento.

Se i numeri di telefono possono essere rappresentati come un intero -1, possiamo evitare di avere un hash-table pieno e basta usare una mappa di bandiera, risparmiando mucchi di memoria (ce la faremo solo bisogno di N-bit di memoria)

Ecco un pseudo-codice in qualche modo dettagliato:

void DeleteDuplicate(File file, int numberOfPhones, int maxMemory) 
{ 
    //Assume each 1'000'000 number of phones that fit in 32-bits. 
    //Assume 2MB of memory 
    //Assume that arrays of bool are coalesced into 8 bools per byte instead of 1 bool per byte 
    int chunkSize = maxMemory/2; // 2MB/2/4-byes per int = 1MB or 256K integers 

    //numberOfPhones-bits. C++ vector<bool> for example would be space efficient 
    // Coalesced-size ~= 122KB | Non-Coalesced-size (worst-case) ~= 977KB 
    bool[] exists = new bool[numberOfPhones]; 

    byte[] numberData = new byte[chunkSize]; 
    int fileIndex = 0; 
    int bytesLoaded; 
    do //O(chunkNumber) 
    { 
     bytesLoaded = file.GetNextByes(chunkSize, /*out*/ numberData); 
     List<int> toRemove = new List<int>(); //we still got some 30KB-odd to spare, enough for some 6 thousand-odd duplicates that could be found 

     for (int ii = 0; ii < bytesLoaded; ii += 4)//O(chunkSize) 
     { 
      int phone = BytesToInt(numberData, ii); 
      if (exists[phone]) 
       toRemove.push(ii); 
      else 
       exists[phone] = true; 
     } 

     for (int ii = toRemove.Length - 1; ii >= 0; --ii) 
      numberData.removeAt(toRemove[ii], 4); 

     File.Write(fileIndex, numberData); 
     fileIndex += bytesLoaded; 

    } while (bytesLoaded > 0); // while still stuff to load 
}