动态表扩张和收缩的摊还分析
本文主要分析了动态表扩张和收缩过程中的摊还代价。
摊还分析
当我们对一个数据结构做一系列的操作时，我们不仅希望知道操作的所有时间，也希望知道每一步操作的平均时间，摊还分析就是计算每一步操作的平均代价。值得注意的是，摊还分析不同于平均情况分析，它并不涉及概率，因此可以保证最坏情况下每个操作的平均性能。
假设我们进行 n 步连续的操作，在最坏的情况下总的花费时间为 $T(n)$，则摊还代价为 $T(n)/n$
动态表
在某些应用程序中，我们无法预见会将多少对象保存在表中。我们为一个表分配了固定的内存空间，随后可能出现空间不足的情况。此时，我们必须重新给表分配更大的内存空间，并将原来表中的数据复制到新的空间中。同样，当表中存在大量的空间剩余时，我们可以给它重新分配更小的内存空间。
在这里，我们要考虑的一个核心问题是，重新分配多大的空间才是合理的？如果分配的空间过小，会导致我们需要频繁的分配空间，以适应表中数据的增加，这必然会导致时间性能的上升；但如果分配的空间过大，会导致内存空间的浪费。因此我们需要一个好的策略，实现时间复杂度和空间复杂度的平衡。
表的扩张
我们先考虑只允许向表中插入数据的情况。当我们向一个满的表插入数据时，我们需要扩张表——分配一个包含更多空间的新表。由于我们总是需要表位于连续的内存空间中，因此必须为更大的新表分配一个新的数组，然后将数据从旧表复制到新的表中。
一个常用的分配策略是：新表的空间为旧表的2倍。用C语言写一个简单的动态表。
代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Init_size 1
/* define dynamic array */
typedef int datatype;
typedef struct array {
size_t length, pos;
datatype *a;
}List;
/* append new element in list */
int append(List *newlist, datatype n) {
if (newlist->length == newlist->pos) {
// create new space
datatype *newspace = calloc(newlist->length*2, sizeof(datatype));
if (newspace == NULL)
return 1;
// copy elements from old array to new array
memcpy(newspace,newlist->a,sizeof(datatype)*newlist->length);
free(newlist->a);
newlist->length *= 2;
newlist->a = newspace;
}
newlist->a[newlist->pos++] = n;
return 0;
}
/* print array information */
void show(List *newlist) {
printf("space: %lu\nelements: ", newlist->length);
for (int i = 0; i < newlist->pos; i++) {
printf("%d ", newlist->a[i]);
}
printf("\n");
}
int main(void) {
int *init = calloc(Init_size, sizeof(datatype));
List new = {Init_size, 0, init};
for (int i = 0; i < 8; i++){
if (append(&new, i) == 1){
printf("memory error\n");
break;
}
show(&new);
}
return 0;
}
程序的运行结果为：
space: 1
elements: 0
space: 2
elements: 0 1
space: 4
elements: 0 1 2
space: 4
elements: 0 1 2 3
space: 8
elements: 0 1 2 3 4
space: 8
elements: 0 1 2 3 4 5
space: 8
elements: 0 1 2 3 4 5 6
space: 8
elements: 0 1 2 3 4 5 6 7
摊还分析
假设我们对一个空表执行了 n 次插入操作，我们来计算一下操作的代价。由于表每次扩张，其空间都变为原来的两倍，因此表的实际长度必然为 2 的幂。我们两种情况进行讨论：
- 第 i 次操作时表未装满，我们只需要在表中插入新的元素，因此代价为 $c_i=1$。
- 假如 $i-1=2$ 的幂，即第 i 次操作时，表已经装满，需要动态扩张，因此我们需要重新分配空间，并在新的表中插入 i 个元素，代价为 $c_i = i$。
所以 n 次操作的总代价为：
$$\sum_{i=1}^{n} c_i \leq n + \sum_{j=0}^{lgn}2^j < n+ 2n = 3n$$
因此，单一操作的摊还代价不会大于 3。这样的设计保证了摊还代价为 $O(1)$。
表的收缩
当我们设计表的收缩策略时，我们希望满足以下条件：
- 表操作的摊还代价应该有一个常数上界
- 表空间的利用率应当有一个常数下界，保证空间的有效利用
对于表的收缩策略，我们直观的认为，当插入数据时应当将表的存储空间加倍，那么删除数据使表空间利用率不足一半时，应当将表的规模减半，这样表的空间利用率大于等于 0.5，但这样的设计存在致命的缺陷。我们考虑以下场景。
当表已经处于充满状态时，我们对他进行反复的插入、删除操作。
第一个插入操作会导致表的扩张，空间会扩张为原来的2倍，此时我们再进行删除操作，表会收缩至原来的1/2，而接下来的操作又会引起表的扩张。以此类推，每个操作的摊还代价为 $O(n)$。
我们对此策略进行改进：
当删除操作导致表的利用率不到1/4时，我们将表的空间收缩为原来的1/2。
这样做使得表的空间利用率不会低于1/4，同时所有操作的摊还成本依然为 $O(1)$。
python代码分析
python的list使用相似的扩张和收缩策略，我们先对他做简单的研究
>>> a = []
>>> sys.getsizeof(a)
72
我们先创建一个空表 a，可以看到空表占72 bytes，接着我们对空表.append(1)，看一下表 a 所占用空间的变化。
>>> b = [1] # create a new list
>>> sys.getsizeof(b) # a list with one element occupy 80 bytes
80
>>> a.append(1)
>>> sys.getsizeof(a)
104
我们先创建一个只有一个元素的list，发现它占据了80个bytes，由此可知，每个element占据8个bytes，接着我们对表a 做.append(1)，发现 a 的空间变为了 104个bytes，和我们之前预想的不同。
那么python具体是如何实现动态表的扩张的呢，这时候我们需要RTFS——python的源代码：
static int
array_resize(arrayobject *self, Py_ssize_t newsize)
{
char *items;
size_t _new_size;
...
/* Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize. If the newsize is 16 smaller than the
current size, then proceed with the realloc() to shrink the array.
*/
if (self->allocated >= newsize &&
Py_SIZE(self) < newsize + 16 &&
self->ob_item != NULL) {
Py_SIZE(self) = newsize;
return 0;
}
if (newsize == 0) {
PyMem_FREE(self->ob_item);
self->ob_item = NULL;
Py_SIZE(self) = 0;
self->allocated = 0;
return 0;
}
/* 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.
*/
_new_size = (newsize >> 4) + (Py_SIZE(self) < 8 ? 3 : 7) + newsize;
items = self->ob_item;
/* XXX The following multiplication and division does not optimize away
like it does for lists since the size is not known at compile time */
if (_new_size <= ((~(size_t)0) / self->ob_descr->itemsize))
PyMem_RESIZE(items, char, (_new_size * self->ob_descr->itemsize));
else
items = NULL;
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
self->ob_item = items;
Py_SIZE(self) = newsize;
self->allocated = _new_size;
return 0;
}
从这一段代码中，我们可以看出python的内存分配策略。我们来解释一下这条代码。
newsize：操作后，实际需要存储的元素个数_new_size：操作后，这条 list 实际分配的内存空间self->allocated：未操作前，list实际分配的内存空间Py_size(self)：上一次进行内存分配时，list内存储数据的数量
首先，python会判断内存空间是否足够，且利用率够高：
if (self->allocated >= newsize &&
Py_SIZE(self) < newsize + 16 &&
self->ob_item != NULL) {
Py_SIZE(self) = newsize;
return 0;
}
假如之前分配的内存空间已经够用，且存储元素数量和之前相比没有明显的减少，则不改变内存空间。
如果不满足以上条件，python就重新计算所需要的内存空间：
_new_size = (newsize >> 4) + (Py_SIZE(self) < 8 ? 3 : 7) + newsize;
当我们对一个空列表进行插入操作时，内存会以以下形式扩张
self->allocated |
Py_size(self) |
newsize |
_new_size |
|---|---|---|---|
| 0 | 0 | 1 | 0+3+1=4 |
| 4 | 1 | 2 | 不变 |
| 4 | 2 | 3 | 不变 |
| 4 | 3 | 4 | 不变 |
| 4 | 4 | 5 | 0+3+5=8 |
$~$
内存空间的增长序列为：0, 4, 8, 16, 25, 34, 46, 56, 67, 79, …
假如Py_SIZE(self) >= newsize + 16，说明此时实际存储的元素个数相比之前，明显减少，需要收回一部分内存，举例来说：
self->allocated |
Py_size(self) |
newsize |
_new_size |
|---|---|---|---|
| 20 | 20 | 4 | 0+7+4=11 |
$~$
新的内存空间小于之前的内存空间，从而收回了一部分内存。