IQueriable <T> for objects with better O (n) performance?

Question

Are there any IQueriable implementations for linq-to-objects that work better than the default linear search performance O (n) that you get when you call myEnumerable.AsQueriable ()?

I looked at http://www.codeplex.com/i4o/ , which has better performance, but seems to rely on using extension methods on IndexedCollection, rather than making IndexedColleciton implement IQueriable.

I try to have my interface return an IQueriable <T> since I do not want anyone to know if they get into the cache or db.

Answer 1

In any case, any request to a non-indexed resource (such as a list or IEnumerable) will be O (n) at best, because it must iterate over each item in the list to check the condition. To achieve better performance than O (n), you need to look at indexing data in one form or another.

As you mentioned, you probably want to look at the library to complete the creation of these indexes, especially if you only want to expose IQueryable.

If you were interested in a more manual way of searching for data with better performance, I would suggest looking at dictionaries for efficient key searches or, possibly, using b-trees if you need to make range queries. Here's a good MSDN post about data structures, including b-trees, if you're interested in the theory behind it. In addition, NGenerics can be an interesting project to watch.

Answer 2

you can look at plinq http://msdn.microsoft.com/en-us/magazine/cc163329.aspx

Answer 3

Another answer might be to support it in a database of memory objects, for example: db4o