Как сохранить очередь с большим приоритетом с наиболее актуальными элементами?

Question

В задаче оптимизации я оставляю в очереди множество вариантов решения, которые проверяю в соответствии с их приоритетом .

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

Чтобы сделать это эффективно, я сохраняю большой (фиксированный размер) массив с кандидатами и двумя связанными косвенными двоичными кучами: одна обрабатывает кандидатов в порядке убывания приоритета, а другая - в порядке возрастания релевантности.

Это достаточно эффективно для моих целей, и необходимое дополнительное пространство составляет около 4 дюймов / кандидат, что также является разумным. Однако это сложно для кода, и это не кажется оптимальным.

Мой вопрос заключается в том, знаете ли вы о более адекватной структуре данных или о более естественном способе выполнения этой задачи без потери эффективности.

Answer 1

Вот эффективное решение, которое не изменяет сложность времени или пространства по сравнению с обычной кучей:

В минимальной куче каждый узел меньше, чем оба его потомка.В max-heap каждый узел больше, чем его дочерние элементы.Давайте чередуем свойство min и max для каждого уровня, делающего его: каждая нечетная строка меньше своих потомков и внуков, и обратная для четных строк.Тогда нахождение наименьшего узла совпадает с обычным, а нахождение самого большого узла требует, чтобы мы посмотрели на дочерние элементы корня и взяли самый большой.Пузырьковые узлы (для вставки) становятся немного сложнее, но они по-прежнему имеют ту же сложность O (logN).

Отслеживание емкости и определение самого маленького (наименее значимого) узла - простая часть.1006 * РЕДАКТИРОВАТЬ: Это, кажется, стандартная куча мин-макс!См. здесь для описания.Есть реализация C: header , source и example .Вот пример графика:

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

Answer 2

Если вы используете skip-lists вместо кучи, у вас будет O (1) время для удаления элементов из очереди, при этом все еще выполняя поиск в O (logn).
С другой стороны, список пропускасложнее реализовать и использует больше места, чем двоичная куча.

Answer 3

«Оптимальный» трудно судить (почти невозможно) без профилирования.

Иногда «тупой» алгоритм может быть самым быстрым, потому что процессоры Intel невероятно быстры при сканировании тупых массивов на смежных блоках памяти, особенно если цикл и данные могут помещаться на кристалле. В отличие от этого, переход по указателям в большем блоке памяти, который не помещается на кристалле, может быть в десятки, сотни или в несколько раз медленнее.

У вас также могут возникнуть проблемы, когда вы пытаетесь распараллелить ваш код, если в «умной» структуре данных введена блокировка, предотвращающая одновременное развитие нескольких потоков.

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

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

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