c# - c# 搜索大文本文件

Question

我正在尝试优化对大型文本文件（300-600mb）中字符串的搜索。使用我目前的方法，花费的时间太长。

目前我一直在使用IndexOf搜索字符串，但是用字符串为每一行建立索引所花费的时间太长（20s）。

如何优化搜索速度？我已经尝试过Contains()，但这也很慢。有什么建议么？我在考虑正则表达式匹配，但我没有看到它有显着的速度提升。也许我的搜索逻辑有缺陷

例子

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

score 12 · Accepted Answer

您使用的蛮力算法在O(nm)时间内执行，其中n是正在搜索的字符串的长度，m是您尝试查找的子字符串/模式的长度。您需要使用字符串搜索算法：

Boyer-Moore 是“标准”，我认为： http ://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
但是还有更多： http ://www-igm.univ-mlv.fr/~lecroq/string/
包括莫里斯-普拉特： http: //www.stoimen.com/blog/2012/04/09/computer-algorithms-morris-pratt-string-searching/
和 Knuth-Morris-Pratt： http ://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

但是，根据您要查找的内容，使用精心设计的正则表达式可能就足够了。请参阅Jeffrey 的 Friedl的著作Mastering Regular Expressions以获取有关构建高效正则表达式（例如，无回溯）的帮助。

您可能还想参考一个好的算法文本。我偏爱 Robert Sedgewick 的各种化身算法（[C|C++|Java] 中的算法）

score 2 · Accepted Answer

不幸的是，我不认为你可以在直接的 C# 中做很多事情。

我发现 Boyer-Moore 算法对于这项任务非常快。但我发现没有办法做到这一点IndexOf。我的假设是这是因为IndexOf我的代码在 C# 中运行时是在手动优化的汇编程序中实现的。

您可以在文章Fast Text Search with Boyer-Moore中查看我的代码和性能测试结果。

score 1 · Accepted Answer

你见过这些问题（和答案）吗？

如果您只想阅读文本文件，那么按照您现在的方式进行操作似乎是可行的方法。其他想法：

如果可以对数据进行预排序，例如在将数据插入文本文件时，那可能会有所帮助。
您可以将数据插入数据库并根据需要进行查询。
你可以使用哈希表

score 1 · Accepted Answer

您可以使用 regexp.Match(String)。正则表达式匹配更快。

静态无效主要（）

{

  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();
  }

}

c# - c# 搜索大文本文件

4 回答 4

Related

Reference