时间戳

首页 > 解决方案 > array.array 插入如何在 python 的引擎盖下工作？

python - array.array 插入如何在 python 的引擎盖下工作？

问题描述

在 python 中，array.array 是一个可变结构。

但是，我不确定插入操作在 array.array 结构中是如何工作的。

由于 array.array 使用的是连续内存，如果新元素不能以连续方式放置，它是否会创建一个新的内存块并复制数组的所有元素？它是否保留额外的未使用空间以防插入操作？

标签： pythonarrays

解决方案

清单[Python 3.Docs]: array - 高效的数值数组，以防万一。

任何在后台将数据保存在连续内存区域中的体面容器，分配的内存比保存当前元素数量所需的内存要多。
如果在插入（附加是一种特殊情况）元素时没有额外元素的空间会发生什么：

  1. 分配内存区域（当前大小+一（元素大小））
  2. 将数据复制到新区域
  3. 免费旧区
  4. 无论如何都完成了额外的小操作（如大小（计数器）更新，...）

正如所见，在追加（这是添加元素的最常见操作）时，会有很多工作需要时间和资源（CPU能力、内存）。

现代容器具有不断增长的策略算法：每次需要重新分配内存区域（容器已满）时，都会在现有大小上添加N个元素以计算新大小，等等：N每次都变大这样的重新分配发生了。那就是最小化（昂贵的）内存操作。
当然，在间隔的另一端可能会为容器分配大量内存（例如500 MiB），但这不可行，因为大量内存只会“坐”在那里保留以防拥有的容器可能需要它。
毕竟，这只是一个妥协的问题。

您可以检查[CPRPeference]: std::vector作为示例（大小和容量方法）。

回到我们的问题：array.array确实是一个分配未使用空间的现代容器。来自[GitHub]：python/cpython - (master) cpython/Modules/arraymodule.c：

/* This over-allocates proportional to the array size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 34, 46, 56, 67, 79, ...
 * Note, the pattern starts out the same as for lists but then
 * grows at a smaller rate so that larger arrays only overallocate
 * by about 1/16th -- this is done because arrays are presumed to be more
 * memory critical.
 */

至于插入算法本身，查看ins1函数：

  • 检查（并更新）大小，并在需要时增加内存
  • 插入位置之后的元素向末尾（“右”）移动一个位置
  • 新元素放置在插入位置

作为旁注，其他Python容器使用此技术，请查看[SO]：为什么列表会询问 __len__？（@CristiFati 的回答）了解更多详情。

推荐阅读