在电子表格计算架构上应用稀疏数组技术的设计

在电子表格计算架构上应用稀疏数组技术的设计

　

　

柳鲲鹏

2007-1-20

　

关键字：电子表格 计算架构 稀疏数组

简介：电子表格的扩容，计算量大大增加。如果想达到理想性能，就必须在计算架构中应用稀疏数组技术。本文详细的讨论了设计与实现方法，在各OFFICE的电子表格计算架构首次创新性应该了稀疏数组技术。

　

　

电子表格的扩容... 1

算子计算流程... 1

数据分布分析... 2

数组的数据结构... 3

新的计算流程流程... 4

改进分析... 5

对小范围引用计算的影响... 5

对大范围引用计算的改进... 6

　

　

电子表格的扩容

　　电子表格是办公软件的重要组成部分，而电子云表格的最基本、最主要矛盾的功能是计算。人们除了要求计算正确之外，希望计算的速度性能也非常好。很难想象人们输入一个数字后要花大量的时间等待结果的出现，没有人喜欢以此锻炼自己的耐心。

　　从电子表格的容量来看，以前常见的大小是65536行，256列。随着社会的发展，需要处理的数据也越来越多。有的办公软件就开始扩容以适应这种变化。例如最新的MS OFFICE的电子表格容量就扩大了很多：行扩容为1048576（16倍），列扩容为16384（64倍）。容量增加到了原来的1024倍。有消息说有的办公软件准备扩容的倍数更多。如此在幅度的扩容，也对电子表格的计算性能提出了新的挑战。本人从事电子表格计算架构的设计、开发多年，深知在如此大幅度的扩容下，原有的计算架构已经不能满足要求，必须做出很大的改进。

　

　

算子计算流程

　　对电子表格的公式来说，其组成元素有：

1. 算数（Operand）：如整数、浮点数、字串、地址引用等。一个公式必须有至少一个算数。
2. 算子（Operator）：对一个或几个算数进行计算处理，如加、减、乘、除等。为了方便，我们也可以把函数当作算子。
3. 格式（Format）：空格、换行等。为了让公式看起来更方便，使用者特意加的。

　　对于电子表格来说，公式的计算是非常复杂的。不仅因为各种各样的处理、转换，还因为公式中的每个算子进行计算时，结果都可能返回多个值（即数组）。这一点不仅在数组公式如此，对于普通公式也是必须的。也就是说，对于每个算子来说，计算都是以数组计算为其基础的，单个值的计算只是特殊情况而已。

　　那么在电子表格的计算架构中，一个算子的计算流程是什么样子的呢？以加算子为例，简要的计算流程伪代码如下：

　　//初始化左算数

　　leftOperand.initialize();

　　//初始化右算数

　　rightOperand.initialize();

　　//初始化保存结果的对象，rows\columns是两个算数初始化后再经过处理得到的

　　result.initialize(rows, columns);

　　//通过两层循环，计算所有的值

　　for(int i=0; i