Быстрая очередь на Java

Question

Я ищу быструю queue реализацию в Java. Я вижу, что LinkedList реализует интерфейс Queue, но он будет работать так же быстро, как LinkedList, верно? Есть ли способ иметь очередь, которая будет быстрее, особенно для add (мне нужно только poll, add и проверить на empty). В дальнейшем мне может понадобиться PriorityQueue, но пока нет.

Answer 1

Если несколько потоков будут обращаться к очереди, рассмотрите возможность использования ArrayBlockingQueue. В противном случае взгляните на ArrayDeque. Из ArrayDeque API:

Этот класс, вероятно, будет быстрее, чем Стек при использовании в качестве стека и быстрее чем LinkedList при использовании в качестве очереди.

В частности, реализация очереди на основе массива уменьшает необходимость изменения размера нижележащего массива, если существующий массив имеет достаточную емкость, что делает добавления в очередь, как правило, быстрее, чем LinkedList. Имейте в виду, что ArrayBlockingQueue является ограниченной реализацией, тогда как ArrayDeque будет изменять размер по мере необходимости.

Обратная сторона в том, что LinkedList обычно обеспечивает гораздо более компактное представление, особенно в тех случаях, когда ваша очередь увеличивается или уменьшается в размерах. Например, если вы добавили 10 000 000 элементов к ArrayDeque, а затем удалили 9 999 999 элементов, базовый массив все равно будет иметь длину 10 000 000, тогда как LinkedList не будет страдать от этой проблемы.

В действительности, для однопоточного доступа к неблокирующей очереди я предпочитаю LinkedList. Я думаю, что различия в производительности настолько незначительны, что вы все равно не заметите разницу.

Answer 2

Я вижу, что LinkedList реализует интерфейс очереди, но он будет работать так же быстро, как и LinkedList, верно?

Глядя на исходный код, LinkedList равен O (1) для операций Queue.add, Queue.poll и Queue.peek.

Надеюсь, это достаточно быстро.

Answer 3

Если бы производительность связанного списка действительно была проблемой, альтернативой было бы реализовать «круговую очередь» в массиве, то есть очередь, в которой начальная и конечная точки перемещаются по мере добавления и удаления записей. Я могу дать более подробную информацию, если вы заботитесь. Когда я использовал языки, у которых не было библиотеки коллекций, я всегда реализовывал очереди, потому что их было легче писать, чем связанный список, и это было быстрее. Но со встроенными коллекциями, усилия по написанию и отладке моей собственной коллекции для особого случая не стоят проблем в 99% случаев: когда она уже написана, тот факт, что я мог написать ее не так, как мог переписать его так, как это делает Java, в значительной степени не имеет значения. И любой выигрыш в производительности, вероятно, будет слишком маленьким, чтобы стоить хлопот. Я подтипирую существующие коллекции, чтобы получить особенное поведение, в котором я нуждаюсь время от времени, но мне трудно думать о том, когда я в последний раз писал одну с нуля.

Answer 4

Возможно, вы захотите взглянуть на http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list, который вводит GapList. Эта новая реализация списка объединяет сильные стороны ArrayList и LinkedList.

Следовательно, он реализует интерфейс Deque, но также может быть настроен как вышеупомянутый ArrayDeque. Кроме того, вы также получаете все возможности интерфейса List бесплатно.

Answer 5

Начните с действительно упрощенной реализации очереди с вращением с отношением «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());

}
}

А затем улучшите его.