Получить наименьший элемент, элементы динамически упорядочены

Question

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

Обычно я бы использовал PriorityQueue, поскольку они разработаны специально для этой цели, и предлагал бы O (log (n)) время для методов удаления из очереди.

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

Если я не могу использовать PriorityQueue, Collections.min будет моим следующим инстинктом. Однако это перебирает всю коллекцию, что, по-видимому, дает время O (n). Это следующее лучшее решение?

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

Edit:
Порядок изменения нескольких элементов на одну операцию поиска

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

Answer 1

Я думаю, что если изменение действительно «непредсказуемо», возможно, вы застряли в Collections.min (). Однако, может быть, для некоторых других коллекций, таких как PriorityQueue, вы можете попробовать, прежде чем позвонить на мин.

1. Добавьте что-то, что вы ЗНАЕТЕ, это мин.
2. Удалите это
3. Тогда спросите еще раз "настоящие" минуты и надейтесь, что ваш маленький клуг прибегнул к вещам ...

В качестве альтернативы, вы знаете, изменился ли заказ со временем? например какой-нибудь OrderChangedEvent может быть запущен? Если это так, воссоздайте отсортированные данные по мере необходимости.

Answer 2

Возможный способ сделать это - расширить PriorityQueue, который содержит список в качестве одного из полей.Этот список будет хранить java.lang.Object.hashCode() каждого объекта.Всякий раз, когда на PriorityQueue вызывается добавление, просмотр, опрос, предложение и т. Д., Очередь проверяет хэш-коды каждого элемента и проверяет, изменился ли какой-либо элемент.Если они есть, он будет переупорядочивать элементы, которые изменились.Затем он заменит хеш-коды измененных элементов в списке.Я не знаю, как быстро это будет, но я подозреваю, что это будет быстрее, чем O (n).

Answer 3

Без каких-либо дополнительных предположений относительно операций, которые вы собираетесь выполнять , вы не сможете добиться лучшей производительности, чем с PriorityQueue или другим O (log (n)) - вставкой коллекции (TreeSet,например, но вы теряете O (1) -пик).Как вы правильно предположили, Collections.min(Collection, Comparator) является линейной операцией.

Но зависит от того, как часто вам нужно менять порядок: например, если вам нужно только изменить его время от времении все еще сохраняйте «стандартный» порядок, min() является жизнеспособным вариантом, но если вам нужно полностью изменить порядок, то вам, вероятно, будет лучше с переупорядочением очереди / набора (то есть обходом и добавлением всех элементов вновый), жесткий по цене O (nlog (n)).Использование Collections.sort(List, Comparator) может быть эффективным, если вам требуется много переупорядочения по сравнению со вставками, но требует от вас использования List.

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

Редактировать: Таким образом, у вас есть (более или менее) конечное числоупорядочения (не берите в голову, что это один и тот же тип сравнения по разным полям, это разные компараторы и вот что имеет значение)?Если это так, вы, вероятно, сможете добиться максимальной производительности, используя m очередей, которые ссылаются на одни и те же объекты, каждая из которых использует свой компаратор (самый простой метод, на самом деле).Таким образом, у вас есть:

• постоянный доступ к времени
• O (m * logn (n)) вставок (для вставки в каждую очередь)
• O (m *)n) удаления (для удаления из каждой очереди)
• без затрат на заказ (так как он обрабатывается вставками)
• немного большая стоимость памяти (вероятно, незначительная)
• дополнительная O (n * log (n)) стоимость в первый раз, когда запрошено частичное упорядочение

Предполагая, что значение на m порядков меньше n, это сопоставимо с оптимальной производительностью PriorityQueue для однократного упорядочения.Для удобства вы можете обернуть это в пользовательскую коллекцию, которая принимает параметр Comparator в операциях поиска, и использовать его в качестве ключа для HashMap всех PriorityQueues.

Edit # 2: В этом случае нет лучшего решения, чем запуск min () для каждого поиска (если только вы не можете делать предположения об изменениях данных);это также означает, что лучше использовать ArrayList в качестве коллекции, поскольку он имеет минимально возможную стоимость для каждой операции, и вы в любом случае не будете извлекать выгоду из естественного упорядочивания PriorityQueue.В результате вы получите линейную стоимость при извлечении (за мин) и постоянную при вставке и удалении: это оптимально, поскольку не существует алгоритма сортировки, который в любом случае имел бы меньше Ω (n) и Θ (nlog n).

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

Answer 4

Разве вы не можете использовать java TreeSet, который постоянно хранит отсортированную коллекцию.Для этого вам необходимо реализовать интерфейс Comparable на ваших объектах.Оформить заказ http://docs.oracle.com/javase/1.4.2/docs/api/java/util/TreeSet.html