IQueriable<T> для объектов с производительностью лучше чем O(n)?

Question

Существуют ли какие-либо реализации IQueriable для linq-to-objects, которые работают лучше, чем производительность линейного поиска по умолчанию O(n), которую вы получаете при вызове myEnumerable.AsQueriable()?

Я взглянул на http://www.codeplex.com/i4o/ который имеет лучшую производительность, но, похоже, полагается на использование методов расширения в IndexedCollection, а не на то, чтобы IndexedColleciton реализовывал IQueriable.

Я стараюсь, чтобы мой интерфейс возвращал IQueriable, поскольку я не хочу, чтобы кто-либо знал, поражают ли они кеш или дб.

Answer 1

По сути, любой запрос неиндексированного ресурса (такого как список или IEnumerable) будет в лучшем случае O(n), потому что он должен перебирать каждый элемент в списке, чтобы проверить условие. Чтобы достичь производительности лучше, чем O(n), вам нужно взглянуть на индексирование данных в той или иной форме.

Как вы упомянули, вы, вероятно, захотите взглянуть на библиотеку, чтобы завершить создание этих индексов, особенно если вы хотите предоставить только IQueryable.

Если вы заинтересованы в более ручном способе поиска данных с более высокой производительностью, то я бы посоветовал посмотреть в словарях для эффективного поиска по ключам или, возможно, использовать b-деревья, если вам нужно выполнить диапазонные запросы. Вот хороший пост MSDN о структурах данных, включая b-деревья, если вам интересна теория, лежащая в его основе. Кроме того, NGenerics может быть интересным проектом.

Answer 2

Возможно, вы захотите взглянуть на plinq http://msdn.microsoft.com/en-us/magazine/cc163329.aspx

Answer 3

Другим ответом может быть поддержка базы данных объектов в памяти, например: db4o