Java 中的快速队列

A fast queue in Java

提问by Eqbal

I am looking for a fast queueimplementation in Java. I see that LinkedListimplements the Queueinterface, but it will only be as fast as a LinkedListright? Is there a way to have a queue that will be faster especially for add(I only need poll, addand check for empty). Down the line I may also need a PriorityQueuebut not yet.

我正在寻找queue在 Java 中的快速实现。我看到LinkedList实现了Queue接口，但它只会和一个一样快LinkedList吗？有没有办法让队列更快，特别是对于add（我只需要poll，add并检查empty）。接下来，我可能还需要一个，PriorityQueue但还没有。

采纳答案by Noel Ang

I see that LinkedList implements the Queue interface, but it will only be as fast as a LinkedList right?

我看到 LinkedList 实现了 Queue 接口，但它只会和 LinkedList 一样快，对吗？

Eyeballing the source code, LinkedList is O(1) for Queue.add, Queue.poll, and Queue.peek operations.

观察源代码，LinkedList 对于 Queue.add、Queue.poll 和 Queue.peek 操作的复杂度为 O(1)。

I hope that's fast enough.

我希望这足够快。

回答by Adamski

If multiple threads are going to be accessing the queue then consider using an ArrayBlockingQueue. Otherwise take a look at ArrayDeque. From the ArrayDequeAPI:

如果多个线程要访问队列，请考虑使用ArrayBlockingQueue. 否则看看ArrayDeque。从ArrayDequeAPI：

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

此类用作堆栈时可能比 Stack 快，用作队列时比 LinkedList 快。

Specifically an array-based queue implementation reduces the need to resize the underlying array if the existing array has sufficient capacity, thus making additions to the queue generally faster than LinkedList. Be aware that ArrayBlockingQueueis a bounded implementation whereas ArrayDequewill resize as required.

具体来说，如果现有数组有足够的容量，则基于数组的队列实现减少了调整底层数组大小的需要，从而使添加到队列的速度通常比 快LinkedList。请注意，这ArrayBlockingQueue是一个有界实现，而ArrayDeque将根据需要调整大小。

The flip-side is that LinkedListwill typically provide a much more compact representation, particularly in cases where your queue grows and shrinks by a large amount. For example, if you added 10,000,000 elements to an ArrayDequeand then removed 9,999,999 elements, the underlying array would still be of length 10,000,000 whereas a LinkedListwould not suffer from this problem.

另一方面，LinkedList这通常会提供更紧凑的表示，特别是在您的队列大量增长和缩小的情况下。例如，如果向 an 添加 10,000,000 个元素ArrayDeque，然后删除 9,999,999 个元素，则底层数组的长度仍为 10,000,000，而 aLinkedList不会遇到此问题。

In reality, for single-threaded access to a non-blocking queue I tend to favour LinkedList. I imagine the performance differences are so negligable you wouldn't notice the difference anyway.

实际上，对于对非阻塞队列的单线程访问，我倾向于使用LinkedList. 我想性能差异是如此微不足道，您无论如何都不会注意到差异。

回答by Jay

If performance of a linked list was really a problem, an alternative would be to implement a "circular queue" in an array, i.e. a queue where the start and end point move as entries are added and deleted. I can give more details if you care. When I was using languages that did not have a library of collections, this was how I always implemented queues because it was easier to write than a linked list and it was faster. But with built-in collections, the effort of writing and debugging my own collection for a special case is not worth the trouble 99% of the time: When it's already written, the fact that I could write it a different way faster than I could re-write it the way Java does is pretty much an irrelevant fact. And any performance gain is likely to be too small to be worth the trouble. I sub-type existing collections to get special behavior I need now and then, but I'm hard-pressed to think of the last time that I wrote one from scratch.

如果链表的性能确实是一个问题，另一种方法是在数组中实现一个“循环队列”，即在添加和删除条目时起点和终点移动的队列。如果你关心，我可以提供更多细节。当我使用没有集合库的语言时，我总是这样实现队列，因为它比链表更容易编写并且速度更快。但是使用内置集合，为特殊情况编写和调试我自己的集合的努力在 99% 的时间都不值得麻烦：当它已经被写入时，事实上我可以用不同的方式比我更快地编写它以 Java 的方式重新编写它几乎是一个无关紧要的事实。任何性能提升都可能太小，不值得麻烦。

回答by Thomas Mauch

You may want to have a look at http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-listwhich introduces GapList. This new list implementation combines the strengths of both ArrayListand LinkedList.

您可能想看看http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list，它引入了GapList. 这个新的列表实现结合了ArrayList和的优点LinkedList。

It therefore implements the Dequeinterface, but can also be presized like the above mentioned ArrayDeque. In addition, you also get all the possibilities of the Listinterface for free.

因此它实现了Deque接口，但也可以像上面提到的那样预先设置大小ArrayDeque。此外，您还可以List免费获得界面的所有可能性。

回答by Jan Cajthaml

Start with really simplistic rotating Queue implementation with "C/C++ like" attitude and fixed size.

从真正简单的旋转队列实现开始，具有“类似 C/C++”的态度和固定大小。

class SimpleQueue<E>
{

int index   = 0;
int head    = 0;
int size    = 100;
int counter = 0;
E[] data    ;


@SuppressWarnings("unchecked")
SimpleQueue()
{
    data = (E[]) new Object[size];
}

public void add(E e)
{
    data[index]=e;
    index=(index+1)%size;
    counter++;
}

public E poll()
{
    E value = data[head];
    head=(head+1)%size;
    counter--;
    return value;
}

public boolean empty()
{ return counter==0; }

//Test
public static void main(String[] args)
{
    SimpleQueue<Integer> s = new SimpleQueue<Integer>();

    System.out.println(s.empty());

    for(int i=0; i< 10; i++)
        s.add(i);

    System.out.println(s.empty());

    for(int i=0; i<10; i++)
        System.out.print(s.poll()+",");

    System.out.println("\n"+s.empty());

}
}

And then improve it.

然后改进它。