在电子表格计算架构上应用稀疏数组技术的设计
柳鲲鹏
2007-1-20
关键字：电子表格 计算架构 稀疏数组
简介：电子表格的扩容，计算量大大增加。如果想达到理想性能，就必须在计算架构中应用稀疏数组技术。本文详细的讨论了设计与实现方法，在各OFFICE的电子表格计算架构首次创新性应该了稀疏数组技术。
电子表格的扩容... 1
算子计算流程... 1
数据分布分析... 2
数组的数据结构... 3
新的计算流程流程... 4
改进分析... 5
对小范围引用计算的影响... 5
对大范围引用计算的改进... 6
电子表格的扩容
电子表格是办公软件的重要组成部分，而电子云表格的最基本、最主要矛盾的功能是计算。人们除了要求计算正确之外，希望计算的速度性能也非常好。很难想象人们输入一个数字后要花大量的时间等待结果的出现，没有人喜欢以此锻炼自己的耐心。
从电子表格的容量来看，以前常见的大小是65536行，256列。随着社会的发展，需要处理的数据也越来越多。有的办公软件就开始扩容以适应这种变化。例如最新的MS OFFICE的电子表格容量就扩大了很多：行扩容为1048576（16倍），列扩容为16384（64倍）。容量增加到了原来的1024倍。有消息说有的办公软件准备扩容的倍数更多。如此在幅度的扩容，也对电子表格的计算性能提出了新的挑战。本人从事电子表格计算架构的设计、开发多年，深知在如此大幅度的扩容下，原有的计算架构已经不能满足要求，必须做出很大的改进。
算子计算流程
对电子表格的公式来说，其组成元素有：
算数（Operand）：如整数、浮点数、字串、地址引用等。一个公式必须有至少一个算数。
算子（Operator）：对一个或几个算数进行计算处理，如加、减、乘、除等。为了方便，我们也可以把函数当作算子。
格式（Format）：空格、换行等。为了让公式看起来更方便，使用者特意加的。
对于电子表格来说，公式的计算是非常复杂的。不仅因为各种各样的处理、转换，还因为公式中的每个算子进行计算时，结果都可能返回多个值（即数组）。这一点不仅在数组公式如此，对于普通公式也是必须的。也就是说，对于每个算子来说，计算都是以数组计算为其基础的，单个值的计算只是特殊情况而已。
那么在电子表格的计算架构中，一个算子的计算流程是什么样子的呢？以加算子为例，简要的计算流程伪代码如下：
//初始化左算数
leftOperand.initialize();
//初始化右算数
rightOperand.initialize();
//初始化保存结果的对象，rows\columns是两个算数初始化后再经过处理得到的
result.initialize(rows, columns);
//通过两层循环，计算所有的值
for(int i=0; i<rows; i++)
{
for (int j=0; j<columns; j++)
{
int leftValue = leftOperand.nextValue(i, j);
int rightValue = rightOperand.nextValue(i, j);
result.putValue(leftValue + rightValue);
}
}
//计算完成后，做一下收尾工作
rsult.finish();
通过上面的流程可以看出，对于大数据量的计算，最影响的，就是那个两层循环：参与计算的引用范围越大，那么计算量就越多。扩容后这个问题就会更明显。这也是我们进行优化改进的重点。那么，是否能够大量减少这里的循环量从而提高计算性能呢？我们先来看看电子表格中数据分布的情况。
数据分布分析
电子表格的容量增加了1000多倍，是不是数据量也相应增加了这么多倍呢？从日常经验来看，这是不会的（否则大家光输入数据也忙死了）。对于绝大多数（我认为唯一的例外情况是测试时）的工作表来说，数据分布有以下特点：
绝大多数的格子是空的。
一般只有几个区域范围内有数据。
如果有大量的数据，那么这些数据的值大多一样，或者是分属几种情况。
上述几个特点，很象数学上的稀疏矩阵——从计算的角度看，是稀疏数组。也就是说，在进行大数据量计算的时候，实际上大多数的计算结果是一样的。这就为改进计算架构提供了可能：如果能够把这部分的计算量通过某种技术节省下来，性能就会得到大幅改进。当然，本文讨论的内容是计算架构中的改进，不涉及工作表中的数据如何组织的（工作表的数据也应该按照稀疏数组的方式组织）。
对一个引用，其数据的分布有以下几种情况：
全空。
相同值。
部分数据不同，其他为空。
部分数据不同，其他相同值。
全部数据不同。
以上几种情况的组合。
需要说明的是，第3、4和5之间，有时并没有太大的差别，如何划分由具体的分类标准确定。
为了讨论方便，我们确定以下规则：
参与计算的工作表的一个矩形范围称为引用，以区别于数组。
这里所指的块（block），都指数组内的一个矩形（可能是整个数组）。
某个块中，如果只包含一个数据，或者包含多个数据，其中至少有一个数据不同于其他数据的，则称这个为数值块，块中的数据称为数值。
某个块中，如果其中的数据全部相同，则称这个区域为零值块，相同的值称为零值。特别的，空也是一种零值。
一个数组中，可以包含多个数值块、零值块。
显然，确定一个区域是否数值块，跟制定的策略有关。比如下表的一个数组：
这个数组可以划分为一个数值块和两个零值块，也可以划分为一个数值块。考虑到计算的方便和对性能的影响，划分的区域不宜太大，也不宜太小。就上面这种情况，我们认为划分为一个数值块最合理。
数组的数据结构
在计算过程中，形成数组有两种方式。一是本来就是数组，如={1,2,3}就包含一个数组。这种情况下，不会有很多的数据（这类数组的限制是行512，列64）。另外一种方式是通过引用计算产生的，如=1+A1:B2。由于引用范围是不确定性的（甚至可以是整个工作表），所以可能产生很大的数组，这是我们要讨论改进的。
通过引用产生的数组有以下几种情况：
只有一个数值块的数组。根据划分策略，如果引用的范围太小，或者其中没有发现零值，就会产生这种数组。
只有一个零值块的数组。由于整个引用范围都是零值，所以产生了这样的数组。
组合情况。
多数值块。
多零值块。
如果在计算架构中，增加了新的数组类型，整个的计算架构都要相应改动，代码也变得复杂多了。而且事实上，这是没有必要的。所以，我们这里只定义稀疏数组，其他都是稀疏数组的特殊情况。这样，我们把数组结构确定为：
TYPE+TOTAL_ROWS+TOTAL_COLUMNS
+VALUE_VLOCK_COUNT+ZERO_BLOCK_COUNT
+[BLOCK_INDEX+ROWS+COLUMNS+[VALUE_TYPE+VALUE_DATA]]
+[BLOCK_INDEX+ROWS+COLUMNS+ZERO_TYPE+ZERO_DATA]
[]之内的内容表示可选或重复。
需要强调的是，这里只是为了说明问题，并不代表真正的实用结构。不同的计算架构有自己的做法，需要做出相适应的改动。
新的计算流程流程
根据以上的设计，我们要对每个算子的计算流程进行改造。内容包括：
两个算数初始化后，要一起进行判断，确定各个要进行计算的数值块和零值块。对两个数值块，可能的关系有以下几种情况：
重叠。作为一个数值块进行计算。
相交。取两个数据块的最大范围作为一个新的区域。
不相交。那么就作为两个数据块计算。
对各个数值进行计算。
对各个零值块进行计算和处理。
于是，新的加法算子的计算流程伪代码就成了下面的样子：
//初始化左算数
leftOperand.initialize();
//初始化右算数
rightOperand.initialize();
//对比二者的数组情况，确定计算的各个数值块和零值块。
orgnize(leftOperand, rightOperand);
//对保存结果的对象进行初始化
result.initialize();
//对每个数值块进行计算计算
for (int blockIndex=0; blockIndex<blockNumber; blockIndex++)
{
//初始化一个数值块
result.initializeBlock(blockIndex, blocks);
//对这个数值块内的数据进行计算
for (int i=blocks[blockIndex].startRow; i<blocks[blockIndex].endRow; i++)
{
for (int j=blocks[blockIndex].startColumn; j<blocks[blockIndex].endColumn; j++)
{
int leftValue = leftOperand.nextValue(i, j);
int rightValue = rightOperand.nextValue(i, j);
result.putValue(leftValue + rightValue);
}
}
}
//之后对零值进行计算
for (int zeroIndex=0; zeroIndex<zeroNumber; zeroInex++)
{
result.initializeZero(zeroIndex);
int leftZero = leftOperand.nextZero(zeroIndex);
int rightZero = rightOperand.nextZero(zeroIndex);
result.putZero(leftZero + rightZero);
}
//做一些收尾工作
result.finish();
当然，上面只是一个简单的流程示意。如果要变成相应的程序，还要经过一番努力。而这之前，还要建立一个计算架构。这已经超出了本文的范围了。
改进分析
一项成功的改进，在解决已有问题的同时，不能产生新的问题。这项设计的改进，同样要求在解决大区域计算的性能的时候，不能对小区域计算的性能产生不好的影响。下面，我们分别对这两种情况进行分析。
对小范围引用计算的影响
对小范围引用来说，流程只多了几个简单的语句判断。所以不会对这种情况产生什么影响。另外，根据算子的流程，对各种值的访问，完全封装在算数之内。如果有必要，完全可能在这个算数内开辟一条直通车，而各个算子的计算流程、代码都不必改动。
对大范围引用计算的改进
在应用数组技术以后，对大范围引用的计算，计算量将大大节省，性能了得至极大的改进。这种改进，还需要高超的算法技术上：
对算数中各个数值块的关系判断。
对取值时的定位。如果数值块多了，由于各个值分布在不同的数值块上，如何迅速准确的定位，是一个体现技巧的大好时机。
对算数中的数据进行更有效的组织，也是一个很好的展现技术的地方。
各个函数的相应优化处理，也提出了新的要求。
限于篇幅，这里就不再对这些细节问题详细讨论了。下面以一列（1048576个格子）加一列为例（假设其中有一个各有1*1000个数值区），看看改进的效果（估计）：
附言
本人自从想出这个思路之后，首先是想申请专利，结果公司没有兴趣。后来投稿，发现要什么基金项目的，只能作罢。现在就正式发表在博客，希望对某些人有点启发。有人会问，那EXCEL有没有实现？我可以绝对肯定的回答，EXCEL 2003没有这样做，实际上EXCEL 2007也没有做。
