【性能优化】5.5 [有序遍历] 后半序分组
5.5 后半序分组
我们处理了“前半有序”的情况，那么“后半有序”是不是也会可利用的地方？
还是这个帐户交易表，在每个帐户下的数据是按日期排序的，现在我们想统计所有日期下的交易总额。整个数据表不是按日期有序的，不能使用有序分组。不过几年的日期也不多，仍然是个小分组，可以轻松地用 groups 写出来：
A |
|
1 |
=file("trades.btx").cursor@b(dt,amount) |
2 |
=A1.groups(dt;sum(amount)) |
但这并没有利用到帐户内数据对日期有序的特点，仍然是常规的哈希分组机制。
我们以这个例子来说明如何利用“后半有序”。
我们先假定按有序分组的机制来实现，遍历到记录时只和当前最后一条分组记录对比分组键以决定是新产生分组还是累计上去。在同一帐户内 dt 是有序的，就不会出现错误，也能减少哈希值的计算和比对。遍历到下一个帐户时，dt 会重新开始排序了，新记录的 dt 就可能比当前最后一条分组记录中的 dt 更小，发现这个现象时，只要拿这个 dt 再和当前分组记录的第一条开始比对，找到合适的地方，要么累计上去要么插入一条，然后再去遍历下一条交易记录，而分组记录表中已经比对过的不用再比对了，因为它也是有序的。要等遍历到下一个帐户时才会再次从头和分组记录表比对。
结果就是，一个个帐户遍历下去时，这个分组记录表也会被一遍遍地从头到尾比对一次. 有序分组每遍历一条记录时只会比一次，而这种算法有可能会比多次才能找到合适的位置，但只要比过的分组记录要等下一个帐户被遍历到才会再次比对。
整体比对次数当然会比有序分组更多，但如果大部分数据都是有序的，从头对比（遍历到下一个帐户时）的发生占比相对（在同一个帐户内）较少，增加的比对次数并不会太多，有可能比哈希分组更有优势。
这里有个关键在于有可能要对分组记录表进行插入，而常规的顺序插入是个非常复杂的动作，要保持有序，要把后面的成员都向后移动以腾出空位，这个操作的复杂度会把利用有序带来的优势都抵消掉。所以，这里需要使用链表来做保持分组记录表，插入时只改变插入点前后的成员属性，不会搬动大量成员。使用链表后不能再做二分查找了，不过分组记录表本来也是顺序对比的，在这里影响并不大。
SPL 把这个机制也做成了选项，可以直接使用：
A |
|
1 |
=file("trades.btx").cursor@b(dt,amount) |
2 |
=A1.groups@h(dt;sum(amount)) |
groups@h 时就不会使用常规哈希方法了，而是使用上面说的链表机制。
大分组也可以执行这种后半有序的分组，算法是类似的，只是当内存中的分组记录表大到一定程度时就要写出到缓存中，然后重新开始这个过程。最后把这些缓存文件再一起归并，大体过程和排序大分组类似，也能够自适应大小分组。
A |
|
1 |
=file("trades0.btx").cursor@b() |
2 |
=A1.groupx@h(id;sum(amount)) |
假定 trade0 按日期排序，同一日期内的交易按帐户排序，上面代码就可以较高性能地计算出每个帐户的交易总额。
不过，大分组上的主要成本在于缓存文件的写和读，使用这种算法仍会有优势，但不会像小分组那么显著。
理论上，这个算法可以针对于任何数据工作，并不要求一定要“后半有序”，因为其实任何数据都可以看成后半有序的。但如果有序程度太低，频繁导致要从头和分组记录表对比，那性能就会赶不上哈希分组了，所以使用时要注意了解数据的有序程度。
后半有序程度越高，这个算法优势就越明显，有序程度到了极致时就变成有序分组了。
和前半有序的方法可以用于排序不同，这个办法用于排序的意义并不大。小排序通常使用的快速排序算法已经可以利用原数据的有序程度，而大排序时主要成本在于缓存文件的写和读上，这种算法并不会减少缓存文件的容量，优势就不明显了。
分组运算因为可能会产生聚合，实际的缓存文件通常要比原数据小，有时候还会小很多，这样内存中对比的时间成本占比会变高，算法的优势就会显现出来。如果分组键在全表接近唯一，实际上的聚合很少发生，缓存文件和原表区分不大，那这个算法也不会比哈希分组或排序分组有多大优势。
