Analisi efficiente di un grande file di testo in C#

Question

Ho bisogno di leggere un grande file di testo separato dallo spazio e contare il numero di istanze di ogni codice nel file. Essenzialmente, questi sono i risultati dell'esecuzione di alcuni esperimenti centinaia di migliaia di volte. Il sistema sputa fuori un file di testo che appare un po 'come questo:

A7PS A8PN A6PP23 ... 

E ci sono letteralmente centinaia di migliaia di queste voci e ho bisogno di contare le occorrenze di ciascuno dei codici.

Immagino di poter aprire uno StreamReader e passare linea per linea, dividendo il carattere dello spazio. Verifica se il codice è già stato rilevato e aggiungendo 1 al conteggio di quel codice. Tuttavia, questo è probabilmente piuttosto ingenuo, data la dimensione dei dati.

Qualcuno sa di un algoritmo efficiente per gestire questo tipo di elaborazione?

UPDATE:

OK, in modo che il consenso sembra essere il mio approccio è nella giusta direzione

Quello che mi sarei interessato a sentire le cose come sono - che è più efficiente - StreamReader. TextReader, BinaryReader

Qual è la migliore struttura per memorizzare il mio dizionario di risultati? HashTable, SortedList, HybridDictionary

Se non ci sono interruzioni di riga, il file (non mi è stato ancora fornito un campione) dividerà il tutto in uno spazio inefficiente?

In sostanza, sto cercando di rendere il più performante possibile le

grazie ancora

Answer 1

Il tuo approccio sembra buono.

1. Leggere in linea per linea
2. Split ogni riga dallo spazio
3. aggiunge un record a un dizionario se non esiste ancora e se esiste, fare il valore ++

Answer 2

direi che in generale il vostro approccio è giusto, ma v'è spazio per il parallelismo. Ti suggerirei di avviare più thread o attività (in .NET 4) per analizzare parti/blocchi di file. Inoltre, invece di leggere riga per riga, leggere in blocchi di byte, offre prestazioni migliori dal punto di vista del disco IO.

Modifica: ecco lo schema della soluzione.

1. Diciamo procederemo pezzi M di N caratteri al momento (perché vogliamo limitare la quantità di memoria necessaria e numero di thread utilizzato).
2. Allocare il buffer di caratteri N * M. Useremo questo buffer ciclicamente.
3. Utilizzerà il modello produttore-consumatore. Il produttore riempirà il buffer. Lo standard cercherà di trovare il limite della parola vicino al limite del chunk (ad esempio vicino a ogni carattere dell'N ° ). Quindi avremo M pezzi di circa N caratteri con start e indice finale nel buffer
4. Ora avviare thread M worker per elaborare ogni blocco. Ogni lavoratore utilizzerà il proprio dizionario per contare le parole - questo eliminerà la necessità di sincronizzazione dei thread.
5. Aggregherà i risultati alla fine dell'iterazione. Il processo deve essere ripetuto fino alla lettura dell'intero file.

Naturalmente, sto assumendo file davvero enormi per adottare questo approccio. Probabilmente userò la ricerca di caratteri vecchio stile nel buffer per trovare codice di ricerca per il contrassegno del limite delle parole come non sicuro per evitare verifiche vincolate.

Answer 3

A un livello molto elementare, inizierei con uno Dictionary<string, int>, stringa.split il documento sugli spazi e mantieni il conto tramite il semplice parsing di quei dati.

string.split è un metodo relativamente affidabile che, e qualcuno mi correggerà sicuramente se ho torto, è stato creato per usare espressioni regolari ed è immensamente più complesso di quello che serve per questo scenario.

Scrivere il proprio metodo di split sarà probabilmente una soluzione più valida rispetto a quella del framework. Suggerisco di utilizzare prima la versione standard, come descritto sopra, quindi riscrivere la tua se si determina che la prestazione è un problema.

Ian

Answer 4

Sono d'accordo con il commento di PoweRoy: perché non provarlo? Forse non ci sono problemi nella pratica.

Se è necessario qualcos'altro, è possibile provare a scrivere un codice che prende uno Stream e restituisce un IEnumerable<string>. Leggeresti i caratteri dal suo input uno alla volta - se hai bisogno di un buffer per l'efficienza puoi sempre avvolgere lo FileStream in questo codice in uno BufferStream - e controlla se è uno spazio (o possibile un EOL?). Se non lo è, aggiungerà il carattere a un buffer di stringa (forse un StringBuilder?), Ma se lo sarà sarà il yield return buffer di stringa corrente e cancellarlo.

Dopodiché puoi solo foreach sul risultato di chiamare questo codice sul contenuto del file e otterrai i codici dal file uno per uno.

È quindi possibile utilizzare una sorta di struttura dati come un Dictionary<string,int> per contare il numero di occorrenze per ciascun codice, mantenendo il codice come chiave e il conteggio come valore. Ma questo passo sarebbe lo stesso se leggi il file riga per riga e usa string.Split per dividerli in spazi.

Answer 5

Se non ci sono altre restrizioni, è necessario leggere il file completo come descritto.

Per salvare i codici e il conteggio, è necessario utilizzare una struttura dati che consenta la ricerca e inserisca il tempo O (log n). SortedDictionary lo faranno in C#.

EDIT:

Qual è la struttura migliore per conservare il mio dizionario dei risultati? HashTable, SortedList, HybridDictionary

Perché modo ordinato sembra non essere richiesto un HybridDictionary o un Dictionary sarà perfom meglio nella maggior parte dei casi. SortedList sarà probabilmente la soluzione più lenta, perché gli inserti prendono O (n). Dovresti fare alcuni test con le diverse implementazioni se le prestazioni sono così importanti.

Answer 6

Se si desidera provare qualcosa di diverso, è possibile provare a utilizzare uno BinaryReader e leggere lo stream byte per byte e aumentare un contatore di uno ogni volta che si incontra uno spazio.

Answer 7

Centinaia di dischi non sono così tanti. Vorrei usare un Dictionary<string,int>. Per memorizzare la chiave e il conteggio.

Ma se si verificano problemi di memoria, perché non utilizzare un database, anche un database come SQL Compact o SQLite. Crea una tabella con un record contenente la chiave e il conteggio.

Mantenere i dati in memoria è il più rapido per piccole quantità di dati, ma quando si raggiungono i limiti di memoria del computer, un database sarà più veloce.

Answer 8

static string LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 
    static string NUMBERS = "1234567890"; 
    static Random rdGen = new Random(); 
    static Dictionary<string, int> myDic = new Dictionary<string, int>(); 
    static void WriteTest(int max) 
    { 
     myDic = new Dictionary<string, int>(); 
     Stopwatch sw = new Stopwatch(); 
     sw.Start(); 
     for (int i = 0; i < max; i++) 
     { 
      string code = LETTERS[rdGen.Next(0, 26)].ToString() + NUMBERS[rdGen.Next(0, 10)].ToString() + LETTERS[rdGen.Next(0, 26)].ToString() + LETTERS[rdGen.Next(0, 26)].ToString(); 
      if (myDic.ContainsKey(code)) myDic[code]++; 
      else 
      { 
       myDic[code] = 1; 
      } 
     } 
     sw.Stop(); 
     Console.WriteLine(max.ToString() + " itérations : " + sw.ElapsedMilliseconds.ToString()); 

    } 

WriteTest (10000000); // Prende 7,5 secondi.

Sembra abbastanza efficiente per me.