当我必须插入很少的元素时,哪种方式可以更快地入队和出队,数组比链表更好吗?
我需要插入一些元素,并且必须从队列中删除并读取该删除的元素。
如果它是数组,每次删除元素时我可能都必须修改索引。插入和删除也可能同时发生。
从下面的案例来看,哪一个更好呢?
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;
}
这取决于您将执行多少操作以及数组版本的具体实现方式。
如果您执行的操作相对较少,即总共少于 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;
}
只是不要忘记对正常的东西进行错误检查。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)