사전 검색 (O (1)) vs Linq 여기서

Question

무엇이 빠르며 속도를 높이기 위해 Linq 표준을 희생해야합니까? (사전 조회가 실제로 더 빠름을 가정 할 때)? 그래서 제가 정성 들여 보자

을 나는 다음과 같은 한 :

List<Product> products = GetProductList(); 

내가 예를 들어, 일부 속성을 기반으로 제품을 검색 할 필요 일련 번호가 있습니다. 내가 먼저 사전을 만든 다음 다음과 같이 그것을 채울 수 :

Dictionary<string, Product> dict = new Dictionary<string, Product>(); 
foreach(Product p in products) 
{ 
    dict.Add(p.serial, p); 
} 

는, 제품 검색 O를 활용하는 시간

(1) 사전 룩업에 의해 제공 :

string some_serial = ...; 
try { Product p = dict[some_serial]; } catch(KeyNotFoundException) { } 

Linq에를 사용 또는

는 :

DICT 방법의 단점은 물론이다

Product p = products.Where(p => p.serial.Equals(some_serial)).FirstOrDefault(); 

이 (이것의 대부분은 논쟁의 여지가 있지만) 등 더 많은 메모리 공간, 쓸 수있는 더 많은 코드 덜 우아한 필요합니다. 그것이 비 요소라고 가정합니다. 첫 번째 접근 방식을 취해야합니까?

결론적으로, 나는 위의 Linq 접근법의 복잡성이 실제로 O (n)인지 그리고 그것이 그보다 나은 방법은 없는지 확인하고 싶습니다.

Answer 1

당신이 객체의 열거로 시작하고 한 번만하고있는 가정 ...

백업을 찾고 다음 Dictionary<TKey,TValue>에 추가하고 반대로 Where 방법을 수행하는 빠른 것입니다. 이유는 사전 방법이 이 아니라 O (1)이기 때문입니다. 이 시나리오에서는 항목을 사전에 추가 한 다음 찾고 있습니다. 추가 부분은 추가 메모리 오버 헤드가있는 Where 메서드와 마찬가지로 비싸지 만 O (N)입니다.

주의해야 할 또 다른 사소한 점은 Dictionary<TKey,TValue>이 진정한 O (1)가 아니라는 것입니다. 대신 O (1)에 접근하지만 특정 상황 (예를 들어 충돌 키가 많음)에서 성능이 저하 될 수 있습니다.