數據蔣堂有序分組

知識 10-14

來源：數據蔣堂

作者：蔣步星

本文長度為1500字，建議閱讀3分鐘

本文為你講解以有序集合為考慮對象時，如何考慮成員次序對分組的影響。

我們知道，SQL延用了數學上的無序集合概念，所以SQL的分組並不關注過待分組集合中成員的次序。我們在前面討論過的等值分組和非等值分組，也都沒有關注過這個問題，分組規則都是建立在本身的成員取值本身上。但如果我們要拓展SQL，以有序集合為考慮對象時，那就必須考慮成員次序對分組的影響了，而且，現實業務中有大量的有序分組應用場景。

1. 序號分組

一個簡單的例子：將一個班的學生平均分成三份（假定人數能被3整除）。按我們在前面所說的分組定義，這也可以看成是一種分組，但這個運算在SQL中卻很難寫出來，因為分組依據和成員取值沒有關係。

如果使用我們在前面講有序遍歷語法時的#符號，這個問題就很容易解決了。

A.group( (#-1)*3A.len() ) // 按序號分成前1/3，中1/3，後1/3

A.group( (#-1)%3 ) // 還可以按序號每三個中取一個構成分組子集

用SQL實現這個運算就麻煩很多，需要先用子查詢造出一個序號，然後再執行類似的分組規則。

上面這個例子中其實還沒有真正關注成員的次序，只是說明了序號的作用，當待分組集合的成員是其它次序時也可以得到可用的結果。

我們再看更多例子。

處理文本日誌時，有些日誌的基本單位不是1行，而可能是3行，即每個事件總是寫出3行文本，這並不是多罕見的情況。對付這種日誌時，就需要把文本每3行拆成一個分組子集，然後針對每個分組再進行詳細的分析處理。這時要正確的分組運算就必須依賴於待分組集合中成員（文本日誌的行）的次序了。

入學考試之後，把學生按成績排序蛇行分拆成兩個班，即名次1,4,5,8,...在一個班，而2,3,6,7,...在另一個班，這樣能保證兩個班的平均名次是相同的。這個分組也可以用序號做出來：

A.sort@z(score).group(#%4

這裡用的分組值不再是常見的普通數值，而是一個布爾量，相當於按「真「值和「假」值分成兩個組，真值對應第一個班，假值對應另一個班。本質上講，這還是個等值分組，只是用到的分組值可以是任意泛型。

顯然，這個分組的正確性也嚴重依賴於待分組集合的成員次序。

順便說一句，這又是一個只關注分組子集而不關心聚合值的例子。

按序號分組在很多情況下就是用序號來計算出分組依據，然後就變成普通的等值分組了。那麼有沒有不能簡單地轉換成等值分組的情況呢？

2. 值變化分組

有一組嬰兒出生記錄，是按出生次序排序的，我們現在關心連續出生的同性別嬰兒數量超過5的有多少批？

簡單想，這就是先GROUP，計算每組COUNT值，然後數出有幾個大於5的。後兩步很簡單，問題是怎麼GROUP？

直接按嬰兒性別分組當然是不對的，必須考慮次序，依次掃描記錄，當嬰兒性別發生變化時則產生一個新組。這種分組顯然沒法直接用等值分組做出來了。

我們可以提供一個有序分組方法來實現這種分組：當考察值發生變化時就產生一個新的分組。

A.group@o(gender).count(~.len()>5) // @o選項表示分組值變化時將產生新分組。

用SQL就麻煩很多，需要先造成中間標誌和變數來生成組的序號，大概是這樣

SELECT COUNT(*) FROM

(SELECT ChangeNumber FROM

(SELECT SUM(ChangeFlag) OVER (ORDER BY birthday) ChangeNumber FROM

(SELECT CASE WHEN gender=LAG(gender) OVER ( ORDER BY birthday) THEN 0 ELSE 1 END ChangeFlag FROM A))

GROUP ChangeNumber HAVING COUNT(*)>5)

這樣的SQL，看懂都不是很容易的。而且必須藉助birthday這種欄位來形成次序，而前述的有序分組寫法在原數據有序時根本用不著這個信息。

這種場景同樣可能出現在文本分析中。每個用戶的事件日誌可能有多行，而且行數不確定，但寫日誌時會在每個行開始處寫上用戶號。這樣我們可以按這個用戶號進行有序分組，它變化時就說明是另一個用戶的事件了。

即使是普通的等值分組，如果事先知道原集合對分組欄位有序，也可以使用這種方案來實施，這將獲得更高的性能，比資料庫常用的HASH分組方案要快得多，而且特別適合大數據遍歷的情況。

3. 條件變化分組

再看一個著名的問題：一支股票最長連續上漲了多少天？

這個問題當然可以直接遍歷去解決，不過我們現在用分組的思路來處理，至少在SQL體系下只能這麼做（嚴格些說，這是目前找到的最簡單可行的辦法）。

將股票收盤價按日期排序，然後將連續上漲的日期分到同一組，這樣只要考慮哪一組成員數最多即可。更明確地說，就是當某天上漲了，就把這一天和前一天分到一個組中，某天下跌了，則產生一個新組。

用SQL實現這個思路，同樣需要用中間標誌和變數來生成組序號：

SELECT MAX(ContinuousDays) FROM

(SELECT COUNT(*) ContinuousDays FROM

(SELECT SUM(RisingFlag) OVER (ORDER BY TradingDate ) NoRisingDays FROM

(SELECT TradingDate,

CASE WHEN ClosingPrice>LAG(ClosingPrice) OVER (ORDER BY TradingDate THEN 0 ELSE 1 END) RisingFlag

FROM A))

GROUP BY NoRisingDays)

如果有專門的有序分組方法以及以前說過的有序遍歷語法，這個運算就很簡單了：

A.sort(TradingDate).group@i(ClosingPrice

與SQL不同，雖然實現思路完全一樣，但寫出來是分步的，而不是一個多層嵌套語句，並且書寫和理解都要容易得多。

同樣地，這種場景也會在文本分析中有用。不確定行數的日誌中，有時會在事件開始時寫一個標誌串，當掃描到這個標誌串的時候就產生一個新的分組，有序分析的條件可設定為當前掃描行和指定文字相同，這樣就能保證同一事件的日誌信息在同一個組中。

後兩種有序分組的情況，理論上當然也可以轉換成等值分組來處理（用SQL就要這麼做，這也能從另一個側面說明SQL運算體系的完備性），但確實是相當麻煩的，所以我們一般不把它再當成等值分組來處理了。

到目前為止的分組討論，都是假定待分組集合已經準備好，其成員可以被隨機訪問到。但假設數據量巨大而不能全部讀入時，如果繼續做這種假定，會導致頻繁的外存交換而性能極差，這時需要再設計以流方式邊讀入邊分組並且邊聚合的運算體系。事實上日誌分析中更常見的是這種情況，這些問題我們將再撰文研究，但基本方法思路仍然離不開上面這些內容。

專欄作者簡介

潤乾軟體創始人、首席科學家

清華大學計算機碩士，著有《非線性報表模型原理》等，1989年，中國首個國際奧林匹克數學競賽團體冠軍成員，個人金牌；2000年，創立潤乾公司；2004年，首次在潤乾報表中提出非線性報表模型，完美解決了中國式複雜報表製表難題，目前該模型已經成為報錶行業的標準；2014年，經過7年開發，潤乾軟體發布不依賴關係代數模型的計算引擎——集算器，有效地提高了複雜結構化大數據計算的開發和運算效率；2015年，潤乾軟體被福布斯中文網站評為「2015福布斯中國非上市潛力企業100強」；2016年，榮獲中國電子信息產業發展研究院評選的「2016年中國軟體和信息服務業十大領軍人物」；2017年, 自主創新研發新一代的數據倉庫、雲資料庫等產品即將面世。

數據蔣堂

《數據蔣堂》的作者蔣步星，從事信息系統建設和數據處理長達20多年的時間。他豐富的工程經驗與深厚的理論功底相互融合、創新思想與傳統觀念的相互碰撞，虛擬與現實的相互交織，產生出了一篇篇的瀝血之作。此連載的內容涉及從數據呈現、採集到加工計算再到存儲以及挖掘等各個方面。大可觀數據世界之遠景、小可看技術疑難之細節。針對數據領域一些技術難點，站在研發人員的角度從淺入深，進行全方位、360度無死角深度剖析；對於一些業內觀點，站在技術人員角度闡述自己的思考和理解。蔣步星還會對大數據的發展，站在業內專家角度給予預測和推斷。靜下心來認真研讀你會發現，《數據蔣堂》的文章，有的會讓用戶避免重複前人走過的彎路，有的會讓攻城獅面對扎心的難題茅塞頓開，有的會為初入行業的讀者提供一把開啟數據世界的鑰匙，有的甚至會讓業內專家大跌眼鏡，產生思想交鋒。

數據蔣堂 |常規遍歷語法

編輯：黃繼彥

校對：朱江華峰

為保證發文質量、樹立口碑，數據派現設立「錯別字基金」，鼓勵讀者積極糾錯。

若您在閱讀文章過程中發現任何錯誤，請在文末留言，或到後台反饋，經小編確認後，數據派將向檢舉讀者發8.8元紅包。

同一位讀者指出同一篇文章多處錯誤，獎金不變。不同讀者指出同一處錯誤，獎勵第一位讀者。

感謝一直以來您的關注和支持，希望您能夠監督數據派產出更加高質的內容。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！