C# wyszukiwanie dużego pliku tekstowego

Question

Próbuję zoptymalizować wyszukiwanie ciągu znaków w dużym pliku tekstowym (300-600 MB). Używanie mojej obecnej metody trwa zbyt długo.

Obecnie używam IndexOf, aby wyszukać ciąg znaków, ale czas, jaki zajmuje, jest zbyt długi (20s), aby utworzyć indeks dla każdej linii za pomocą ciągu.

Jak mogę zoptymalizować prędkość wyszukiwania? Próbowałem już Contains(), ale to również jest powolne. Jakieś sugestie? Myślałem o dopasowaniu do regex, ale nie widzę, żeby miało znaczący wzrost prędkości. Może moja logika wyszukiwania jest wadliwa

przykład

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

Answer 1

algorytm brute force używasz wykonuje w O (nm) czas, gdzie n jest długość łańcucha są wyszukiwane i m długość podciągu/wzoru, który próbujesz znaleźć. Trzeba użyć ciąg wyszukiwania algorytm:

• Boyer-Moore jest "średnia", myślę: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

• Ale istnieje wiele więcej tam: http://www-igm.univ-mlv.fr/~lecroq/string/

• tym Morrisa-Pratta: http://www.stoimen.com/blog/2012/04/09/computer-algorithms-morris-pratt-string-searching/

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

Jednak za pomocą wyrażenia regularnego spreparowany z opieki może być wystarczająca, w zależności od tego, co starają się znaleźć. Zobacz artykuł o numerze Jeffrey's Friedl, Mastering Regular Expressions, aby uzyskać pomoc w budowaniu wydajnych wyrażeń regularnych (np. Bez cofania).

Możesz również chcieć zapoznać się z tekstem dobrych algorytmów. Jestem częściowym Robert Sedgewick na Algorithms w swoich various incarnations (algorytmów w [C | C++ | Java])

Answer 2

Widzieliście te pytania (i odpowiedzi)?

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

Robi to tak, jesteś teraz wydaje się być droga, jeśli wszystko, co chcesz zrobić, to odczytać plik tekstowy. Inne pomysły:

• Jeśli istnieje możliwość wstępnego sortowania danych, na przykład podczas wstawiania ich do pliku tekstowego, może to pomóc.

• Można wstawić dane do bazy danych i wykonać zapytanie w razie potrzeby.

• Można użyć tabeli mieszania

Answer 3

Można regexp.Match użytkownika (String). Dopasowanie RegExp jest szybsze.

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

Niestety, nie sądzę, nie ma dużo można zrobić w prosty C#.

Zauważyłem, że algorytm Boyer-Moore jest wyjątkowo szybki do wykonania tego zadania. Ale okazało się, że nie było sposobu, aby zrobić to tak szybko, jak IndexOf. Zakładam, że jest tak, ponieważ IndexOf jest zaimplementowany w asembleru zoptymalizowanym ręcznie, podczas gdy mój kod działa w języku C#.

Możesz zobaczyć mój kod i wyniki testu wydajności w artykule Fast Text Search with Boyer-Moore.