Ordinamento esterno delle stringhe con vincoli di memoria, con duplicati combinati e contati, su un server critico (miliardi di nomi di file)

Il nostro server produce file come {c521c143-2a23-42ef-89d1-557915e2323a}-sign.xml nella sua cartella di registro. La prima parte è GUID; la seconda parte è il nome del modello.

Voglio contare il numero di file con lo stesso modello di nome. Ad esempio, abbiamo

 {c521c143-2a23-42ef-89d1-557915e2323a}-sign.xml {aa3718d1-98e2-4559-bab0-1c69f04eb7ec}-hero.xml {0c7a50dc-972e-4062-a60c-062a51c7b32c}-sign.xml 

Il risultato dovrebbe essere

 sign.xml,2 hero.xml,1 

I tipi totali di possibili modelli di nomi sono sconosciuti, probabilmente superano int.MaxValue .

Il numero totale di file sul server è sconosciuto, probabilmente supera int.MaxValue .

Requisiti :

Il risultato finale dovrebbe essere ordinato per modello di nome.

Il server su cui verrà eseguito lo strumento è estremamente critico. Dovremmo essere in grado di indicare l’utilizzo della memoria (MB) e il numero di file temporanei generati, se presenti, prima di eseguire lo strumento e senza conoscere alcuna caratteristica della cartella di registro.

Usiamo il linguaggio C #.

La mia idea :

  • Per i primi 5000 file, contare le occorrenze, scrivere il risultato in Group1.txt .
  • Per i secondi 5000 file, contare le occorrenze, scrivere il risultato in Group2.txt .
  • Ripeti fino a quando tutti i file sono stati elaborati. Ora abbiamo un gruppo di file di gruppo.

Quindi unisco tutti questi file di gruppo.

  Group1.txt Group2.txt Group3.txt Group4.txt \ / \ / Group1-2.txt Group3-4.txt \ / Group1-4.txt 

Group1-4.txt è il risultato finale.

Il disaccordo tra me e il mio amico è il modo in cui contiamo le occorrenze.

Suggerisco di usare il dizionario. Il modello del nome del file è la chiave. Sia la dimensione della partizione. (In questo esempio è 5000.) Quindi la complessità temporale O (m), la complessità spaziale O (m).

Il mio amico suggerisce di ordinare il modello del nome quindi conta l’occorrenza in una sola passata mentre gli stessi modelli di nomi sono tutti insieme ora. complessità temporale O (m log m), complessità spaziale O (m).

Non possiamo persuaderci a vicenda. Ragazzi, vedete qualche problema con i due metodi?

    IDK se è stato studiato l’ordinamento esterno con il conteggio dei duplicati. Ho trovato un documento del 1983 (vedi sotto). Di solito, gli algoritmi di ordinamento sono progettati e studiati con l’assunzione di oggetti di ordinamento per chiavi, quindi le chiavi duplicate hanno oggetti diversi. Potrebbe esserci della letteratura esistente su questo, ma è un problema molto interessante. Probabilmente è solo considerato un’applicazione di dizionari compatti combinata con l’ordinamento di unione esterno.

    I dizionari efficienti per memorizzare grandi quantità di stringhe in poca memoria sono un problema molto ben studiato. La maggior parte delle strutture dati utili possono includere dati ausiliari per ogni parola (nel nostro caso, un conteggio indietro).


    TL: Riepilogo DR di idee utili, dal momento che ho parlato in modo troppo dettagliato di molte cose nel corpo principale di questa risposta:

    • Confini batch quando la dimensione del dizionario raggiunge una soglia, non dopo un numero fisso di file di input. Se ci fossero molti duplicati in un gruppo di 5000 stringhe, non userai ancora molta memoria. Puoi trovare più duplicati nel primo passaggio in questo modo.

    • I lotti ordinati rendono la fusione molto più veloce. Puoi e dovresti unire molti-> uno invece di unione binaria. Usa un valore PriorityQueue per capire quale file di input ha la linea che dovresti prendere in seguito.

    • Per evitare uno spreco di memoria durante l’ordinamento delle chiavi in ​​una tabella hash, utilizzare un dizionario in grado di eseguire una traversata di chiavi in ​​ordine. (cioè ordinare al volo.) C’è SortedDictionary (basato su un albero binario). Questo interlaccia anche l’utilizzo della CPU dell’ordinamento con l’I / O in attesa di ottenere le stringhe di input.

    • Radix: ordina ciascun batch in output per primo carattere (az, non alfabetico che ordina prima di A e non alfabetico che ordina dopo z ). O qualche altra scelta di scelta che distribuisce bene le tue chiavi. Utilizza dizionari separati per ciascun bucket Radix e svuota solo il più grande in un batch quando raggiungi il limite massimo di memoria. (l’euristica di sfratto più folle di “più grande” potrebbe valerne la pena).

    • throttle I / O (specialmente durante l’unione) e verifica il carico della CPU e la memoria della memoria del sistema. Adeguare il comportamento di conseguenza per assicurarsi di non causare alcun impatto quando il server è più occupato.

    • Per i file temporanei più piccoli al costo del tempo della CPU, utilizzare una codifica con prefisso comune o forse lz4.

    • Un dizionario efficiente in termini di spazio consentirà dimensioni di batch maggiori (e quindi una finestra di individuazione dei duplicati più ampia) per lo stesso limite superiore di memoria. Un Trie (o meglio, Radix Trie ) potrebbe essere l’ideale, perché memorizza i caratteri all’interno dei nodes dell’albero, con prefissi comuni memorizzati solo una volta. I grafi aciclici orientati sono ancora più compatti (trovando ridondanza tra sottostringhe comuni che non sono prefissi). Usarne uno come dizionario è difficile ma probabilmente ansible (vedi sotto).

    • Approfitta del fatto che non è necessario eliminare alcun nodo o stringhe dell’albero finché non si svuota l’intero dizionario. Usa un array di nodes crescente e un altro char array espandibile che racchiude le stringhe dalla testa alla coda. (Utile per un Trie Radix (nodes multi-char), ma non un Trie regolare in cui ogni nodo è un singolo carattere.)

    • A seconda di come vengono distribuiti i duplicati, potresti non essere in grado di trovarne molti al primo passaggio. Ciò ha alcune implicazioni, ma in realtà non cambia il modo in cui finisci per fondere.


    Presumo che tu abbia in mente un’idea di trasversale di directory, che può fornire in modo efficiente il tuo codice con un stream di stringhe per essere univoci e conteggiati. Quindi dirò semplicemente “stringhe” o “chiavi”, per parlare degli input.

    Taglia il maggior numero ansible di caratteri non necessari (ad esempio, perdi il .xml se sono tutti .xml ).


    Potrebbe essere utile eseguire il lavoro intensivo della CPU / memoria su una macchina separata, a seconda di quale altro hardware si ha con una connessione di rete veloce al server di produzione critico.

    È ansible eseguire un semplice programma sul server che invia nomi di file su una connessione TCP a un programma in esecuzione su un’altra macchina, dove è sicuro utilizzare molta più memoria. Il programma sul server potrebbe ancora eseguire piccoli batch di dizionari e archiviarli su un filesystem remoto.


    E ora, dal momento che nessuna delle altre risposte ha messo insieme tutti i pezzi, ecco la mia risposta effettiva:

    Un limite superiore all’utilizzo della memoria è facile. Scrivi il tuo programma per utilizzare un limite di memoria costante, indipendentemente dalle dimensioni dell’input. Ingressi più grandi porteranno a più fasi di fusione, non più utilizzo della memoria in qualsiasi momento.

    La migliore stima dello spazio di archiviazione temporaneo dei file che è ansible eseguire senza guardare l’input è un limite superiore molto conservativo che presuppone che ogni stringa di input sia univoca. Hai bisogno di un modo per stimare quante stringhe di input ci saranno. (La maggior parte dei filesystem sa quanti file separati contengono, senza dover percorrere l’albero delle directory e contarli.)

    Puoi fare alcune ipotesi sulla distribuzione dei duplicati per fare una stima migliore.

    Se il numero , piuttosto che la dimensione, dei file scratch è un problema, è ansible memorizzare più batch nello stesso file di output, uno dopo l’altro. O metti le intestazioni di lunghezza all’inizio di ciascuna per consentire di saltare avanti per batch o scrivere offset di byte in un stream di dati separato. Se anche la dimensione è importante, consulta il mio paragrafo sull’utilizzo della compressione del prefisso comune in stile frcode.


    Come sottolinea Ian Mercer nella sua risposta, l’ordinamento dei lotti renderà la fusione molto più efficiente. Se non lo fai, rischi di colpire un muro dove il tuo algoritmo non può progredire, o devi fare qualcosa come caricare un batch, scansionare un altro batch per le voci che sono nel primo e riscrivere il secondo batch con rimosse solo le voci corrispondenti potenzialmente poche.

    Non ordinare i tuoi batch rende la complessità temporale del primo passaggio O (N), ma o devi ordinare in un momento successivo, o le fasi successive hanno un limite nel caso peggiore che è drammaticamente peggiore. Volete che l’output sia ordinato globalmente, quindi a parte l’approccio di RadixSort, non è ansible evitare un O (N log N) da qualche parte.

    Con una dimensione di batch limitata, sono previsti passaggi di unione O (log N), pertanto l’analisi originale ha mancato la complessità O (N log N) del proprio approccio ignorando ciò che deve accadere dopo la scrittura dei lotti di fase1.


    Le scelte progettuali appropriate cambiano molto a seconda che il nostro soffitto di memoria sia abbastanza grande da trovare molti duplicati all’interno di un lotto. Se anche una complessa struttura di dati compatta come un Trie non aiuta molto, inserire i dati in un Trie e rimuoverlo di nuovo per scrivere un batch è uno spreco di tempo della CPU.

    Se non si riesce a fare molta eliminazione dei duplicati all’interno di ogni lotto, è necessario ottimizzare per mettere insieme le chiavi di corrispondenza ansible per la fase successiva. Il primo stadio può raggruppare stringhe di input per primo byte, in un massimo di 252 file di output (non tutti i 256 valori sono caratteri di file legali) o in 27 o più file di output (alfabeto + misc) o 26 + 26 + 1 per maiuscolo / minuscolo + non alfabetico. I file temporanei possono omettere il prefisso comune di ogni stringa.

    Quindi la maggior parte di questi lotti del primo stadio dovrebbe avere una densità di duplicati molto più alta. In realtà, questa distribuzione Radix degli input nei bucket di output è utile in ogni caso, vedi sotto.

    Dovresti comunque ordinare le uscite della prima fase in blocchi, per dare alla prossima passata una finestra di ricerca duplica molto più ampia per la stessa RAM.


    Trascorrerò più tempo nel dominio in cui è ansible trovare una quantità utile di duplicati nel stream iniziale, prima di utilizzare fino a ~ 100MiB di RAM o qualsiasi altra cosa scegliamo come limite superiore.

    Ovviamente aggiungiamo stringhe a una sorta di dizionario per trovare e contare i duplicati al volo, mentre richiediamo solo spazio sufficiente per l’insieme di stringhe univoche. Memorizzare semplicemente le stringhe e poi ordinarle sarebbe significativamente meno efficiente, perché avremmo raggiunto il limite della RAM molto prima senza il rilevamento immediato del duplicato.

    Per minimizzare il lavoro di fase2, la fase1 dovrebbe trovare e contare quanti più duplicati ansible, riducendo la dimensione totale dei dati p2. Anche la riduzione della quantità di lavoro di fusione per phase2 è buona. I lotti più grandi aiutano con entrambi i fattori , quindi è molto utile avvicinarsi al limite massimo di memoria in modo sicuro in fase1. Invece di scrivere un batch dopo un numero costante di stringhe di input, fallo quando il consumo di memoria si avvicina al soffitto scelto. I duplicati vengono conteggiati e gettati via, e non richiedono spazio aggiuntivo.

    Un’alternativa alla contabilità accurata della memoria è il tracciamento delle stringhe univoche nel dizionario, che è facile (e fatto per te dall’implementazione della libreria). Accumulare la lunghezza delle stringhe aggiunte può darti una buona stima della memoria usata per memorizzare anche le stringhe. O fai solo una supposizione sulla distribuzione della lunghezza delle stringhe. Rendi la tua tabella hash delle dimensioni giuste inizialmente, in modo che non debba crescere mentre aggiungi elementi, quindi ti fermi quando è piena al 60% (fattore di carico) o qualcosa del genere.


    Una struttura dati efficiente dal punto di vista dello spazio per il dizionario aumenta la nostra finestra di ricerca dup per un dato limite di memoria. Le tabelle hash diventano estremamente inefficienti quando il loro fattore di carico è troppo alto, ma la tabella hash deve solo memorizzare i puntatori alle stringhe. È il dizionario più familiare e ha implementazioni di libreria.

    Sappiamo che vorremmo ordinare il nostro batch una volta che avremo visto un numero sufficiente di chiavi univoche, quindi potrebbe essere logico utilizzare un dizionario che può essere attraversato in ordine. Ordinare al volo ha senso perché le chiavi arriveranno lentamente , limitate dal disco IO poiché stiamo leggendo i metadati del filesystem. Uno svantaggio è se la maggior parte delle chiavi che vediamo sono duplicate, quindi stiamo facendo molte ricerche O (log batch size), piuttosto che molte ricerche O (1). Ed è più probabile che una chiave sia duplicata quando il dizionario è grande, quindi la maggior parte di queste query O (log batch) sarà con una dimensione del lotto vicino al massimo, non distribuita uniformsmente tra 0 e max. Un albero paga l’overhead O (log n) dell’ordinamento per ogni ricerca, indipendentemente dal fatto che la chiave sia o meno unica. Una tabella hash paga solo il costo di smistamento alla fine dopo aver rimosso i duplicati. Quindi per un albero è O (total_keys * log unique_keys), la tabella hash è O (unique_keys * log unique_keys) per ordinare un batch.

    Una tabella hash con fattore di carico massimo impostato su 0,75 o qualcosa potrebbe essere piuttosto densa, ma dover ordinare i KeyValuePair prima di scrivere un batch probabilmente mette un freno all’utilizzo del dizionario standard. Non hai bisogno di copie delle stringhe, ma probabilmente finirai per copiare tutti i puntatori (refs) per liberare spazio per un ordinamento non sul posto, e forse anche quando li tiri fuori dalla tabella hash prima di ordinare. (O invece dei soli puntatori, KeyValuePair, per evitare di dover tornare indietro e cercare ogni stringa nella tabella hash). Se i picchi di grandi quantità di memoria sono tollerabili e non ti permettono di scambiare / pagina su disco, potresti stare bene. Ciò è evitabile se è ansible eseguire un ordinamento sul posto nel buffer utilizzato dalla tabella hash, ma dubito che ciò possa accadere con i contenitori della libreria standard.

    Un stream costante di utilizzo della CPU per mantenere il dizionario ordinato con le chiavi di velocità è disponibile è probabilmente meglio di scoppi infrequenti dell’utilizzo della CPU per ordinare tutte le chiavi di un batch, oltre allo spreco di consumo di memoria.

    La libreria standard .NET ha SortedDictionary , che i documenti dicono è implementato con un albero binario. Non ho verificato se ha una funzione di ribilanciamento o utilizza un albero rosso-nero per garantire le prestazioni peggiori di O (log n). Non sono sicuro di quanta memoria ci sarebbe. Se si tratta di un’attività unica, ti consiglio assolutamente di utilizzarla per implementarla in modo rapido e semplice. E anche per una prima versione di un design più ottimizzato per l’uso ripetuto. Probabilmente troverai che è abbastanza buono, a meno che tu non riesca a trovare una buona implementazione della libreria di Tries.


    Strutture dati per dizionari ordinati efficienti per la memoria

    Più il dizionario è efficiente per la memoria, più sono i duplicati che possiamo trovare prima di dover scrivere un batch ed eliminare il dizionario. Inoltre, se si tratta di un dizionario ordinato, tanto più grandi possono essere i nostri lotti anche quando non riescono a trovare duplicati.

    Un impatto secondario della scelta della struttura dati è la quantità di traffico di memoria che generiamo durante l’esecuzione sul server critico. Un array ordinato (con O (log n) tempo di ricerca (ricerca binaria) e O (n) inserire il tempo (shuffle elementi per fare spazio)) sarebbe compatto. Tuttavia, non sarebbe solo lento, saturerebbe la larghezza di banda della memoria con memmove per un sacco di tempo. L’utilizzo del 100% della CPU in questo modo avrebbe un impatto maggiore sulle prestazioni del server rispetto al 100% di utilizzo della CPU nella ricerca di un albero binario. Non sa dove caricare il prossimo nodo finché non viene caricato il nodo corrente, quindi non può pipeline richieste di memoria. I succursali errati del ramo dei confronti nella ricerca ad albero aiutano anche a moderare il consumo della larghezza di banda di memoria condivisa da tutti i core. (Esatto, alcuni programmi di utilizzo del 100% -CPU sono peggiori di altri!)

    È bello se svuotare il nostro dizionario non lascia frammenti di memoria quando lo svuotiamo. I nodes dell’albero avranno dimensioni costanti, quindi, un gruppo di fori sparsi sarà utilizzabile per le future allocazioni dei nodes dell’albero. Tuttavia, se disponiamo di dizionari separati per più bucket radix (vedi sotto), le stringhe di tasti associate ad altri dizionari potrebbero essere combinate con i nodes dell’albero. Ciò potrebbe portare a un malloc che fatica a riutilizzare tutta la memoria liberata, aumentando potenzialmente l’effettivo utilizzo della memoria visibile del sistema operativo con un piccolo fattore. (A meno che C # runtime garbage collection non compatta, nel qual caso si prende cura della frammentazione.)

    Dal momento che non è necessario eliminare i nodes finché non si desidera svuotare il dizionario ed eliminarli tutti, è ansible memorizzare i nodes Tree in un array che può essere ingrandito. Pertanto, la gestione della memoria deve solo tenere traccia di una grande allocazione, riducendo l’overhead della contabilità rispetto al malloc di ciascun nodo separatamente. Invece dei puntatori reali, i puntatori figlio sinistro / destro potrebbero essere indici di array. Questo ti permette di usare solo 16 o 24 bit per loro. (Un Heap è un altro tipo di albero binario memorizzato in un array, ma non può essere utilizzato in modo efficiente come un dizionario: è un albero, ma non un albero di ricerca ).

    La memorizzazione delle chiavi di stringa per un dizionario dovrebbe essere normalmente eseguita con ogni stringa come object allocato separatamente, con i puntatori ad essi in una matrice. Dato che, ancora una volta, non è necessario eliminarlo, ingrandirlo o modificarne uno fino a quando non si è pronti a eliminarli tutti, è ansible impacchettarli in un array di caratteri, con un byte zero terminante alla fine di ciascuno. Questo salva di nuovo un sacco di contabilità, e rende anche facile tenere traccia di quanta memoria è in uso per le stringhe di tasti, consentendoti di avvicinarti in sicurezza al limite superiore della memoria scelta.

    Trie / DAWG per una memoria ancora più compatta

    Per una memorizzazione ancora più densa di un set di stringhe, possiamo eliminare la ridondanza di memorizzazione di tutti i caratteri di ogni stringa, poiché probabilmente ci sono molti prefissi comuni.

    Un Trie memorizza le stringhe nella struttura ad albero, fornendo una compressione con prefisso comune. Può essere attraversato in ordine, quindi ordina al volo. Ogni nodo ha tanti figli quanti sono i successivi caratteri nell’insieme, quindi non è un albero binario. L’implementazione parziale di AC # Trie (cancellare non scritta) può essere trovata in questa risposta SO , ad una domanda simile a questa, ma che non richiede il batching / l’ordinamento esterno.

    I nodes Trie devono memorizzare potenzialmente molti indicatori figli, quindi ogni nodo può essere grande. O ogni nodo potrebbe essere di dimensioni variabili, tenendo la lista di nextchar: coppie di ref all’interno del nodo, se C # rende ansible ciò. O come dice l’articolo di Wikipedia, un nodo può essere effettivamente un elenco di link o un albero di ricerca binario, per evitare di sprecare spazio nei nodes con pochi bambini. (I livelli inferiori di un albero ne avranno molto.) I marcatori / nodes di fine parola sono necessari per distinguere tra sottostringhe che non sono voci di dizionario separate e quelle che sono. Il nostro campo di conteggio può servire a questo scopo. Conteggio = 0 significa che la sottostringa che termina qui non è nel dizionario. contare> = 0 significa che lo è.

    Un Trie più compatto è Radix Tree o PATRICIA Tree , che memorizza più caratteri per nodo.

    Un’altra estensione di questa idea è l’ automa dello stato finito aciclico deterministico (DAFSA) , a volte chiamato DAWG (Directed Acyclic Word Graph), ma si noti che l’ articolo wikipedia DAWG tratta di una cosa diversa con lo stesso nome. Non sono sicuro che un DAWG possa essere percorso in ordine per ottenere tutte le chiavi alla fine e, come indicato da wikipedia, la memorizzazione dei dati associati (come un conteggio duplicato) richiede una modifica. Inoltre, non sono sicuro che possano essere creati in modo incrementale, ma penso che tu possa fare ricerche senza essere compattato. Le nuove voci aggiunte verranno memorizzate come un Trie, fino a quando un passo di compattazione ogni 128 nuove chiavi le unirà nel DAWG. (Oppure esegui la compattazione meno frequentemente per i DAWG più grandi, quindi non lo fai troppo, come raddoppiare la dimensione di una tabella hash quando deve crescere, invece di crescere linearmente, per ammortizzare l’operazione costosa).

    È ansible rendere un DAWG più compatto memorizzando più caratteri in un singolo nodo quando non ci sono branching / convergenti. Questa pagina menziona anche un approccio di codifica Huffman ai DAWG compatti, e ha altri collegamenti e citazioni di articoli.

    L’implementazione DAWG di JohnPaul Adamovsky (in C) sembra buona e descrive alcune ottimizzazioni che utilizza. Non ho guardato attentamente per vedere se è in grado di mappare le stringhe ai conteggi. È ottimizzato per memorizzare tutti i nodes in un array.

    Questa risposta alle parole di conteggio dup in 1 TB di domande di testo suggerisce DAWG e ha un paio di collegamenti, ma non sono sicuro di quanto sia utile.


    Scrittura batch: Radice sul primo carattere

    Potresti avere il tuo RadixSort acceso e tenere separati dizionari per ogni carattere di partenza (o per az, non alfabetico che ordina prima di un, non alfabetico che ordina dopo z). Ogni dizionario scrive su un diverso file temporaneo. Se disponi di più nodes di calcolo disponibili per un approccio MapReduce, questo sarebbe il modo per distribuire il lavoro di unione ai nodes di calcolo.

    Ciò consente una modifica interessante: invece di scrivere tutti i bucket radix in una sola volta, scrivi solo il dizionario più grande come batch . Questo impedisce che piccoli lotti entrino in alcuni secchi ogni volta che lo fai. Ciò ridurrà la larghezza della fusione all’interno di ciascun bucket, accelerando la fase2.

    Con un albero binario, questo riduce la profondità di ogni albero di circa log2 (num_buckets), velocizzando le ricerche. Con un Trie, questo è ridondante ( ogni nodo usa il prossimo carattere come una radice per ordinare gli alberi figli). Con un DAWG, questo in realtà fa male alla tua efficienza spaziale perché perdi la ricerca della ridondanza tra stringhe con avviamenti diversi ma parti condivise in seguito.

    Questo ha il potenziale di comportarsi male se ci sono alcuni secchi raramente toccati che continuano a crescere, ma di solito non sono i più grandi. Potrebbero utilizzare una grande parte della memoria totale, creando piccoli lotti dalle benne usate di solito. È ansible implementare un algoritmo di sfratto più intelligente che registra quando un bucket (dizionario) è stato svuotato l’ultima volta. Il punteggio NeedsEmptying per un bucket sarebbe qualcosa come un prodotto di dimensioni ed età. O forse qualche funzione dell’età, come sqrt (età). Sarebbe anche utile un modo per registrare quanti duplicati trovati da ciascun bucket dall’ultima svuotamento. Se ti trovi in ​​una posizione nel stream di input in cui ci sono molte ripetizioni per uno dei bucket, l’ultima cosa che vuoi fare è svuotare frequentemente. Forse ogni volta che trovi un duplicato in un bucket, incrementa un contatore. Guarda il rapporto tra età e dups trovati. Le benne a basso consumo che si trovano lì, portando via la RAM dagli altri secchi, saranno facili da trovare in quel modo, quando le loro dimensioni inizieranno a salire. I bucket di valore reale potrebbero essere mantenuti anche quando sono i più grandi attuali, se stanno trovando molti duplicati.

    Se le strutture dati per il rilevamento dell’età e dei duplicati rilevati sono strutture di array, la (last_emptied[bucket] - current_pos) / (float)dups_found[bucket] può essere eseguita in modo efficiente con virgola mobile vettoriale. Una divisione intera è più lenta di una divisione FP. Una divisione FP ha la stessa velocità delle 4 divisioni FP, e si spera che i compilatori si auto-vettorizzino se si rende facile per loro come questo.

    C’è molto lavoro da fare tra il riempimento dei secchi, quindi la divisione sarebbe un piccolo singhiozzo a meno che non si utilizzino molti secchi.

    scegliere come secchio

    Con un buon algoritmo di sfratto, una scelta ideale di bucketing metterà chiavi che raramente hanno duplicati insieme in alcuni bucket e bucket che hanno molti duplicati insieme in altri bucket. Se sei a conoscenza di eventuali pattern nei tuoi dati, questo sarebbe un modo per sfruttarli. Avere dei bucket che sono per lo più low-dup significa che tutte quelle chiavi univoche non cancellano le preziose chiavi in ​​un batch di output. Un algoritmo di sfratto che osserva quanto è stato prezioso un bucket in termini di duplicati trovati per chiave univoca determinerà automaticamente quali bucket sono preziosi e vale la pena tenere, anche se le loro dimensioni stanno aumentando.

    Ci sono molti modi per radiare le tue corde in secchi. Alcuni faranno in modo che ogni elemento in un bucket paragoni meno di ogni elemento in ogni bucket successivo, quindi produrre output completamente ordinati è facile. Alcuni non lo faranno, ma hanno altri vantaggi. Ci saranno dei compromessi tra le scelte di bucketing, tutte dipendenti dai dati:

    • bravo a trovare molti duplicati nel primo passaggio (ad esempio separando i modelli high-dup dai pattern low-dup)
    • distribuisce il numero di batch in modo uniforms tra i bucket (quindi nessun bucket ha un numero enorme di batch che richiedono un’unione multistadio in fase2) e forse altri fattori.
    • produce cattivo comportamento quando combinato con l’algoritmo di sfratto sul tuo set di dati.
    • quantità di fusione tra bucket necessaria per produrre output ordinati globalmente. L’importanza di questo ridimensiona con il numero totale di stringhe univoche, non il numero di stringhe di input.

    Sono sicuro che le persone intelligenti hanno pensato a dei buoni modi per stringere le stringhe prima di me, quindi probabilmente vale la pena cercarlo se l’approccio ovvio del primo carattere non è l’ideale. Questo caso d’uso speciale (dell’ordinamento eliminando / contando i duplicati) non è tipico. Penso che la maggior parte del lavoro sull’ordinamento consideri solo i tipi che conservano i duplicati. Quindi potresti non trovare molto che aiuti a scegliere un buon algoritmo di bucketing per un ordinamento esterno di conteggio dup. In ogni caso, dipenderà dai dati.

    Alcune opzioni concrete per il bucketing sono: Radix = primi due byte insieme (combinando ancora lettere maiuscole / minuscole e combinazione di caratteri non alfabetici). O Radice = il primo byte del codice hash. (Richiede un’unione globale per produrre l’output ordinato). O Radice = (str[0]>>2) < < 6 + str[1]>>2 . vale a dire ignorare i 2 bit bassi dei primi 2 caratteri, per mettere insieme [abcd][abcd].* , [abcd][efgh].* insieme, ecc. Ciò richiederebbe anche una fusione dei risultati ordinati tra alcune serie di secchi. es. daxxx sarebbe nel primo bucket, ma aexxx sarebbe nel 2 °. Ma solo i bucket con gli stessi high-bit di prima class devono essere uniti l’un l’altro per produrre l’output finale ordinato.

    Un’idea per la gestione di una scelta di bucket che offre un grande dup-finding ma necessita di un merge-sorting tra i bucket: quando si scrive l’output di phase2, si esegue il bucket con il primo carattere come radice per produrre l’ordinamento desiderato. Ogni secchio di fase 1 disperde l’output nei bucket di fase2 come parte dell’ordinamento globale. Una volta che tutti i batch di fase1 che possono includere stringhe che iniziano con a sono stati elaborati, eseguire l’unione di a bucket di fase2 nell’output finale ed eliminare i file temporanei.

    Radix = primi 2 byte (combinando non alfabetici) potrebbero fare per 28 2 = 784 bucket. Con 200MiB di RAM, la dimensione del file di output medio è di appena ~ 256k. Lo svuotamento di un solo secchio alla volta lo renderebbe il minimo e di solito si otterrebbero lotti più grandi, quindi potrebbe funzionare. (Il tuo algoritmo di sfratto potrebbe colpire un caso patologico che gli ha permesso di tenere un sacco di grossi secchi, e scrivere una serie di piccoli lotti per i nuovi secchi.Esistono dei pericoli per un’euristica intelligente se non esegui un test accurato).

    Più batch raggruppati nello stesso file di output è probabilmente più utile con molti piccoli bucket. Avrai ad esempio 784 file di output, ciascuno contenente una serie di lotti. Speriamo che il vostro filesystem abbia abbastanza spazio libero contiguo, ed è abbastanza intelligente, per fare un buon lavoro di non frammentare troppo male quando si diffondono scritture di piccole dimensioni su molti file.


    Fusione:

    Nelle fasi di fusione, con lotti ordinati non abbiamo bisogno di un dizionario. Prendi la riga successiva dal batch che ha il valore più basso, combinando i duplicati quando li trovi.

    MergeSort tipicamente unisce le coppie, ma quando si fa un ordinamento esterno (es. Disk -> disk) , è molto più ampio l’input per evitare di leggere e riscrivere l’output molte volte. Avere 25 file di input aperti per unire in un file di output dovrebbe andare bene. Utilizzare l’implementazione della libreria di PriorityQueue (in genere implementata come heap) per scegliere il successivo elemento di input da molti elenchi ordinati. Magari aggiungi le linee di input con la stringa come priorità e il numero di conteggio e di input come payload.

    Se hai utilizzato radix distribuisci per primo carattere nel primo passaggio, quindi unisci tutti i lotti nel file di output finale (anche se questo processo richiede più fasi di fusione), quindi tutti i batch b , ecc. è necessario controllare uno qualsiasi dei batch dall’inizio con a bucket contro i lotti da qualsiasi altro bucket , quindi questo consente di risparmiare un sacco di lavoro di fusione, specialmente se le tue chiavi sono ben distribuite dal primo personaggio.


    Ridurre al minimo l’impatto sul server di produzione:

    Accelera l’I / O del disco durante l’unione, per evitare di mettere il tuo computer in ginocchio se il prefetch del disco genera un’enorme profondità di lettura delle code I / O. Limitare l’I / O, piuttosto che un’unione più ristretta, è probabilmente una scelta migliore. Se il server è impegnato con il suo normale lavoro, è probabile. non farò molte letture sequenziali di grandi dimensioni anche se stai leggendo solo un paio di file.

    Controllare il carico del sistema di tanto in tanto durante l’esecuzione. Se è alto, dormi per 1 sec prima di fare ancora un po ‘di lavoro e controllare di nuovo. Se è veramente alto, non lavorare più finché la media del carico non cala (dormendo 30 secondi tra un assegno e l’altro).

    Controllare anche l’utilizzo della memoria di sistema e ridurre la soglia del lotto se la memoria è troppo stretta sul server di produzione. (O se davvero stretto, lava il tuo lotto parziale e dormi finché la pressione della memoria non diminuisce).

    Se la dimensione del file temporaneo è un problema, è ansible eseguire una compressione con prefisso comune come frcode da updatedb / locate per ridurre significativamente la dimensione del file per gli elenchi ordinati di stringhe. Utilizzare probabilmente l’ordinamento case-sensitive all’interno di un batch, ma la radixing non sensibile al maiuscolo / minuscolo. Quindi ogni partita nel secchio avrà tutte le A , quindi tutte le a . O persino comprimere / decomprimere LZ4 al volo. Usa hex per i conteggi, non decimale. È più breve e più veloce da codificare / decodificare.

    Utilizzare un separatore che non sia un carattere di nome file legale, come / , tra chiave e conteggio. L’analisi delle stringhe potrebbe richiedere molto tempo CPU nella fase di unione, quindi vale la pena considerare. Se puoi lasciare le stringhe nei buffer di input per file, e basta puntare il tuo PQueue su di loro, potrebbe essere positivo. (E dirvi da quale file di input proviene una stringa, senza memorizzarla separatamente).


    ottimizzazione delle prestazioni:

    Se le stringhe iniziali non ordinate erano disponibili estremamente veloci, una tabella hash con piccoli batch che si adattano al dizionario nella cache della CPU L3 potrebbe essere una vittoria, a meno che una finestra più grande non includa una frazione molto più grande di chiavi e trovi più duplicati. Dipende da quante ripetizioni sono tipiche dei file da 100k. Costruisci piccoli lotti ordinati nella RAM mentre leggi, quindi uniscili in un batch di dischi. Questo può essere più efficiente di un grande quicksort in memoria, dato che non hai accesso casuale all’input finché non lo hai letto inizialmente.

    Poiché l’I / O sarà probabilmente il limite, i grandi batch che non rientrano nella cache dei dati della CPU sono probabilmente una vittoria, per trovare più duplicati e (notevolmente?) Ridurre la quantità di lavoro di fusione da eseguire.

    Potrebbe essere utile controllare la dimensione della tabella hash / il consumo di memoria dopo ogni blocco di nomi di file che si ottiene dal sistema operativo, o dopo ogni sottodirectory o qualsiasi altra cosa. As long as you choose a conservative size bound, and you make sure you can’t go for too long without checking, you don’t need to go nuts checking every iteration.


    This paper from 1983 examines external merge-sorting eliminating duplicates as they’re encountered, and also suggests duplicate elimination with a hash function and a bitmap. With long input strings, storing MD5 or SHA1 hashes for duplicate-elimination saves a lot of space.

    I’m not sure what they had in mind with their bitmap idea. Being collision-resistant enough to be usable without going back to check the original string would require a hash code of too many bits to index a reasonable-size bitmap. (eg MD5 is a 128bit hash).

    How do you “merge the group files” in your approach? In worst case every line had a different name template so each group file had 5,000 lines in it and each merge doubles the number of lines until you overflow memory.

    Your friend is closer to the answer, those intermediate files need to be sorted so you can read them line by line and merge them to create new files without having to hold them all in memory. This is a well-known problem, it’s an external sort . Once sorted you can count the results.

    A jolly good problem.

    Considering that you intend to process the results in batches of 5000 , I don’t believe memory optimisations will be of particular importance so we could probably ignore that aspect like a bad Adam Sandler film and move onto the more exciting stuff. Besides, just because some computation uses more RAM does not necessarily imply it’s a bad algorithm. No one ever complained about look-up tables.

    However, I do agree computationally the dictionary approach is better because it’s faster . With respect to the alternative, why perform an unnecessary sort even if its quick? The latter, with its “O(m log m)” is ultimately slower than “O(m)”.

    The Real Problem?

    With RAM out of the equation, the problem is essentially that of computation . Any “performance problem” in the algorithm will arguably be insignificant to the time it takes to traverse the file system in the first place .

    That’s arguably where the real challenge will be. A problem for another time perhaps?

    EDIT : displayName makes a good point about using Hadoop – quite ideal for concurrent jobs and compute

    In bocca al lupo!

    Your problem is a very good candidate for Map-Reduce . Great news: You don’t need to move from C# to Java (Hadoop) as Map-Reduce is possible in .NET framework!

    Through LINQs you have the basic elements of execution in place already for performing Map Reduce in C#. This might be one advantage over going for External Sort though there is no question about the observation behind External Sort. This link has the ‘Hello World!’ of Map-Reduce already implemented in C# using LINQs and should get you started.


    If you do move to Java, one of the most comprehensive tutorial about it is here . Google about Hadoop and Map-Reduce and you will get plenty of information and numerous good online video tutorials.

    Further, if you wish to move to Java, your requirements of:

    • Sorted results
    • critical RAM usage

    will surely be met as they are inbuilt fulfillments you get from a Map-Reduce job in Hadoop.