C# recherche fichier texte volumineux

Question

J'essaie d'optimiser la recherche d'une chaîne dans un fichier texte volumineux (300-600mb). En utilisant ma méthode actuelle, cela prend trop de temps.

Actuellement, j'ai utilisé IndexOf pour rechercher la chaîne, mais le temps qu'il faut est trop long (20s) pour construire un index pour chaque ligne avec la chaîne.

Comment puis-je optimiser la vitesse de recherche? J'ai essayé Contains() mais c'est lent aussi. Aucune suggestion? Je pensais match regex mais je ne vois pas cela ayant un coup de pouce de vitesse significative. Peut-être que ma logique de recherche est erronée

exemple

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

Answer 1

L'algorithme de force brute que vous utilisez effectue dans O (nm) temps où n est la longueur de la chaîne recherchée et m la longueur de la sous-chaîne/du motif que vous essayez de trouver. Vous devez utiliser un algorithme de recherche de chaîne :

• Boyer-Moore est "la norme", je pense: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

• Mais il y a beaucoup plus là-bas: http://www-igm.univ-mlv.fr/~lecroq/string/

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

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

Cependant, en utilisant une expression régulière conçu pourrait être suffisant avec soin , en fonction de ce que vous essayez de trouver. Voir le tome Jeffrey's Friedl, Mastering Regular Expressions pour obtenir de l'aide sur la création d'expressions régulières efficaces (par exemple, pas de retour en arrière).

Vous pouvez également consulter un bon texte d'algorithmes. Je suis partie à Robert Sedgewick de Algorithms dans ses various incarnations (algorithmes dans [C | C++ | Java])

Answer 2

Avez-vous vu ces questions (et réponses)?

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

il Faire la façon dont vous êtes semble maintenant être le chemin à parcourir si tout ce que vous voulez faire est de lire le fichier texte. Autres idées:

• S'il est possible d'effectuer une pré-trier les données, telles que quand il est inséré dans le fichier texte, qui pourrait aider.

• Vous pouvez insérer les données dans une base de données et les interroger si nécessaire.

• Vous pouvez utiliser une table de hachage

Answer 3

Vous pouvez regexp.Match utilisateur (String). RegExp Match est plus rapide.

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

Malheureusement, je ne pense pas qu'il y ait beaucoup que vous pouvez faire en C# droite.

J'ai trouvé l'algorithme de Boyer-Moore extrêmement rapide pour cette tâche. Mais j'ai trouvé qu'il n'y avait aucun moyen de faire même cela aussi vite que IndexOf. Mon hypothèse est que c'est parce que IndexOf est implémenté dans l'assembleur optimisé à la main pendant que mon code s'exécute en C#.

Vous pouvez voir mes résultats de tests de code et de performance dans l'article Fast Text Search with Boyer-Moore.