E92de68f6153810f6e25ec47f710a3dd
内存分配扩张的一点探索

其实本章内容确切的来说和Python并无实质直接联系,但是在上文我们阐述PyListObjectlist_resize操作的时候提高了Python的内存分配增长公式,因此我们接着这个话题继续进行研究。

分摊时间复杂度

在上文PyListObjectlist_resize操作里,有这么一段注释:

This over-allocates proportional to the list 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().

linear-time amortized behavior 的意思表达的是线性的分摊时间复杂度

研究过算法的同学都知道时间复杂度一说,其意义是表征一个特定操作在运算过程中相对的耗时级别。比如我们常见的排序算法:

  • 归并排序 O(nlogn)
  • 冒泡排序 O(n^2)

那么什么是分摊时间复杂度呢?我们就以append操作来举例好了。

假设我数组操作每次空间满的时候我都只分配加一大小的新空间,那么由于堆多次空间分配的随机性,我需要将之前的N个对象,全部搬移到新申请的空间处,然后当append新对象的时猴,新的对象附加在最后。

注:上述数组空间使用的是连续空间,不是链表型。

Ok,每一次搬迁原有N个对象的操作过程就是N次操作,也就是O(N)的时间复杂度。而append的时间复杂度是直接附着在最后,因此操作的复杂度仅仅是O(1)而已。如果我们进行了N次的append操作,那时间复杂度就是N * O(N),达到了O(N^2)的地步。

很明显,我们看到了每次分配大小都仅仅加一的弊端。满溢后的每一次append都造成严重的时间损耗。

因此,有很多前辈大牛就想出了按2的倍数的内存申请方式。比如我们现在仍然是N个对象的数组需要申请新的空间,我们一次性申请了2N的连续空间。第一次搬迁的操作自然而然仍是O(N)的时间复杂度。但是对于接下来的N次append,由于我们已经预留了足够的空间,因此直接append即可。

因此总N次的时间复杂度就变成了 O(N) + N * O(1),时间复杂度仍然是O(N)

2的倍数是个不好的策略

上文我们用2的倍数的扩展思路讲述了什么是线性的分摊时间复杂度。但是实际上,2的倍数的策略是一个非常烂的主意。这一章节我们就重点阐述这为什么是个很烂的分配方式。

假设我现在有N个对象,按照始终2倍大小的增长方式,我需要的分配空间就是2N,4N,8N,16N,依此类推K次需要的操作空间就是N * 2^k。

这会带来什么问题呢?

top Created with Sketch.