Парный приоритет очередь

Question

У меня есть набор A-х и набор B-х, каждая с соответствующим числовым приоритетом, где каждый A может соответствовать некоторым или всем B «S, и наоборот, и моему основному цикл в основном состоит of

Возьмите лучшие A и B в приоритетном порядке, и делайте что-нибудь с A и B.

Самый очевидный способ сделать это с помощью одной приоритетной очереди (A,B) пар, но если есть 100000 A «с и 100000 B» S, то множество O(N^2) пар не помещается в памяти (и диск слишком медленно).

Другая возможность для каждого A, через каждые B. Однако это означает, что глобальный порядок приоритетов - только A, и мне действительно нужно учитывать приоритет обоих компонентов.

(Приложение доказательство теорем, где указанные выше параметры называются алгоритм пара и данный раздел алгоритма соответственно; недостатки каждого из них известны, но я не нашел никаких ссылок на хорошее решение.)

Кажется, что указана некоторая двухуровневая очередь приоритетов, но неясно, как это сделать без использования O(N^2) или O(N^2) времени в худшем случае.

Есть ли известный способ сделать это?

Уточнение: каждый A должен обрабатываться со всеми соответствующими B, а не только одним.

Answer 1

Может быть, есть что-то я не понимая, но,

Почему бы не оставить А-х и Б в отдельных кучах, get_Max на каждом из куч, делать свою работу, удалите каждый максимум из связанных с ним кучи и по-прежнему?

Answer 2

Итак, у вас есть набор из A и набор B, и вам нужно выбрать пару (A, B) из этого множества, чтобы некоторые f (a, b) были самыми высокими из любых других (A , B).

Это означает, что вы можете хранить все возможные (A, B) пары и упорядочивать их, а также просто выбирать максимальный каждый раз через цикл (O (1) на итерацию, кроме O (N * M)).

Или вы можете пропустить все возможные пары и отслеживать текущий максимум и использовать это (O (N * M) для каждой итерации, но только память O (N + M)).

Если я правильно понимаю вас, это то, о чем вы просите.

Я думаю, что это очень зависит от f(), чтобы определить, есть ли лучший способ сделать это.

Если f (a, b) = a + b, то это, очевидно, очень просто, наивысшее A, а самое высокое B - то, что вы хотите.

Answer 3

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

Рассматривали ли вы упорядоченную парамодуляцию или суперпозицию?

Answer 4

Я думаю, что ваша оригинальная идея будет работать, вам просто нужно сохранить свои As и B в отдельных коллекциях и просто привязать ссылки к ним в очереди приоритетов. Если каждая ссылка занимает 16 байт (просто чтобы выбрать номер), то 10 000 000 ссылок A/B будут принимать только 300 МБ. Предполагая, что ваши As и Bs не слишком велики, это должно быть работоспособным.

Answer 5

Похоже, что элементы в A имеют индивидуальный приоритет, элементы в B имеют индивидуальный приоритет, а пары (A, B) имеют совмещенный приоритет. Только общий приоритет имеет значение, но, надеюсь, мы можем использовать отдельные свойства на этом пути. Тем не менее, существует также сопоставление между элементами в A и элементами в B, что является независимым приоритетом.

Я предполагаю, что для всех a из A, b1 и b2 в B, таких как Match (a, b1) и Match (a, b2), тогда Priority (b1)> = Priority (b2) подразумевает CombinedPriority (a, b1)> = CombinedPriority (a, b2).

Теперь, начните с сортировки В в порядке убывания приоритета. Пусть B (j) указывает j-й элемент в этом отсортированном порядке. Кроме того, пусть A (i) указывает i-й элемент A (который может быть или не быть в отсортированном порядке).

Пусть nextb (i, j) - это функция, которая найдет наименьшее j '> = j такое, что Match (A (i), B (j')). Если такой j 'не существует, функция возвращает значение null (или другое подходящее значение ошибки). Поиск j 'может включать в себя только петлю вверх от j, или мы сможем сделать что-то быстрее, если узнаем больше о структуре отношения Match.

Создайте очередь приоритетов Q, содержащую (i, nextb (i, 0)) для всех индексов i из A таких, что nextb (i, 0)! = Null. Пар (i, j) в Q упорядочивается CombinedPriority (A (i), B (j)).

Теперь проведите цикл до тех пор, пока Q не будет пустым. Вытащите пара наивысшего приоритета (i, j) и процесс (A (i), B (j)) соответственно. Затем повторно вставьте (i, nextb (i, j + 1)) в Q (если nextb (i, j + 1) не равен нулю).

В целом это занимает время O (N^2 log N) в худшем случае, что все пары совпадают. В общем случае требуется O (N^2 + M log N), где M - количество совпадений. Компонент N^2 может быть уменьшен, если есть более быстрый способ вычисления nextb (i, j), который просто зацикливается вверх, но это зависит от знания отношения Match.

(В приведенном выше анализе, я предполагал, А и Б были размером N. Формулы могут быть легко изменены, если они имеют разные размеры.)

Вы, казалось, хотели что-то лучше, чем O (N^2) в худшем случае, но если вам нужно обработать каждое совпадение, то у вас есть нижняя граница M, которая может быть самой N^2. Я не думаю, что вы сможете сделать лучше, чем O (N^2 log N), если только не существует специальной структуры для комбинированного приоритета, который позволяет использовать приоритетную очередь лучше, чем лог-N.