队列性能更好的实现 - 数组或链接列表

当我不得不插入很少的元素时，哪种方式可以提供更快的入队和出队，数组是否优于链接列表？队列性能更好的实现 - 数组或链接列表

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

从下面的情况哪个更好？

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

来源

2011-02-24 Anil Arrabole

CPU缓存位置为王。一个数组非常*难以击败。 – 2011-02-24 23:04:01

@Hans：阵列很难被击败，除非你需要调整它们，否则它们对你的缓存线太大了。尽管大小合理的数组链接列表相当不错。 – nmichaels 2011-02-24 23:10:57

使用nmichaels。如果您希望它对于小型和大型队列来说是快速的，则阵列的链接列表是最好的。 – Tobu 2011-02-27 17:11:30

这取决于你有多少操作来执行，这也正是数组版本中实现。

如果你正在进行比较少的操作，即少于1000个左右的入队/出队总数，那么阵列会更快，因为它在内存中是连续的。保持一个指向前面的指针和一个指向后面的指针，总是在后面添加并在前面出列。

另一方面，即使列表不超过30个元素，如果这种情况持续很长时间，您将不会有任何阵列调整大小问题，这是阵列潜在的问题。

链接列表保证了出色的性能，你必须注意调整大小。

编辑：正如@Hans Passant所提到的，阵列速度很快，因为它们具有CPU缓存局部性。只要你的阵列很小，你的硬件就会优化性能，这样与存储阵列相关的内存就会保存在L2中。指数可能在注册商中。这真的很快。根据你不需要很多元素的事实来看，在这种情况下数组将是理想的。是的，当你移动元素时你将不得不修改索引，但这实际上是一个非常快速的操作，因为如果你通过优化构建代码，索引将被存储在注册服务器中。

虽然你提到你可能必须同时进行入队和出队，这是否意味着它是并行的，即多线程访问内存？如果是这样的话，数组仍然会更快，但是你会看到性能降低800倍。为什么？因为处理器不再能够缓冲与你的队列相关联的内存，但它必须存储在主内存中。另外，您正在冒着在线程之间创建竞争条件的风险。想象一下，如果一个线程试图出队，而另一个线程试图排队，而列表中只有一个元素，则可能会发生灾难。无论哪种方式，如果这个应用程序的性能非常强大，请确保在NDEBUG和-O3标志上编译（假设gcc）。

第二编辑：看看代码，并在下面看其他答案，我会建议让你的数组代码更有效率，并把它变成一个圆形数组，因为它听起来像你有一个上限的数量元素。作为一个方面说明，你当前的数组实现是非常低效的，每次你删除你复制队列的其余部分，这没有任何意义，只需增加一个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; 
}

只是不要忘了做错误检查为正常的东西。

来源

2011-02-24 22:38:45 themaestro

我认为标题中的“DeQueue”是指[双端队列]（http://en.wikipedia.org/wiki/Deque），尽管它不完全清楚。 – nmichaels 2011-02-24 22:46:43

编辑我的问题，以明确 – 2011-02-24 23:27:55

伟大的东西。感谢themaestro。 – 2011-02-25 17:22:01

如果您要存储在队列中的元素总数有上限，请使用circular array。这消除了在连续向其末尾添加元素时调整数组大小的需要。

来源

2011-02-24 23:51:30

即使您有很多元素，数组实现可能是最快的。为了获得灵感，我看了一下GCC的C++出列。它将队列存储为数组数组。我不确定迭代器是否环绕在循环缓冲区中。数组实现也具有快速的随机访问，如果您稍后需要它。

来源

2011-02-24 23:55:37 antonakos

队列性能更好的实现 - 数组或链接列表

回答

相关问题