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

Question

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

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

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

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