No Headback

talent-plan tidb 部分个人题解-week 1

Xargin -

第一周是给定了函数签名实现多路归并排序。这里。

为啥要考这个问题呢？个人认为多路归并在分布式数据库、分布式搜索引擎领域是挺常见的算法。用我相对熟悉的 es 来举例，在搜索数据时，我们会指定 bool 表达式来对数据进行筛选，同时需要指定每个查询 sort by 字段以及 size，但分布式环境下，我们没有办法确定这 size 个元素要在每个 shard 里取几个元素。所以最基本的思路：

  1. 每个 shard 里都取出 size 个元素
  2. 拉到中心节点来进行多路归并，输出前 size 个元素
  3. 每个 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