5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Ignore my delete answer. I missed one small detail. I like that version with the queue better because it doesn't require this complex index manipulations and has only one loop. \$\endgroup\$ – t3chb0t Jul 6 '19 at 16:32
  • \$\begingroup\$ @t3chb0t: but you have a point in that if countis large, the queue gets large, resulting in a large memory consumption an the overhead of copying the data. \$\endgroup\$ – Henrik Hansen Jul 6 '19 at 16:37
  • 1
    \$\begingroup\$ I think it'll rarely get larger than 1 so your caching techinique with the Queue is very cool :-) if count it would get so large that it would cause memory issues then there is a much bigger issue with the application logic. Or can you think of any example when it would make sense to use SkipLast(1_000_000)? \$\endgroup\$ – t3chb0t Jul 6 '19 at 16:40
3
\$\begingroup\$
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.

\$\endgroup\$
  • \$\begingroup\$ Interesting new optimized versions and tests. I only tested performance on a couple of counts and length and it didn't show much differences. GetEnumerator() has often showed to be much faster than a foreach loop, which IMO is strange, because the latter calls GetEnumerator(). \$\endgroup\$ – Henrik Hansen Jul 7 '19 at 5:07
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ +1 the BCL implementation does a variation on the former - and the different appears to be measureable - but doesn't for the latter, and there would all benefit from some type specialisation. I suspect I'm going to end up spending a lot of time running benchmarks... \$\endgroup\$ – VisualMelon Jul 7 '19 at 0:53
  • \$\begingroup\$ I have actually made a version after my post that is implemented as your first suggestion. \$\endgroup\$ – Henrik Hansen Jul 7 '19 at 4:26
4
\$\begingroup\$

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;
      }
    }
  }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Same benchmark with this (7) and a slight variation (8): gist. This method consistently out-performs the BCL version, except in the case where the source is empty but the count is high (it uses a Queue, so doesn't have to allocate the big array), and performs similarly when the count is otherwise zero with the Range. (There is some serious between-test variation, presumably because due to the variable background loading on my machine). \$\endgroup\$ – VisualMelon Jul 7 '19 at 13:08
  • 1
    \$\begingroup\$ I'd be cool if Take had this behaviour when you specify a negative count. \$\endgroup\$ – t3chb0t Jul 7 '19 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.