内存数据集产生的隐性成本

Original 蒋步星数据蒋堂 2023-02-25

当我们要对数据做一些非常规的复杂运算时，通常要将数据装入内存。现在也有不少程序设计语言提供了内存数据集对象及基本的运算方法，可以较方便地实现这类运算。不过，如果对内存数据集的工作原理了解不够，就可能写出低效的代码。

我们看数据集的产生。比如要生成一个100行2列的数据集，第一列x为序号，第二列xx是第一列的平方。

第一种方法，先生成一个空数据集，再一行一行地追加数据进去。

	A	B
1	=create(x,xx)
2	for 100	>A1.insert(0,A2,A2*A2)

第二种方法，直接产生相应行数的数据集。

	A	B
1	=100.new(~:x,~*~:xx)

这两种方法产生的结果集相同，实质的循环次数和每次循环的计算内容看起来也相同，但执行效率却不一样，后者要比前者更快。

数据集在内存中会保存成一个连续的数组。动态追加的数据集，会导致这个数组长度不断地变长，原先为这个数组分配的空间也要扩大。而内存分配不是一件很简单的事情，已经分配好的空间的后面内存很可能已经被占用而不能再继续扩大，只能重新分配一块更大的空间，然后将原空间内的数据复制过来。寻找空间和复制数据都要占用CPU时间，常常比运算本身的消耗都大。一般情况下，分配内存时会多预留一些空间来应付可能的增长，这样不致于每次追加都导致重新内存分配，但也不可能预留太多而浪费内存，如果追加次数过多，仍然还会有不少时间消耗到内存分配上。而如果事先知道数据集行数一次性创建出来后，则只需要在开始做一次内存分配即可。

动态追加的数据集虽然使用起来更灵活，但性能却赶不上静态数据集，在关注性能时要习惯性地避免。

其实，用这个例子来对比并不很恰当，因为有100.new(~:x,~*~:xx)这样的简单写法时，很少人会采用动态追加的数据集了，这里用这个例子主要是为了突出关键差异。而实际应用中会有不少情况下很难用一句话写出数据集生成，程序员就可能习惯性地采用动态追加的数据集了。

举一个更恰当的例子，我们想生成一个20行2列的Fibonacci数据集，第一列key为行号，即1,2,3,…；第二列value为值。Fibonacci数列的规则是：第1、第2行取值为1，从第3行起，取值为前两行之和。这个运算需要一步步实现，使用动态数据集就是很自然的想法了：

	A	B
1	=create(key,value)
2	>a=0	>b=1
3	for 20	>A1.insert(0,A3,b)
4		>b=a+b,a=b-a

不过，使用静态数据集的性能更好，即使计算本身仍然需要一步步实现，但数据集可以一次性产生：

	A	B
1	=20.new(0:key,0:value)
2	>a=0	>b=1
3	for A1	>A3.key=#A3,A3.value=b
4		>b=a+b,a=b-a

先生成一个都填满0的数据集（随便别的什么数也可以），然后再用循环把正确的值填进去。实质计算量仍然一样，但避免了动态分配。

除了行方向动态追加外，还有列方向的问题，即在数据集上增加新的列。

列追加比行追加要更为复杂。内存数据集中的一行是一条记录，物理上也是一个数组。因为数据结构很少改变，大多数内存数据集不会在生成这个数组时预留空间，否则内存浪费就太多了（每一行都有）。这时候每次追加列时都会发生前面说的重新分配空间，而且要针对每一行记录进行，再将原记录数据抄过来，这个动作的时间成本经常远远超过追加的那个列本身的计算。

内存数据集一般都有提供追加列的功能，这会带来方便性，但在关注性能时却要慎用。能不用则不用，一定需要时，也是如上所述，最好是一次性把需要追加的列都加上，而不要一遍遍地追加。

比如我们想在第一个例子中的数据集上再追加两个列y=x+xx和yy=y*y。看起来较自然的两步写法：