SkipLast of an IEnumerable<T> - Linq Extension

Question

As my answer to this question, I came up with this solution:

static public IEnumerable<T> SkipLast<T>(this IEnumerable<T> data, int count)
{
  if (data == null || count < 0) yield break;

  Queue<T> queue = new Queue<T>(data.Take(count));

  foreach (T item in data.Skip(count))
  {
    queue.Enqueue(item);
    yield return queue.Dequeue();
  }
}

It returns all items in the set but the count last, but without knowing anything about the size of the data set. I think it's funny and that it's working, but a comment claims that is doesn't. Am I overlooking something?

---

A version with a circular queue could be:

static public IEnumerable<T> SkipLast<T>(this IEnumerable<T> data, int count)
{
  if (data == null || count < 0) yield break;
  if (count == 0)
  {
    foreach (T item in data)
      yield return item;
  }
  else
  {
    T[] queue = data.Take(count).ToArray();
    int index = 0;

    foreach (T item in data.Skip(count))
    {
      index %= count;
      yield return queue[index];
      queue[index] = item;
      index++;
    }
  }
}

Performance wise they seems to be even.

---

Compared to other solutions like the most obvious:

data.Reverse().Skip(count).Reverse()

It seems to be at least as fast and for very large set about twice as fast.

Test case:

  int count = 20;
  var data = Enumerable.Range(1, count);

  for (int i = 0; i < count + 5; i++)
  {
    Console.WriteLine($"Skip: {i} => {(string.Join(", ", data.SkipLast1(i)))}");
  }

Any comments are useful.

Answer 1

if (data == null || count < 0) yield break;

This behaviour is somewhat consistent with Take, but not with Skip: Skip treats a negative values as a zero. As, indeed, does the SkipLast which doesn't appear in .NET Framework.

It should throw on a null argument with an ArgumentNullException.

---

My only other real issue with the methods is that neither will work with IEnumerables that can't be enumerated multiple times, and will incur overheads in any that can but have to generate the data lazily.

I would go for the slightly more painful:

if (source == null)
    throw new ArgumentNullException("Source Enumeration may not be null", nameof(source));

if (count <= 0)
{
    foreach (T item in source)
        yield return item;
}
else
{
    bool yielding = false;
    T[] buffer = new T[count];
    int index = 0;

    foreach (T item in source)
    {
        if (index == count)
        {
            index = 0;
            yielding = true;
        }

        if (yielding)
            yield return buffer[index];

        buffer[index] = item;
        index++;
    }
}

If I cared about performance, I might consider the following, which reduces the amount of decision making inside the loop (which might make it faster: I'd better benchmark it).

// just the bit inside the else
T[] buffer = new T[count];

using (var e = source.GetEnumerator())
{
    // initial filling of buffer
    for (int i = 0; i < buffer.Length; i++)
    {
        if (!e.MoveNext())
            yield break;

        buffer[i] = e.Current;
    }

    int index = 0;
    while (e.MoveNext())
    {
        yield return buffer[index];
        buffer[index] = e.Current;
        index = (index + 1) % count;
    }
}

---

Performance wise they seems to be even.

That's encouraging, since Queue<T> is also implemented as a circular buffer. You'd hope that the array based version would be a bit lighter, but may consume more memory is Count > data.Count().

Having benchmarked your two proposals, my two proposals, and the .NET Core SkipLast (didn't include the Reverse based method), it seems the fastest methods are that built into .NET Core (hurray) and my last one, but the difference between test instance (with different data lengths and skip counts) is great. Unfortunately, I messed up and didn't run a third of the .NET Core tests, so the saga of incompetence on my part continues. The code and data can be found in a gist. The only real conclusion I would want to draw from this data (aside from 'use the BCL method if you can') is that your first method is consistently the slowest when the input array isn't empty in these tests on my machine with it's current workload. The difference is jolly significant, with your first method requiring twice as much time as others in some cases. Why the methods have different performance is less than clear.

Answer 2

There are 2 cases for which both your and VisualMelon's implementation can be improved:

• If count is less than or equal to 0, then you can return source directly. This speeds up iteration by removing an unnecessary intermediate step. For this to work, the yielding part of the method has to be moved into another method, but that's easy with local functions.
• If source is ICollection<T> collection, then you can return source.Take(collection.Count - count), which is faster and uses less memory because it doesn't need to buffer anything. The higher count is, the more of a difference this makes.

The first of these is probably not a very useful edge-case, so it might not be worth the extra code, but I would definitely include the second optimization.

Answer 3

Takning all considerations by VisualMelon and Pieter Witvoet into account a solution could now be:

static public IEnumerable<T> SkipLast<T>(this IEnumerable<T> data, int count)
{
  if (data == null) throw new ArgumentNullException(nameof(data));
  if (count <= 0) return data;

  if (data is ICollection<T> collection)
    return collection.Take(collection.Count - count);

  IEnumerable<T> Skipper()
  {
    using (var enumer = data.GetEnumerator())
    {
      T[] queue = new T[count];
      int index = 0;

      while (index < count && enumer.MoveNext())
        queue[index++] = enumer.Current;

      index = -1;
      while (enumer.MoveNext())
      {
        index = (index + 1) % count;
        yield return queue[index];
        queue[index] = enumer.Current;
      }
    }
  }

  return Skipper();
}

---

Update

In order to optimize when the data set is empty, a MoveNext() call could be made before the allocation of a potentially large queue array:

static public IEnumerable<T> SkipLast2<T>(this IEnumerable<T> data, int count)
{
  if (data == null) throw new ArgumentNullException(nameof(data));
  if (count <= 0) return data;

  if (data is ICollection<T> collection)
    return collection.Take(collection.Count - count);

  return Skipper();

  IEnumerable<T> Skipper()
  {
    using (var enumer = data.GetEnumerator())
    {
      if (!enumer.MoveNext())
        yield break;

      T[] queue = new T[count];
      queue[0] = enumer.Current;
      int index = 1;

      while (index < count && enumer.MoveNext())
        queue[index++] = enumer.Current;

      index = -1;
      while (enumer.MoveNext())
      {
        index = (index + 1) % count;
        yield return queue[index];
        queue[index] = enumer.Current;
      }
    }
  }
}