Попарная итерация в C # или перечислителе скользящего окна

Question

Если у меня есть IEnumerable вроде:

string[] items = new string[] { "a", "b", "c", "d" };

Я бы хотел пройти через все пары последовательных элементов (скользящее окно размера 2). Который будет

("a","b"), ("b", "c"), ("c", "d")

Мое решение было это

    public static IEnumerable<Pair<T, T>> Pairs(IEnumerable<T> enumerable) {
        IEnumerator<T> e = enumerable.GetEnumerator(); e.MoveNext();
        T current = e.Current;
        while ( e.MoveNext() ) {
            T next = e.Current;
            yield return new Pair<T, T>(current, next);
            current = next;
        }
    }

 // used like this :
 foreach (Pair<String,String> pair in IterTools<String>.Pairs(items)) {
    System.Out.PrintLine("{0}, {1}", pair.First, pair.Second)
 }

Когда я писал этот код, мне было интересно, есть ли уже функции в .NET Framework, которые делают то же самое и делают это не только для пар, но и для кортежей любого размера. ИМХО, должен быть хороший способ сделать этот вид операций со скользящим окном.

Я использую C # 2.0 и могу представить, что в C # 3.0 (с LINQ) есть более (и более приятные) способы сделать это, но в первую очередь меня интересуют решения C # 2.0. Хотя я также буду признателен за решения C # 3.0.

Answer 1

В .NET 4 это становится еще проще: -

var input = new[] { "a", "b", "c", "d", "e", "f" };
var result = input.Zip(input.Skip(1), (a, b) => Tuple.Create(a, b));

Answer 2

Вместо того, чтобы требовать тип кортежа (пары), почему бы просто не принять селектор:

public static IEnumerable<TResult> Pairwise<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TSource, TResult> resultSelector)
{
    TSource previous = default(TSource);

    using (var it = source.GetEnumerator())
    {
        if (it.MoveNext())
            previous = it.Current;

        while (it.MoveNext())
            yield return resultSelector(previous, previous = it.Current);
    }
}

Что позволяет пропустить промежуточный объект, если вы хотите:

string[] items = new string[] { "a", "b", "c", "d" };
var pairs = items.Pairwise((x, y) => string.Format("{0},{1}", x, y));

foreach(var pair in pairs)
    Console.WriteLine(pair);

Или вы можете использовать анонимный тип:

var pairs = items.Pairwise((x, y) => new { First = x, Second = y });

Answer 3

Самый простой способ - использовать ReactiveExtensions

using System.Reactive;
using System.Reactive.Linq;

и создайте себе метод расширения, чтобы объединить это вместе

public static IEnumerable<IList<T>> Buffer<T>(this IEnumerable<T> seq, int bufferSize, int stepSize)
{
    return seq.ToObservable().Buffer(bufferSize, stepSize).ToEnumerable();
}

Answer 4

Немного опоздал на вечеринку, но в качестве альтернативы всем этим методам расширения можно использовать фактический "скользящий" Collection для хранения (и отбрасывания) данных.

Вот один, который я сделал сегодня:

public class SlidingWindowCollection<T> : ICollection<T>
{
    private int _windowSize;
    private Queue<T> _source;

    public SlidingWindowCollection(int windowSize)
    {
        _windowSize = windowSize;
        _source = new Queue<T>(windowSize);
    }

    public void Add(T item)
    {
        if (_source.Count == _windowSize)
        {
            _source.Dequeue();
        }
        _source.Enqueue(item);
    }

    public void Clear()
    {
        _source.Clear();
    }

    ...and just keep forwarding all other ICollection<T> methods to _source.
}

Использование:

int pairSize = 2;
var slider = new SlidingWindowCollection<string>(pairSize);
foreach(var item in items)
{
    slider.Add(item);
    Console.WriteLine(string.Join(", ", slider));
}

Answer 5

Просто для удобства, вот вариант ответа @ dahlbyk без селектора.

public static IEnumerable<Tuple<T, T>> Pairwise<T>(this IEnumerable<T> enumerable)
{
    var previous = default(T);

    using (var e = enumerable.GetEnumerator())
    {
        if (e.MoveNext())
            previous = e.Current;

        while (e.MoveNext())
            yield return Tuple.Create(previous, previous = e.Current);
    }
}

Answer 6

Расширение на предыдущий ответ , чтобы избежать подхода O (n ² ), явно используя переданный итератор:

public static IEnumerable<IEnumerable<T>> Tuples<T>(this IEnumerable<T> input, int groupCount) {
  if (null == input) throw new ArgumentException("input");
  if (groupCount < 1) throw new ArgumentException("groupCount");

  var e = input.GetEnumerator();

  bool done = false;
  while (!done) {
    var l = new List<T>();
    for (var n = 0; n < groupCount; ++n) {
      if (!e.MoveNext()) {
        if (n != 0) {
          yield return l;
        }
        yield break;
      }
      l.Add(e.Current);
    }
    yield return l;
  }
}

Для C # 2 перед методами расширения удалите «this» из входного параметра и вызовите как статический метод.

Answer 7

Простите, если я что-то упускаю, но почему не что-то простое, например, цикл for?:

public static List <int []> ListOfPairs (int [] items)
{
    List <int> output = new List <int>();
    for (int i=0; i < items.Length-1; i++)
    {
        Int [] pair = new int [2];
        pair [0]=items [i];
        pair [1]=items [i+1];
        output.Add (pair);
    }
    return output;
}

Answer 8

Вот мое решение с использованием стека. Это коротко и кратко.

string[] items = new string[] { "a", "b", "c", "d" };

Stack<string> stack = new Stack<string>(items.Reverse());

while(stack.Count > 1)
{
  Console.WriteLine("{0},{1}", stack.Pop(), stack.Peek());
}

Answer 9

C # 3.0 решение (извините:)

public static IEnumerable<IEnumerable<T>> Tuples<T>(this IEnumerable<T> sequence, int nTuple)
{
    if(nTuple <= 0) throw new ArgumentOutOfRangeException("nTuple");

    for(int i = 0; i <= sequence.Count() - nTuple; i++)
        yield return sequence.Skip(i).Take(nTuple);
}

Это не самый производительный в мире, но на него приятно смотреть.

Действительно, единственное, что делает это решение на C # 3.0, - это конструкция .Skip.Take, поэтому, если вы просто измените ее, добавив вместо этого элементы из этого диапазона в список, она должна быть золотой для 2.0. Тем не менее, он по-прежнему не работает.

Answer 10

Примерно так:

public static IEnumerable<TResult> Pairwise<T, TResult>(this IEnumerable<T> enumerable, Func<T, T, TResult> selector)
{
    var previous = enumerable.First();
    foreach (var item in enumerable.Skip(1))
    {
        yield return selector(previous, item);
        previous = item;
    }
}