2018/05/09

下大雨了，于是就想表達一些只有下雨才能表達的東西。夜半酒酣驚覺起，使我流淚憶江南…前天晚上下班帶著小小在暴雨中狂奔，非常舒服，其實也算是流言終結者吧。反駁一下幾千年來在我國北方通過長輩代代相傳的淋雨和感冒之間的因果關系。

昨天早上很早起來，聽雨作文，今天早上繼續，文章不算太長。

合并兩個有序鏈表

這是一道超級常見的課后作業題或者面試題，網上答案一搜一籮筐，我自己也寫了一個 不會編程版 ：
有序鏈表合并C語言遞歸版–我稍微會一點編程 ：https://blog.csdn.net/dog250/article/details/80154795
寫是寫出來了，但寫得不好。不管怎么說也算是一個答案。

但是，這個問題有什么實際意義呢？或者說它是不是僅僅就是一個單純考查你對編程技法掌握程度的問題呢？類似我們大學教科書課后的習題？用 “*” 號打印個菱形？寫個冒泡排序？

其實并不是。在看一個實際問題之前，我們先暫時拋開代碼實現，來看一下所謂的 合并兩個有序鏈表 在 觀感 上到底需要做什么。這個問題相信一個完全不懂IT技術的人也能給出答案。

如下圖，兩個有序鏈表，假設均為升序鏈表：

所謂的合并，其實就是做下面的事：

就是這么一個簡單的過程，在出現大小交錯的錨點處，斷開舊鏈接，接入新鏈接，僅此而已，剩下的問題就是如何用Java，C/C++這種語言來表達了，事實證明，用編程語言表達它并不比用自然語言表達它更困難。

好的，原理就這么簡單，當你拋開代碼的時候，才會知道它到底有什么用。現在來看一個實際問題

Linux FQ實現

Linux內核在3.12版本引入了FQ這個Schedule，它的實現參照我的這篇文章：
Linux FQ 隊列實現原理淺析 ：https://blog.csdn.net/dog250/article/details/80025939

其實，你有沒有發現，FQ的dequeue例程要做的就是把N個流所代表的N個有序鏈表進行合并并輸出的過程，只不過這個過程是動態的！我來解釋一下。

在FQ中，每一個socket代表一個流，系統為每一個流維護了一個發送隊列，該隊列可以視為一個skb作為元素，按照該socket指示的pacing確定的發送時間升序排列的有序鏈表，系統中有N個socket，就有N條該類型鏈表：

注意，每一個鏈表的時間序都是按照skb在該流的上的相對發送時間排序的，縱然軟件層面可以維護很多的隊列，網卡卻只有一張，網線只有一條，每個時刻只能有一個skb可以被發送，所以，所有的隊列中的所有的數據包還需要基于絕對發送時間進行排序，我們按照絕對發送時間展開上圖，即將多個鏈表映射到同一個排序維度(簡略版)：

然后絕對發送序列就很明顯了：

這其實就是一個典型的 合并N個有序鏈表 的實例！合并后的結果完全可以有足夠的信息指示數據包調度系統 什么時間做什么事。

Linux FQ的實現使用了紅黑樹來定義錨點，即所有的鏈表中 下一個要check 的節點都被維護在一棵紅黑樹中，這樣做的目的是高效取出離當前節點最近的錨點進行check。

合并N個有序鏈表的基本思想

很簡單：

盡量保持在當前鏈表向后遍歷，直到當前鏈表下一個節點的key大于其它鏈表最小錨點的key；

將當前節點的下一個節點作為一個錨點插入紅黑樹，從該最小錨點開始繼續遍歷，重復第1步。

這是一個遞歸實現的好場所！

合并N個有序鏈表的C語言實現

不得不說這其實就是Linux FQ實現的抽象版本了，因此必然也是用紅黑樹來維護錨點咯…

我并沒有自己從零開始實現一版紅黑樹，估計我也寫不出來…我直接用了github上別人的實現，我使用的是這一版：
https://github.com/manuscola/rbtree
值得注意的是，這一版紅黑樹實現是不允許插入鍵值相同的元素的，為此要稍微做一點點修改，使得重復鍵值元素可以插入，這樣代碼實現起來按照統一的方式處理會更加清爽簡單些。

代碼如下所示：

#include <stdio.h> #include <stdlib.h> #include"rbtree.h"int a[] = {1,3,7,8,10,11,12,15,19,21,22,24,25,26}; int b[] = {0,4,5,6,9,16,17,18,27,30,31,32}; int c[] = {13,14,20,23,28,29}; int d[] = {2,33,100};struct list {struct list *next;struct rbtree_node *node;int v; };int compare(void* key_a,void* key_b) {int v_a = *(int *) (key_a);int v_b = *(int *) (key_b);if (v_a > v_b) {return 1;} else if (v_a == v_b) {return 0;}return -1; }void merge(struct list *iter, struct rbtree* tree) {struct list *last = iter, *base = NULL;struct rbtree_node *base_node = rbtree_min(tree);// 取出最小的錨點并從紅黑樹中將其刪除if (base_node) {base = (struct list *)base_node->data;__rbtree_remove(base_node,tree);}if (!iter) {return;}iter = iter->next;// 一直遍歷，直到next大于錨點while (iter && (!base || iter->v < base->v)) {last = iter;iter = iter->next;}// 將next作為新的錨點加入紅黑樹if (last->next) {rbtree_insert(tree, &last->next->v, last->next);}// 遞歸重復last->next = base;merge(base, tree); }int main(int argc, char **argv) {int i = 0;struct list *al = (struct list*)calloc(14, sizeof(*al));struct list *bl = (struct list*)calloc(12, sizeof(*bl));struct list *cl = (struct list*)calloc(6, sizeof(*cl));struct list *dl = (struct list*)calloc(3, sizeof(*dl));struct list *itera;struct list *iterb;struct list *iterc;struct list *iterd;struct list *base;struct rbtree* tree = rbtree_init(compare);// create 3 ordered-lists{for (i = 0; i < 14; i++) {itera = &al[i];itera->v = a[i];itera->next = &al[i+1];if (i == 0) {rbtree_insert(tree, &itera->v, itera);}}itera->next = NULL;for (i = 0; i < 12; i++) {iterb = &bl[i];iterb->v = b[i];iterb->next = &bl[i+1];if (i == 0) {rbtree_insert(tree, &iterb->v, iterb);}}iterb->next = NULL;for (i = 0; i < 6; i++) {iterc = &cl[i];iterc->v = c[i];iterc->next = &cl[i+1];if (i == 0) {rbtree_insert(tree, &iterc->v, iterc);}}iterc->next = NULL;for (i = 0; i < 3; i++) {iterd = &dl[i];iterd->v = d[i];iterd->next = &dl[i+1];if (i == 0) {rbtree_insert(tree, &iterd->v, iterd);}}iterd->next = NULL;}// merge n sorted-lists{struct rbtree_node *node;node = rbtree_min(tree);__rbtree_remove(node,tree);base = (struct list *)node->data;merge(base, tree);}// print the result{// 注意，從base開始遍歷for (; base; base=base->next) {printf("%d %p\n", base->v, base);}} }

注意，之所以選擇紅黑樹而不是最小堆，是因為紅黑樹的cache親和性要比最小堆好！在紅黑樹的旋轉過程中，最大限度地在樹的平衡性以及節點的局部性之間取得了比較好的折中，這點是我看中的。此外，Linux FQ以及CFS等大量使用了紅黑樹，所以我也就用了。

總結

本文用Linux FQ包調度機制解釋了合并N個有序鏈表到底有什么用，在該例子中，其實實施的就是將N個相對時間序列整合到一個絕對時間序列的過程，這是一個典型的案例。

除此之外，鏈表合并在批處理任務調度系統中也有非常多的應用，和Linux FQ一樣，其實也是一個N到1整合的過程。鏈表合并并不單單是一道面試題，一道課后作業，它確確實實是真有用啊！

浙江溫州皮鞋濕，下雨進水不會胖。

總結

以上是生活随笔為你收集整理的合并N个有序链表与FQ公平调度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。