双标准优先队列

Question

有没有一种不太复杂的方法来实现具有两个标准的优先队列？该队列使用两个比较器创建，并提供（除add之外）poll1()和poll2()操作，其中每个操作根据相应的比较器删除并返回最小元素。

请注意，它与这些 two questions 没有任何共同之处。

动机

我的用例是分支限界优化。当您有无限时间时，通过扩展具有最佳边界的候选项可以证明是最佳的。假定无限的时间是可证明错误的。

严格遵循此策略通常会导致在截止日期到达时根本没有解决方案。一个简单的对策是首先将搜索引导到解决方案，然后再切换到最佳边界策略。这相当不令人满意，因为找到的第一个解决方案可能质量很低。

这就是为什么我想使用双标准队列：在一个步骤中，扩展最佳边界候选者，在另一个步骤中，根据某些启发式方法扩展“最佳外观”候选者。

另一个可能的用途是帕累托优化。

- maaartinus

---

为什么不创建一个由两个“PriorityQueue”支持的表面？ - Sotirios Delimanolis

@SamiKorhonen 这听起来不错，但可能会让太多的元素在队列中停留太久。也许定期清理可以解决这个问题。 - maaartinus

我猜你可以为每个队列设置一个无效引用计数器。如果计数器超过指定阈值，你只需使用迭代器将它们删除。你可以使用读写锁来同步清理：使用读锁进行轮询，使用写锁进行清理。原子操作应该作为计数器很好地工作。 - Sami Korhonen

@SamiKorhonen 这种清空操作通常无法正常工作，因为实际对象需要用于排序。您需要在包装器中存储用于排序的值，但我不确定它是否比我的实际对象更小。++计数器的想法听起来不错。 - maaartinus

听起来有一些有趣的地方，但我很想知道这是如何被使用的（特别是一个令人信服的例子，在这个例子中，它比两个单独的优先队列更有意义）。 - Marco13

Answer 1

使用两个TreeSet。每个set都采用自己的比较器，add()方法将提供的值添加到每个set中。poll1()会获取第一个set中的first()值，并从两个set中删除该值。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

---

+1 这很简单，肯定能够工作，但是使用 TreeSet 比堆要占用更多的内存，可能也需要更长的时间，因此效率不高。 - maaartinus

@maaartinus：我选择了一种数据结构，它可以提供正确的大O行为。如果您的队列大小相对较小，则两个优先级队列可能已经足够。如果您预计队列非常大，请考虑使用B+树实现而不是TreeSet。 - jxh

令人惊讶的是，你的解决方案比我尝试 kajacx 的答案要快得多。如果感兴趣，可以查看我的评论以获取链接。 - maaartinus

我现在明白了，我实现了另外一种方法...使用两个“PriorityQueue”并跟踪删除。有一天我也会尝试你的解决方案。 - maaartinus

Answer 2

如果你只关心渐进复杂度，我会选择@jxh的解决方案，它使用O(n)内存和保证O(log(n))每个操作的时间（这是最好的可能性），并且需要很少的编码工作。

然而，TreeSet由TreeMap支持，它为条目使用TreeEntry，一个条目将占用总共32B的内存，再加上有两棵树将导致每个元素64B的内存！ 编辑2：旧答案是错误的，我已经将其移动这里，如果有人想要查看它，那么就跟随（希望）正确的答案。

这个想法非常简单。让我们有两个普通的堆，一个通过第一个比较器排序，另一个通过第二个比较器排序。并且使用两个索引数组来链接堆之间的元素。

例如，如果元素X在堆1中的位置为2，在堆2中的位置为8，则链接数组将如下所示：

linkFrom1To2[2] = 8;
linkFrom2To1[8] = 2;

所以，如果你在任何一个堆中移动了任何元素，你都必须相应地更新这些数组。

但是，现在如果你从一个堆中删除最小值，你知道该元素在第二个堆中的位置，因此你也可以从那里将其删除。

我已经发布了完整的代码（在这里），这个解决方案每个元素只需要16B，并且在我进行的测试中比@jxh的解决方案更快，但我使用的是具有最大容量的简单数组，而不是像ArrayList这样的自动增长结构。

- kajacx

---

你能发一下你的代码吗？据我所知，这个想法类似于MinMaxPriorityQueue，所以我想知道为什么它不起作用。 - maaartinus

当然，请看这里的代码（http://pastebin.com/HC3Y3qdj），但它并不是非常干净，但您应该在第19个时期看到首次检查失败。 'add()'方法不起作用，因为我忘记了当元素改变楼层时，它与较低元素的比较器也可能会改变。 - kajacx

+1 纯粹是因为你有勇气使用众所周知的概念编写自己的代码。 - djechlin

我猜问题在于add中步骤1和2的顺序。通过与祖父交换，您可能会引入与永远不会得到修复的父级别不一致性。我尝试了另一种方式，到目前为止，测试似乎是通过的。（接口） - maaartinus

我错了，交换顺序是不够的，selftest 函数已经严重损坏。恐怕在交换之后，还需要检查更多的事情，并可能需要修复它们。 - maaartinus

我已经让它工作了，但是每一步都必须查看祖父母、父母、两个孩子和所有孙子。目前，它的速度非常慢，正如我的基准测试所示。jxh的解决方案要快得多，但我更喜欢你的想法。 - maaartinus

Answer 3

使用两个优先队列。

一种方法是在下一个轮到被删除的项目时为其打上标记。如果另一个队列看到了它，则跳过并移动到下一个。我不确定这种方法的复杂度，但它将取决于一些微妙的问题，例如一个项目在队列中比另一个项目多等待多长时间。建议根据您实际的情况进行性能分析。

- djechlin

---

+1 这很好，除了一件事，即可能在其中一个队列中累积已经消耗的东西（正如您所指出的）。它可能运行良好，并且进行分析也不是坏主意，但它无法告诉我对于其他输入会发生什么。 - maaartinus

Answer 4

这项任务的目标是希望保持目标优先队列的平摊运行时间相同。这些运行时间对于插入和删除都是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);
        }
    }
}

- Strikeskids

---

计数是不必要的复杂，你只需要一个Set。我实际上实现了你的解决方案（不完全相同，也缺少很多测试）。如果感兴趣，可以查看下面另一个答案中的链接。剩下的问题是可能会积累无效条目。 - maaartinus

正如我之前提到的，如果你的队列相对较小，使用两个优先队列是可以的（我不确定我理解标记的必要性）。你想要保持队列小的原因是，使用PriorityQueue进行删除的时间复杂度是O(n)，而不是O(log n)。这个poll()方法的实现在最坏情况下的时间复杂度是O(n log n)，这使得它的平均性能难以分析。 - jxh

你们两个都是不正确的。一个集合无法正确地处理同一对象的多个实例。因为优先队列可以有两个相同的对象，所以这是必要的。此外，平均性能并不难计算。虽然最坏情况下的一个poll可能是nlogn，但整个结构在使用期间的平均情况性能是log n。因为每个元素只从每个优先级队列中添加和删除一次，所以总体性能是log n。 - Strikeskids

@Strikeskids：也许在整个数据结构使用期间平均性能方面，你说得对。然而，如果使用大多倾向于一个队列，那么另一个队列的使用可能总是会产生O(n log n)的行为。更令人担忧的是，倾斜的使用情况可能导致很少使用的队列使用无限制的内存。 - jxh

@jxh 算法运行时间估计的整个重点是对整个队列进行估计。如果您非常担心其他队列的大小会增加，那么当它达到双倍于双队列的总大小时，您可以清除不存在于有问题队列中的元素。即使 poll 方法的一个执行比其他执行时间长得多，poll 的总体执行时间也将是 log n。 - Strikeskids

Answer 5

你可以做类似于这样的事情。

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;
  }
}

- Zixradoom

---

哦，天啊，我喜欢空间，但为什么有这么多人呢？ - Marco Acierno

哈哈，这仅仅是我习惯的风格。我的大部分大学朋友都不喜欢它。 - Zixradoom

@MarcoAcierno 我猜是因为空格打印起来很便宜，因为不需要墨水？然而，看到这么多空格让我的眼睛难受。另一个问题是 poll1 会保留在 q2 中的元素，这意味着我需要处理两次。 - maaartinus

已更新以考虑从其他队列中删除。 - Zixradoom

我的内部脑解析器在读取 Queue < T> 时一直抱怨“不可比较的类型” :-( - Marco13