连续追加数据时,数组容量不足就可能需要分配更大的空间并复制旧内容。每次只增加很少容量,会频繁重复复制早已存在的元素;按比例增长通常会用更多空位换取较少复制。
本例比较两种确定规则:容量不足时加上固定增量,或把原容量翻倍。开始容量相同,逐次追加一个元素,扩容时复制当前已有的全部元素,普通追加本身不计为复制。没有删除或缩容。
初始容量6,固定增长每次增加4,共追加44个元素。翻倍策略只在不足时乘二。
大小 | 固增容量 | 本次复制 | 累计复制 | 翻倍容量 | 本次复制 | 累计复制 1 | 6 | 0 | 0 | 6 | 0 | 0 2 | 6 | 0 | 0 | 6 | 0 | 0 3 | 6 | 0 | 0 | 6 | 0 | 0 4 | 6 | 0 | 0 | 6 | 0 | 0 5 | 6 | 0 | 0 | 6 | 0 | 0 6 | 6 | 0 | 0 | 6 | 0 | 0 7 | 10 | 6 | 6 | 12 | 6 | 6 8 | 10 | 0 | 6 | 12 | 0 | 6 9 | 10 | 0 | 6 | 12 | 0 | 6 10 | 10 | 0 | 6 | 12 | 0 | 6 11 | 14 | 10 | 16 | 12 | 0 | 6 12 | 14 | 0 | 16 | 12 | 0 | 6 13 | 14 | 0 | 16 | 24 | 12 | 18 14 | 14 | 0 | 16 | 24 | 0 | 18 15 | 18 | 14 | 30 | 24 | 0 | 18 16 | 18 | 0 | 30 | 24 | 0 | 18 17 | 18 | 0 | 30 | 24 | 0 | 18 18 | 18 | 0 | 30 | 24 | 0 | 18 19 | 22 | 18 | 48 | 24 | 0 | 18 20 | 22 | 0 | 48 | 24 | 0 | 18 21 | 22 | 0 | 48 | 24 | 0 | 18 22 | 22 | 0 | 48 | 24 | 0 | 18 23 | 26 | 22 | 70 | 24 | 0 | 18 24 | 26 | 0 | 70 | 24 | 0 | 18 25 | 26 | 0 | 70 | 48 | 24 | 42 26 | 26 | 0 | 70 | 48 | 0 | 42 27 | 30 | 26 | 96 | 48 | 0 | 42 28 | 30 | 0 | 96 | 48 | 0 | 42 29 | 30 | 0 | 96 | 48 | 0 | 42 30 | 30 | 0 | 96 | 48 | 0 | 42 31 | 34 | 30 | 126 | 48 | 0 | 42 32 | 34 | 0 | 126 | 48 | 0 | 42 33 | 34 | 0 | 126 | 48 | 0 | 42 34 | 34 | 0 | 126 | 48 | 0 | 42 35 | 38 | 34 | 160 | 48 | 0 | 42 36 | 38 | 0 | 160 | 48 | 0 | 42 37 | 38 | 0 | 160 | 48 | 0 | 42 38 | 38 | 0 | 160 | 48 | 0 | 42 39 | 42 | 38 | 198 | 48 | 0 | 42 40 | 42 | 0 | 198 | 48 | 0 | 42 41 | 42 | 0 | 198 | 48 | 0 | 42 42 | 42 | 0 | 198 | 48 | 0 | 42 43 | 46 | 42 | 240 | 48 | 0 | 42 44 | 46 | 0 | 240 | 48 | 0 | 42 最后空位:固定增长2,翻倍4。
记录中的编号只用来区分本例对象,不应与大小排名或另一组记录的身份混淆。先核对单位和边界,再跟随中间值检查结果。空结果、零值与尚未确定是不同状态;分数保留精确含义,显示小数只为方便阅读。
每次追加后大小不得超过容量;没有扩容时复制数为零。总复制数是每次扩容前大小的和,不是最终数组长度,也不是最终容量。扩出来但尚未使用的格子占空间,却不是需要从旧数组复制的有效元素。
把两条容量曲线和累计复制量并排记录,尤其观察刚跨过容量边界的那一步。一次追加触发大量复制,并不意味着此前每次追加都同样昂贵;反过来,单次追加很便宜也不能说明整段过程总成本低。
这是操作次数模型,不等同实际分配耗时;内存分配器、缓存和元素移动方式都会影响测量。翻倍也不一定符合所有设备的内存预算,本例只是让时间与额外空间之间的取舍可计算。
练习时可以一次只改变一个条件,比较差异从哪个步骤开始。若自己的结果不同,先核对是否采用同样的规则,再定位第一个不一致的中间状态,不要只修改最终答案。输入与运算过程需要一起保存,才能判断结论究竟适用于哪一个具体场景。
以便获取最新的优惠活动以及最新资讯!