第 26 期:再谈有序分组

简介:

细心的读者可能会发现,我们在讨论有序分组时只研究了待分组集合的成员次序对分组运算可能的影响,但即然要考虑集合的有序性,那么结果集的成员次序是不是也有业务意义呢?

确实有意义,不过重要程度不如原集有序性。

分组结果集的有序性有两个方面,一是这些分组子集以什么次序返回,二是分组子集的成员是什么次序构成的。

在考虑有序集合的等值分组运算时,我们认为在缺省状态下分组子集保持原序最为合理,即每个分组子集成员第一次在原集中出现的次序。这个原因在于:其它次序(比如按分组字段值)可以针对结果集再排序而获得,而原序很可能在分组完成后就丢失了,或者至少再获得会比较困难。

比如我们要统计一本教科书中单词的重复次数,这是个简单的等值分组运算,缺省的结果集应当是以新单词在书中出现的先后次序为序的,这个次序是有业务意义的,向学生讲授这本书时可以按该次序让学生预习生词。而这个次序如果不是在分组运算后返回,就会很难获得了。需要给每个单词人为增加一个在书中出现的次序号,分组时同时把次序号的最小值也统计出来,然后再按这个值排序,最后又丢弃这个值。运算过程繁琐且效率低。

对位分组和枚举分组的结果集次序,显然应当与基准集合一致。而有序分组的结果集次序,则显然按每个分组产生的次序最为合理。

基于无序集合的 SQL 没有约定分组结果集的次序,返回结果集就不能保证原序了。在实践上,数据库一般是采用 HASH 方法来实现分组的,这时结果集的次序常常是 HASH 值的次序,而 HASH 值次序毫无业务意义,在关心次序时就还需要再排序,而为了获得排序依据就要象前面例子中说的那样在原集中新增序号信息,并参与到分组运算中,麻烦且低效。还有的数据库是用排序来做分组,结果集的次序就是分组字段(表达式)的次序,这个次序有一定业务意义了,但想还原出原序也不容易。

我们前面说过,SQL 中用 LEFT JOIN 的方法可以实现出对位和枚举分组的效果,但无论是 HASH 方法还是排序方法,结果集都会丧失基准集合的次序。而对位和枚举分组的结果集次序又是非常必要的,想通过再排序来获得这个次序,需要在基准集合中就要维护个次序号,这会使得本来简单的单值成员集合变成多字段的记录集合,而且当基准集合需要插入 / 删除成员时还要继续维护序号会是个很麻烦的事情,被改动成员后面的成员序号都要调整。所以 SQL 实现对位和枚举分组是个很繁琐的事情。

至于子集成员的次序,原则上也应当缺省保持原序,也就是在原集合中的次序。不过,它是否有意义取决于后续要执行的动作。

比如 SQL 就完全不关心这个次序,SQL 在分组后会强制聚合,而且只有 SUMM/COUNT 这些运算结果与执行次序无关的常规聚合运算,分组子集的成员次序就没有意义了。

但有些非常规聚合运算可能和执行次序有关,比如用登录日志(日志缺省都是按事件发生时刻有序的)列出每个用户的最后两次登录的时间间隔,就是按用户分组后取出分组子集的最后两条记录计算时间差,这时就会关心子集成员的次序了。不过,这已经是聚合运算的范畴了,我们将在后面的文章中再详细讨论。

作者:279400248
链接:http://c.raqsoft.com.cn/article/1533871136862
来源:乾学院
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相关文章
|
10月前
|
存储 算法
轮转数组问题:如何实现数组“整体逆序,内部有序”?“三步转换法”妙转数组(一)
这篇内容讲述了数组向右轮转k个位置的问题,主要分为两种解决思路。第一种是“轮转k次法”,直接在原数组上操作,每次循环k次,将数组末尾元素移到开头,时间复杂度为O(N*K),效率较低。第二种是“额外数组法”,使用额外数组存储部分元素,然后移动原数组元素,最后归还额外数组元素,时间复杂度和空间复杂度均为O(N)。文章还介绍了更高效的“三步转换法”,通过三次逆序操作实现数组轮转,分别是逆置后k个元素、逆置前n-k个元素以及整体逆置,这种方法时间复杂度为O(N)且空间复杂度为O(1)。
105 1
|
10月前
|
C语言
轮转数组问题:如何实现数组“整体逆序,内部有序”?“三步转换法”妙转数组 (二)
这是一个关于字符串处理的问题,要求将一句话中的单词顺序倒置,但保持单词内部的字符顺序不变。例如,"I like beijing." 变为 "beijing. like I"。解决方法可以分为三个步骤:分块、内部逆序和整体逆序。代码示例使用C语言实现,通过指针和while循环操作字符串数组。最终总结提到,无论先逆置哪个部分,只要确保所有部分都逆置过,结果都是相同的。
73 0
|
存储 程序员 C语言
c++ 如何做出实现一组数据的实际索引
c++ 如何做出实现一组数据的实际索引
|
SQL 关系型数据库 MySQL
|
存储 程序员 C语言
c++ 如何做出实现一组数据的实际索引
C++是一种计算机高级程序设计语言, 由​​C语言​​​扩展升级而产生 , 最早于1979年由​​本贾尼·斯特劳斯特卢普​​在AT&T贝尔工
|
人工智能 算法 BI
算法每日一题(合并两个有序的数组)
算法每日一题(合并两个有序的数组)
134 0
【牛客】合并两个有序的数组
【牛客】合并两个有序的数组
135 0
【牛客】合并两个有序的数组
开窗函数第一招式(排序聚合我要看顺序)
先看下我找的题目,ENG OMG 放心 我给安排了中文
142 0
开窗函数第一招式(排序聚合我要看顺序)
算法与数据结构全阶班-左程云版(二)基础阶段之2.链表、栈、队列、递归行为、哈希表和有序表(下)
本文主要介绍了一些常用的数据结构,包括链表、栈、队列、递归、哈希表和有序表。
算法与数据结构全阶班-左程云版(二)基础阶段之2.链表、栈、队列、递归行为、哈希表和有序表(下)
|
算法 Java API
算法与数据结构全阶班-左程云版(二)基础阶段之2.链表、栈、队列、递归行为、哈希表和有序表(上)
本文主要介绍了一些常用的数据结构,包括链表、栈、队列、递归、哈希表和有序表。
算法与数据结构全阶班-左程云版(二)基础阶段之2.链表、栈、队列、递归行为、哈希表和有序表(上)