题 为什么Stack 和Queue 用数组实现?


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

堆栈在内部使用 根据需要调整大小的数组,与队列和列表一样。 (第288页,第4段)

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

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


25
2018-06-08 19:03


起源


另一点是底层数组以循环方式使用,因此数组元素在头部和尾部移动时被回收(如果不超过边界)。 - Tim Lloyd
3个字:内存管理开销。 - Mehrdad
@SebastianNegraszus谢谢。你怎么找到的?我搜索了很多,没有找到任何东西。 - KooKoo
@KooKoo这是本页“相关”下的顶级链接之一。我不能说我是否会通过搜索找到它。 - Sebastian Negraszus


答案:


但O(n)最坏的情况

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

数组也使用  空间而不是链表(毕竟必须为每个元素存储一个额外的指针)。

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


22
2018-06-08 19:04



@Femaref:不 - 它真的被称为 deque不是 dequeue。 - Konrad Rudolph
此外,使用数组将为您提供本地化的好处。 - Brian Rasmussen
哦对不起。拼写“队列”是一个很常见的错误,所以我认为你已经堕落,没有冒犯。 - Femaref


这是对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是堆栈中的项目数。这似乎是一个非常糟糕的事情,除了两个因素:它几乎不会发生,因为扩展在每个增量加倍,并且阵列复制操作高度优化并且速度惊人。因此,实际上,扩展很容易被其他堆栈操作淹没。

同样对于队列。


20
2018-06-08 19:43



您的假设仅适用于值类型。如果T是引用类型,则两个实现都需要几乎相同的资源。因为数组条目将引用每个项目的堆元素。 - Michael Barabash
@MichaelBarabash - 这取决于你的意思“差不多”。如果您将我从Int32提供的示例转换为引用类型,那么除了您将引用类型值的存储添加到两者之外,所有内容都是相同的,这将完全相同。如果您使用的是64位,那么您还可以将存储值的大小加倍以容纳更大的引用,但无论哪种方式,总大小都会增加两种方法中的相同数量。就这样 额外 链表使用的存储空间仍然是额外的。 (继续...) - Jeffrey L Whitledge
但是,你正确的意思是链表开销占总数的一小部分。 - Jeffrey L Whitledge
杰弗里嗨,完全同意。 - Michael Barabash


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

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

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

这样做了 排列 到目前为止最有效的数据结构,其元素按顺序存储在内存中。到目前为止,链表是最糟糕的数据结构,其元素通过内存自然分散,可能会导致每个元素的非常昂贵的缓存未命中。

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


14
2018-02-22 10:29