LINQ大型集合的性能
我按字母顺序排序了大量字符串（最多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查询，我有哪些选择？
在当前代码中，您没有使用Dictionary / SortedDictionary / HashSet集合的任何特殊function，您使用它们的方式与使用List方式相同。 这就是为什么你没有看到性能上的任何差异。
如果您使用字典作为索引，其中字符串的前几个字符是键，字符串列表是值，您可以从搜索字符串中挑选出可能匹配的整个字符串集合的一小部分。
我写了下面的课来测试这个。 如果我用一百万个字符串填充它并用八个字符串搜索它会在大约3毫秒内完成所有可能的匹配。 使用一个字符串进行搜索是最糟糕的情况，但它会在大约4毫秒内找到前1000个匹配项。 查找一个字符串的所有匹配大约需要25毫秒。
该类为1,2,4和8个字符键创建索引。 如果查看特定数据和搜索内容，则应该能够选择要创建的索引以根据您的条件对其进行优化。
public class IndexedList { private class Index : Dictionary> { 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 list; if (!this.TryGetValue(key, out list)) { Add(key, list = new List ()); } list.Add(value); } } public IEnumerable 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 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 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); } }
我打赌你在列上有一个索引，所以SQL服务器可以在O（log（n））操作而不是O（n）中进行比较。 要模仿SQL服务器行为，请使用已排序的集合并查找所有字符串，使得s> = query，然后查看值，直到找到不以s开头的值，然后对值执行其他过滤。 这就是所谓的范围扫描（Oracle）或索引搜索（SQL服务器）。
这是一些示例代码很可能会进入无限循环或一次性错误，因为我没有测试它，但你应该得到这个想法。
// Note, list must be sorted before being passed to this function IEnumerable FindStringsThatStartWith(List 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，并且它都非常特定于您的特定情况，但它应该工作。 如果任何一个没有意义，请告诉我。
如果您正在尝试优化查找具有给定前缀的字符串列表，您可能需要查看在C＃中实现Trie （不要误解为常规树 ）数据结构。
尝试提供非常快速的前缀查找，并且与用于此类操作的其他数据结构相比具有非常小的内存开销。
关于LINQ to Objects一般。 与SQL相比，降低速度并不罕见。 网上散落着分析其表现的文章 。
只看你的代码，我会说你应该重新排序比较，以便在使用布尔运算符时利用短路：
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正在执行的操作（在索引的情况下），这只是您的重复工作。
我认为问题是Linq没有办法使用你的序列已经排序的事实。 特别是它无法知道，应用StartsWith函数会保留订单。
我建议使用List.BinarySearch方法和IComparer ，它只对第一个查询字符进行比较（这可能很棘手，因为它不清楚，如果查询字符串将始终是第一个或第二个参数到() ）。
您甚至可以使用标准字符串比较，因为BinarySearch返回一个负数，您可以补充（使用〜）以获得大于查询的第一个元素的索引。
然后，您必须从返回的索引（两个方向！）开始，以查找与查询字符串匹配的所有元素。