Pair-wise iteration in C# or sliding window enumerator
C#.NetIteratorIenumerableC# Problem Overview
If I have an IEnumerable like:
string[] items = new string[] { "a", "b", "c", "d" };
I would like to loop thru all the pairs of consecutive items (sliding window of size 2). Which would be
("a","b"), ("b", "c"), ("c", "d")
My solution was is this
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)
}
When I wrote this code, I wondered if there are already functions in the .NET framework that do the same thing and do it not just for pairs but for any size tuples. IMHO there should be a nice way to do this kind of sliding window operations.
I use C# 2.0 and I can imagine that with C# 3.0 (w/ LINQ) there are more (and nicer) ways to do this, but I'm primarily interested in C# 2.0 solutions. Though, I will also appreciate C# 3.0 solutions.
C# Solutions
Solution 1 - C#
In .NET 4 this becomes even easier:-
var input = new[] { "a", "b", "c", "d", "e", "f" };
var result = input.Zip(input.Skip(1), (a, b) => Tuple.Create(a, b));
Solution 2 - C#
Rather than require a tuple (pair) type, why not just accept a selector:
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);
}
}
Which allows you to skip the intermediate object if you want:
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);
Or you can use an anonymous type:
var pairs = items.Pairwise((x, y) => new { First = x, Second = y });
Update: I just implemented this on a real project and used C# 7.0 ValueTuple
instead:
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);
}
}
Solution 3 - C#
The easiest way is to use ReactiveExtensions
using System.Reactive;
using System.Reactive.Linq;
and make yourself an extension method to kit bash this together
public static IEnumerable<IList<T>> Buffer<T>(this IEnumerable<T> seq, int bufferSize, int stepSize)
{
return seq.ToObservable().Buffer(bufferSize, stepSize).ToEnumerable();
}
Solution 4 - C#
Just for convenience, here is a selector-less version of @dahlbyk's answer.
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);
}
}
Solution 5 - C#
A little late to the party, but as an alternative to all these extension methods, one might use an actual "sliding" Collection
to hold (and discard) the data.
Here is one I ended up making today:
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.
}
Usage:
int pairSize = 2;
var slider = new SlidingWindowCollection<string>(pairSize);
foreach(var item in items)
{
slider.Add(item);
Console.WriteLine(string.Join(", ", slider));
}
Solution 6 - C#
Here is my solution using a Stack. It is short and concise.
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());
}
You can take the same concept and use a queue which avoids the need for reversing the items and is even simpler:
var queue = new Queue<string>(items);
while (queue.Count > 1)
{
Console.WriteLine("{0},{1}", queue.Dequeue(), queue.Peek());
}
A short word about performance:
I believe it's important to realize that unless you know that a task is causing a bottleneck in your real application, it's probably not worth working out what the truly fastest way of doing is. Instead, write the code which does the job for you. Also, use code you can remember, so it easily flows out of your hand the next time you need it.
Nevertheless, in case you care for some performance data for 10.000.000 random strings:
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
Tested using Jon Skeet's micro benchmarking tool.
If you want to take a look at the source for the test go here: gist here
Solution 7 - C#
Expanding on the previous answer to avoid of O(n2) approach by explicitly using the passed iterator:
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;
}
}
For C# 2, before extension methods, drop the "this" from the input parameter and call as a static method.
Solution 8 - C#
Something like this:
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;
}
}
Solution 9 - C#
Forgive me if I'm overlooking something, but why not something simple, like a for loop?:
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;
}
Solution 10 - C#
C# 3.0 solution (sorry:)
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);
}
This isn't the most performant in the world, but it's sure pleasant to look at.
Really, the only thing making this a C# 3.0 solution is the .Skip.Take construct, so if you just change that to adding the elements in that range to a list instead, it should be golden for 2.0. That said, it's still not performant.
Solution 11 - C#
Alternate Pairs
implementation, using last pair to store previous value:
static IEnumerable<Pair<T, T>> Pairs( IEnumerable<T> collection ) {
Pair<T, T> pair = null;
foreach( T item in collection ) {
if( pair == null )
pair = Pair.Create( default( T ), item );
else
yield return pair = Pair.Create( pair.Second, item );
}
}
Simple Window
implementation (only safe for private use, if caller does not save returned arrays; see note):
static IEnumerable<T[]> Window( IEnumerable<T> collection, int windowSize ) {
if( windowSize < 1 )
yield break;
int index = 0;
T[] window = new T[windowSize];
foreach( var item in collection ) {
bool initializing = index < windowSize;
// Shift initialized window to accomodate new item.
if( !initializing )
Array.Copy( window, 1, window, 0, windowSize - 1 );
// Add current item to window.
int itemIndex = initializing ? index : windowSize - 1;
window[itemIndex] = item;
index++;
bool initialized = index >= windowSize;
if( initialized )
//NOTE: For public API, should return array copy to prevent
// modifcation by user, or use a different type for the window.
yield return window;
}
}
Example use:
for( int i = 0; i <= items.Length; ++i ) {
Console.WriteLine( "Window size {0}:", i );
foreach( string[] window in IterTools<string>.Window( items, i ) )
Console.WriteLine( string.Join( ", ", window ) );
Console.WriteLine( );
}
Solution 12 - C#
The F# Seq
module defines the pairwise function over IEnumerable<T>
, but this function is not in the .NET framework.
If it were already in the .NET framework, instead of returning pairs it would probably accept a selector function due to the lack of support for tuples in languages like C# and VB.
var pairs = ns.Pairwise( (a, b) => new { First = a, Second = b };
I don't think any of the answers here really improve on your simple iterator implementation, which seemed the most natural to me (and the poster dahlbyk by the looks of things!) too.
Solution 13 - C#
I created a slightly modified version of the late-2020-updated code in @dahlbyk's answer. It is better suited for projects with nullable reference types enabled (<Nullable>enable</Nullable>
). I also added basic docs.
/// <summary>
/// Enumerates over tuples of pairs of the elements from the original sequence. I.e. { 1, 2, 3 } becomes { (1, 2), (2, 3) }. Note that { 1 } becomes { }.
/// </summary>
public static IEnumerable<(T, T)> Pairwise<T>(this IEnumerable<T> source)
{
using var it = source.GetEnumerator();
if (!it.MoveNext())
yield break;
var previous = it.Current;
while (it.MoveNext())
yield return (previous, previous = it.Current);
}
Solution 14 - C#
New C# language allows to do something like this:
var pairlist = new (string, string)[] { ("a", "b"), ("b", "c"), ("c", "d") };
foreach (var pair in pairlist)
{
//do something with pair.Item1 & pair.Item2