c – 使用向量类实现堆栈的链接列表与动态数组

矢量调整大小

矢量根据需要动态调整自身大小.它通过分配新的内存块,将数据从旧块移动(或复制)到新块,释放旧块来实现.在一个典型的情况下,新的大小是旧的大小的1.5倍(与流行的看法相反,2x在实践中似乎很不寻常).这意味着在重新分配时的短时间内,它需要的内存大约相当于实际存储数据的2.5倍.剩下的时间,使用的“块”至少为2/3rds,最多为完全满.如果所有尺寸都具有相同的可能性,我们可以预期平均约为5/6.从另一个方向看,我们可以预期大约1/6,或大约17％的空间在任何给定时间被“浪费”.

当我们通过这样的常数因子进行调整时(而不是,例如,总是添加特定大小的块,例如以4Kb增量增长),我们得到所谓的分摊的常量时间添加.换句话说,随着阵列的增长,调整大小的@L_696_8@会少得多.数组中项目的平均复制@L_696_8@趋于一个常数(通常约为3,但取决于您使用的增长因子).

链表分配

使用链表,情况有很大不同.我们从未看到调整大小,因此我们没有看到一些插入的额外时间或内存使用情况.与此同时,我们确实看到了基本上一直使用的额外时间和记忆.特别是,链表中的每个节点都需要包含指向下一个节点的指针.根据节点中数据的大小与指针的大小相比,这可能导致显着的开销.例如,假设您需要一堆int.在int与指针大小相同的典型情况下,这将意味着50％的开销 – 始终如此.指针大于int的情况越来越常见;两倍大小相当常见(64位指针,32位int).在这种情况下,你有大约67％的开销 – 即,显然足够的是,每个节点在存储数据时投入的空间是指针的两倍.

不幸的是,这通常只是冰山一角.在典型的链表中,每个节点都是单独动态分配的.至少如果您要存储小数据项(例如int),为节点分配的内存可能(通常会)甚至大于您实际请求的数量.所以 – 你要求12个字节的内存来保存一个int和一个指针 – 但你获得的内存块可能会被舍入到16或32个字节.现在你看到至少75％的开销,很可能~88％.

就速度而言,情况非常相似：动态分配和释放内存通常很慢.堆管理器通常具有可用内存块,并且必须花时间搜索它们以找到最适合您要求的大小的块.然后它(通常)必须将该块分成两部分,一部分用于满足您的分配,另一部分用于满足其他分配.同样,当你释放内存时,它通常会返回到相同的空闲块列表,并检查是否有一个相邻的内存块已经空闲,因此它可以将两者重新连接在一起.

分配和管理大量内存块非常昂贵.

缓存使用情况

最后,在最近的处理器中,我们遇到了另一个重要因素：缓存使用率在矢量的情况下,我们将所有数据彼此相邻.然后,在正在使用的向量部分结束之后,我们有一些空的内存.这导致优秀的缓存使用 – 我们使用的数据被缓存;我们没有使用的数据对缓存几乎没有影响.

使用链表,指针(以及每个节点中可能的开销)分布在整个列表中.也就是说,我们关心的每一条数据都紧挨着它,指针的开销,以及分配给我们没有使用的节点的空白空间.简而言之,缓存的有效大小与列表中每个节点的总体开销大致相同 – 即,我们可能很容易看到只有1/8的缓存存储了我们关心的日期,而7 / 8ths致力于存储指针和/或纯垃圾.

摘要

当您拥有相对较少的节点时,链接列表可以很好地工作,每个节点都是相当大的节点.如果(对于堆栈来说更典型)你正在处理相对大量的项目,每个项目都是单独的非常小,你不太可能看到节省时间或内存使用.恰恰相反,对于这种情况,链表更可能基本上浪费大量的时间和记忆.