linq-to-objects - 可查询的对于性能优于 O(n) 的对象？

Question

是否有任何用于 linq-to-objects 的 IQueriable 实现比调用 myEnumerable.AsQueriable() 时获得的默认 O(n) 线性搜索性能更好？

我看过http://www.codeplex.com/i4o/它有更好的性能，但似乎依赖于在 IndexedCollection 上使用扩展方法，而不是让 IndexedColleciton 实现 IQueriable。

我很想保持我的界面返回 IQueriable<T> 因为我不希望任何人知道他们是在访问缓存还是数据库。

score 1 · Accepted Answer

1

于 2008-09-18T18:55:03.770 回答

score 0 · Accepted Answer

0

另一个答案可能是通过内存对象数据库来支持它，例如：db4o

于 2008-09-19T13:49:50.040 回答

score 0 · Accepted Answer

本质上，对非索引资源（例如列表或 IEnumerable）的任何查询最多只能是 O(n)，因为它必须遍历列表中的每个项目以检查条件。为了获得比 O(n) 更好的性能，您需要考虑以某种形式对数据进行索引。

正如您所提到的，您可能希望查看一个库来结束创建这些索引，特别是如果您只想公开 IQueryable。

如果您对一种更手动的方式来查找具有更好性能的数据感兴趣，那么我建议您查看字典以通过键进行有效查找，或者如果您需要进行范围查询，则可能使用 b-trees。如果您对背后的理论感兴趣，这里有一篇关于数据结构（包括 b 树）的精彩 MSDN帖子。此外，NGenerics可能是一个值得关注的有趣项目。

3 回答 3