2

私は次の方法にかなり満足しています。それは列挙可能でソートされた互いに素な範囲のリストを取り、範囲内にないアイテムをスキップします。範囲がnullの場合、すべてのアイテムをウォークします。列挙可能な範囲と範囲のリストは両方とも大きい可能性があります。この方法を可能な限り高性能にする必要があります。

誰かがもっとエレガントなコードを思いつくことができますか？私は主にC＃の実装に興味がありますが、誰かが3文字のAPL実装を持っているのであれば、それもすばらしいことです。

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++;
    }
}
4

6 に答える 6

0

コレクションを手動で反復処理して、列挙子がスキップされるときに現在のアイテムを取得しないようにすることができます。

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++;
        }
    }
}
于 2010-11-24T20:50:16.513 に答える
0

多分あなたのようなものにlinqを使用してくださいsource：

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

目の前に Windows PC がなく、あなたのコードを正しく理解しているかどうかわかりませんが、代わりにあなたのテキストを理解しようとしました。

更新:パフォーマンスの問題に関しては、いくつかの簡単なテストと時間の両方の機能でパフォーマンスをテストすることをお勧めします。

于 2010-11-24T20:26:59.740 に答える
0

ソース リストを配列にコピーしてから、範囲ごとに、新しいソース配列から適切な場所にあるターゲット配列へのブロック コピーを行うことができます。ソース コレクションを配列として渡すことができれば、これはさらに優れたアプローチになります。最初のコピーを実行する必要がある場合は、その操作の O(N) に O(M) を加えたものになります。ここで、M は最終的な配列内のアイテムの総数です。したがって、いずれの場合も O(N) になります。

于 2010-11-24T20:40:06.277 に答える
0

2 回目の試行では、範囲の順序を考慮します。まだ試していませんが、うまくいくと思います:)。コードの一部を小さな関数に抽出して、読みやすくすることができます。

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
    }
}
于 2010-11-24T22:38:49.357 に答える
0

これが私の見解です。よりエレガントではないにしても、理解しやすいと思います。

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();
        }
}
于 2010-11-24T20:47:13.973 に答える
0

これはどうですか（未テスト）？かなり類似したパフォーマンス特性 (純粋なストリーミング、不要なバッファリングなし、迅速な終了) を持つ必要がありますが、従うのは簡単です、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));

}
于 2010-11-24T20:48:45.050 に答える