队列性能明智哪个更好的实现 - 数组或链表 [英] Queue performance wise which is better implementation - Array or Linked list

问题描述

当我必须插入很少的元素时，哪种方式可以更快地入队和出队，数组是否比链表更好?

Which way gives the faster enqueueing and dequeuing when I have to insert very few elements, Is array better than a linked list?

我需要插入一些元素，我必须从队列中删除并读取已删除的元素.如果它是数组，我可能必须在每次删除元素时修改索引.插入和删除也可能同时发生.

I need to insert few element and I have to remove and read that removed element from queue. If it is array I may have to modify the indexes every time I remove an element. Inserting and deleting may happen simultaneously also.

以下哪个更好?

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

推荐答案

这取决于您将执行的操作数量以及数组版本的具体实现方式.

It depends on how many operations you'll be performing and exactly how the array version is implemented.

如果您执行的操作相对较少，即总共少于 1000 个左右的入队/出队，那么数组会更快，因为它在内存中是连续的.保持一个指向前和一个指向后的指针，总是在后面添加，在前面出列.

If you're doing comparatively few operations, ie less than 1000 or so enqueue/dequeues in total, then an array would be faster because it is contiguous in memory. Maintain a pointer to the front and a pointer to the back, always add at the back and dequeue at the front.

另一方面，即使列表不超过 30 个左右的 elems，如果这必须持续很长时间，您也不会有任何数组大小调整问题，这是数组的潜在问题.

On the other hand even if the list is no longer than 30 or so elems ever, if this has to persist of a long period you won't have any array resizing issues which is a potential problem with the array.

链表保证了出色的性能，数组大小调整时必须注意.

Linked list is guaranteed excellent performance, array you have to watch for resizing.

正如@Hans Passant 所提到的，数组速度很快，因为它们具有 CPU 缓存位置.只要您的阵列很小，您的硬件就会优化性能，以便与存储阵列相关的内存将保留在 L2 中.可能在寄存器中的索引.这真的很快.从不需要很多元素的事实来看，在这种情况下数组将是理想的.是的，您在移动元素时必须修改索引，但这实际上是一个非常快的操作，因为如果您使用优化构建代码，索引将存储在注册商中.

As mentioned by @Hans Passant, arrays are fast because they have CPU cache locality. As long as your array is small, your hardware will optimize performance such that the memory associated with storing the array will be kept in your L2. Indices likely in registers. This is REALLY fast. Judging by the fact that you won't need many elements, an array would be ideal in this case. And yes, you will have to modify indices when you move elements, but this is actually an extremely fast operation since if you build the code with optimization the indices will be stored in registrars.

不过，这里有一个问题，您提到您可能必须同时进行入队和出队，这是否意味着它是并行的，即访问内存的多个线程?如果是这种情况，数组仍然会更快，但您会看到性能下降了 800 倍.为什么?因为处理器不再可以缓冲与您的队列相关的内存在模具上，但它必须存储在主内存中.此外，您还冒着在线程之间创建竞争条件的风险.想象一下，如果一个线程试图出队，而另一个线程试图入队，而列表中只有一个元素，你可能会遇到灾难.无论哪种方式，如果此应用程序非常受性能驱动，请务必使用 NDEBUG 和 -O3 标志进行编译(假设为 gcc).

Here's the catch though, you mention you may have to do both enqueue and dequeue at the same time, by this do you mean it's parallel ie multiple threads accessing the memory? If this is the case, arrays would still be faster, but you'll see something like a 800 fold decrease in performance. Why? because no longer can the processor buffer the memory associated with your queue on the die, but it must be stored in main memory. In addition, you're running the risk of creating a race condition between threads. Imagine if one thread tried to dequeue while another tried to enqueue and there was only one elem in the list, you could have disaster. Either way, if this application is very perfromance driven, be sure to compile (assuming gcc) with the NDEBUG and -O3 flags on.

第二次查看代码，并查看下面的其他答案，我建议您提高数组代码的效率并将其转换为圆形数组，因为听起来您对元素数量有上限.附带说明一下，您当前的数组实现效率极低，每次删除时都会向前复制队列的其余部分，这是没有意义的，只需增加一个指向第一个"索引的 int 指针即可.

Second Looking at the code, and looking below at other answers, I'd suggest making your array code more efficient and turning it into a circular array since it sounds like you have an upper bound on the number of elements. As a side note, you're current array implementation is extremely inefficient, every time you remove you copy forward the rest of the Queue, this makes no sense, just increment a int pointer to the "first" index.

伪代码:

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

只是不要忘记对正常的东西进行错误检查.

just don't forget to do error checking for the normal stuff.

这篇关于队列性能明智哪个更好的实现 - 数组或链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！