我最近开始使用LINQ了,我还没有真正看到任何LINQ方法的运行时复杂性.显然,这里有很多因素在起作用,所以让我们将讨论局限于普通的IEnumerableLINQ-to-Objects提供者.此外,假设任何Func作为选择器/ mutator /等传入的是廉价的O(1)操作.
它似乎很明显,所有的单次操作(Select,Where,Count,Take/Skip,Any/All,等)将是O(n)的,因为他们只需要步行的顺序一次; 虽然这甚至会受到懒惰的影响.
对于更复杂的操作来说,事情变得更加模糊; 集合类运算符(Union,Distinct,Except等)使用工作GetHashCode在默认情况下(据我所知),所以它似乎是合理的假设他们使用一个哈希表内,使这些操作为O(n)为好,一般.使用的版本怎么样IEqualityComparer？
OrderBy需要排序,所以很可能我们正在看O(n log n).如果它已经排序了怎么办？如果我说OrderBy().ThenBy()并为两者提供相同的密钥怎么样？
我可以看到GroupBy(和Join)使用排序或散列.这是什么？
Contains将是O(n)on a List,但是O(1)on a HashSet- LINQ检查底层容器以查看它是否可以加快速度？
真正的问题 - 到目前为止,我一直坚信运营是高效的.但是,我可以依靠吗？例如,STL容器清楚地指定了每个操作的复杂性..NET库规范中的LINQ性能是否有类似的保证？
更多问题(回应评论):
没有真正想过开销,但我没想到对于简单的Linq-to-Objects有很多.CodingHorror帖子讨论的是Linq-to-SQL,在那里我可以理解解析查询并使SQL增加成本 - 对象提供者也有类似的成本吗？如果是这样,如果您使用声明性或功能性语法,它会有所不同吗？