大型集合下的LINQ性能优化

Question

大型集合下的LINQ性能优化

21

我有一个按字典序排序的大量字符串集合（最多1M）。我已经尝试使用HashSet、SortedDictionary和Dictionary对此集合进行LINQ查询。我将该集合静态缓存，其大小达到50MB，并且我始终针对已缓存的集合调用LINQ查询。我的问题如下：

无论集合类型如何，性能都比SQL差得多（高达200毫秒）。当针对底层SQL表执行类似的查询时，性能要快得多（5-10毫秒）。我按照以下方式实现了我的LINQ查询：

public static string ReturnSomething(string query, int limit)
{
  StringBuilder sb = new StringBuilder();
  foreach (var stringitem in MyCollection.Where(
      x => x.StartsWith(query) && x.Length > q.Length).Take(limit))
  {
      sb.Append(stringitem);
  }

  return sb.ToString();
}

据我所知，HashSet、Dictionary等实现查找时使用的是二叉树搜索而不是标准枚举。那么，对于这些高级集合类型，我有什么高性能的LINQ查询选项呢？

- Iconic

6个回答

3

我敢肯定你在这个列上有一个索引，因此SQL服务器可以通过O(log(n))操作进行比较，而不是O(n)。为了模拟SQL server的行为，请使用已排序的集合，并找到所有字符串s，使得s >= query，然后查看值，直到找到不以s开头的值，然后对值进行额外的过滤。这就是所谓的区间扫描（Oracle）或索引搜索（SQL服务器）。

以下是一些示例代码，很可能会进入无限循环或出现一次性错误，因为我没有测试它，但你应该能够理解其思想。

// Note, list must be sorted before being passed to this function
IEnumerable<string> FindStringsThatStartWith(List<string> list, string query) {
    int low = 0, high = list.Count - 1;
    while (high > low) {
        int mid = (low + high) / 2;
        if (list[mid] < query)
            low = mid + 1;
        else
            high = mid - 1;
    }

    while (low < list.Count && list[low].StartsWith(query) && list[low].Length > query.Length)
        yield return list[low];
        low++;
    }
}

- erikkallen

2

如果您正在执行“starts with”，则只关心序数比较，并且可以将集合排序（再次按序数顺序），然后建议您将值放在列表中。然后，您可以进行二进制搜索以找到以正确前缀开头的第一个值，然后沿着列表线性向下产生结果，直到第一个不以正确前缀开头的值。

实际上，您可能还可以为不以该前缀开头的第一个值执行另一个二进制搜索，因此您将拥有起始点和结束点。然后，您只需要将匹配部分应用于该匹配部分的长度标准即可。（我希望如果这是合理的数据，则前缀匹配将消除大多数候选值）。找到第一个不以前缀开头的值的方法是搜索字典上第一个不以前缀开头的值 - 例如，以前缀“ABC”搜索“ABD”。

所有这些都不使用LINQ，并且非常特定于您的特定情况，但它应该有效。如果其中任何内容不清楚，请告诉我。

- Jon Skeet

2

如果你想要优化查找具有给定前缀的字符串列表，你可能需要考虑在C#中实现一个Trie（不要与常规树混淆）数据结构。

Trie提供非常快速的前缀查找，并且与其他数据结构相比，对于这种操作具有非常小的内存开销。

关于LINQ to Objects。一般来说，与SQL相比，速度会有所降低。网络上充斥着分析其性能的文章。

- Ben S

0

仅凭您的代码，我会建议您重新排列比较顺序，以利用布尔运算符的短路特性：

foreach (var stringitem in MyCollection.Where(
    x => x.Length > q.Length && x.StartsWith(query)).Take(limit))

长度比较始终是一个O(1)操作（因为长度作为字符串的一部分存储，不会每次计算每个字符），而调用StartsWith将是一个O(N)操作，其中N是查询的长度（或字符串的长度，以较小者为准）。

通过在调用StartsWith之前放置长度比较，如果该比较失败，您可以节省一些额外的循环，这在处理大量项目时可能会累加。

我认为查找表在这里不会对您有所帮助，因为查找表适用于比较整个键，而不是像您使用StartsWith调用时那样比较键的部分。

相反，您可能最好使用基于列表中单词中字母拆分的树结构。

但是，在那时，您实际上只是重新创建SQL Server正在执行的内容（在索引的情况下），这只是您的重复努力。

- casperOne

0

我认为问题在于Linq没有办法利用您的序列已经排序这一事实。特别是它无法知道应用StartsWith函数会保留顺序。

我建议使用List.BinarySearch方法和一个IComparer<string>，只比较第一个查询字符（这可能有些棘手，因为不清楚查询字符串是否总是作为()的第一个或第二个参数）。

您甚至可以使用标准字符串比较，因为BinarySearch返回一个负数，您可以通过取反（使用~）来获取第一个大于查询的元素的索引。

然后，您必须从返回的索引开始（向两个方向！）查找所有与查询字符串匹配的元素。

- MartinStettner

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Guffa · Accepted Answer

你当前的代码没有充分利用 Dictionary / SortedDictionary / HashSet 这些特殊集合的功能，你使用它们的方式与使用 List 的方式相同。所以你看不到任何性能上的差异。

如果你将字典作为索引，其中字符串的前几个字符是键，字符串列表是值，那么从搜索字符串中可以挑选出可能匹配的一小部分整个字符串集合。

我编写了下面的类来测试这个想法。如果我用一百万个字符串填充它，并用一个八个字符的字符串进行搜索，则可以在大约3毫秒内快速找到所有可能的匹配项。用一个字符的字符串进行搜索是最坏的情况，但它可以在大约4毫秒内找到前1000个匹配项。查找一个字符字符串的所有匹配项需要大约25毫秒。

该类创建1、2、4和8字符键的索引。如果你查看你的具体数据和搜索内容，你应该能够选择要创建哪些索引来优化你的条件。

public class IndexedList {

    private class Index : Dictionary<string, List<string>> {

        private int _indexLength;

        public Index(int indexLength) {
            _indexLength = indexLength;
        }

        public void Add(string value) {
            if (value.Length >= _indexLength) {
                string key = value.Substring(0, _indexLength);
                List<string> list;
                if (!this.TryGetValue(key, out list)) {
                    Add(key, list = new List<string>());
                }
                list.Add(value);
            }
        }

        public IEnumerable<string> Find(string query, int limit) {
            return
                this[query.Substring(0, _indexLength)]
                .Where(s => s.Length > query.Length && s.StartsWith(query))
                .Take(limit);
        }

    }

    private Index _index1;
    private Index _index2;
    private Index _index4;
    private Index _index8;

    public IndexedList(IEnumerable<string> values) {
        _index1 = new Index(1);
        _index2 = new Index(2);
        _index4 = new Index(4);
        _index8 = new Index(8);
        foreach (string value in values) {
            _index1.Add(value);
            _index2.Add(value);
            _index4.Add(value);
            _index8.Add(value);
        }
    }

    public IEnumerable<string> Find(string query, int limit) {
        if (query.Length >= 8) return _index8.Find(query, limit);
        if (query.Length >= 4) return _index4.Find(query,limit);
        if (query.Length >= 2) return _index2.Find(query,limit);
        return _index1.Find(query, limit);
    }

}