数据立方体的多路数组聚集

最近上课老师讲到数据立方体，讲到了数据立方体的预处理。为什么要预处理？因为如果不预处理的话，每次需要相关信息都需要从头计算，需要消耗大量的时间，因此为了便于选取数据，需要对数据立方体进行预处理。预处理一般分为两种：

1. 部分处理（冰山立方体，外壳立方体等等）
2. 完全处理，下文就要讨论一种完全处理的方式：多路数组聚集。

用最简单暴力的方法来进行完全处理的话，在应对很大的数据集时，将会做很多重复冗余的工作，因此就有了多路数组聚集的方式，它的基本思想是通过一次遍历，来计算出需要的所有同一维立方体。比如基础立方体是一个3-D立方体，那么用多路数组聚集的方法计算所有2-D立方体，只需要进行一次对基础立方体的遍历，在遍历的过程中同时对所有的2-D立方体进行处理。

虽然只需要一次遍历，但是考虑到节省内存开支，对于遍历的顺序也需要仔细考虑。一般来说，沿着最短的维开始遍历，然后是次短的，以此类推。为什么是这样，举下面一个例子：

• 首先来假设有一个3-D立方体，分为A, B, C三个维度，三个维度的大小分别是:40, 400, 4000;
• 现在将这个立方体沿每个维分为四个部分，那么在A, B, C三个维上，每一个基本段的大小就是10，100，1000。整个立方体也被分为了64个部分，如下图：
• 按序号升序开始遍历。当遍历到4时，2-D立方体（实际是表）中的$b_0c_0$b0​c0​已经计算完毕，同理，遍历到5时，$b_1c_0$b1​c0​遍历完毕，因此对于2-D立方体BC的计算，只需要为其预留1000*100即100000的大小即可。如下图：
• 继续遍历，当序号到达13时，2-D立方体AC中的$a_0c_0$a0​c0​可以计算，紧接着到14时$a_1c_0$a1​c0​也可以计算，但是为了避免重新遍历取得$a_1,a_0$a1​,a0​段的值，需要将它们计算过程中得到的值在之前遍历的过程中就保存起来，同理对于$a_3, a_4$a3​,a4​也是这样，因此需要预留40*1000的空间即40000。如下图：
• 继续遍历，当序号到达49是，2-D立方体AB中的$a_0b_0$a0​b0​可以计算得到，紧接着到50时，$a_1b_0$a1​b0​也可计算出，但是可以看到为了计算出这个值而又不需要重新遍历，需要把之前遍历的过程中计算的AB面相关中间值都保存下来（注意此时必须要预留整个面对应的大小，否则需要重复遍历）因此，预留的空间时40*400即16000。如下图：
• 此时需要预留的总内存的大小是：16000+40000+100000 = 156000

可以按照上述的方法按其它顺序遍历，会发现上述的遍历顺序取得最小的预留内存。