Мудрая производительность очереди, которая является лучшей реализацией - массив или связанный список

Question

Какой способ дает более быструю постановку в очередь и снятие очереди, когда мне нужно вставить очень мало элементов. Является ли массив лучше связанного списка?

Мне нужно вставить несколько элементов, и мне нужно удалить и прочитать этот удаленный элементиз очереди.Если это массив, мне, возможно, придется изменять индексы каждый раз, когда я удаляю элемент.Вставка и удаление могут происходить одновременно.

Какой вариант лучше из нижнего регистра?

typedef struct{
    mylist list;
    struct mylistQ *next;
}mylistQ;

Код массива

 static mylist myListQ[QUEUESIZE+1];
int qLast = 0;

void enqueue_element(mylist qItem)
{
        myListQ[qLast] = qItem;
    qLast++;
}

mylist dequeue_element()
{
 retryq:
   if(qLast >0) {
    mylist qReturn = myListQ[0];  
    int i;
    for (i = 0; i < qLast - 1; i++){
        myListQ[i] = myListQ[i + 1];
    }
    qLast--; 
    return qReturn;
     }
   else {
    goto retryq;
    }
}

Связанный список

 int qLast = 0;

mylistQ *headElement = NULL;   
mylistQ *tailElement = NULL;     

void enqueue_element(mylist *List)
{
    mylistQ *newnode;      
    newnode=(mylistQ*)av_malloc(sizeof(mylistQ));
    newnode->next=NULL;
    newnode->list=*List;
    qLast++;
    if(headElement==NULL && tailElement==NULL)
    {
        headElement=newnode;
        tailElement=newnode;
    }
    else
    {
        tailElement->next=newnode;
        tailElement=newnode;
    }
 }

mylist dequeue_element()
{
    mylistQ *delnode;      /* Node to be deleted */
    mylist Dellist;
    if(headElement==NULL && tailElement==NULL){
        LOg( "Queue is empty to delete any element");
        }
    else
    {
       Log("In dequeue_picture queue is not empty");
        delnode=headElement;
        headElement=headElement->next;
    if (!headElement){
        tailElement=NULL;
    }
        Dellist = delnode->list;
        av_free(delnode);
    qLast--;
    }
        return Dellist;
}

Answer 1

Это зависит от того, сколько операций вы будете выполнять и как именно будет реализована версия массива.

Если вы выполняете сравнительно небольшое количество операций, то есть менее 1000 или около того, ставите в очередь / удаляют в общей сложности, тогда массив будет быстрее, потому что он непрерывен в памяти. Сохраняйте указатель на передней панели и указатель на задней части, всегда добавляйте заднюю часть и удаляйте из нее лицевую сторону.

С другой стороны, даже если список не длиннее 30 или более элементов, если он будет сохраняться в течение длительного периода, у вас не возникнет проблем с изменением размера массива, что является потенциальной проблемой с массивом.

Связанный список гарантирует отличную производительность, массив, который вы должны следить за изменением размера.

EDIT: Как упомянул @Hans Passant, массивы бывают быстрыми, потому что имеют локальность кэша процессора. Пока ваш массив небольшой, ваше оборудование будет оптимизировать производительность, так что память, связанная с хранением массива, будет храниться в вашем L2. Индексы скорее всего в регистрах. Это действительно быстро. Судя по тому, что вам не нужно много элементов, в этом случае массив будет идеальным. И да, вам придется изменять индексы при перемещении элементов, но на самом деле это очень быстрая операция, поскольку, если вы строите код с оптимизацией, индексы будут храниться в регистраторах.

Здесь есть одна загвоздка, вы упомянули, что вам, возможно, придется одновременно выполнять и постановку в очередь, и удаление из очереди, то есть вы подразумеваете, что она параллельна, то есть несколько потоков обращаются к памяти? Если это так, массивы все равно будут быстрее, но вы увидите примерно 800-кратное снижение производительности. Зачем? потому что процессор больше не может буферизовать память, связанную с вашей очередью, на матрице, но она должна храниться в основной памяти. Кроме того, вы рискуете создать состояние гонки между потоками. Представьте, что если один поток попытался удалить из очереди, а другой попытался поставить в очередь, и в списке был только один элемент, вы можете потерпеть неудачу. В любом случае, если это приложение ориентировано на производительность, обязательно скомпилируйте (при условии gcc) с включенными флагами NDEBUG и -O3.

Второе редактирование: Посмотрев на код и посмотрев ниже на другие ответы, я бы посоветовал сделать код массива более эффективным и превратить его в круговой массив, поскольку он звучит так, как будто у вас есть верхняя граница числа элементов. Напомним, что текущая реализация массива крайне неэффективна: каждый раз, когда вы удаляете, вы копируете вперед оставшуюся часть очереди, это не имеет смысла, просто увеличивайте указатель int на «первый» индекс.

Псевдокод:

int ciruclarArray[SIZE];
int front = 0;
int back = 0;

void enqueue(int elem)
{
    circularArray[back] = elem;
    if(back < (circularArray.length - 1))
        back++;
    else
        back = 0;
    return elem;
}

int dequeue()
{
    int toReturn = circularArray[front];
    //do same check for incrementing as enqueue
    return toReturn;
}

только не забудьте выполнить проверку ошибок для нормальных вещей.

Answer 2

Если есть верхняя граница для общего количества элементов, которые вы собираетесь сохранить в очереди, используйте круговой массив .Это устраняет необходимость изменения размера массива при непрерывном добавлении элементов в его конец.

Answer 3

Даже если у вас много элементов, реализация массива, вероятно, самая быстрая. Для вдохновения я взглянул на деку C ++ в GCC. Он хранит очередь в виде массива массивов. Я не уверен, что итераторы обертываются как в кольцевом буфере. Реализация массива также имеет быстрый произвольный доступ, если он понадобится вам позже.