为什么Stack <T>和Queue <T>用数组实现？

Question

我正在Albahari兄弟的Nutshell中阅读C#4.0,我发现了这个:

堆栈在内部实现,其数组根据需要调整大小,与Queue和List一样.(第288页,第4段)

我不禁想知道为什么.LinkedList提供O(1)头尾插入和删除(这应该适用于堆栈或队列).可调整大小的数组有O(1)缓冲插入(如果我没记错的话),但O(n)最坏的情况(我不确定删除).它可能比链表使用更多的空间(对于大型堆栈/队列).

还有更多吗？双链表实现的缺点是什么？

Answer 1

但O(n)最坏的情况

的摊销最坏的情况下仍然是O(1).长期和短期插入时间平均 - 这是摊销分析的整个点(并且删除相同).

数组也比链表使用更少的空间(毕竟必须为每个元素存储一个额外的指针).

此外,开销远远低于链表.总而言之,基于数组的实现对于几乎所有用例来说都是(非常)更高效,即使偶尔访问需要更长时间(事实上,通过采取一些队列可以更有效地实现页面本身在链表中管理的优点 - 请参阅C++的std::deque实现.

Answer 2

以下是对100 System.Int32s 堆栈使用的内存资源的粗略估计:

数组实现需要以下内容:

type designator                          4 bytes
object lock                              4
pointer to the array                     4 (or 8)
array type designator                    4
array lock                               4
int array                              400
stack head index                         4
                                       ---
Total                                  424 bytes  (in 2 managed heap objects)

链表实现需要以下内容:

type designator                          4 bytes
object lock                              4
pointer to the last node                 4 (or 8)
node type designator         4 * 100 = 400
node lock                    4 * 100 = 400
int value                    4 * 100 = 400
pointer to next node  4 (or 8) * 100 = 400 (or 800)
                                     -----
Total                                1,612 bytes  (in 101 managed heap objects)

数组实现的主要缺点是在需要扩展时复制数组的行为.忽略所有其他因素,这将是O(n)操作,其中n是堆栈中的项目数.这似乎是一个非常糟糕的事情,除了两个因素:它几乎不会发生,因为每次增加时扩展加倍,并且阵列复制操作高度优化并且速度惊人.因此,实际上,扩展很容易被其他堆栈操作淹没.

同样对于队列.

Answer 3

这是因为.NET被设计为在现代处理器上运行.哪个比内存总线快得多.处理器的运行速度约为2千兆赫兹.机器中的RAM通常为几百兆赫兹.从RAM读取一个字节需要超过一百个时钟周期.

这使得CPU缓存在现代处理器上非常重要,大量的芯片空间被烧毁,使缓存尽可能大.典型的今天是L1缓存64 KB,最快的内存和非常接近处理器核心的物理位置,L2缓存256 KB,慢速和远离核心,L3缓存大约8 MB,更慢和更远离开,由芯片上的所有核心共享.

要使缓存有效,按顺序访问内存非常重要.如果需要L3或RAM存储器访问,读取第一个字节可能非常昂贵,接下来的63个字节非常便宜."高速缓存行"的大小,即内存总线的数据传输单位.

这使得数组成为迄今为止最有效的数据结构,其元素按顺序存储在内存中.到目前为止,链表是最糟糕的数据结构,其元素通过内存自然分散,可能会导致每个元素的非常昂贵的缓存未命中.

因此,除LinkedList <>之外的所有.NET集合都在内部实现为数组.请注意,Stack <>已经自然地实现为数组,因为您只能从数组的末尾推送和弹出元素.O(1)操作.调整数组大小是分摊O(logN).