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

Question

У меня есть набор A и набор B, каждый со связанным числовым приоритетом, где каждый A может соответствовать некоторым или всем B и наоборот, и мой основной цикл в основном состоит из:

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

Наиболее очевидный способ сделать это - с одной приоритетной очередью из пар (A,B), но если есть 100 000 A и 100 000 B, то набор пар O(N^2) не будет вписывается в память (и диск слишком медленный).

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

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

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

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

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

Answer 1

Похоже, что элементы в 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 в порядке убывания приоритета. Пусть B (j) обозначает j-й элемент в этом отсортированном порядке. Также позвольте A (i) указать i-й элемент A (который может быть или не быть в отсортированном порядке).

Пусть nextb (i, j) будет функцией, которая находит наименьшее j '> = j такое, что Match (A (i), B (j')). Если такого j не существует, функция возвращает ноль (или другое подходящее значение ошибки). Поиск 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.

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

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

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

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