중첩 된 위치 (LINQ) 절을 사용하여 배열 반복 최적화

Question

검색 기능이있는 (C#) 도구를 만들고 있습니다. 이 검색은 "ReSharper has or VS2013"과 같이 "어디에서나 이동"검색과 비슷합니다.

검색 컨텍스트 전면까지의 모든 항목을 포함하는 문자열 배열이다

private string[] context; // contains thousands of elements 

검색이 증가하고, 사용자가 제공하는 모든 새로운 입력 (문자)로 발생한다.

내가 확장 방법은 LINQ 사용하여 검색 구현 : "캘리포니아"에 대한 사용자 검색, 내가 검색 컨텍스트로 이전 결과를 사용하려고

// User searched for "c" 
var input = "c"; 
var results = context.Where(s => s.Contains(input)); 

그러나이 원인을 (내가 생각을 ?) 중첩 된 Where 반복 및 매우 잘 실행되지 않습니다. 이 코드와 같은 것을 생각해보십시오.

// Cache these results. 
var results = var results = context.Where(s => s.Contains(input)); 

// Next search uses the previous search results 
var newResults = results.Where(s => s.Contains(input)); 

이 시나리오를 최적화하는 방법이 있습니까?

검색 할 때마다 IEnumerable을 배열로 변환하면 메모리 할당이 높아지고 잘못 실행됩니다.

Answer 1

수천 개의 검색 결과를 사용자에게 제시하는 것은 꽤 쓸모가 없습니다. 결과를 사용자에게 표시하기 전에 쿼리에 "최상위"(linq에 Take) 문을 추가해야합니다.

var results = context.Where(s => s.Contains(input)).Take(100); 

그리고 당신은 사용자에게 다음 (100 개) 결과를 발표 할 경우 :이 더 장점이없는 한

이

var results = context.Where(s => s.Contains(input)).Skip(100).Take(100); 

이

또한 단지 모든 검색어 원래 배열을 사용하여 중첩 된 Where 당신이 을 실현하지 하지 않는 한 쿼리.

Answer 2

alloc가 걱정되는데 trie 구현을 작성하거나 제 3 자 코드를 사용하고 싶지 않은 경우 컨텍스트 배열을 계속 파티셔닝하여 정면에서 일치하는 항목을 묶어야합니다. LINQ-ish는 아니지만 빠르며 메모리 비용이 없습니다. 를 기반으로

파티셔닝 확장 방법, C++의 std::partition

/// <summary> 
/// All elements for which predicate is true are moved to the front of the array. 
/// </summary> 
/// <param name="start">Index to start with</param> 
/// <param name="end">Index to end with</param> 
/// <param name="predicate"></param> 
/// <returns>Index of the first element for which predicate returns false</returns> 
static int Partition<T>(this T[] array, int start, int end, Predicate<T> predicate) 
{ 
    while (start != end) 
    { 
     // move start to the first not-matching element 
     while (predicate(array[start])) 
     { 
      if (++start == end) 
      { 
       return start; 
      } 
     } 

     // move end to the last matching element 
     do 
     { 
      if (--end == start) 
      { 
       return start; 
      } 
     } 
     while (!predicate(array[end])); 

     // swap the two 
     var temp = array[start]; 
     array[start] = array[end]; 
     array[end] = temp; 

     ++start; 
    } 
    return start; 
} 

그래서 지금 당신은 context 길이 초기화해야 마지막 파티션 인덱스, 저장해야하는 각 변경 다음

private int resultsCount = context.Length; 

을 인풋으로 점진적으로 실행할 수 있습니다 :

resultsCount = context.Partition(0, resultsCount, s => s.Contains(input)); 

이 때마다 이전에 필터링되지 않은 요소에 대한 검사 만 수행됩니다. 이는 정확히 사용자가 수행 한 작업입니다.

비 증분 변경마다 resultsCount을 원래 값으로 재설정해야합니다.

당신은 편리하고, 디버거 및 LINQ 친화적 인 방법으로 결과를 표시 할 수 있습니다 : 나는 유용한 점 몇 코멘트 너무 많은 추가 할 수있어

public IEnumerable<string> Matches 
{ 
    get { return context.Take(resultsCount); } 
} 

Answer 3

.

먼저, .take(100)으로 시작해야하는 다른 의견에 동의하며로드 시간을 줄입니다. 더 좋은 시간에 하나 개의 결과를 추가

var results = context.Where(s => s.Contains(input)); 
var resultEnumerator = result.GetEnumerator() 

루프를 resultEnumerator을 통해, 시간에 결과를 표시 정지 화면이 꽉 찼거나 새로운 검색이 시작됩니다.

두 번째로 입력을 줄입니다. 사용자가 Hello을 작성하는 경우 H, He, Hel, Hell 및 Hello에 대해 5 회 검색을 수행하지 않으려는 경우 Hello만을 검색하려고합니다. 사용자가 나중에 world을 추가하면 이전 결과를 가져와 Hello world을 where 절에 추가하는 것이 좋습니다.

results = results.Where(s => s.Contains(input)); 
resultEnumerator = result.GetEnumerator() 

물론 사용자가 새 텍스트를 추가 할 때 진행중인 진행 상황을 취소하십시오. Rx를 사용

은 스로틀 부분은 쉽게,이 같은 것을 얻을 것이다 :

var result = context.AsEnumerable(); 
var oldStr = ""; 
var resultEnumerator = result.GetEnumerator(); 
Observable.FromEventPattern(h => txt.TextChanged += h, h => txt.TextChanged -= h) 
     .Select(s => txt.Text) 
     .DistinctUntilChanged().Throttle(TimeSpan.FromMilliseconds(300)) 
     .Subscribe(s => 
     { 
      if (s.Contains(oldStr)) 
       result = result.Where(t => t.Contains(s)); 
      else 
       result = context.Where(t => t.Contains(s)); 
      resultEnumerator = result.GetEnumerator(); 
      oldStr = s; 
      // and probably start iterating resultEnumerator again, 
      // but perhaps not on this thread. 
     });