Почему ArrayDeque лучше, чем LinkedList

Я считаю, что основное узкое место производительности в LinkedList Это тот факт, что всякий раз, когда вы нажимаете на любой конец deque, за сценой реализация выделяет новый узел связанного списка, который по существу включает JVM/OS, и это дорого. Кроме того, всякий раз, когда вы поп с любого конца, внутренние узлы LinkedList получить право на сбор мусора, и это больше работы за кулисами. Кроме того, поскольку узлы связанного списка выделяются здесь и там, использование кэша ЦП не будет предоставить много пользы.

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

ArrayDeque является новым С Java 6, поэтому многие коды (особенно проекты, которые пытаются быть совместимыми с более ранними версиями Java) не используют его.

это "лучше" в некоторых случаях, потому что вы не выделяете узел для каждого элемента для вставки; вместо этого все элементы хранятся в гигантском массиве, который изменяется, если он заполняется.

все люди критикуют a LinkedList, подумайте о каждом другом парне, который использовал List в Java, вероятно, использует ArrayList и LinkedList в большинстве случаев, потому что они были до Java 6 и потому что это те, которые преподаются в качестве начала в большинстве книг.

но это не значит, что я бы слепо принимать LinkedListили ArrayDeque'ы стороны. Если вы хотите знать, взгляните на нижеприведенный тест сделал Брайан.

тестовая установка считает:

• каждый тестовый объект представляет собой строку из 500 символов. Каждая строка-это отдельный объект в памяти.
• размер тестового массива будет варьироваться во время тестов.
• для каждой комбинации размера массива / реализации очереди выполняется 100 тестов и вычисляется среднее время на тест.
• каждый тест состоит из заполнения каждой очереди всеми объектами, а затем их удаления.
• мера время в миллисекундах.

Результат Теста:

• ниже 10 000 элементов, как LinkedList, так и ArrayDeque тесты усреднены на уровне суб 1 мс.
• поскольку наборы данных становятся больше, различия между ArrayDeque и LinkedList среднее время тестирования становится больше.
• при тестовом размере 9,900,000 элементов подход LinkedList занял ~165% больше времени, чем ArrayDeque подход.

график:

вывод:

• если ваше требование хранит 100 или 200 элементов, то оно не сделало бы большая разница в использовании любой из очередей.
• однако, если вы разрабатываете на мобильном телефоне, вы можете использовать ArrayList или ArrayDeque С хорошим предположением максимальной емкости что список может потребоваться быть из-за строгого ограничение памяти.
• существует много кода, написанного с помощью LinkedList Так что будьте осторожны при принятии решения, чтобы использовать ArrayDeque тем более, что он не реализует List интерфейс(я думаю, что это достаточно большая причина). Возможно, ваша кодовая база активно взаимодействует с интерфейсом списка, скорее всего, и вы решите перейти к ArrayDeque. Используя его для внутренних реализаций может быть хорошей идеей...

доступ к элементу в ArrayDeque всегда быстрее по сравнению с LinkedList с O (1) для доступа к элементам. В связанном списке потребуется O (N), чтобы найти последний элемент.

ArrayDeque является эффективной памятью, так как вам не нужно отслеживать следующий узел в отличие от связанного списка.

даже в соответствии с документацией Java, он был процитирован, что

ArrayDeque-это масштабируемая реализация массива интерфейса Deque. Массив деки не имеют емкости ограничения; они растут по мере необходимости для поддержки использования. Они не являются потокобезопасными; в отсутствие внешней синхронизации они не поддерживают параллельный доступ несколькими потоками. Нулевые элементы запрещены. Этот класс, вероятно, будет быстрее, чем стек при использовании в качестве стека, и быстрее, чем LinkedList при использовании в качестве очереди.

бенчмаркинг из этих двух доказывает, что ArrayDeque быстрее.

хотя ArrayDeque<E> и LinkedList<E> есть и реализован Deque<E> интерфейс, но ArrayDeque использует в основном массив объектов E[] для хранения элементов внутри своего объекта, поэтому он обычно использует индекс для определения местоположения головных и хвостовых элементов.

одним словом, он просто работает как Deque (со всем методом Deque), однако использует структуру данных массива. Что касается, какой из них лучше, зависит от того, как и где вы использовать их.

временная сложность для ArrayDeque для доступа к элементу равна O(1), а для LinkList-O (N) для доступа к последнему элементу. ArrayDeque не является потокобезопасным, поэтому необходима ручная синхронизация, чтобы вы могли получить доступ к нему через несколько потоков, и поэтому они быстрее.