大型集合的LINQ性能

Dictionary / SortedDictionary HashSet 集合,您使用它们的方式与使用 List

如果使用字典作为索引,其中字符串的前几个字符是键,字符串列表是值,则可以从搜索字符串中选择整个字符串集合中可能存在匹配项的一小部分。

该类为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);
    }

}

我打赌列上有一个索引,因此SQLServer可以在O(log(n))操作而不是O(n)操作中进行比较。要模拟SQL server行为,请使用已排序的集合并查找所有字符串s,以便s>=查询并查看值,直到找到一个不以s开头的值,然后对这些值执行附加筛选。这就是所谓的范围扫描(Oracle)或索引查找(SQL server)。

这是一些很可能进入无限循环或出现一次性错误的示例代码,因为我没有对其进行测试,但您应该明白这一点。

// 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++;
    }
}

不 以正确的前缀开始。

事实上,您可能会对第一个不以前缀开头的值执行另一个二进制搜索,因此您将有一个起点和一个终点。然后,您只需要将长度标准应用于匹配部分。(我希望如果它是合理的数据,前缀匹配将去除大多数候选值。)找到不以前缀开头的第一个值的方法是按字典顺序搜索不以前缀开头的第一个值-例如,使用前缀“ABC”,搜索“ABD”。

所有这些都没有使用LINQ,而且都非常特定于您的特定情况,但它应该可以工作。如果这些都不合理,请告诉我。

如果您正试图优化查找具有给定前缀的字符串列表,那么您可能希望了解如何实现 Trie (不要误认为是普通的 tree )C#中的数据结构。

尝试提供非常快速的前缀查找,并且与此类操作的其他数据结构相比,具有非常小的内存开销。

littered with articles 分析其性能。

只要看看您的代码,我会说您应该重新排序比较,以利用使用布尔运算符时的短路:

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

通过将长度比较放在调用StartsWith之前,如果比较失败,您可以节省一些额外的周期,这些周期在处理大量项目时可能会累积起来。

我不认为查找表会对您有所帮助,因为当您比较整个键而不是部分键时,查找表是很好的,就像您在调用StartsWith时所做的那样。

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

然而,在这一点上,您实际上只是在重新创建SQL Server正在做的事情(在索引的情况下),而这只是重复您的工作。

我认为问题在于Linq无法利用序列已经排序的事实。特别是它不能知道,应用 StartsWith 函数保留顺序。

List.BinarySearch IComparer<string> 这只会比较第一个查询字符(这可能很棘手,因为不清楚查询字符串是否始终是要比较的第一个或第二个参数) () ).

您甚至可以使用标准的字符串比较,因为BinarySearch返回一个负数,您可以使用~)进行补码,以获得比查询大的第一个元素的索引。

然后必须从返回的索引(双向!)开始查找与查询字符串匹配的所有元素。