optimization - 基本队列优化

Question

如何为典型的队列优化：

访问/存储

内存使用情况

除了尝试在其上运行压缩算法之外，我不确定是否要减少内存，但这将花费相当多的存储时间作为权衡 - 我必须重新压缩我认为的所有内容。

因此，我在想带有指针的典型链表....一个圆形队列？

有任何想法吗？

谢谢

编辑：不管上面是什么；本质上如何制作最快/最少内存密集型的基本队列结构？

Answer 1

链表实际上并不是很典型（除非在函数式语言中或者当新手错误地认为链表比动态数组快时）。动态循环缓冲区更为典型。增长（以及，可选地，收缩）的工作方式与动态数组略有不同：如果“数据保存部分”越过数组的末尾，数据应该以保持连续的方式复制到新空间（简单地扩展数组会在数据中间产生间隙）。

像往常一样，它有一些优点和一些缺点。

缺点：

• 稍微复杂的实现
• 不适合无锁同步

优点：

• 更紧凑：在最坏的情况下（当它刚刚增长或即将缩小但还没有时）它有大约 100% 的空间开销，单链表几乎总是有 100%或更多的开销（除非数据元素大于指针），双向链表更糟糕。
• 缓存效率：读取发生在接近于先前的读取，写入发生在接近于先前的写入。因此缓存未命中很少见，当它们确实发生时，它们会读取最相关的数据（或者在写入的情况下：它们得到一个可能很快会再次写入的缓存行）。在链表中，局部性很差，每次缓存未命中的大约一半都浪费在开销上（指向其他节点的指针）。

通常这些优点大于缺点。