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

Ответ 1

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

Наблюдение за исходным кодом, LinkedList - это O (1) для операций Queue.add, Queue.poll и Queue.peek.

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

Ответ 2

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

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

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

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

Начните с действительно упрощенной версии очереди с поддержкой "C/С++ like" и фиксированного размера.

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());

}
}

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