Какая реализация менее "тяжелая": PriorityQueue или отсортированный LinkedList (с использованием компаратора)?
Я хочу, чтобы все отсортированные элементы. Вставка будет очень частым, и иногда мне придется запустить весь список, чтобы выполнить некоторые операции.
A LinkedList - худший выбор. Используйте либо ArrayList (или, более общо, RandomAccess, либо PriorityQueue. Если вы используете список, сортируйте его только перед повторением его содержимого, а не после каждой вставки.
Следует отметить, что итератор PriorityQueue не предоставляет элементы в порядке; вам действительно нужно удалить элементы (пустую очередь), чтобы упорядочить по своим элементам по порядку.
Вы должны реализовать оба метода, а затем выполнить тестирование производительности по фактическим данным, чтобы увидеть, какая из них лучше всего подходит в ваших конкретных обстоятельствах.
Я сделал небольшой ориентир по этой проблеме. Если вы хотите, чтобы ваш список сортировался после конца all, то между PriorityQueue и LinkedList почти нет разницы (LinkedList немного лучше, от 5 до 10 процентов быстрее на моем машина), однако, если вы используете ArrayList, вы получите почти в 2 раза более быструю сортировку, чем в PriorityQueue.
В моем тесте для списков я измерил время с начала заполнения его значениями до конца сортировки. Для PriorityQueue - от начала заполнения до конца опроса всех элементов (поскольку элементы упорядочиваются в PriorityQueue, удаляя их, как указано в ответе erickson)
Если вы используете LinkedList, вам нужно будет прибегать к элементам каждый раз, когда вы их добавили, а так как вставки часты, я бы не использовал LinkedList. Поэтому в этом случае я бы использовал PriorityQueue Если вы добавите только уникальные элементы в список, я рекомендую использовать SortedSet (одна реализация - TreeSet).
Существует фундаментальное различие между двумя структурами данных, и они не так легко взаимозаменяемы, как вы думаете.
В соответствии с документацией PriorityQueue:
Итератору, предоставленному в методе итератора(), не гарантируется пересечение элементов очереди приоритетов в любом конкретном порядке.
Используйте ArrayList и вызывайте Collections.sort() на нем только перед итерированием списка.
Проблема с PriorityQueue заключается в том, что вам нужно очистить очередь, чтобы упорядочить элементы. Если это то, что вы хотите, то это прекрасный выбор. В противном случае вы можете использовать ArrayList, который вы сортируете, только если вам нужен отсортированный результат, или, если элементы отличаются (относительно компаратора), a TreeSet. Оба TreeSet и ArrayList не очень "тяжелы" по пространству; который быстрее зависит от варианта использования.
Добавление объектов в очередь приоритетов будет O log (n) и одинаковым для каждого поля. Если вы часто делаете вставки в очень больших очередях, это может повлиять на производительность. Вставка в вершину ArrayList является постоянной, поэтому в целом все эти вставки будут быстрее работать в ArrayList, чем в очереди приоритетов.
Если вам нужно захватить ВСЕ элементы в отсортированном порядке, Collections.sort будет работать в общей сумме времени O n log (n). Где каждый полюс из очереди приоритетов будет O log (n) time, поэтому, если вы захватите все n вещей из очереди, которая снова будет O n log (n).
Вариант использования, в котором выигрывает очередь приоритетов, заключается в том, что вы пытаетесь найти то, что самое большое значение в очереди в любой момент времени. Чтобы сделать это с помощью ArrayList, вам нужно отсортировать весь список каждый раз, когда вы хотите узнать самый большой. Но с приоритетной очередью он всегда знает, что самое большое значение.
Нужно ли это отсортировать в любое время? Если это так, вы можете пойти с чем-то вроде древовидного набора (или другого SortedSet с быстрым поиском).
Если вам это нужно только время от времени сортировать, перейдите со связанным списком и отсортируйте его, когда вам нужен доступ. Пусть он будет несортирован, когда вам не нужен доступ.
java.util.PriorityQueue является
"Неограниченная очередь приоритетов, основанная на приоритетная куча"
. Структура данных кучи имеет гораздо больший смысл, чем связанный список
Я вижу два варианта, который лучше зависит от того, нужно ли иметь дублирующиеся элементы.
Если вам не нужно поддерживать повторяющиеся элементы в вашем списке, я бы использовал SortedSet (возможно, TreeSet).
Если вам нужно поддерживать повторяющиеся элементы, я бы пошел с LinkedList и вставлял новые элементы в список в правильном порядке.
Приоритет PriorityQueue не подходит, если вы не хотите удалять элементы во время операций.
Следуя другим, убедитесь, что вы используете профилирование, чтобы убедиться, что вы выбрали правильное решение для вашей конкретной проблемы.
IMHO: нам не нужен 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, нам действительно не нужен этот класс.