The following code:
List<Interval> intervals = new List<Interval>();
List<int> points = new List<int>();
//Initialization of the two lists
// [...]
foreach (var point in points)
{
intervals.RemoveAll (x => x.Intersects (point));
}
is at least 100x faster than this when the lists are of size ~10000:
List<Interval> intervals = new List<Interval>();
List<int> points = new List<int>();
//Initialization of the two lists
// [...]
foreach (var point in points)
{
for (int i = 0; i < intervals.Count;)
{
if (intervals[i].Intersects(point))
{
intervals.Remove(intervals[i]);
}
else
{
i++;
}
}
}
How is it possible? What is performed under the hood with "RemoveAll"? According to MSDN, "RemoveAll" performs a linear search and is therefore in O(n). So I would expect similar performance for both.
When replacing "Remove" by "RemoveAt", the iteration is much faster, comparable to "RemoveAll". But both "Remove" and "RemoveAt" have O(n) complexity, so why is the performance difference between them so big? Could it only be due to the fact that "Remove (item)" compares the list elements with "item" and "RemoveAt" doesn't perform any comparison?
RemoveAll
does not use LINQ, it is a standard method onList<T>
. This is noted by the fact thatRemoveAll
modifies the collection in place - LINQ does not modify collections.intervals.RemoveAt(i);
instead ofintervals.Remove (intervals[i]);
, I think.RemoveAll
andRemove
areO(n)
, so it's easy to believe the one which has an additionalfor
loop will performn
times slower.RemoveAll
and LINQ:intervals.RemoveAll(i => points.Any(p => i.Intersects(p)));