C# ricerca di file di testo di grandi dimensioni

Question

Sto cercando di ottimizzare la ricerca di una stringa in un file di testo di grandi dimensioni (300-600mb). Usando il mio metodo attuale, ci vuole troppo tempo.

Attualmente sto usando IndexOf per cercare la stringa, ma il tempo necessario è troppo lungo (20 secondi) per creare un indice per ogni riga con la stringa.

Come ottimizzare la velocità di ricerca? Ho provato Contains() ma anche questo è lento. Eventuali suggerimenti? Stavo pensando alla partita di regex ma non vedo che abbia un significativo aumento di velocità. Forse la mia logica di ricerca è viziata

esempio

while ((line = myStream.ReadLine()) != null) 
{ 
    if (line.IndexOf(CompareString, StringComparison.OrdinalIgnoreCase) >= 0) 
    { 
     LineIndex.Add(CurrentPosition); 
     LinesCounted += 1; 
    } 
} 

Answer 1

L'algoritmo di forza bruta che si sta utilizzando esibisce in O (nm) tempo, dove n è la lunghezza della stringa da ricercare e m la lunghezza della sottostringa/modello che stai cercando di trovare. È necessario utilizzare un stringa di algoritmo di ricerca:

• Boyer-Moore è "lo standard", penso: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

• ma ci sono molti più là fuori: http://www-igm.univ-mlv.fr/~lecroq/string/

• compreso Morris-Pratt: http://www.stoimen.com/blog/2012/04/09/computer-algorithms-morris-pratt-string-searching/

• e Knuth-Morris-Pratt: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

Tuttavia, utilizzando un'espressione regolare realizzato con cura potrebbe essere sufficiente, a seconda di ciò che si sta cercando di trovare. Vedere il capitolo Jeffrey's Friedl, Mastering Regular Expressions per assistenza sulla creazione di espressioni regolari efficienti (ad esempio, nessun backtracking).

Si potrebbe anche voler consultare un buon testo algoritmi. Io ho un debole per Robert Sedgewick di Algorithms nelle sue various incarnations (Algoritmi in [C | C++ | Java])

Answer 2

Hai visto queste domande (e risposte)?

• Processing large text file in C#
• Is there a way to read large text file in parts?
• Matching a string in a Large text file?

Farlo così come sei ora sembra essere la strada da percorrere se tutto quello che vogliamo fare è leggere il file di testo. Altre idee:

• Se è possibile pre-ordinare i dati, ad esempio quando viene inserito nel file di testo, che potrebbero aiutare.

• È possibile inserire i dati in un database e interrogarli secondo necessità.

• Si potrebbe utilizzare una tabella hash

Answer 3

È possibile regexp.Match utente (String). RegExp Match è più veloce.

static void Main()

{

string text = "One car red car blue car"; 
    string pat = @"(\w+)\s+(car)"; 

    // Instantiate the regular expression object. 
    Regex r = new Regex(pat, RegexOptions.IgnoreCase); 

    // Match the regular expression pattern against a text string. 
    Match m = r.Match(text); 
    int matchCount = 0; 
    while (m.Success) 
    { 
    Console.WriteLine("Match"+ (++matchCount)); 
    for (int i = 1; i <= 2; i++) 
    { 
     Group g = m.Groups[i]; 
     Console.WriteLine("Group"+i+"='" + g + "'"); 
     CaptureCollection cc = g.Captures; 
     for (int j = 0; j < cc.Count; j++) 
     { 
      Capture c = cc[j]; 
      System.Console.WriteLine("Capture"+j+"='" + c + "', Position="+c.Index); 
     } 
    } 
    m = m.NextMatch(); 
    } 

}

Answer 4

Purtroppo, non credo che ci sia un bel po 'che si può fare in rettilineo C#.

Ho trovato l'algoritmo di Boyer-Moore estremamente veloce per questo compito. Ma ho scoperto che non c'era modo di farlo anche alla velocità di IndexOf. La mia ipotesi è che questo sia dovuto al fatto che lo IndexOf è implementato in un assemblatore ottimizzato a mano mentre il mio codice viene eseguito in C#.

È possibile visualizzare il codice e i risultati del test delle prestazioni nell'articolo Fast Text Search with Boyer-Moore.