Java - PriorityQueue против отсортированного LinkedList

Question

Какая реализация менее «тяжелая»: PriorityQueue или отсортированный LinkedList (с использованием Comparator)?

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

Answer 1

A LinkedList - худший выбор. Либо используйте ArrayList (или, в более общем случае, RandomAccess агрегатор), либо PriorityQueue. Если вы используете список, сортируйте его только перед повторением его содержимого, а не после каждой вставки.

Следует отметить, что итератор PriorityQueue не обеспечивает элементы в порядке; на самом деле вам придется удалить элементы (очистить очередь), чтобы перебрать их элементы по порядку.

Answer 2

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

Answer 3

Я сделал небольшой тест по этому вопросу. Если вы хотите, чтобы ваш список сортировался после окончания всех вставок, тогда почти нет разницы между PriorityQueue и LinkedList (LinkedList немного лучше, на 5-10% быстрее на моей машине ), однако, если вы используете ArrayList, вы получите сортировку почти в 2 раза быстрее, чем в PriorityQueue.

В моем тесте для списков я измерил время от начала заполнения его значениями до конца сортировки. Для PriorityQueue - от начала заполнения до конца опроса всех элементов (поскольку элементы упорядочиваются в PriorityQueue при их удалении, как указано в erickson answer)

Answer 4

Если вы используете LinkedList, вам нужно будет прибегать к элементам каждый раз, когда вы добавляете один, а поскольку вставки происходят часто, я бы не стал использовать LinkedList. Поэтому в этом случае я бы использовал PriorityQueue. Если вы будете добавлять в список только уникальные элементы, я рекомендую использовать SortedSet (одна реализация - TreeSet).

Answer 5

добавление объектов в приоритетную очередь будет O log (n) и одинаково для каждого опроса.Если вы часто выполняете вставки в очень большие очереди, это может повлиять на производительность.Вставка в верхнюю часть ArrayList является постоянной, поэтому в целом все эти вставки будут проходить быстрее в ArrayList, чем в очереди с приоритетами.

Если вам нужно захватить ВСЕ элементы в отсортированном порядке, Collections.sort будет работать примерно за O n log (n) общего времени.Где, поскольку каждый опрос из очереди приоритетов будет O log (n) время, поэтому, если вы извлекаете все n вещей из очереди, то снова будет O n log (n).выигрыш, если вы пытаетесь найти, какое наибольшее значение в очереди в любой момент времени.Чтобы сделать это с ArrayList, вам нужно сортировать весь список каждый раз, когда вы хотите узнать самый большой.Но с приоритетной очередью он всегда знает, какое наибольшее значение.

Answer 6

Проблема с PriorityQueue заключается в том, что вам нужно очистить очередь, чтобы привести элементы в порядок. Если это то, что вы хотите, то это хороший выбор. В противном случае вы можете использовать ArrayList, который вы сортируете, только когда вам нужен отсортированный результат или, если элементы различны (относительно компаратора), TreeSet. И TreeSet, и ArrayList не очень "тяжелые" с точки зрения пространства; скорость зависит от варианта использования.

Answer 7

Существует фундаментальное различие между двумя структурами данных, и они не так легко взаимозаменяемы, как вы думаете.

Согласно документации PriorityQueue:

Итератор, предоставленный в методе iterator (), не гарантирует прохождение элементов очереди с приоритетами в любом конкретном порядке.

Используйте ArrayList и вызывайте Collections.sort () для него только перед итерацией списка.

Answer 8

ИМХО: нам не нужно PriorityQueue, если есть LinkedList. Я могу отсортировать очередь с LinkedList быстрее, чем с PriorityQueue. например,

Queue list = new PriorityQueue();
list.add("1");
list.add("3");
list.add("2");
while(list.size() > 0) {
    String s = list.poll().toString();
    System.out.println(s);
}

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

Queue list = new LinkedList();
list.add("1");
list.add("3");
list.add("2");
List lst = (List)list;
Collections.sort(lst);
while(list.size() > 0) {
    String s = list.poll().toString();
    System.out.println(s);
}

Я думаю, что этот код будет отсортирован только один раз, и он будет быстрее, чем с помощью PriorityQueue. Таким образом, я могу один раз отсортировать свой LinkedList, прежде чем использовать его, в любом случае, и он будет работать быстрее. И даже если это происходит в одно и то же время, мне не нужен PriorityQueue, нам действительно не нужен этот класс.

Answer 9

Я вижу два варианта, один из которых лучше, зависит от того, нужно ли вам иметь дубликаты.

Если вам не нужно хранить дубликаты в вашем списке, я бы использовал SortedSet (возможно, TreeSet).

Если вам нужно сохранить дубликаты, я бы добавил LinkedList и вставил новые элементы в список в правильном порядке.

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

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

Answer 10

java.util.PriorityQueue это

"Очередь с неограниченным приоритетом на основе куча приоритетов "

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