Comments 21
Память не тратится, как вы выразились, «в пустую», изначальный размер задается для динамической амортизации размера массивов:
https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array
Есть еще одна реализация списка: LinkedList. В нем используется двусвязный список вместо динамического массива. Казалось бы, если нам не нужно часто брать элемент списка по индексу, то выбор очевиден.
Спасибо за более развернутый ответ. Хотелось просто несколько успокоить читателей и показать, что не все так плохо с ArrayList или HashMap, как может показаться из этой статьи.
Выбор в пользу LinkedList очевиден, когда в коде используются частые операции вставки/удаления.
Если это удаление, то легче написать обёртку, которая будет использовать внутри ArrayList и помечать удалённые элементы как null.
Если вставка в начало, то легче написать обёртку в которой несколько ArrayList и при необходимости добавить что-то — можно просто сделать новый ArrayList и считать его элементы начальными.
И только если вставка проводится в произвольные места во время итерации по листу и удаление проходит в этом же режиме — вот тут в LinkedList есть какой-то смысл. Да и то...
У Шипилёва кажется был разбор почему у ЛинкедЛиста нету ни одного юзкейса.
Второе, это хэш-таблицы, у которой в случае коллизий элементы объединяют в связанный список
А ведь в Джаве вместо списка можно было положить туда массив и существенно сэкономить память и немного увеличить скорость.
кроме этого при помощи связанного списка достаточно просто реализуется очередь или стек
Очередь или стек это структуры где нет вставки в середине. Тут массив просто великолепен.
В действительности джавовская реализация LinkedList имеет очень ограниченное применение из-за того, что нет возможности работать с узлом списка (ListNode)
Джавовская реализация LinkedList жрёт раз в 6 больше памяти чем ArrayList и сборщик мусора вынужден бегать по всем узлам LinkedList. Вот поэтому её и не применяют особенно. А работать с узлом списка можно с помощью итераторов.
Например, в .net вставка/удаление может производиться не только в голову или хвост, но и перед/после любого узла (node) списка
B Java тоже можно вставить куда угодно в любой момент.
А ведь в Джаве вместо списка можно было положить туда массив и существенно сэкономить память и немного увеличить скорость.В текущей реализации используется именно список. Массив бы ничего не сэкономил, а ровно наоборот, попробуйте реализовать свою версию, поймете.
Очередь или стек это структуры где нет вставки в середине. Тут массив просто великолепен.Особенно при вставке в начало ;). Да, при реализациях стека/очереди используют именно массив для организации циклического буфера с указателями на начало и конец элементов в буфере.
Джавовская реализация LinkedList жрёт раз в 6 больше памяти чем ArrayList и сборщик мусора вынужден бегать по всем узлам LinkedList. Вот поэтому её и не применяют особенно. А работать с узлом списка можно с помощью итераторов.Хорошо что в java нет типов с семантикой значения, поскольку для связанных списков конечно же лучше подходят большие структуры данных, в случае использования массивов таких структур затраты на копирования убили бы производительность. Со ссылочными типами все несколько проще, потому в java LinkedList совсем непопулярен.
B Java тоже можно вставить куда угодно в любой момент.Если я не ошибаюсь, в текущей реализации вставка add(int index, T element) связана с поиском, а это O(n)
В текущей реализации используется именно список.
Если точнее, то в текущей реализации список сделан прямо на месте. Структура Node объявлена внутри HashMap. LinkedList там не использутся.
Массив бы ничего не сэкономил, а ровно наоборот, попробуйте реализовать свою версию, поймете.
В массиве на каждый элемент приходится 8 байт. В LinkedList на каждый элемент приходится 8 байт на указатель на элемент, 8 байт на указатель на следующий узел, 8 байт на указатель на предыдущий узел и 16 байт оверхеда на объект Node.
Итого на один элемент в LinkedList приходится в 5 раз больше места, чем в массиве. В HashMap ссылки на предыдущие элементы нет, поэтому тут разница в 4 раза. Вот такая экономия. Если вы объясните как использование массива может привести к обратному — пожалуйста объясните.
Если я не ошибаюсь, в текущей реализации вставка add(int index, T element) связана с поиском, а это O(n)
Это не в текущей реализации, это во всех реализациях на всех языках. Если хочешь вставить элемент в произвольное место — получится O(n). Причём что в связном списке, что в динамическом массиве.
Но если ты перебираешь элементы и тебе надо вставить что-то после текущего, то в связном списке это O(1), потому что до нужного элемента ты уже добрался.
Если уж так хочется экономить на спичках — то стоит ещё вспомнить про autoboxing — и что это ещё тот overhead — как по памяти, так и по производительности (derefence тоже не бесплатный) — и есть для этого специализированные коллекции — trove, koloboke, eclipse collections etc.
И самое главное, что кажется тут возможно подразумевается, но упущено — можно было сделать ArrayList, который бы всегда ужимался — но тогда будет страдать производительность, можно использовать TreeMap вместо HashMap (что фактически сделано в c++ с std::map) — это разумный trade-off — вы уж выбирайте — шашечки или ехать.
Согласен, что если так сильно запаривает память — то выделяй для ArrayList размер (если он известен), после можно делать trimToSize, или вызывать copy-ctor — это и для ArrayList/HashMap/CHM/HashSet и т.п справедливо.
- Помечает недоступные объекты (marking)
- Удаление помеченных объектов (deletion)
- Уплотнение кучи (heap compaction)
на все это необходимы определенные процессорные ресурсы и желательно отсутствие закрепленных (pinned) объектов. При любом подходе к управлению памятью следует избегать ненужных операций выделения памяти, за это придется рано или поздно заплатить. Просто наличие GC скрывает много важных деталей, ну и в конечном итоге позволяет среднему программисту относительно качественно управлять памятью, т.е. не задумываться об этом
Как предотвратить перерасход памяти при использовании Java-коллекций