Каковы различия между двумя распространенными реализациями очереди?

Question

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

Answer 1

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

Что касается других соображений:

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

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

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

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

Answer 2

Примерно такая же разница, как между ArrayList и LinkedList.

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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