Я пытаюсь понять , почему Java ArrayDeque лучше, чем Java LinkedList, поскольку оба они реализуют интерфейс Deque.
Я почти не вижу, чтобы кто-то использовал ArrayDeque в своем коде. Если кто-то проливает больше света на то, как ArrayDeque реализован, было бы полезно.
Если я это понимаю, я буду более уверенно использовать его. Я не мог четко понять реализацию JDK в том, как он управляет заголовками и хвостами.
Связанные структуры, возможно, являются наихудшей структурой для итерации с пропуском кеша для каждого элемента. Кроме того, они потребляют больше памяти.
Если вам нужно добавить/удалить оба конца, ArrayDeque значительно лучше, чем связанный список. Случайный доступ к каждому элементу также O (1) для циклической очереди.
Единственная лучшая операция связанного списка - удаление текущего элемента во время итерации.
ArrayDeque является новым с Java 6, поэтому многие коды (особенно проекты, которые пытаются быть совместимыми с более ранними версиями Java) не используют его.
В некоторых случаях это "лучше", потому что вы не выделяете node для каждого вставляемого элемента; вместо этого все элементы хранятся в гигантском массиве, который изменяется, если он заполняется.
Я считаю, что основным недостатком производительности в LinkedList является тот факт, что всякий раз, когда вы нажимаете на любой конец deque, за сценой реализация выделяет новый связанный список node, который по существу включает JVM/OS и это дорого. Кроме того, всякий раз, когда вы выходите из любого конца, внутренние узлы LinkedList становятся доступными для сбора мусора и что больше работы за сценой.
Если это может быть интересно, у меня есть доказательство того, что добавление элемента в ArrayList или ArrayDeque выполняется в аморифицированном постоянном времени; обратитесь к этому.
Доступ к элементу в ArrayDeque всегда быстрее по сравнению с LinkedList с O (1) для доступа к элементам. В связанном списке для поиска последнего элемента потребуется O (N).
ArrayDeque эффективен с точки зрения памяти, поскольку вам не нужно отслеживать следующий node, в отличие от Linked List.
Даже в соответствии с документацией по Java, было указано, что
ArrayDeque - это реализация интерфейса Deque Resizable-array. Недопустимые ограничения на пропускную способность массива; они растут по мере необходимости для поддержки использования. Они не являются потокобезопасными; в отсутствие внешней синхронизации они не поддерживают одновременный доступ несколькими потоками. Нулевые элементы запрещены. Этот класс, вероятно, будет быстрее, чем Stack при использовании в качестве стека, и быстрее, чем LinkedList при использовании в качестве очереди.
Бенчмаркинг этих двух доказательств того, что ArrayDeque быстрее.
Все люди, критикующие LinkedList, думают о каждом другом, который использовал List в Java, вероятно, используют ArrayList и LinkedList большую часть времени, потому что они были до Java 6 и потому, что те которые учат как начало в большинстве книг.
Но это не значит, я бы слепо взял сторону LinkedList или ArrayDeque. Если вы хотите узнать, посмотрите нижеуказанный ориентир выполненный Брайаном.
В тестовой настройке учитывается:
- Каждый тестовый объект представляет собой строку с 500 символами. Каждая строка является другим объектом в памяти.
- Размер тестового массива будет изменяться во время тестов.
- Для каждой комбинации размеров массива/очереди-реализации выполняется 100 тестов и вычисляется среднее время на тест.
- Каждый тест состоит из заполнения каждой очереди всеми объектами, а затем их удаления.
- Измерьте время в миллисекундах.
Результат теста:
- Ниже 10000 элементов тесты LinkedList и ArrayDeque усредняются на уровне менее 1 мс.
- По мере увеличения наборов данных различия между средним временем тестирования ArrayDeque и LinkedList становятся больше.
- При размере теста, равном 9 900 000 элементов, подход LinkedList занял ~ 165% дольше, чем подход ArrayDeque.
Graph:
Вынос:
ArrayList или ArrayDeque с хорошей догадкой о максимальной емкости
что список может потребоваться из-за строгого ограничения памяти.LinkedList так осторожно, чтобы решить, использовать ArrayDeque, особенно потому, что он НЕ реализует интерфейс List (я думаю, что причина достаточно большой). Возможно, ваша кодовая база очень часто разговаривает с интерфейсом "Список", и, возможно, вы решите перейти с помощью ArrayDeque. Использование его для внутренних реализаций может быть хорошей идеей...хотя ArrayDeque<E> и LinkedList<E> реализовали интерфейс Deque<E>, но ArrayDeque использует в основном массив Object E[] для сохранения элементов внутри своего объекта, поэтому он обычно использует индекс для определения элементов головы и хвоста.
Одним словом, он просто работает как Deque (со всем методом Deque), однако использует структуру данных массива. Что касается того, что лучше, зависит от того, как и где вы их используете.
Сложность времени для ArrayDeque для доступа к элементу - это O (1), а для LinkList - O (N) для доступа к последнему элементу. ArrayDeque не является потокобезопасным, поэтому необходима синхронизация вручную, чтобы вы могли получить к нему доступ через несколько потоков, и поэтому они быстрее.