LINQ大型集合的性能

Question

我按字母顺序排序了大量字符串(最多1M).我已经使用HashSet,SortedDictionary和Dictionary对这个集合进行了LINQ查询.我是静态缓存集合,它的大小高达50MB,我总是在缓存集合中调用LINQ查询.我的问题如下:

无论集合类型如何,性能都比SQL差很多(最多200ms).对基础SQL表执行类似的查询时,性能要快得多(5-10ms).我已经实现了我的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查询,我有哪些选择？

Answer 1

在您当前的代码中,您没有使用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);
    }

}