内存LINQ性能

不仅仅是关于LINQ [在这里插入您最喜欢的提供者],这个问题是关于搜索或过滤内存中的集合.

我知道LINQ(或搜索/过滤扩展方法)适用于实现IEnumerable或的对象IEnumerable.问题是:由于枚举的性质,每个查询的复杂性至少为O(n)？

例如:

var result = list.FirstOrDefault(o => o.something > n);

在这种情况下,除非按顺序排序,否则每个算法至少需要O(n),在这种情况下,搜索应采用O(log(n)):它应该是二进制搜索.但是,如果我理解正确,这个查询将通过枚举来解决,所以它应该采用O(n),即使以前订购过.list'something'list

我可以做些什么来解决O(log(n))中的查询？

如果我想要性能,我应该使用Array.Sort和Array.BinarySearch吗？

Jon Skeet.. 5

即使使用并行化,它仍然是O(n).常数因子会有所不同(取决于您的核心数量),但随着n的变化,总时间仍会线性变化.

当然,您可以在自己的数据类型上编写自己的各种LINQ运算符的实现,但它们只适用于非常特定的情况 - 您必须确定谓词仅在优化方面运行数据.例如,如果你有一个按年龄排序的人员列表,它不会帮助你查询试图找到具有特定名称的人:)

要检查谓词,你必须使用表达式树而不是委托,生活将变得更加困难.

我怀疑我通常会添加新的方法,这些方法很明显,您使用的是索引/有序/数据类型的任何性质,并且总是能够正常工作.当然,您无法轻松地从查询表达式中调用这些额外的方法,但您仍然可以使用带有点表示法的LINQ.

即使使用并行化,它仍然是O(n).常数因子会有所不同(取决于您的核心数量),但随着n的变化,总时间仍会线性变化.

当然,您可以在自己的数据类型上编写自己的各种LINQ运算符的实现,但它们只适用于非常特定的情况 - 您必须确定谓词仅在优化方面运行数据.例如,如果你有一个按年龄排序的人员列表,它不会帮助你查询试图找到具有特定名称的人:)

要检查谓词,你必须使用表达式树而不是委托,生活将变得更加困难.

我怀疑我通常会添加新的方法,这些方法很明显,您使用的是索引/有序/数据类型的任何性质,并且总是能够正常工作.当然,您无法轻松地从查询表达式中调用这些额外的方法,但您仍然可以使用带有点表示法的LINQ.