Двухкритериальная приоритетная очередь
Есть ли не слишком сложный способ реализации очереди с приоритетами, работающей по двум критериям? Очередь создается с 2 Comparatorс и обеспечивает (кроме add) операции poll1() а также poll2()где каждый удаляет и возвращает наименьший элемент согласно соответствующему компаратору.
Обратите внимание, что это не имеет ничего общего с этими двумя вопросами.
мотивация
Мой вариант использования - Оптимизация ветвей и границ. Расширение кандидата с наилучшим пределом доказуемо оптимально, если вам предоставляется неограниченное время. Предполагать, что неограниченное время доказуемо неправильно.
Строго следование этой стратегии часто заканчивается отсутствием решения вообще, когда наступает крайний срок. Простая помощь - сначала направить поиск к решению, а затем переключиться на лучшую стратегию привязки. Это довольно неудовлетворительно, поскольку первое найденное решение может иметь произвольное низкое качество.
Вот почему я хотел бы использовать очередь из двух критериев: в одном шаге разверните кандидата с наилучшими связями, а в другом - "наиболее привлекательного" кандидата в соответствии с некоторыми эвристиками.
Другое возможное использование было бы для парето-оптимизации.
5 ответов
Надеемся, что целью этой задачи будет поддержание того же амортизированного времени выполнения для очереди с целевым приоритетом.
Эти среды выполнения O(log n) для вставки и удаления.
Поддерживайте две приоритетные очереди, каждая со своим собственным компаратором. Вести карту подсчета добавленных объектов. Когда объект удаляется из очереди, уменьшите счетчик. Если объект, который вы пытаетесь опросить из очереди, имеет счетчик <= 0, то опросите другой элемент.
Следующая реализация поддерживает время выполнения. Это амортизировало O(log n) для вставки и удаления. Поскольку каждый элемент добавляется в каждую очередь и удаляется из каждой очереди только один раз, он должен быть постоянным кратным времени выполнения одной очереди. Кроме того, на карте есть время вставки и удаления O(1), что не способствует O(log n) время выполнения для очередей.
public class DualPriorityQueue<T> {
private Queue<T> queue1, queue2;
private Map<T, Integer> counts;
public DualPriorityQueue(int size, Comparator<T> c1, Comparator<T> c2) {
queue1 = new PriorityQueue(size, c1);
queue2 = new PriorityQueue(size, c2);
counts = new HashMap<T, Integer>(size);
}
public T poll1() {
return poll(queue1);
}
public T poll2() {
return poll(queue2);
}
private T poll(Queue<T> queue) {
T t = null;
while (!queue.isEmpty() && !removeCount(t = queue.poll())) {
t = null;
}
return t;
}
public boolean offer(T t) {
queue1.offer(t);
queue2.offer(t);
addCount(t);
return true;
}
private boolean removeCount(T t) {
final Integer value = counts.get(t);
if (value != null && value > 0) {
final int newValue = value - 1;
if (newValue == 0) {
counts.remove(t);
} else {
counts.put(t, newValue);
}
return true;
}
return false;
}
private void addCount(T t) {
final Integer prev = counts.get(t);
if (prev == null || prev <= 0) {
counts.put(t, 1);
} else {
counts.put(t, prev + 1);
}
}
}
Использовать два TreeSets. Каждый набор берет своего уважаемого компаратора, и add() Метод добавляет предоставленное значение к каждому набору. poll1() приобретет first() значение в первом наборе, и удалите значение из обоих наборов. Аналогично для poll2(),
add(), poll1() а также poll2() будет иметь log (журнал N).
Ниже приведен пример реализации (реальная вещь, вероятно, нуждается в дополнительной проверке ошибок и дополнительных методах):
class Priority2Queue <E>
{
private TreeSet<E> q1;
private TreeSet<E> q2;
public Priority2Queue (Comparator<E> c1, Comparator<E> c2) {
q1 = new TreeSet<E>(c1);
q2 = new TreeSet<E>(c2);
}
public void add (E e) {
q1.add(e);
q2.add(e);
}
private E pollx (TreeSet<E> a, TreeSet<E> b) {
E top = a.first();
a.remove(top);
b.remove(top);
return top;
}
public E poll1 () { return pollx(q1, q2); }
public E poll2 () { return pollx(q2, q1); }
}
Используйте две приоритетные очереди.
Один из способов сделать это - пометить элемент для удаления, когда он следующий в опросе. Если другая очередь видит это, пропустите и перейдите к следующему. Я не уверен в сложности этого, но это будет зависеть от тонких вопросов, таких как то, как долго один элемент остается в очереди, чем другой. Я бы предложил профилирование для вашей реальной ситуации.
Если вы заботитесь только об асимптотической сложности, я бы выбрал решение @jxh, которое использует O(n) память и гарантированное время O(log(n)) за операцию (это самое лучшее) и требует очень мало кодирования.
тем не мение TreeSet поддерживается TreeMap и что использует TreeEntry для записей, и одна запись займет всего 32B памяти, плюс 2 дерева приведет к 64B памяти на элемент!
РЕДАКТИРОВАТЬ 2: старый ответ был неправильным, я переместил его сюда, если кто-то хочет увидеть его в любом случае. Следует (надеюсь) правильный ответ.
Идея действительно проста. Давайте получим 2 обычных кучи, одна отсортирована через первый компаратор, другая отсортирована через второй компаратор. И с этими 2 индексными массивами, которые будут связывать элементы между кучами.
Например, если элемент X находится в позиции 2 в куче 1 и в позиции 8 в куче 2, тогда массивы связывания будут выглядеть так:
linkFrom1To2[2] = 8;
linkFrom2To1[8] = 2;
Поэтому, если вы выполняете какой-либо элемент, перемещающийся в одну из куч, вы должны соответствующим образом обновить эти массивы.
Но теперь, если вы удалите минимум из одной кучи, вы знаете, где этот элемент находился во второй куче, так что вы также можете удалить его оттуда.
Я разместил полный код здесь, это решение требует только 16B на элемент и даже быстрее, чем решение @jxh в тестах, которые я делал, но я использовал простые массивы с максимальной емкостью вместо некоторых автоматически растущих структур, таких как ArrayList,
Вы могли бы сделать что-то похожее на это.
public final class MyPriorityQueue < T >
{
private static final int INITIAL_CAPACITY = 10;
private final Queue < T > q1;
private final Queue < T > q2;
private final List < Queue < T > > queues;
public MyPriorityQueue ( Comparator < T > comparator1,
Comparator < T > comparator2 )
{
q1 = new PriorityQueue < T > ( INITIAL_CAPACITY, comparator1 );
q2 = new PriorityQueue < T > ( INITIAL_CAPACITY, comparator2 );
queues = Arrays.asList ( q1, q2 );
}
public void enqueue ( T t )
{
for ( Queue < T > queue : queues )
queue.add ( t );
}
public T poll1 ()
{
T returnValue = q1.poll ();
q2.remove ( returnValue );
return returnValue;
}
public T poll2 ()
{
T returnValue = q2.poll ();
q1.remove ( returnValue );
return returnValue;
}
}
Это может быть еще одна модификация.
public final class MyPriorityQueue < T >
{
private static final int INITIAL_CAPACITY = 10;
private final Map < Comparator < T >, Queue < T > > queues;
public MyPriorityQueue ( List < Comparator < T > > comparators )
{
queues = new HashMap < Comparator < T >, Queue < T > > ();
for ( Comparator < T > comparator : comparators )
{
Queue < T > q = new PriorityQueue < T > ( INITIAL_CAPACITY, comparator );
queues.put ( comparator, q );
}
}
public void enqueue ( T t )
{
for ( Queue < T > queue : queues.values () )
queue.add ( t );
}
public T poll ( Comparator < T > comparator )
{
Queue < T > q = queues.get ( comparator );
if ( q == null )
return null;
T returnValue = q.poll ();
for ( Queue < T > queue : queues.values () )
if ( queue != q )
queue.remove ( returnValue );
return returnValue;
}
}