“后半”有序的分组

上一期我们说了前半有序的数据，这次我们来看看“后半”有序的情况。

回顾一下前半有序的说法：我们要把数据集T按字段a,b排序时，如果T已经对a有序，则可以利用这一特点实现高性能算法。但后半有序却不是对称地把问题理解成T已经对b有序时要对a,b排序的任务，这个“后半”序信息并没有多大利用价值。这里说的“后半”有序问题是指：如果T已经对a,b有序，现在我们要将T按b排序。

这其实是很常见的情况。多维分析的数据集一般总会按某套（比如按日期、帐户）维度已经排好序，但我们可能希望按第二维度（帐户）再排序或分组，是否可以利用这个特点提高性能呢？

我们用a(i),b(i)表示表T中第i条记录的字段a,b取值。T对a,b有序，意味着如果a(i)=a(i+1)则必然有b(i)<=b(i+1)，即相邻的a值相同的记录的b值会构成一个有序子集。这时候如果我们能够把这些有序子集都找出来（遍历一次将a值发生变化的位置记下来即可）再进行归并排序，就可以得到对b有序的结果集了。而归并排序的复杂度相对较低（nlogk，k是归并路数，一般远小于n)，遍历一次的成本也不算高（相对于排序算法的复杂度nlogn），看起来这会是一个有效的手段。

但是，我们产生了一批有这样特征的数据来做实验，发现并没有比直接针对b使用快速排序（Quicksort）算法有明显的优势。

其实道理很简单，快速排序本来就是一种递归的分段排序再归并的算法，对于一个已经大体有序的数组，快速排序的速度已经能够很快。它的复杂度nlogn是指平均情况，对于上述这种“后半”有序的b值来讲，快速排序的复杂度也就是相当于nlogk的复杂度，和我们设想的办法一样。

这个方法对于排序没有效果，但对于分组却有意义。

我们把任务改变一下：对T按b分组并计算每个组的某种聚合值。

通用分组算法一般采用hash方案，即计算每个分组键的hash值，相同hash值的记录被分拣到一个小集合，然后在这个小集合内遍历找同值再聚合。复杂度，也就是比较次数，取决于hash函数重码率。在hash空间比较小的时候，重码率就会比较高，比较次数会较多，性能就受影响。为了保证性能，就需要分配较大的内存来存放hash表。另外，有些数据类型（长字串）的hash计算也比较慢，这也会影响性能。

而如果利用“后半”有序的特征则可以避免hash运算。我们将数据按b排序，然后再执行有序分组，即每条记录只与上一条记录比较，发现有不同时则新建一个分组，相同则聚合到当前组中。这样的分组运算的复杂度为n，而且没有hash计算和重码率的问题。如果排序足够快，就可以获得比hash分组更快的性能，而且并不需要太多内存用于存放hash表。

没有这个“后半”有序的前提时，先排序的时间成本通常会很高，超过hash分组的耗时。所以,排序分组的方案虽然简单易行，但商用数据库一般却不采用，有些开源数据库或报表工具为了图省事才会使用。然而，如果数据满足了这个条件时，排序就会快很多，有序分组的时间复杂度又很低，这样配合起来就可以获得更高的分组性能。

排序分组还有个好处在于，结果集是天然有序的。这样，易于实现大数据以及分布式分组运算。

目前的大数据分组一般也是采用hash方案，将原始数据先根据hash值分成几堆，然后分别针对每一堆再做分组。如果是分布式系统，在“分堆”时就会有大量的网络传输动作。而如果数据满足“后半”有序的条件，则可以采用类似大排序的方案来做分组，即读入每一段后进行排序分组再写出成临时数据，然后再将这些临时数据归并，因为每一段临时数据都是有序的，后续的归并就可以进行。在分布式运算时也可以每个分机独立做分组，最后统一归并汇总即可，过程中只有归并那一步需要网络传输。

排序分组算法因为性能不佳而在大多数场合被弃用，但在特定条件下却又能发挥出更好的效果。其实很少有什么算法一定好或一定坏，适合数据和运算特征的算法才是好算法。

在内存中要执行排序分组算法很简单，只要分两步先排序再分组就可以了，用基本方法组合即可，不需要实现专门方法。而对于大数据则不可以先做排序后再基于结果再做分组，因为大排序本身就要写出缓存数据，再来一轮大分组又写一次，就得不偿失了。针对大数据执行排序分组算法需要把这个算法固化到分组运算中，而不能用基本运算组合出来。所以，集算器在大分组方法中提供了选项供程序员根据现场情况决定是否使用排序分组算法。