Алгоритм поиска (с уже реализованным алгоритмом сортировки)

Question

Я занимаюсь Java-приложением, и я сталкиваюсь с некоторыми сомнениями в отношении производительности.

У меня есть PriorityQueue, которая гарантирует, что удаленный элемент имеет больший приоритет. Это PriorityQueue имеет экземпляры класса Event (который реализует Сопоставимый интерфейс). Каждое событие связано с сущностью .

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

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

Есть предложения?

Спасибо!

Answer 1

Пара идей:

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

Answer 2

Есть несколько вариантов:

1. Не могли бы вы использовать отдельные очереди для каждая сущность? Поэтому, когда вы получаете событие для "XPTO" вы положили его в XptoPriorityQueue? Это уменьшит размер каждой очереди, но может также привести к некоторому другому управлению проблемы.
2. Вы удаляете события для конкретный объект для их обработки раньше? Если это так, то вы должны просто дать этим лицам более высокую приоритет и поднять их на вершину очередь.
3. Вы удаляете события для конкретной сущности, чтобы удалить их из очереди и игнорировать их? Если так что они никогда не должны получить в очередь или должен получить ниже приоритет.

Answer 3

Звучит так, как будто вам нужно реализовать очередь с форсированным приоритетом. В частности, вам нужно время удаления O (logN). Вы можете сделать это, сохранив две структуры данных: массив Events, который в основном представляет собой двоичную кучу , в которой хранится ваша очередь приоритетов, и HashMap из Event в смещение этого события в массиве (или, возможно, из Entity к списку смещений событий в этом массиве).

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

Answer 4

Я бы посоветовал вам создать класс, состоящий из PriorityQueue и Set, со следующими операциями:

• Чтобы добавить элемент, удалите его из набора и, если его там не было, добавьте его в PriorityQueue.
• Чтобы удалить элемент, добавьте его в набор.
• Чтобы удалить элемент из очереди, снимите элементы в очереди с PriorityQueue до тех пор, пока элемент без очереди не появится в наборе. Удалите все неподписанные элементы из набора.

Answer 5

Поскольку remove является линейной операцией по времени, вы получаете производительность O (N * N).

Если вы создаете подкласс PriorityQueue и создаете новый метод (возможно, с именем removeIf), который объединяет методы итератора и remove, то вы можете уменьшить его до O (N log (N)).