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框架中是否已经有函数可以做到相同的事情，并且不仅针对成对元组，而是针对任何大小的元组。我的想法是，应该有一种好的方法来执行这种滑动窗口操作。

我使用的是C# 2.0，我可以想象，通过C# 3.0（使用LINQ），有更多更好的方法来实现此功能，但我主要关注C# 2.0的解决方案。尽管如此，我也会欣赏C# 3.0的解决方案。

- f3lix

---

这似乎可以与Jon Skeet的SmartEnumerator共享很多实现，它可以告诉你一个项目是否是列表中的最后一个。http://msmvps.com/blogs/jon_skeet/archive/2007/07/27/smart-enumerations.aspx - Ben Voigt

参考资料，这个函数在F#中被称为“Windowed”：https://dev59.com/i1_Va4cB1Zd3GeqPSFCU - Benjol

有点相关：使用LINQ获取IEnumerable中的前一个和后一个项。 - Theodor Zoulias

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

- Ian Mercer

---

值得一提的是，这将会对 input 进行两次求值——对于数组来说不是问题，但如果它是惰性求值的，那可能会很昂贵。 - dahlbyk

Zip 的第二个参数可以作为一个方法组传递：...input.Zip(input.Skip(1), Tuple.Create);。 - Jay

我只是用单元测试做了这个，只是为了看看差别。使用Enumerable.Range(0, count)作为迭代器，我不得不将计数增加到大约100万才能注意到延迟，而增加到约1000万时，它才变得足够缓慢，让我感到烦扰。然而，@dahlbyk的解决方案优雅地避免了这个问题，所以我会随时使用它。（扩展方法的整个重点是能够隐藏不易阅读的代码，使其脱离视线，因此在这里的优先级应该是直接明了的...）。 - Tomas Aschan

@Jay，自从2019年.NET Core 3.0发布以来，就有一个重载函数可以完全跳过该参数，因此var result = input.Zip(input.Skip(1));。 - Jeppe Stig Nielsen

Answer 2

不要求使用元组（pair）类型，为什么不直接接受选择器呢：

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

更新：我刚刚在一个真实的项目中实施了这个功能，并使用了C# 7.0的ValueTuple代替：

public static IEnumerable<(T, T)> Pairwise<T>(this IEnumerable<T> source)
{
    var previous = default(T);
    using (var it = source.GetEnumerator())
    {
        if (it.MoveNext())
            previous = it.Current;

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

- dahlbyk

---

在yield return …(previous, previous = …)中，我想知道执行顺序。C#语言是否保证在计算第二个参数之前准备好了第一个参数？ - stakx - no longer contributing

我相当确定它可以，但我必须检查规格以确保。 - dahlbyk

是的，参见C#规范的section 7.4.1。*"在运行时处理函数成员调用时，参数列表中的表达式或变量引用将按从左到右的顺序依次计算，如下所示：..."* - Scott Chamberlain

只是想说一下，我对这个版本进行了一些性能分析，使用Dequeue/Peek和Zip方法的队列。队列方法实际上比GetEnumerator方法快两倍，比Zip快6倍，而且我认为它比两者都更易读。例如： var queue = new Queue<T>(enumerable); while(queue.Count() > 1){ yield return func(queue.Dequeue,queue.Peek); } - Novaterata

非常有趣...你能把你的基准测试发布到Gist或其他地方吗？ - dahlbyk

@Novaterata 那么你的基准测试是有缺陷的。如果使用正确，GetEnumerator() 总是更好。对于具体的 List<T>，您不希望使用其通用枚举器，如我在其他答案中所解释的那样。 - l33t

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

- bradgonesurfing

---

与其强制转换可观察对象，Rx 的交互式扩展伴侣（https://www.nuget.org/packages/ix-main）提供了一个 IEnumerable<T> 版本的 Buffer() 方法：https://github.com/Reactive-Extensions/Rx.NET/blob/2252cb4edbb25aca12005b9a912311edd2f095f3/Ix.NET/Source/System.Interactive/EnumerableEx.Single.cs#L211-L229 - dahlbyk

Answer 4

为了方便起见，这里是@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);
    }
}

- James Holwell

---

我认为这比原来的代码更加简洁。在现代C#中，可以这样使用：foreach (var (previous, next) in Enumerable.Range(0, 10).PairWise()) Console.WriteLine(previous + "-" + next); - Zar Shardan

Answer 5

虽然有一点晚了，但除了所有这些扩展方法外，一个人可以使用实际的“滑动”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));
}

- Sphinxxx

Answer 6

以下是我使用栈的解决方案。它短小精悍。

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

您可以采用相同的概念并使用队列，这样就不需要反转项目，而且更加简单：

var queue = new Queue<string>(items);

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

关于性能的简短说明：

我认为重要的是要意识到，除非你知道一个任务在你的实际应用程序中引起了瓶颈，否则弄清楚最快的执行方式可能没有什么价值。相反，编写完成工作的代码。此外，使用你可以记住的代码，这样下次需要时它就可以轻松地从你的手中流出。

尽管如此，如果您关心一些10,000,000个随机字符串的性能数据：

Run #1
  InputZip             00:00:00.7355567
  PairwiseExtension    00:00:00.5290042
  Stack                00:00:00.6451204
  Queue                00:00:00.3245580
  ForLoop              00:00:00.7808004
  TupleExtension       00:00:03.9661995

Run #2
  InputZip             00:00:00.7386347
  PairwiseExtension    00:00:00.5369850
  Stack                00:00:00.6910079
  Queue                00:00:00.3246276
  ForLoop              00:00:00.8272945
  TupleExtension       00:00:03.9415258

使用Jon Skeet的微基准测试进行了测试。

如果你想查看测试的源代码，请点击这里：gist here

- Postlagerkarte

---

这是非常低效的，特别是如果集合中有大量元素。你的空间复杂度是O(n)，而不是O(1)。你的时间复杂度也是O(n)，与其他解决方案一样，但仍然比一个常数因子慢。 - Zar Shardan

这不是关于过早优化的问题。你正在用更多的代码做比必要更多的工作。这只是糟糕的设计。 - Zar Shardan

好的，这个页面上一些更好的解决方案是通用方法，可以直接使用并复制粘贴到项目中进行一些小的参数检查。而你的只是一个三行的想法。而且不是一个好的想法。你将空间复杂度从非常可接受的O(1)增加到平庸的O(n)，并且在没有任何收益的情况下将执行时间翻倍。 - Zar Shardan

确实，string.format函数影响了结果。我复制/粘贴了原始解决方案，并进行了修复，并将所有类型更改为ValueTuple（很好的建议），还切换了测试以使用James Holwell的解决方案。看着结果，我不认为称任何给定的解决方案为“低效”是公平的。 - Postlagerkarte

为你测试的努力点赞。但我仍然不喜欢你的O(n)空间解决方案 :D - Zar Shardan

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

- Tim Earley

Answer 8

类似这样：

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

- Quiz

Answer 9

扩展 之前的回答，通过显式使用传递的迭代器来避免 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" 并作为静态方法调用。

- Richard

---

这段代码并不能返回问题所要求的结果。 Enumerable.Range(1, 5).Tuples(2) 返回的是 {{1, 2}, {3, 4}, {5}} ，而不是所期望的滑动窗口 {{1, 2}, {2, 3}, {3, 4}, {4, 5}}。 - Sammy S.

Answer 10

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 版本。尽管如此，它仍然没有高效。

- mqp

---

性能不佳？这是一个O(n*n)的实现！对于一个仅包含10个项目的小列表，整个列表被遍历了20次。 - configurator

这是正确的，但这只有两行（真正的）代码，并且显然是一个简单的实现。这取决于 OP 是否需要快速解决方案 - 也许他只需要对几十个项目的列表执行此操作。 - mqp