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

Question

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

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

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

Answer 1

Вы можете посмотреть на plinq http://msdn.microsoft.com/en-us/magazine/cc163329.aspx

Answer 2

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

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

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

Answer 3

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