Как работает метод RemoveRange() в списке <>?

Question

Как и в заголовке. Я знаю, что это, вероятно, объединяет 2 подсписок до и после удаленных элементов, но как этот метод ведет себя при удалении элементов LAST? Другими словами: делает ли он каким-то образом копию всех элементов, расположенных перед удалением индекса? Мне просто интересно, как использовать RemoveRange в гигантском списке (скажем, 5000 элементов), чтобы удалить f.e. только последние 2 из них.

Если это делает копию, есть ли способ изменить некоторую внутреннюю переменную, которая задает размер списка (и обрабатывать остальную часть выделенных элементов как мусор)?

Мне удалось найти информацию о том, что это алгоритм сложности O (n), но я не уверен, что «n» в этом случае является размером списка или количеством элементов для удаления.

Будем рады любому намеку.

Answer 1

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

В качестве примера, рассмотрим следующий список:

index - value 

0 - A 
1 - B 
2 - C 
3 - D 
4 - E 
5 - F 
6 - G

Если мы называем RemoveRange(2, 2) Тогда мы удалим два элемента, начиная с индекса 2, поэтому мы удалим C и D.

Эта означает, что E нужно скопировать в индекс 2, затем F нужно скопировать в индекс 3, а G нужно скопировать в индекс 4. Сразу после удаления последнего элемента для каждого элемента есть одна операция копирования.

Обратите внимание, что из-за того, что вы можете переместить весь блок памяти «вверх» на два, это на практике становится более эффективным, если копировать каждый элемент по отдельности. Память компьютеров намного проще перемещать весь блок памяти на некоторое фиксированное количество байтов, чем перемещать множество небольших разделов памяти в разные произвольные местоположения. Однако он будет иметь такую ​​же асимптотическую сложность.

Answer 2

List<T> - это всего лишь обертка вокруг массива, называемая _items в коде ниже. В массиве может быть больше слотов, чем в элементе списка, поэтому _size используется для отслеживания количества действительных значений. Когда вы делаете RemoveRange(index, count) ...

_size -= count; 
if (index < _size) 
    Array.Copy(_items, index + count, _items, index, _size - index); 
Array.Clear(_items, _size, count); 

... он копирует элементы из прошлых диапазона в теперь пустое пространство, и очищает старые элементы.

Если вы удаляете диапазон, близкий к началу большого списка, тогда стоимость пропорциональна размеру списка, потому что столько вещей нужно сдвинуть вниз.

Если вы удаляете большой диапазон ближе к концу большого списка, то копирование дешево, но очистка стоит дорого, поэтому стоимость будет пропорциональна размеру удаляемого диапазона.