누군가이 열거 자의 더 나은 버전을 생각해 낼 수 있습니까?

Question

다음과 같은 방법으로 매우 만족합니다. 열거 형 및 정렬 된 분리 된 범위의 목록을 사용하고 범위에없는 항목을 건너 뜁니다. 범위가 null 인 경우 모든 항목을 그냥 걷습니다. 열거 가능 영역과 범위 목록은 모두 커질 수 있습니다. 이 방법은 가능한 한 높은 성능을 원합니다.

누가 좀 더 우아한 코드를 생각해 낼 수 있습니까? 나는 주로 C# 구현에 관심이 있지만 누군가가 3 글자로 APL을 구현했다면 멋지다. 나는 내 앞에 내 Windows PC가없는

public static IEnumerable<T> WalkRanges<T>(IEnumerable<T> source, List<Pair<int, int>> ranges) 
{ 
    if(ranges == null) 
     return null; 
    return source.Where((item, index) => ranges.Any(y => y.First < index && y.Second > index)).AsEnumerable(); 
} 

그리고 내가 제대로 코드를 이해 모르겠지만, 시도 :

public static IEnumerable<T> WalkRanges<T>(IEnumerable<T> source, List<Pair<int, int>> ranges) 
{ 
    Debug.Assert(ranges == null || ranges.Count > 0); 

    int currentItem = 0; 
    Pair<int, int> currentRange = new Pair<int, int>(); 
    int currentRangeIndex = -1; 
    bool betweenRanges = false; 
    if (ranges != null) 
    { 
     currentRange = ranges[0]; 
     currentRangeIndex = 0; 
     betweenRanges = currentRange.First > 0; 
    } 

    foreach (T item in source) 
    { 
     if (ranges != null) { 
      if (betweenRanges) { 
       if (currentItem == currentRange.First) 
        betweenRanges = false; 
       else { 
        currentItem++; 
        continue; 
       } 
      } 
     } 

     yield return item; 

     if (ranges != null) { 
      if (currentItem == currentRange.Second) { 
       if (currentRangeIndex == ranges.Count - 1) 
        break; // We just visited the last item in the ranges 

       currentRangeIndex = currentRangeIndex + 1; 
       currentRange = ranges[currentRangeIndex]; 
       betweenRanges = true; 
      } 
     } 

     currentItem++; 
    } 
} 

Answer 1

아마처럼 source 뭔가 LINQ를 사용 대신 텍스트를 이해하고 위의 코드가 작동 할 수 있습니다.

업데이트 : 성능 문제와 관련하여 몇 가지 간단한 테스트와 두 가지 기능으로 성능을 테스트 해 보시기 바랍니다.

Answer 2

원본 목록을 배열에 복사 한 다음 각 범위에 대해 새 원본 배열에서 적절한 위치의 대상 배열로 복사를 차단할 수 있습니다. 소스 컬렉션을 배열로 전달할 수 있다면 더 나은 접근 방식이 될 것입니다. 초기 사본을 작성해야하는 경우 O (N)에 O (M)를 더한 것입니다. 여기서 M은 최종 배열의 항목 수입니다. 그래서 두 경우 모두 O (N)로 나옵니다.

Answer 3

다음은 필자의 것입니다. 좀 더 우아하지 않다면 이해하기가 더 쉽습니다.

public static IEnumerable<T> WalkRanges<T>(IEnumerable<T> source, List<Tuple<int, int>> ranges) 
{ 
    if (ranges == null) 
     return source; 

    Debug.Assert(ranges.Count > 0); 
    return WalkRangesInternal(source, ranges); 
} 

static IEnumerable<T> WalkRangesInternal<T>(IEnumerable<T> source, List<Tuple<int, int>> ranges) 
{ 
    int currentItem = 0; 
    var rangeEnum = ranges.GetEnumerator(); 
    bool moreData = rangeEnum.MoveNext(); 

    using (var sourceEnum = source.GetEnumerator()) 
     while (moreData) 
     { 
      // skip over every item in the gap between ranges 
      while (currentItem < rangeEnum.Current.Item1 
       && (moreData = sourceEnum.MoveNext())) 
       currentItem++; 
      // yield all the elements in the range 
      while (currentItem <= rangeEnum.Current.Item2 
       && (moreData = sourceEnum.MoveNext())) 
      { 
       yield return sourceEnum.Current; 
       currentItem++; 
      } 
      // advance to the next range 
      moreData = rangeEnum.MoveNext(); 
     } 
} 

Answer 4

어때요 (테스트 안 함)? IMO, 따라 매우 유사한 성능 특성 (순수 스트리밍, 불필요한 버퍼링, 빠른 출구)를 가지고 있지만 쉽게해야 : 당신이 인덱스를 버퍼링 괜찮다면, 당신은 같은 것을 할 수

public static IEnumerable<T> WalkRanges<T>(IEnumerable<T> source, 
              List<Pair<int, int>> ranges) 
{ 
    if (source == null) 
     throw new ArgumentNullException("source"); 

    // If ranges is null, just return the source. From spec. 
    return ranges == null ? source : RangeIterate(source, ranges); 
} 

private static IEnumerable<T> RangeIterate<T>(IEnumerable<T> source, 
               List<Pair<int, int>> ranges) 
{ 
    // The key bit: a lazy sequence of all valid indices belonging to 
    // each range. No buffering. 
    var validIndices = from range in ranges 
         let start = Math.Max(0, range.First) 
         from validIndex in Enumerable.Range(start, range.Second - start + 1) 
         select validIndex; 

    int currentIndex = -1; 

    using (var indexErator = validIndices.GetEnumerator()) 
    { 
     // Optimization: Get out early if there are no ranges. 
     if (!indexErator.MoveNext()) 
      yield break; 

     foreach (var item in source) 
     { 
      if (++currentIndex == indexErator.Current) 
      { 
       // Valid index, yield. 
       yield return item; 

       // Move to the next valid index. 
       // Optimization: get out early if there aren't any more. 
       if (!indexErator.MoveNext()) 
        yield break; 
      } 
     } 
    } 
} 

, 어떤 IMO, 더 명확 :

public static IEnumerable<T> WalkRanges<T>(IEnumerable<T> source, 
              List<Pair<int, int>> ranges) 
{ 
    if (source == null) 
     throw new ArgumentNullException("source"); 

    if (ranges == null) 
     return source; 

    // Optimization: Get out early if there are no ranges.  
    if (!ranges.Any()) 
     return Enumerable.Empty<T>(); 

    var validIndices = from range in ranges 
         let start = Math.Max(0, range.First) 
         from validIndex in Enumerable.Range(start, range.Second - start + 1) 
         select validIndex; 

    // Buffer the valid indices into a set. 
    var validIndicesSet = new HashSet<int>(validIndices); 

    // Optimization: don't take an item beyond the last index of the last range. 
    return source.Take(ranges.Last().Second + 1) 
       .Where((item, index) => validIndicesSet.Contains(index)); 

} 

Answer 5

당신은 그것을 생략 할 때 수동으로 현재 항목을 얻기에서 열거를 방지하기 위해 컬렉션을 반복 할 수

:

public static IEnumerable<T> WalkRanges<T>(IEnumerable<T> source, List<Pair<int, int>> ranges) 
{ 
    Debug.Assert(ranges == null || ranges.Count > 0); 

    int currentItem = 0; 
    Pair<int, int> currentRange = new Pair<int, int>(); 
    int currentRangeIndex = -1; 
    bool betweenRanges = false; 
    if (ranges != null) 
    { 
     currentRange = ranges[0]; 
     currentRangeIndex = 0; 
     betweenRanges = currentRange.First > 0; 
    } 

    using (IEnumerator<T> enumerator = source.GetEnumerator()) 
    { 
     while (enumerator.MoveNext()) 
     { 

      if (ranges != null) 
      { 
       if (betweenRanges) 
       { 
        if (currentItem == currentRange.First) 
         betweenRanges = false; 
        else 
        { 
         currentItem++; 
         continue; 
        } 
       } 
      } 

      yield return enumerator.Current; 

      if (ranges != null) 
      { 
       if (currentItem == currentRange.Second) 
       { 
        if (currentRangeIndex == ranges.Count - 1) 
         break; // We just visited the last item in the ranges 

        currentRangeIndex = currentRangeIndex + 1; 
        currentRange = ranges[currentRangeIndex]; 
        betweenRanges = true; 
       } 
      } 

      currentItem++; 
     } 
    } 
} 

Answer 6

두 번째 시도에서 범위의 순서를 고려합니다. 나는 피난처가 아직 시도했지만 그것이 작동한다고 생각합니다 :). 좀 더 쉽게 읽을 수 있도록 코드 중 일부를 더 작은 함수로 추출 할 수 있습니다.

public static IEnumerable<T> WalkRanges<T>(IEnumerable<T> source, List<Pair<int, int>> ranges) 
{ 
    int currentIndex = 0; 
    int currentRangeIndex = 0; 
    int maxRangeIndex = ranges.Length; 
    bool done = false; 
    foreach(var item in source) 
    { 
     if(currentIndex > range[currentRangeIndex].Second) 
     { 
      while(currentIndex > range[currentRangeIndex].Second) 
      { 
       if(!++currentRangeIndex < maxRangeIndex) 
       { 
        // We've passed last range => 
        // set done = true to break outer loop and then break 
        done = true; 
        break; 
       } 
      } 
      if(currentIndex > range[currentRangeIndex].First) 
       yield item; // include if larger than first since we now it's smaller than second 
     } 
     else if(currentIndex > range[currentRangeIndex].First) 
     { 
      // If higher than first and lower than second we're in range 
      yield item; 
     } 
     if(done) // if done break outer loop 
      break; 

     currentIndex++; // always increase index when advancint through source 
    } 
}