“后半”有序的分组

简介:

回顾一下前半有序的说法:我们要把数据集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值分成几堆,然后分别针对每一堆再做分组。如果是分布式系统,在“分堆”时就会有大量的网络传输动作。而如果数据满足“后半”有序的条件,则可以采用类似大排序的方案来做分组,即读入每一段后进行排序分组再写出成临时数据,然后再将这些临时数据归并,因为每一段临时数据都是有序的,后续的归并就可以进行。在分布式运算时也可以每个分机独立做分组,最后统一归并汇总即可,过程中只有归并那一步需要网络传输。

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

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


原文发布时间为:2018-11-20

本文作者:蒋步星

本文来自云栖社区合作伙伴“数据蒋堂”,了解相关信息可以关注“数据蒋堂”。

相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
相关文章
|
14天前
|
移动开发 HTML5
分组元素
分组元素。
18 3
|
14天前
|
人工智能 BI
经典问题之区间分组
经典问题之区间分组
|
10月前
有序序列合并
有序序列合并
47 0
|
7月前
|
算法 搜索推荐
排序篇(六)----排序小结
排序篇(六)----排序小结
23 0
|
JSON 数据格式 Python
一日一技:包含非hashable元素的列表如何去重并保持顺序?
一日一技:包含非hashable元素的列表如何去重并保持顺序?
87 0
|
算法 搜索推荐
用函数的方法通过冒泡法实现对一个数组(乱序)到有序排序(由大到小排序)
用函数的方法通过冒泡法实现对一个数组(乱序)到有序排序(由大到小排序)
84 0
用函数的方法通过冒泡法实现对一个数组(乱序)到有序排序(由大到小排序)
算法001:合并两个有序的数组
算法001:合并两个有序的数组
算法001:合并两个有序的数组
|
机器学习/深度学习 人工智能 BI
【集合论】有序对 ( 有序对 | 有序三元组 | 有序 n 元祖 )
【集合论】有序对 ( 有序对 | 有序三元组 | 有序 n 元祖 )
556 0
|
存储 人工智能 测试技术
求两无序不重复数组的交集
求两无序不重复数组的交集
85 0
|
SQL 监控 数据库

热门文章

最新文章