Java - PriorityQueue по сравнению с отсортированным LinkedList
Какая реализация менее "тяжела": PriorityQueue или отсортированный LinkedList (использующий Компаратор)?
Я хочу иметь все отсортированные объекты. Вставка будет очень частой, и иногда я должен буду выполнить весь список для создания некоторых операций.
8 ответов
LinkedList - наихудший выбор. Либо используйте ArrayList (или, в более общем смысле, средство реализации RandomAccess ), либо PriorityQueue . Если вы все же используете список, сортируйте его только перед итерацией по его содержимому, а не после каждой вставки.
Следует отметить, что итератор PriorityQueue не предоставляет элементы по порядку; вам фактически придется удалить элементы (очистить очередь), чтобы перебрать ее элементы по порядку.
Нужна ли вам постоянная сортировка? Если это так, то лучше выбрать что-то вроде tree-set (или другой SortedSet с быстрым поиском).
Если сортировка нужна только время от времени, используйте связный список и сортируйте его, когда вам нужен доступ. Пусть он будет несортированным, когда доступ не нужен.
Вы должны реализовать оба, а затем провести тестирование производительности фактических данных, чтобы увидеть, что лучше всего работает в ваших конкретных обстоятельствах.
Если вы используете LinkedList, вам придется пересортировывать элементы при каждом добавлении, а поскольку вставки происходят часто, я бы не стал использовать LinkedList. Поэтому в этом случае я бы использовал PriorityQueue'Если вы будете добавлять в список только уникальные элементы, я рекомендую использовать SortedSet (одна из реализаций - TreeSet).
Проблема с PriorityQueue заключается в том, что вам нужно очистить очередь, чтобы привести элементы в порядок. Если это то, что вы хотите, то это прекрасный выбор. В противном случае вы можете использовать ArrayList , который вы сортируете только тогда, когда вам нужен отсортированный результат, или, если элементы различны (относительно компаратора), TreeSet . И TreeSet , и ArrayList не очень «тяжелые» с точки зрения пространства; что быстрее, зависит от варианта использования.
Между двумя структурами данных существует фундаментальная разница, и они не так легко взаимозаменяемы, как вы думаете.
Согласно документации PriorityQueue:
Итератор, предоставленный в методе iterator (), не гарантирует обход элементов очереди с приоритетами в каком-либо определенном порядке.
Используйте ArrayList и вызывайте для него Collections.sort () только перед повторением списка.
java.util.PriorityQueue is
«Неограниченная очередь приоритетов на основе приоритетная куча »
. Структура данных кучи имеет гораздо больший смысл, чем связанный список
Я вижу два варианта, какой из них лучше, зависит от того, нужна ли вам возможность иметь дубликаты элементов.
Если вам не нужно поддерживать дубликаты элементов в списке, я бы использовал SortedSet (возможно, TreeSet).
Если вам нужно поддерживать дубликаты элементов, я бы выбрал LinkedList и вставлял новые элементы в список в правильном порядке.
PriorityQueue не очень подходит, если только вы не хотите удалять элементы всякий раз, когда выполняете операции.
Вместе с другими, убедитесь, что вы используете профилирование, чтобы убедиться, что вы выбираете правильное решение для вашей конкретной проблемы.