美文网首页
1600万的整数排序pingcap-talent-plan(1)

1600万的整数排序pingcap-talent-plan(1)

作者: 日月神父 | 来源:发表于2020-03-13 19:06 被阅读0次

Merge Sort

问题描述

Go 语言实现一个16M的整数(int64)多路归并的数组排序

思路

将待排序数组分成多个组,利用多个goroutine实现各个组的并行排序;然后通过Heap(最小堆)进行多路归并排序

实现

实现一个协程池实现任务的并行处理,将待排序切片分组并封装成SortTask放入协程池
运行,待全部执行完成后ConcurrentSorter收集排序结果,并封装成MergeTask放入协程池中进行合并。

  • 协程池pool.go

    • 配置最大协程数量
    • 按需创建协程
    • 空闲超时则回收协程
  • 合并有序切片algorithm.heap_merge.go
    若采用2路循环合并,每次合并需要申请长度为2路之和的内存保存合并结果,循环合并会导致过多的内存申请。通过堆实现多路的有序切片的合并,只需要额外申请一次一倍的内存用于存放合并结果。

归并算法

输入:n路待合并的有序slice
输出:有序slice

堆node定义为一个SortedSlice,实现了hasNext函数,用于迭代到当前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
}
  1. 构建一个n个元素的最小堆
  2. 从每路slice中取首个元素组成数组,调整堆;每次从堆顶,取一个元素,放入合并后的slice中
    • 如果hasNext=true,执行当前node的Next(),重新调整当前的原因
    • 如果hasNext=false, 当前slice已经空了,因此剔除堆顶, 然后需要重建堆,原因是堆中的父子关系已经破坏。
if h.nodes[0].HasNext() {
    h.nodes[0].Next() //不需要获取值
    h.adjust(0, len(h.nodes))
} else { // 顶部的node(slice)已经为空
    if len(h.nodes) >= 1 {
        // 移除为已经合并完成的slice
        h.nodes = h.nodes[1:]
        //h.adjust(0, len(h.nodes))
        h.Build()
    } else {
        return 0, errors.New("merge complete")
    }
}

代码结构

截屏2020-03-1318.33.34.png

性能测试

并发8路排序的的情况下,性能大约提升三倍,主要原因是分组排序之后需要进行多路的合并。测试结果如下:

截屏2020-03-1317.11.58.png

内存消耗比直接排序增加了128M,是因为合并排序结果过程申请了一块内存来暂存结果128M = 16M*8B

截屏2020-03-1317.12.43.png

cpu的消耗大多在排序过程,merge过程5%


截屏2020-03-1317.18.11.png

merge过程中调用append(slice)消耗了290ms,直接改为修改slice的下标竟然减少了大约10ms

截屏2020-03-1317.20.47.png
截屏2020-03-1319.05.17.png

github-mergesort源码

相关文章

  • 1600万的整数排序pingcap-talent-plan(1)

    Merge Sort 问题描述 Go 语言实现一个16M的整数(int64)多路归并的数组排序 思路 将待排序数组...

  • dart实现基数排序(Redix Sort)

    基数排序(Redix Sort) [toc] 基数排序非常适合用于整数排序(尤其是非负整数) 1.思路 依次对个位...

  • (数据结构入门)2018-06-23

    1.哈希表(Hash Table) 基数排序 (Radix Sort) 是一种非比较型整数排序算法,其原理是将整数...

  • 整数排序

    给一组整数,按照升序排序,使用选择排序,冒泡排序或者任何 O(n2) 的排序算法。

  • 【桶排序】[位运算交换值]

    【桶排序】[位运算交换值]40、求最小值 给定一个未排序的整数数组,找出其中没有出现的最小的正整数。示例 1:​ ...

  • go算法实现

    1.简易的桶排序 2.冒泡排序 3.求整数二进制表示中1的个数

  • [LintCode]整数排序

    原文发表在我的博客:整数排序求关注、求交流、求意见、求建议。 问题 LintCode:整数排序 描述 给一组整数,...

  • 选择排序

    请用选择选择排序方法对 1010 个整数从小到大排序。 输入格式 输入 1010 个整数。 输出格式 输出排序后的...

  • leetcode 41. 缺失的第一个正数(Java版)

    题目描述(题目难度,困难) 给定一个未排序的整数数组,找出其中没有出现的最小的正整数。 示例 1: 输入: [1,...

  • [算法] 排序

    插入排序 希尔排序缩小增量排序:先取一个正整数 d1(d1 < n),把全部记录分成 d1 个组,所有距离为 d1...

网友评论

      本文标题:1600万的整数排序pingcap-talent-plan(1)

      本文链接:https://www.haomeiwen.com/subject/kureshtx.html