Kann jemand eine bessere Version dieses Enumerators finden?

Question

Ich bin ziemlich glücklich mit der folgenden Methode. Es benötigt eine Aufzählung und eine Liste von sortierten, disjunkten Bereichen und überspringt Objekte, die nicht in den Bereichen liegen. Wenn die Bereiche Null sind, gehen wir einfach jeden Gegenstand. Die Aufzählung und die Liste der Bereiche sind beide möglicherweise groß. Wir möchten, dass diese Methode so leistungsstark wie möglich ist.

Kann jemand an ein eleganteres Stück Code denken? Ich bin hauptsächlich an C# -Implementierungen interessiert, aber wenn jemand eine dreistellige APL-Implementierung hat, ist das auch cool.

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

Vielleicht Linq auf source so etwas wie verwenden:

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(); 
} 

Ich habe nicht meinen Windows-PC vor mir und ich bin nicht sicher, ob ich den Code richtig verstanden hat, aber ich versuchte, um stattdessen Ihren Text zu verstehen und der obige Code könnte funktionieren .... oder so ähnlich.

AKTUALISIERT: In Bezug auf das Leistungsproblem würde ich Ihnen empfehlen, die Leistung mit einigen einfachen Test- und Zeitfunktionen zu testen.

Answer 2

Sie können die Quellliste in ein Array kopieren und dann für jeden Bereich die Kopie von Ihrem neuen Quell-Array zu einem Ziel-Array an der richtigen Stelle blockieren. Wenn Sie Ihre Quellensammlung als Array übergeben können, wäre dies ein noch besserer Ansatz. Wenn Sie die erste Kopie erstellen müssen, ist dies O (N) für diese Operation plus O (M), wobei M die Gesamtzahl der Elemente im endgültigen Array ist. Also kommt es in jedem Fall zu O (N).

Answer 3

Hier ist meine Aufnahme. Ich finde es leichter zu verstehen, wenn nicht eleganter.

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

Wie wäre es damit (ungetestet)? Sollte haben ziemlich ähnliche Leistungsmerkmale (reines Streaming, keine unnötige Pufferung, schnellen Ausstieg), ist aber einfacher zu folgen, 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; 
      } 
     } 
    } 
} 

Wenn Sie keine Pufferung Indizes dagegen haben, Sie so etwas wie dies tun können, was IMO ist noch klarer,:

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

Sie über die Auflistung durchlaufen könnte manuell den Enumerator zu verhindern, dass das aktuelle Element bekommen, wenn sie übersprungen werden:

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

Mein zweiter Versuch, dies wird die Reihenfolge der Bereiche berücksichtigen. Ich habe es noch nicht ausprobiert, aber ich denke, es funktioniert :). Sie könnten möglicherweise einen Teil des Codes in kleinere Funktionen extrahieren, um ihn lesbarer zu machen.

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 
    } 
}