Что быстрее, метод List <T>.Remove (T) или List <T>.RemoveAt (int)?

Question

Является ли List<T>.Remove(T) быстрее, чем метод List<T>.RemoveAt(int) в коллекциях .NET? Отличается ли скорость для типов значений или ссылочных типов?

Answer 1

Простой ответ:

В общем, RemoveAt быстрее, хотя и не всегда очень сильно.

Длинный ответ:

Давайте сначала рассмотрим поиск подходящего предмета. Метод Remove должен искать в списке элемент, который соответствует данному объекту, и, таким образом, в общем случае O(n) время. RemoveAt в списке может просто индексировать данный элемент и, таким образом, O(1).

Теперь удаление элемента из конца списка всегда, конечно, O(1), но в целом удаление элемента занимает O(n) время, потому что необходимо произвести перестановку (перемещение элементов после удаленного вперед). Следовательно, в общем случае общая сложность времени для удаления составляет либо O(n) + O(n), либо O(n) + O(1) для Remove и RemoveAt соответственно, следовательно, просто O(n) в любом случае. Тем не менее, RemoveAt гарантированно будет, по крайней мере, таким же быстрым, хотя масштабирование будет таким же, если только вы не знаете, что удаляете его в конце или ближе к концу.

Answer 2

List.Remove (T) использует IndexOf и RemoveAt (int) в своей реализации. Поэтому List.RemoveAt (int) работает быстрее.

public bool Remove(T item)
{
    int index = this.IndexOf(item);
    if (index >= 0)
    {
        this.RemoveAt(index);
        return true;
    }
    return false;
}

Answer 3

Учитывая, что .Net заражает вектор (или массив), а не связанный список, RemoveAt () быстрее.

Answer 4

Использование System.Diagnostics.Stopwatch()

Я бы просто создал небольшое консольное приложение, чтобы проверить, что быстрее.

Answer 5

Remove (T) внутренне выполняет вызов RemoveAt (int), поэтому непосредственное выполнение removeAt происходит быстрее.

Но Чего вы хотите достичь?