O(n) 성능보다 나은 객체에 대한 IQuerable<T>?

Question

myEnumerable.AsQueriable()을 호출할 때 얻을 수 있는 기본 O(n) 선형 검색 성능보다 더 나은 성능을 발휘하는 linq-to-object에 대한 IQueriaable 구현이 있습니까?

나는 살펴 봤다 http://www.codeplex.com/i4o/ 성능은 더 좋지만 IndexedCollection에서 IQueriable을 구현하는 대신 IndexedCollection에서 확장 메서드를 사용하는 것 같습니다.

나는 인터페이스가 IQueriable<T>을 반환하도록 유지하고 싶습니다. 캐시나 DB에 도달했는지 다른 사람이 알기를 원하지 않기 때문입니다.

Answer 1

기본적으로 인덱싱되지 않은 리소스(예: 목록 또는 IEnumerable)에 대한 쿼리는 조건을 확인하기 위해 목록의 모든 항목을 반복해야 하기 때문에 기껏해야 O(n)이 됩니다.O(n)보다 더 나은 성능을 얻으려면 어떤 형식으로든 데이터 인덱싱을 조사해야 합니다.

언급한 대로 특히 IQueryable만 노출하려는 경우 이러한 인덱스 생성을 마무리하기 위해 라이브러리를 살펴보는 것이 좋습니다.

더 나은 성능으로 데이터를 검색하는 보다 수동적인 방법에 관심이 있다면 키별로 효율적인 검색을 수행하기 위한 사전을 살펴보거나 범위 쿼리를 수행해야 하는 경우 B-트리를 사용하는 것이 좋습니다. 여기 좋은 MSDN이 있습니다. 그 뒤에 있는 이론에 관심이 있다면 b-트리를 포함한 데이터 구조에 대해 게시하세요.또한, 엔제네릭스 볼만한 흥미로운 프로젝트가 될 수 있습니다.

Answer 2

plinq를 살펴보고 싶을 수도 있습니다. http://msdn.microsoft.com/en-us/magazine/cc163329.aspx

Answer 3

또 다른 대답은 다음과 같은 메모리 객체 데이터베이스로 이를 뒷받침하는 것입니다. db4o