Который быстрее, Список <T>.Remove (T) или <T>.RemoveAt Списка (интервал) метод?
List<T>.Remove(T) быстрее, чем List<T>.RemoveAt(int) метод в наборах.NET? Действительно ли скорость отличается для типов значения или ссылочных типов?
5 ответов
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;
}
Remove (T) выполняет внутренний вызов RemoveAt (int). Итак, выполнение непосредственно removeAt выполняется быстрее.
Но чего вы хотите достичь?
Использование System.Diagnostics.Stopwatch()
Я бы просто создал небольшое консольное приложение, чтобы проверить, что быстрее.
Простой ответ:
В целом RemoveAt работает быстрее, хотя и не всегда значительно.
Длинный ответ:
Давайте сначала рассмотрим поиск подходящего элемента. Метод Remove должен искать в списке элемент, который соответствует данному объекту, и, таким образом, обычно занимает O (n) время. RemoveAt в списке может просто индексировать данный элемент, и, таким образом, это O (1) .
Теперь удаление элемента из конца списка всегда O (1) , конечно, но в целом удаление элемента занимает O (n) времени, потому что перетасовка необходимо сделать (перемещение предметов после удаленного вперед). Следовательно, в общем случае общая временная сложность для удаления составляет либо O (n) + O (n) , либо O (n) + O (1) для Remove и RemoveAt соответственно, поэтому в любом случае просто O (n) . Однако RemoveAt гарантированно будет как минимум столь же быстрым, хотя масштабирование будет таким же, если только вы не знаете, что удаляете его в конце / ближе к концу.
Учитывая, что .Net заражает вектор (или массив), а не связанный список, RemoveAt () работает быстрее.