4

Почему в .NET список реализован через массив?

ICollection<T> c = collection as ICollection<T>;
    if( c != null ) {    // if collection is ICollection<T>
        int count = c.Count;
        if (count > 0) {
            EnsureCapacity(_size + count);
            if (index < _size) {
                Array.Copy(_items, index, _items, index + count, _size - index);
            }

При достижении границы массива, происходить копирование элементов в новый массив.

Разве это не менее производительно, чем традиционные списки, где новый элементы добавляются в конец, а последний предпоследний элемент начинает указывать на новый элемент?

4
  • Почитай статьи про фрагментирование листов, как в целом работают листы в дотнете и почему именно так. 8 окт 2018 в 5:41
  • 1
    Разве это не менее производительно — тут важно уточнить для каких задач, для доступа к элементу по индексу сильно быстрее (константа против линейной зависимости), например. Каждая коллекция имеет свою область применения, надо понимать как они устроены и в каких случаях что применять 8 окт 2018 в 5:45
  • 1
    Ну и, кстати, если вы заранее знаете верхнюю оценку размеров списка, вы можете создать список нужной размерности сразу и избежать множественного копирования (см. конструктор с capacity) 8 окт 2018 в 5:47
  • С учетом кэша в процессорах, списки на основе массива рвут в клочья связные списки даже на операцих вставки/удаления в/из середины/начала в большинстве сценариев. 8 окт 2018 в 11:13

2 ответа 2

6

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

Кроме того, хранение данных одним куском удобно для многих операций, например - копирования всего или части.

Связанные списки расходуют больше памяти.

Насчёт скорости при реаллокации памяти - память выделяется с запасом, и пока размер списка не превысит текущую ёмкость, перевыделения не происходит. А за счёт того, что память выделяется с запасом в кратное число раз, амортизированная сложность в расчёте на один элемент остаётся O(1).

Например, при росте ёмкости в 2 раза и расширении списка до 16 элементов:

Capacity   NumOfReallocs   NumOfMemoryOperations на текущий момент
1          1                 1  
2          2                 3 
4          3                 7 
8          4                 15
16         5                 31
5

Потому что "список" не подразумевает "связный список". Используйте LinkedList, он действительно использует связный список и обеспечивает сложность O(1) на операциях вставки элементов.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.