内容简介:第一周是给定了函数签名实现多路归并排序。为啥要考这个问题呢?个人认为多路归并在分布式数据库、分布式搜索引擎领域是挺常见的算法。用我相对熟悉的 es 来举例,在搜索数据时,我们会指定 bool 表达式来对数据进行筛选,同时需要指定每个查询 sort by 字段以及 size,但分布式环境下,我们没有办法确定这 size 个元素要在每个 shard 里取几个元素。所以最基本的思路:参考上面的三条,先做局部排序,再做全局归并,思路也不难,先把大 slice 区分成 N 个 slice,然后对每个 slice 进行
第一周是给定了函数签名实现多路归并排序。 这里 。
为啥要考这个问题呢?个人认为多路归并在分布式数据库、分布式搜索引擎领域是挺常见的算法。用我相对熟悉的 es 来举例,在搜索数据时,我们会指定 bool 表达式来对数据进行筛选,同时需要指定每个查询 sort by 字段以及 size,但分布式环境下,我们没有办法确定这 size 个元素要在每个 shard 里取几个元素。所以最基本的思路:
- 每个 shard 里都取出 size 个元素
- 拉到中心节点来进行多路归并,输出前 size 个元素
- 每个 shard 返回的 size 条数据可以预先 排序 好。
参考上面的三条,先做局部排序,再做全局归并,思路也不难,先把大 slice 区分成 N 个 slice,然后对每个 slice 进行排序,这个过程用 N 个 g 并发进行。然后建立一个小顶堆,比较依据为每个 slice 的头部元素。
建立好堆之后,每次从堆顶取元素,将堆顶 slice 的 idx++,如果已经取完了该 slice 的元素,则对堆进行 pop。如果没取完,则需要对小顶堆进行再平衡。
基本思路就是这样,剩下的就是各种调试了。。。
我的代码在: 这里
有时间应该对 style 进行一些优化。
这里比较麻烦的是,对任务进行切分,并且对局部数组并发排序时,这个拷贝操作怎么都避免不了,否则因为 cpu 的多级 cache 机制导致整体的数组数组被排乱掉。其实就是有 race。
相比标准的 sort.Slice 原地排序,有大量的内存拷贝操作。。没想到有什么好办的优化方法。
~/t/t/mergesort ❯❯❯ make bench master ✱ ◼ go test -bench Benchmark -run xx -count 5 -benchmem goos: darwin goarch: amd64 pkg: pingcap/talentplan/tidb/mergesort BenchmarkMergeSort-8 1 1039028165 ns/op 134228352 B/op 57 allocs/op BenchmarkMergeSort-8 1 1065523444 ns/op 134222144 B/op 43 allocs/op BenchmarkMergeSort-8 1 1064337935 ns/op 134222688 B/op 44 allocs/op BenchmarkMergeSort-8 1 1051075587 ns/op 134221984 B/op 41 allocs/op BenchmarkMergeSort-8 1 1047990178 ns/op 134221888 B/op 40 allocs/op BenchmarkNormalSort-8 1 3277904168 ns/op 64 B/op 2 allocs/op BenchmarkNormalSort-8 1 3256987462 ns/op 64 B/op 2 allocs/op BenchmarkNormalSort-8 1 3259074652 ns/op 64 B/op 2 allocs/op BenchmarkNormalSort-8 1 3327195388 ns/op 64 B/op 2 allocs/op BenchmarkNormalSort-8 1 3356915213 ns/op 64 B/op 2 allocs/op PASS ok pingcap/talentplan/tidb/mergesort 25.773s
以上所述就是小编给大家介绍的《talent-plan tidb 部分个人题解-week 1》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 2018护网杯-web部分题解
- 2019强网杯Web部分题解
- 2019*CTF之Web部分题解
- talent-plan tidb 部分个人题解-week 2
- leetcode题解(动态规划)
- leetcode题解(动态规划)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。