1600萬的整數(shù)排序pingcap-talent-plan(1)

Merge Sort

問題描述

Go 語言實現(xiàn)一個16M的整數(shù)(int64)多路歸并的數(shù)組排序

思路

將待排序數(shù)組分成多個組，利用多個goroutine實現(xiàn)各個組的并行排序蚌本；然后通過Heap(最小堆)進行多路歸并排序扯再；

實現(xiàn)

實現(xiàn)一個協(xié)程池實現(xiàn)任務(wù)的并行處理持际，將待排序切片分組并封裝成SortTask放入?yún)f(xié)程池
運行开镣，待全部執(zhí)行完成后ConcurrentSorter收集排序結(jié)果，并封裝成MergeTask放入?yún)f(xié)程池中進行合并荚藻。

協(xié)程池pool.go
- 配置最大協(xié)程數(shù)量
- 按需創(chuàng)建協(xié)程
- 空閑超時則回收協(xié)程
合并有序切片algorithm.heap_merge.go
若采用2路循環(huán)合并屋灌，每次合并需要申請長度為2路之和的內(nèi)存保存合并結(jié)果，循環(huán)合并會導(dǎo)致過多的內(nèi)存申請应狱。通過堆實現(xiàn)多路的有序切片的合并共郭，只需要額外申請一次一倍的內(nèi)存用于存放合并結(jié)果。

歸并算法

輸入：n路待合并的有序slice
輸出：有序slice

堆node定義為一個SortedSlice疾呻，實現(xiàn)了hasNext函數(shù)除嘹，用于迭代到當(dāng)前slice的下一個元素；

type Iterator struct {
    slice []int64
    index int
}

func (i *Iterator) HasNext() bool {
    return i.index < len(i.slice)-1
}

func (i *Iterator) Next() {
    i.index++
}

func (i *Iterator) Value() int64 {
    return i.slice[i.index]
}

type SortedSlice struct {
    slice []int64
    Iterator
}

堆的定義：

type HeapMerge struct {
    nodes []*SortedSlice
}

構(gòu)建一個n個元素的最小堆
從每路slice中取首個元素組成數(shù)組岸蜗，調(diào)整堆尉咕；每次從堆頂，取一個元素璃岳，放入合并后的slice中
- 如果hasNext=true年缎，執(zhí)行當(dāng)前node的Next()，重新調(diào)整當(dāng)前的原因
- 如果hasNext=false, 當(dāng)前slice已經(jīng)空了铃慷，因此剔除堆頂, 然后需要重建堆单芜，原因是堆中的父子關(guān)系已經(jīng)破壞。

if h.nodes[0].HasNext() {
    h.nodes[0].Next() //不需要獲取值
    h.adjust(0, len(h.nodes))
} else { // 頂部的node(slice)已經(jīng)為空
    if len(h.nodes) >= 1 {
        // 移除為已經(jīng)合并完成的slice
        h.nodes = h.nodes[1:]
        //h.adjust(0, len(h.nodes))
        h.Build()
    } else {
        return 0, errors.New("merge complete")
    }
}