Очередь приоритетов с функцией поиска - Самая быстрая реализация

Question

Я смотрю на реализацию приоритетной очереди с добавленным требованием, функцией поиска / поиска, которая скажет, находится ли элемент где-нибудь в очереди. Так что функции будут: вставить, del-min и найти.

Я не уверен, стоит ли мне использовать кучу или самобалансирующееся двоичное дерево поиска. Похоже, что PQ обычно реализуются с помощью Heap, но мне интересно, есть ли какое-либо преимущество в использовании бинарного дерева поиска, поскольку мне также нужна эта функция find.

Кроме того, в среднем я буду делать больше вставок, чем удалений. Я также рассматриваю d-ary кучу . По сути, каждая секунда имеет значение.

Спасибо!

Answer 1

Если ваша операция поиска встречается относительно редко (а ваша куча довольно мала), я бы просто выполнил линейный поиск. Если это относительно часто, или куча огромна, рассмотрите возможность отслеживания членства в куче (для выполнения теста «найти») с отдельной структурой данных или флагом объекта. Радость внешней индексации - это возможность помещать ваш объект в любое количество контейнеров.

Если под словом «найти» вы действительно имеете в виду «найти и изменить» (я считаю, что мне часто нужно удалять объекты из приоритетных очередей независимо от типичной вставки / делин-мин), я использовал три подхода:

Учитывая высокую скорость вставки / дел-мин (100 к / с непрерывной) и низкую скорость поиска-удаления (скажем, 1 / с) в довольно небольшом рабочем наборе (500-1000), я выполнил линейный поиск элемент, а затем удалил его из дерева стандартным способом.

Учитывая высокую скорость вставки / делин-мин плюс довольно частые операции поиска-удаления, я просто помечал удаленные объекты как «неинтересные» после их косвенного поиска. Фактическое освобождение было отложено до тех пор, пока объект не был снят с производства как обычно.

Учитывая небольшой std :: priority_queue (у которого нет методов доступа вне insert / del-min) только из нескольких элементов и довольно редких удалений, я просто скопировал всю очередь во временный std :: vector и скопировал измененная / желаемая часть возвращается в очередь. Затем я плакал, чтобы уснуть.

Answer 2

Почему нельзя просто использовать приоритетную очередь и сет? Когда вы ставите в очередь что-то, вы добавляете это в набор. Когда вы удаляете его из очереди, вы удаляете его из набора. Таким образом, набор сообщит вам, если что-то находится в очереди.

Answer 3

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

Если это insert, вставьте элемент в них обоих.

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

Если это min, то сначала удалите его из очереди приоритетов, и теперь, когда вы знаете, какой это элемент, вы можете удалить его из дерева двоичного поиска.

если это del, то сначала найдите его в дереве двоичного поиска и удалите, затем продолжите находить его в очереди приоритетов и тоже удалите его.

Предполагается, что узлы двоичного дерева и узлы приоритетной очереди являются указателями на ваши элементы.

Answer 4

Корневые деревья со свойством min-heap обеспечат нужные вам свойства.Это фактически даст вам постоянные временные сложности для ваших операций.Например, если мы рассмотрим эту реализацию на Haskell , все три упомянутые вами операции имеют временную сложность O (min (n, W)) .Где n - количество элементов, а W - количество бит в целых числах (32 или 64).

Answer 5

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

Я связал фильтр Блума с хэш-таблицей в предыдущем проекте, и он ускорилсяв хэш-таблицах в 400 раз больше, чем в среднем около 10 тыс. элементов.

Фильтр Блума имеет несколько интересных свойств:

• Если ответ не от фильтра Блума, этоНадежность на 100%.
• Если ответ положительный, вы должны проверить другую структуру данных, чтобы убедиться, что элемент действительно присутствует.
• Убедитесь, что вы выбрали хорошую хэш-функцию:)

Answer 6

IIRC поиск / поиск в куче равен O(n), тогда как в дереве он равен O(log(n)), а другие стандартные операции PQ такие же.так что если большая очередь, дерево должно быть лучше, если оно маленькое, вам нужно протестировать и профилировать.теоретически хорошо знать, что быстрее, но если эти постоянные факторы велики, это может быть совершенно неактуально для достаточно небольших наборов данных.