在 List 中进行字符串搜索，具有高性能

本文关键字：搜索 字符串 高性能 List | 更新日期: 2023-09-27 18:32:20

我有一个包含 50000+ 字符串的列表，平均长度为 ~1000 个字符。我可以做一个简单的查询，比如：

data.Where(c => c.Contains(query));

但我的猜测是，在性能方面，这不是最好的方法。在尝试提高搜索性能时，您的建议是什么？

我尝试过的事情：

/*** Worst ***/
var result = new List<string>();
foreach (var row in data)
{
    if (row.Contains(query))
        result.Add()
}
/*** Medium ***/
data.Where(c => c.IndexOf(query) != -1);
/*** Best but not that great ***/
data.Where(c => c.Contains(query));

在 List<T> 中进行字符串搜索，具有高性能

在我的头顶上：您可以使用PLINQ来改善搜索响应时间（如果您的机器是多核的）

var result = data.AsParallel()
    .Where(c => c.Contains(query));

除此之外，正如@Tim Schmelter指出的那样，你应该使用数据库表。

如果你能负担得起使用数据库 - 使用它。他们非常擅长快速查询。

如果不能并且需要在内存中执行此操作，则可以使用任何快速字符串搜索算法，在长字符串中查找短字符串。根据您的确切需求，这里有两个建议：

  • Knuth-Morris-Pratt（C#实现） - 当您在许多"字符串数据库"中重复查找相同的字符串时很有用
  • 后缀树（C# 实现） - 在同一个"字符串数据库"中多次搜索不同的字符串时很有用

这些算法中的任何一种对于在长字符串 S 中查找短字符串 P 都很有用。它们的效率根据变化和静止的变化而变化。

在您的情况下，您有一个字符串列表，而不是一个长字符串。但是，在字符串列表中搜索的问题很容易转换为在长字符串中搜索的问题，方法是将所有字符串连接起来，并由任何字符串不使用的特殊字符分隔。

例如，如果我想在字符串列表中查找字符串 P ["Hello"、"World"、"Forty two"]，那么我将创建一个长字符串"Hello$World$Forty Two"（其中 $ 是我的特殊分隔符）并在这个长字符串中查找 P。

相关文章：