Каковы различия между двумя общими реализациями очереди?

Question

В Java одной из реализаций очереди является «круглый массив», а другой - «связанный список». В чем их отличия?

Answer 1

С точки зрения того, как они используются, нет практически никакой разницы, кроме случаев, когда вы дойдете до предела размера очереди (который я объясню в секунду ...)

As для других соображений:

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

• Кроме того, в связанном списке нет неиспользуемой памяти: в круговом массиве подход, если размер очереди меньше максимальной емкости массива, будут «пустые слоты». Однако это не означает, что связанные списки более эффективны с точки зрения памяти, потому что:

• Преимущество кругового массива состоит в том, что нет накладных расходов. Каждый узел в связанном списке должен хранить ссылку на следующий узел - и это добавляется, если список становится большим. С другой стороны, круговой массив - это всего лишь блок памяти, к которому вы обращаетесь, индексируя, поэтому нет накладных расходов.

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

Answer 2

Обычно реализация кругового массива немного лучше повторяет использование памяти, но рискует расти, если слишком много элементов добавлено в очередь - и, возможно, слишком много памяти, если нормальное хранилище и максимальная емкость хранилища слишком разные на практике.

Связанный список более гибкий, но обычно включает в себя сбор мусора.

На практике я думаю, что я был бы удивлен, если бы вы обнаружили, что узкое место вашего кода зависит от этого выбора - используйте то, что вам кажется наиболее интуитивным.

Answer 3

О той же разнице, что и между ArrayList и LinkedList.

• Для массива вам необходимо оценить, насколько велика очередь, потому что вам нужно выделить хранилище для него. Но, сделав это, он будет более компактным, когда он будет заполнен до максимальной емкости. «Свободные точки» по-прежнему занимают место в массиве, чего они не делают в LinkedList.

• Для связанного списка легче удалить и добавить элементы из середины (хотя это не должно быть вообще необходимо для очереди).

• Массив случайного доступа, то есть вы можете быстро добраться до элемента в позиции x. Опять же, эта функция бесполезна в очереди.

Answer 4

Очередь реализована в виде связанного списка не имеет фиксированный размер, в то время как один, реализованного в виде кругового массива, иначе ring buffer, как правило, имеет фиксированный размер (хотя можно было бы сделать одно, что изменяет размер, так же, как изменяется размер ArrayList).

Реализация связанного списка использует больше памяти для каждого элемента, но для реализации массива требуется более непрерывная память. Обе эти проблемы на самом деле являются лишь значительной проблемой, поскольку количество элементов становится довольно большим.

Добавление/удаление элементов в реализацию массива кругового массива очень дешево, так как оно просто включает в себя настройку счетчика и установку ссылки, в то время как реализация связанного списка должна выделять элементы при добавлении и накладывать накладные расходы GC при удалении.

Answer 5

Напишите свой код, чтобы он использовал только интерфейс, за исключением создания очереди. Тогда легко переключить реализации.

Выберите одну реализацию для начала. Обычно я использую варианты массивов (например, ArrayList), потому что они меньше и имеют тенденцию быть несколько более быстрыми на сегодняшних компьютерах, что, я думаю, связано с кешированием (я просто сделал небольшой тест, нажимая 10000000 элементов через 10000-элементную очередь, ~ 8.3s для ArrayBlockingQueue, 10-11 для LinkedBlockingQueue). Если мне нужен индексный доступ, я бы также использовал вариант массива. Только если в середине списка или очереди много вставки/удаления, я выбрал вариант связанного списка.

Если у вас возникли проблемы с производительностью и профилирование, это означает, что очередь является узким местом (что маловероятно), ориентируясь на обе реализации очереди и выбирает лучшую.