C# Suche große Textdatei

Question

Ich versuche, die Suche nach einer Zeichenfolge in einer großen Textdatei (300-600 MB) zu optimieren. Mit meiner derzeitigen Methode dauert es zu lange.

Derzeit verwende ich IndexOf, um nach der Zeichenfolge zu suchen, aber die Zeit, die es dauert, ist viel zu lang (20s), um einen Index für jede Zeile mit der Zeichenfolge zu erstellen.

Wie kann ich die Suchgeschwindigkeit optimieren? Ich habe versucht Contains(), aber das ist auch langsam. Irgendwelche Vorschläge? Ich habe an Regex-Match gedacht, aber ich sehe keinen signifikanten Geschwindigkeitsschub. Vielleicht ist meine Suchlogik fehlerhaft

Beispiel

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

Answer 1

Die Brute-Force-Algorithmus Sie führt verwenden in O (nm) Zeit, wo n die Länge der Zeichenfolge gesucht wird und m Die Länge des Teilstrings/-musters, die Sie suchen. Sie benötigen einen String-Suchalgorithmus verwenden:

• Boyer-Moore ist der "Standard", denke ich: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

• Aber es gibt noch viel mehr gibt: http://www-igm.univ-mlv.fr/~lecroq/string/

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

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

jedoch einen regulären Ausdruck mit Sorgfalt gestaltete könnte ausreichend sein, je nachdem, was Sie versuchen zu finden. Siehe Jeffrey's Friedl 's tome, Mastering Regular Expressions für Hilfe beim Erstellen effizienter regulärer Ausdrücke (z. B. kein Backtracking).

Sie könnten auch einen guten Algorithmus Text konsultieren. Ich bin teilweise zu Robert Sedgewick der Algorithms in seiner various incarnations (Algorithmen in [C | C++ | Java])

Answer 2

Haben Sie diese Fragen gesehen (und Antworten)?

• 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?

es die Art und Weise tun Sie jetzt sind, scheint der Weg zu sein, zu gehen, wenn alles, was Sie tun wollen, um die Textdatei gelesen wird. Andere Ideen:

• Wenn es möglich ist, die Daten vorab sortieren, wie wenn sie in die Textdatei eingefügt werden, helfen, dass könnten.

• Sie können die Daten in eine Datenbank einfügen und nach Bedarf abfragen.

• Sie könnten eine Hash-Tabelle verwenden

Answer 3

Sie können Benutzer regexp.Match (String). RegExp Match ist schneller.

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

Leider, ich glaube nicht, dass es eine ganze Menge Sie in geraden C# tun können.

Ich habe gefunden, dass der Boyer-Moore-Algorithmus für diese Aufgabe extrem schnell ist. Aber ich fand, dass es keine Möglichkeit gab, das so schnell wie IndexOf zu machen. Meine Annahme ist, dass dies so ist, weil IndexOf in handoptimierten Assembler implementiert ist, während mein Code in C# ausgeführt wurde.

Sie können meine Code und Leistung Testergebnisse in dem Artikel Fast Text Search with Boyer-Moore sehen.