IQueriable<T> per oggetti con prestazioni migliori di O(n)?

Question

Esistono implementazioni IQueriable per linq-to-objects che offrono prestazioni migliori rispetto alle prestazioni di ricerca lineare O(n) predefinite che si ottengono quando si chiama myEnumerable.AsQueriable()?

Ho dato un'occhiata http://www.codeplex.com/i4o/ che ha prestazioni migliori, ma sembra fare affidamento sull'uso di metodi di estensione su IndexedCollection piuttosto che fare in modo che IndexedColleciton implementi IQueriable.

Desidero che la mia interfaccia restituisca IQueriable<T> poiché non voglio che nessuno sappia se sta colpendo una cache o un db.

Answer 1

Intrinsecamente, qualsiasi query di una risorsa non indicizzata (come un elenco o IEnumerable) sarà nella migliore delle ipotesi O(n) perché deve scorrere ogni elemento nell'elenco per verificare la condizione.Per ottenere prestazioni migliori di O(n) è necessario esaminare l'indicizzazione dei dati in qualche forma.

Come hai detto, probabilmente vorrai dare un'occhiata a una libreria per concludere la creazione di questi indici, soprattutto se vuoi esporre solo IQueryable.

Se fossi interessato a un modo più manuale di cercare dati con prestazioni migliori, suggerirei di consultare i dizionari per eseguire ricerche efficienti per chiave o eventualmente di utilizzare b-tree se è necessario eseguire query di intervallo. Ecco un bel MSDN pubblica su strutture dati inclusi b-tree se sei interessato alla teoria alla base.Anche, NGenerics potrebbe essere un progetto interessante a cui guardare.

Answer 2

potresti dare un'occhiata a plinq http://msdn.microsoft.com/en-us/magazine/cc163329.aspx

Answer 3

Un'altra risposta potrebbe essere quella di supportarlo con un database di oggetti in memoria come: db4o