5
\$\begingroup\$

How do I improve the following?

List<int> list = new List<int> { 1,2,3,0,5,7,0,6,0,0 };
list.Reverse();
list = list.SkipWhile(l => l == 0).ToList();
list.Reverse();

The goal is to trim trailing zeroes.

\$\endgroup\$
8
\$\begingroup\$

Reversing the list twice as well as creating a new List just to remove trailing zeros is very inefficient.

Running the below vs the other answers in a loop 10 million times shows this performs about 5 times faster than the accepted answer, and about 3 times faster than list.Take(list.FindLastIndex(item => item != 0) + 1).ToList();:

List<int> list = new List<int> { 1, 2, 3, 0, 5, 7, 0, 6, 0, 0 };
for (int index = list.Count - 1; index >= 0 && list[index] == 0; index--)
{
    list.RemoveAt(index);
}

Update (again)

I've redone the measurements using varying inputs. Each answer's code is executed in a loop 10 million times. I've also moved the list creation out of the loop so it doesn't pollute what I'm trying to measure.

1 = Reverse + SkipWhile
2 = For loop + RemoveAt
3 = Take + FindLastIndex
4 = GetRange + FindLastIndex
5 = For loop + FindLastIndex + RemoveRange

Empty lists:

  1. 2258 ms
  2. 62 ms
  3. 844 ms
  4. 488 ms
  5. 138 ms

List of 100 non-zeros:

  1. 52334 ms
  2. 490 ms
  3. 34056 ms
  4. 2170 ms
  5. 665 ms

List of 100 non-zeros, 1 trailing zero:

  1. 53420 ms
  2. 1297 ms
  3. 34268 ms
  4. 2360 ms
  5. 1981 ms

List of 100 non-zeros, 100 trailing zeros:

  1. 67423 ms
  2. 12483 ms
  3. 41153 ms
  4. 8112 ms
  5. 6958 ms

List of 100 zeros:

  1. 15711 ms
  2. 10448 ms
  3. 5404 ms
  4. 5075 ms
  5. 5474 ms

Code used for testing:

class Program
{
    static List<int>[] lists;
    static List<int> nonZeros = new List<int>(Enumerable.Range(1, 100));
    static List<int> zeros = new List<int>(Enumerable.Repeat(0, 100));
    const int max = 10000000;

    static void Main(string[] args)
    {
        List<int> result = null;
        RecreateLists();

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < max; i++)
        {
            result = Enumerable.Reverse(lists[i]).SkipWhile(x => x == 0).Reverse().ToList();
        }
        sw.Stop();
        Console.WriteLine(" 1. {0} ms", sw.ElapsedMilliseconds);

        RecreateLists();
        sw.Restart();
        for (int i = 0; i < max; i++)
        {
            for (int index = lists[i].Count - 1; index >= 0 && lists[i][index] == 0; index--)
            {
                lists[i].RemoveAt(index);
            }
        }
        sw.Stop();
        Console.WriteLine(" 2. {0} ms", sw.ElapsedMilliseconds);

        RecreateLists();
        sw.Restart();
        for (int i = 0; i < max; i++)
        {
            result = lists[i].Take(lists[i].FindLastIndex(item => item != 0) + 1).ToList();
        }
        sw.Stop();
        Console.WriteLine(" 3. {0} ms", sw.ElapsedMilliseconds);


        RecreateLists();
        sw.Restart();
        for (int i = 0; i < max; i++)
        {
            result = lists[i].GetRange(0, lists[i].FindLastIndex(x => x != 0) + 1);
        }
        sw.Stop();
        Console.WriteLine(" 4. {0} ms", sw.ElapsedMilliseconds);


        RecreateLists();
        sw.Restart();
        int toRemove;
        for (int i = 0; i < max; i++)
        {
            toRemove = lists[i].FindLastIndex(item => item != 0) + 1;
            lists[i].RemoveRange(toRemove, lists[i].Count - toRemove);
        }
        sw.Stop();
        Console.WriteLine(" 5. {0} ms", sw.ElapsedMilliseconds);


        lists = null;
        GC.Collect();

        Console.WriteLine("\nComplete!");
        Console.ReadLine();
    }

    static void RecreateLists()
    {
        lists = null;
        GC.Collect();
        GC.WaitForPendingFinalizers();
        lists = new List<int>[max];
        var combined = new List<int>(nonZeros);
        combined.AddRange(zeros);
        for (int i = 0; i < max; i++)
        {
            lists[i] = new List<int>(combined);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ did your test code only use the sample input? I would be curious to see how it performs vs the Range/FLI with varying distributions of trailing zeros \$\endgroup\$ – im so confused Apr 2 '16 at 23:34
  • \$\begingroup\$ @imsoconfused I've updated it now with various inputs. \$\endgroup\$ – 404 Apr 3 '16 at 11:58
  • \$\begingroup\$ Ahh. Good old fashion for loops. #nostalgia \$\endgroup\$ – RubberDuck Sep 3 '16 at 14:31
  • \$\begingroup\$ The compared solutions are not comparable. Some of them mutate the list the others don't and return new lists. There should be two categories. \$\endgroup\$ – t3chb0t Nov 9 '16 at 7:14
5
\$\begingroup\$

List.Reverse() mutates the underlying list and returns void. You do this twice. It would be better to avoid unnecessary mutations. You could do that by enumerating the values in reverse, using Enumerable.Reverse(...), like this:

List<int> list = new List<int> { 1,2,3,0,5,7,0,6,0,0 };
list = Enumerable.Reverse(list).SkipWhile(x => x == 0).Reverse().ToList();

Here, there are actually no mutations.* A new list is created from the original, by iterating from the end, skipping initial zeros, and putting values in the resulting list.

* So I thought. It seems Enumerable.Reverse copies values to a buffer. So no, this doesn't help much.

However, with the two "reverse" operations, this still feels pretty awkward. A simple, more straightforward, and probably faster way will be to get the range of values from the start until the last non-zero value:

list = list.GetRange(0, list.FindLastIndex(x =>x != 0) + 1);

As a side note, I changed the lambda variable from l to x, as l can be hard to read in some fonts. For this reason it's generally recommended to avoid l as a name in programs.

\$\endgroup\$
3
\$\begingroup\$

eurotrash's method can be slightly improved by turning it into a RemoveRange():

var toRemove = list3.FindLastIndex(item => item != 0) + 1;
list.RemoveRange(toRemove, list.Count - toRemove);

Try It Online!

Output:

Reverse() took 3191 ticks.
eurotrash's method took 312 ticks.
eurotrash's method using RemoveRange() took 295 ticks.
The Take() method took 1749 ticks.
The GetRange() method took 330 ticks.
\$\endgroup\$
2
\$\begingroup\$

Using list.Take(list.FindLastIndex(item => item != 0) + 1).ToList(); is slightly faster, as it does not reverse the list twice. (Enumerable.Reverse builds an internal array as a buffer)

Try It Online!

\$\endgroup\$

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.