用空值预填充 Tcl 指令会加快运行时间吗？
Will pre-padding Tcl dicts with empty values speed up runtime?
在解决 Tcl 中的 Advent of Code 2021 难题之一时，我想加快脚本的运行速度。
我的脚本使用一个字典，键作为 {x y} 坐标，0 或 1 作为值。对于循环的每次迭代，拼图的 x-y 感兴趣区域都会增加。因此，每次循环迭代都会将额外的键值对添加到字典中。
我想我曾经了解到 Tcl 字典可能会在必要时在内存中重新构建，这可能是由于添加了越来越多的键。如果是这样，这会导致运行时命中吗？
为了加快运行速度，预先填充一个字典，将键设置为与字典的预期最终大小相匹配的空字符串，这是个好主意吗？
在实现层面，是的，重建哈希 [=18=] 的成本与条目数成线性关系；毕竟，每个条目都必须放在扩大的哈希 table 数组的新桶中。但是，条目本身不需要重新分配；唯一的内存管理更改是针对散列 table 数组本身（分配新的，处理旧的），因此成本并不高。只要散列 table 中的条目数超过散列大小的固定乘数 table，就会触发重建；该加载因子是一个编译时间常数。 （字典是围绕带有 Tcl_Obj 键的散列 table 的包装器，主要是为了添加值语义并确保迭代顺序一致；这些对于重建语义来说并不重要。）没有概念预先调整散列大小 table；该实现不会以有用的方式公开它。它也不会缩小数组；一旦它长大了，它就会一直长大（大多数时候这根本不是问题）。
重建语义的复杂性是 Tcl 的关联数组据说具有随机枚举顺序的部分原因：它实际上不是随机的，但确定性算法对许多人们通常忽略的因素很敏感。在使用字典时，您无需关心这一点，迭代的顺序可以从构建值的方式中准确获知，而不管散列是如何完成的细节。
如果您使用从 0 开始的紧凑型整数键进行查找，则列表的速度会快得多，因为目前总是对字符串表示形式执行散列。复合整数键可能成为嵌套列表。
在解决 Tcl 中的 Advent of Code 2021 难题之一时，我想加快脚本的运行速度。
我的脚本使用一个字典，键作为 {x y} 坐标，0 或 1 作为值。对于循环的每次迭代，拼图的 x-y 感兴趣区域都会增加。因此，每次循环迭代都会将额外的键值对添加到字典中。
我想我曾经了解到 Tcl 字典可能会在必要时在内存中重新构建，这可能是由于添加了越来越多的键。如果是这样，这会导致运行时命中吗？
为了加快运行速度，预先填充一个字典，将键设置为与字典的预期最终大小相匹配的空字符串，这是个好主意吗？
在实现层面，是的，重建哈希 [=18=] 的成本与条目数成线性关系；毕竟，每个条目都必须放在扩大的哈希 table 数组的新桶中。但是，条目本身不需要重新分配；唯一的内存管理更改是针对散列 table 数组本身（分配新的，处理旧的），因此成本并不高。只要散列 table 中的条目数超过散列大小的固定乘数 table，就会触发重建；该加载因子是一个编译时间常数。 （字典是围绕带有 Tcl_Obj 键的散列 table 的包装器，主要是为了添加值语义并确保迭代顺序一致；这些对于重建语义来说并不重要。）没有概念预先调整散列大小 table；该实现不会以有用的方式公开它。它也不会缩小数组；一旦它长大了，它就会一直长大（大多数时候这根本不是问题）。
重建语义的复杂性是 Tcl 的关联数组据说具有随机枚举顺序的部分原因：它实际上不是随机的，但确定性算法对许多人们通常忽略的因素很敏感。在使用字典时，您无需关心这一点，迭代的顺序可以从构建值的方式中准确获知，而不管散列是如何完成的细节。
如果您使用从 0 开始的紧凑型整数键进行查找，则列表的速度会快得多，因为目前总是对字符串表示形式执行散列。复合整数键可能成为嵌套列表。