Как возможно, что "RemoveAll" в LINQ намного быстрее, чем итерация?

Следующий код:

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));
}

по крайней мере, на 100 раз быстрее, чем при списках размером ~ 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++;
        }
    }
}

Как это возможно? Что происходит под капотом с помощью "RemoveAll"? Согласно MSDN, "RemoveAll" выполняет линейный поиск и, следовательно, находится в O (n). Поэтому я ожидал бы аналогичную производительность для обоих.

При замене "Удалить" на "RemoveAt" итерация выполняется намного быстрее, сравнимо с "RemoveAll". Но у "Remove" и "RemoveAt" есть сложность O (n), так почему разница в производительности между ними такая большая? Может ли это быть только из-за того, что "Удалить (элемент)" сравнивает элементы списка с "item" и "RemoveAt" не выполняет никакого сравнения?

Ответы

Ответ 1

Если вы удалите элемент из List<T>, все элементы после него будут перемещены на одно место. Поэтому, если вы удалите n элементов, много элементов будет перемещено n раз.
RemoveAll выполнит только одно перемещение, которое вы можете увидеть в источнике для List<T>: source

Другое дело, что Remove(T item) будет искать весь список для элемента, так что другие n операций.

Что-то, что не имеет никакого отношения к вашему вопросу, но я бы хотел указать на это:
Если вы используете for-loop для удаления элементов из списка, в конце их проще начать:

for (int i = intervals.Count - 1; i >= 0; i--)
{
    if (intervals[i].Intersects(point))
    {
        intervals.RemoveAt(i);
    }
}

Таким образом, вам не нужно это уродливое else-clause

Ответ 2

RemoveAll можно выполнить в O(n), проверив условие для элементов n и перемещая не более n элементов.

Ваш цикл O(n^2), так как каждый Remove должен проверять элементы n. И даже если вы измените его на RemoveAt, ему все равно нужно перейти к n элементам.

Это может быть самым быстрым решением: intervals.RemoveAll(x => points.Any(x.Intersects));

Ответ 3

List - это массив, и удаление одного элемента из массива требует перемещения всех элементов после того, как вы удаляете предыдущий индекс, поэтому a[i] перемещается в a[i-1].

Выполнение этого многократно требует нескольких ходов, даже если большее количество элементов соответствует критериям удаления. RemoveAll может оптимизировать это, перемещая элементы более чем на один индекс за раз, когда он пересекает список и находит больше элементов, соответствующих критериям удаления.

Ответ 4

Различие заключается в том, что само удаление является O (n), поэтому вы получаете O (n ^ 2).

Замените for новой коллекцией и назначением.

items = items.Where(i => ...).ToList();

Этот метод имеет такую же алгоритмическую временную сложность, что и RemoveAll, но использует дополнительную O (n) память.