Как ArrayDeque быстрее, чем стек?
Согласно Javadoc,
Класс ArrayDeque, вероятно, будет быстрее, чем Stack, когда используется в качестве стека
Я не понимаю, как ArrayDeque может быть быстрее, чем стек. Предположим, стек реализован с использованием списка ссылок следующим образом:
Push: Insert new element at the head, teamp->next = head; head = temp
(where temp is the element to be inserted)
Pop: Remove the element from head, and make head = head->next
Для большого количества элементов будут накладные расходы на изменение размера ArrayDeque, чего не будет в случае стека, реализованного с использованием LinkedList. Так как же ArrayDeque быстрее, чем стек?
5 ответов
Поскольку большинство операций не требуют изменения размера массива, особенно после того, как очередь достигла стабильного размера и больше не увеличивается.
Каждый раз, когда вы добавляете товар Stack необходимо выделить новые объекты, обновить ссылки и т. д.
ArrayDeque просто нужно поместить объект в массив и обновить индекс.
ArrayDeque является частью Java Collections Framework и не предназначен для обеспечения безопасности потоков.
Stack вместе с Vector и Hashtable поставлялся с Java 1.0 и был реализован с использованием потоковобезопасных операций (потому что в то время это казалось хорошей идеей). Получение и снятие блокировок потоков является относительно дорогостоящим по времени, поэтому эти структуры данных будут намного медленнее, чем их соотечественники в JCF.
По моему опыту, связанные списки более эффективны, чем списки массивов, только в одном случае - когда вам часто требуется добавить или удалить несколько элементов из случайных точек в списке за один проход. В любом другом случае список массивов обычно лучше - быстрый поиск, произвольный доступ, меньше памяти. Если ArrayDeque основан на массиве - вероятно, нет необходимости выделять дополнительные объекты узла для каждого элемента, хранящегося в нем.
Поскольку в стеке обычно добавляются / удаляются элементы в конец списка, решение на основе массива, вероятно, будет более эффективным
Есть несколько причин использовать ArrayDeque вместо Stack, поскольку ArrayDeque - это очередь с двойным окончанием, реализованная как массив. Таким образом, он может расти относительно очень быстро. Если у вас нет плана использовать стек синхронизации, вероятно, ArrayDeque лучше, чем стек, который является потокобезопасным (и медленным). ArrayDeque также имеет лучшую локальность ссылок.
Ключевое слово "вероятно". Если изменение размера происходит, то это может быть медленнее, но стек вряд ли будет сильно расти.
Пока основная операция, которую вы делаете, не является поиском "содержит" или "массовой вставкой" и т. Д., Массив будет работать быстрее по сравнению с другими структурами данных. "Быстрая" часть всегда зависит от использования. В среднем, т.е. если вы берете среднее время, ArrayDeque будет быстрее, чем стек.