Post by SpreadTooThinI have a list of objects and i need to loop through it and remove elements.
I'm wondering if I need to start from the end of the list and go toward the beginning?
for (i = list.Count - 1; i >= 0; i--)
{
if list.needsDeleting(i))
{
list.RemoveAt(i);
}
}
While this works it is amazingly slow.
The Problem is, that delete operations in linear Arrays are O(n). I.e.
all elements beyond i need to be moved one position to the left. But all
elements that are kept, have to be moved as many times as there are
removed elements with lower index. So the over all performance of this
algorithm is O(n²) - like bubblesort which is basically the same, since
you order the elements by a predicate.
If you start at the front then you need to do move even more elements,
because the deleted elements after the current one have to be moved too,
just to be removed later.
A reasonable implementation of this pattern has O(n).
Just move all elements to be kept to consecutive location at the front
of the list and resize the entire list appropriately afterwards.
See the implementation of List.RemoveAll in the reference source which
does exactly this job.
Btw. looking at the reference source a bug catches my eye. If the
predicate throws an exception the list content is left in an
inconsistent state with duplicate elements.
using System;
using System.Collections.Generic;
public class Test
{
static bool Predicate(int i)
{
if (i == 5)
throw new Exception();
return (i & 1) != 0;
}
public static int Main()
{
var list = new List<int> { 1,2,3,4,5,6,7,8 };
try
{ list.RemoveAll(Predicate);
} catch (Exception ex)
{ // revover
}
foreach (var i in list)
Console.WriteLine(i);
return 0;
}
}
results in
2
4
6
4
5
6
7
8
9
The Java implementation of ArrayList.removeAll is smarter.
Marcel