队列性能明智，这是更好的实现 – 数组或链接列表
当我必须插入很少的元素时，哪种方式可以提供更快的入队和出列，是否数组比链表更好？
我需要插入一些元素，我必须从队列中删除并读取已删除的元素。 如果是数组，我可能每次删除元素时都要修改索引。 插入和删除也可能同时发生。
从下面的案例中哪个更好？
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; }
这取决于您将执行的操作数量以及arrays版本的实现方式。
如果您执行的操作相对较少，即总共少于1000个排队/出队，则数组会更快，因为它在内存中是连续的。 保持指向前方的指针和指向后方的指针，始终在后面添加并在前面出列。
另一方面，即使列表不超过30个左右，如果必须持续很长一段时间，您将不会有任何数组resize问题，这是数组的潜在问题。
链接列表保证了出色的性能，您必须注意resize。
编辑：正如@Hans Passant所提到的，数组很快，因为它们具有CPU缓存局部性。 只要您的arrays很小，您的硬件就会优化性能，以便与存储arrays相关的内存保存在L2中。 可能在登记册中的指数。 这真的很快。 从你不需要很多元素的事实来看，在这种情况下，数组是理想的。 是的，你必须在移动元素时修改索引，但这实际上是一个非常快速的操作，因为如果你用优化构建代码，索引将存储在注册商中。
这里有一个问题，你提到你可能不得不同时进行入队和出队，这是否意味着它是并行的，即多个线程访问内存？ 如果是这种情况，arrays仍然会更快，但你会看到性能下降800倍。 为什么？ 因为处理器不再能够缓冲与芯片上的队列相关的存储器，但它必须存储在主存储器中。 此外，您还存在在线程之间创建竞争条件的风险。 想象一下，如果一个线程试图出列而另一个线程试图入队，并且列表中只有一个elem，那么你可能会遇到灾难。 无论哪种方式，如果此应用程序是非常性能驱动的，请务必编译（假设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; }
只是不要忘记对正常的东西进行错误检查。
如果要在队列中存储的元素总数存在上限，请使用圆形数组 。 当连续向其末尾添加元素时，这消除了调整arrays大小的需要。
即使你有很多元素，数组实现可能是最快的。 为了获得灵感，我看了一下GCC的C ++ dequeue。 它将队列存储为数组数组。 我不确定迭代器是否像循环缓冲区一样环绕。 如果您以后需要，arrays实现还具有快速随机访问。