【数据蒋堂】第28期:迭代聚合语法

发布时间:2017-10-30 分类:数据蒋堂 Tag:,,,,

sjjt-28

我们讨论过的常规聚合运算如SUM/COUNT和非常规聚合运算如maxp/top,都是事先设计好的聚合函数。但如果我们想实现一个以前没有定义过的运算怎么办?是否可以用已有的语法和函数组合出来?比如想做连乘运算,显然这也算是一种聚合。

(题外话:连乘可以用exp(SUM(ln(x)))来做,不过这有点耍赖了,而且这还对付不了成员是负数的情况。)

 

要设计这样的语法方案,我们来看看这些聚合结果值是如何被程序计算出来的。

SUM:先设置一个初始值0,然后遍历集合的每个成员,每次将成员值加到初始值上,直到成员被遍历完。

COUNT:设置初始值0,遍历集合成员,每次碰到非空成员将初始值加1,直到遍历完。

AVERAGE:这个不能边遍历边计算了,不过AVERAGE=SUM/COUNT,算是个导出函数,不用考察了。

MAX:设置初始值为无穷小,遍历集合成员,每碰比初始值更大的成员值则替换初值值,直到遍历完。

MIN:和MAX一样,只是初始值和比较方向是反的。

 

我们发现,这些基本聚合运算的实现方案都有相同的过程:先设置一个初始值,然后遍历集合成员,让当前成员和初始值计算得到一个新的初始值,再进入下一轮循环,直到遍历完整个集成,那个初始值就变成我们需要聚合值了。

这样,我们可以设计一个实现迭代计算的聚合函数:

A.iterate( x, a )

以a为初始值遍历集合A,每次用当前初始值和当前遍历员计算表达式x,得到的结果替换当前初始值,直到遍历完成,返回最后的x值。

这里有个问题,在x中用什么标识符或符号来表示当前初始值和当前成员。当前成员可以用我们以前讨论过的~符号,当前初始值要再找个符号,我们用两个~来表示。

这样,前面那些聚合运算就都可以用这个迭代函数来表示:

A.SUM() = A.iterate( ~~+~, 0 )

A.COUNT() = A.iterate( ~+if(~~,1,0),0 )

A.MAX() = A.iterate( if(~>~~,~,~~), -inf )

A.MIN() = A.iterate( if( ~<~~,~,~~), inf )

连乘当然也很简单了:A.iterate( ~~*~, 1 )

我们提到过的非常规聚合也可以,比如返回单值的maxp可以写成

A.maxp(F) = A.iterate( if (~==null || ~.F>>~~.F,~,~~), null )       这是F表示字段名

但返回集合的情况要麻烦一些:

A.maxp(F) = A.iterate( if(~==null || ~.F>~~.F,~,if(~.F==~~.F,~~|~,~~)), null )       |表示集合的并运算

A.top( n ) = A.iterate( merge(~~,~).to(n), [inf]*n )        merge函数指归并排序运算,to(n)选出集合的前n个成员

A.distinct() = A.iterate( if(~~.contain(~),~,~~|~), [] )         contain函数判断集合是否包含某成员

不过,不是所有的聚合运算都容易用iterate来描述,毕竟聚合运算的定义太宽泛了,比如中位数就不合适用itertate描述。另外,象first/last这种聚合运算不需要遍历,也没必要用iterate描述。

迭代聚合语法不仅能够帮助我们写出一些新的聚合运算,而且它本身就是一种遍历方法。能用迭代语法写出来的聚合运算,都可以一边遍历一边计算,遍历完了就得到聚合值,目标集合只需要遍历一次。

我们知道,计算机不能直接针对外存计算,当数据量很大而不能全部加载进内存时,迭代聚合算法可以只需要较小的内存(能够放下聚合值)就可以完成大数据量的聚合。这对于实现分组后的聚合运算很有意义。

分组子集的总体数据规模和原集是一样大的,基于拆分后的子集再做聚合运算就意味着要遍历两次,对于纯内存运算还不是大问题,但如果数据量大到内存放不下时,就会发生外存倒换的现象,这样效率是非常低的。iterate作为一种聚合运算当然可以用在分组之后,分组后进行能够被iterate描述的聚合运算时,就不需要对原数据遍历两次了,可以一边分组一边聚合,只需要较小的内存(能保存下结果集)就可以完成。

这大概也是SQL没有提供分组子集的原因之一,在发明SQL的那个年代内存很小,绝大多数原始数据都不可能放入内存,先产生分组子集后再聚合的运算效率难以容忍,而分组后直接聚合,且都是可以用iterate描述的聚合,虽然仍然可能发生外存倒换(结果集也装不下内存时)的现象,但问题的严重程度要小很多。

 

更多《数据蒋堂》文章