none
Обьясните разницу коллекций int[], List<int>, LinkedList<int> RRS feed

  • Вопрос

  • Здравствуйте, господа. Есть вопрос к знатокам C#. Вопрос больше теоретический, чем практический, но спать спокойно не дает :)

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

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

     

    6 января 2011 г. 19:33

Ответы

  • Да, при частом добавлении будут частые ресайзы. Не на каждую операцию добавления - потому что массив выделяется сразу с запасом, а не на один элемент больше. Опять же, можно выделить заранее сколько угодно элементов. Вот только мусор в куче не остается. Потому что в .net нет понятия "оставить мусор в куче". При изменении размера списка старый массив становится недостижимым объектом. И может быть собран сборщиком мусора. Пока размер массива не превышает 85000 байт - беспокоиться не о чем. 

    По поводу удаления- время выполнения - O(n), т.к. удаление сдвигает хвост массива на один элемент (часть, после удаленного элемента).

    Мне вот кажется, что ты сравниваешь разные классы с разным назначением. Например List<T> выглядит намного получше, когда тебе надо получить элемент по индексу. А LinkedList<T>  при выполнении этой операции вообще никак не выглядит - в нем даже такого метода нет.

    Если бы был класс, который работал быстрее и потреблял меньше памяти - то его бы и оставили, а второй - выбросили.

    • Помечено в качестве ответа Hagakurje 8 января 2011 г. 9:31
    7 января 2011 г. 10:35
    Модератор

Все ответы

  • Класс List(T) является универсальным эквивалентом класса ArrayList.Он реализует универсальный интерфейс IList(T) с помощью массива, размер которого динамически увеличивается по мере необходимости.

    MSDN, статья про класс List<T>

    Кроме того, ростом массива можно явно управлять выставлением свойства Capacity, вызовами TrimExcess и передачей начального размера в конструктор.

    Что быстрее/потребляет меньше памяти - вопрос относительный. В документации по методам каждого класса явно указан порядок времени, на него и ориентируйся :) 

    6 января 2011 г. 21:14
    Модератор
  • т.е. как я понимаю, List<int> содержит внутри себя int[], а при добавлении/удалении элементов массива вызывается что-то вроде Array.Resize<int> ? Просто по форумам говорят что Array.Resize использовать не рекомендуется, много мусора в куче оставляет..

    Я ж правильно понимаю: при инициализации массива new int[5]  в куче выделяется место под все 5 элементов массива. А когда инициализируется new List<int> ?  При добавлении/удалении элементов происходит переинициализация внутреннего int[] ? Просто мне кажется, что при частом добавлении/удалении элементов из массива это не очень эффективно, связанный список выглядит получше...

    7 января 2011 г. 6:41
  • Да, при частом добавлении будут частые ресайзы. Не на каждую операцию добавления - потому что массив выделяется сразу с запасом, а не на один элемент больше. Опять же, можно выделить заранее сколько угодно элементов. Вот только мусор в куче не остается. Потому что в .net нет понятия "оставить мусор в куче". При изменении размера списка старый массив становится недостижимым объектом. И может быть собран сборщиком мусора. Пока размер массива не превышает 85000 байт - беспокоиться не о чем. 

    По поводу удаления- время выполнения - O(n), т.к. удаление сдвигает хвост массива на один элемент (часть, после удаленного элемента).

    Мне вот кажется, что ты сравниваешь разные классы с разным назначением. Например List<T> выглядит намного получше, когда тебе надо получить элемент по индексу. А LinkedList<T>  при выполнении этой операции вообще никак не выглядит - в нем даже такого метода нет.

    Если бы был класс, который работал быстрее и потреблял меньше памяти - то его бы и оставили, а второй - выбросили.

    • Помечено в качестве ответа Hagakurje 8 января 2011 г. 9:31
    7 января 2011 г. 10:35
    Модератор
  • Спасибо, теперь понятно :)
    8 января 2011 г. 9:31