m个有序数组求第k小的数字

newgod2500 发表于 2017-6-25 00:49
比较暴力,General(如果数组无序）一点的思路是建一个minHeap, 把N个元素塞进去，然后按k取值，这样时间复杂 ...

你这个时间复杂度不对吧 M个数组第一项建堆 是O(M*logM), 然后取k次最小值是 K*logM 所以总的应该是 O(K*logM), 考虑到k可能会很大 所以应该是趋近于O(N*logM)

youziwry 发表于 2017-6-25 01:56
你这个时间复杂度不对吧 M个数组第一项建堆 是O(M*logM), 然后取k次最小值是 K*logM 所以总的应该是 O(K* ...

第一项建堆的时候分析遗漏了哈哈。 你分析是对的。

随机选取一个数，每个数组用binary search找出小于这个数的index, 这样就把所有数分成两部分，a和n-a，再对比a和k决定丢掉哪一半。通过选取最长array的中位数能够避免worst case

Merge K sorted List ?
Time : n Log k
Space O(k)

leonardcohen 发表于 2017-6-25 02:32
Merge K sorted List ?
Time : n Log k
Space O(k)

Space怎么会是O(k)?

从(min+max)/2开始二分，直到所有数组左边的数的个数等于K。从所有数组找到的分界点中，选取最大的那个，就可以了。复杂度m*log(n)。

这里贴一下问题的答案吧

这确实是一道比较难的题目，算法步骤略长，详细的解释与时间复杂度分析在这篇论文里：

Peter J. Varman, Scott D. Scheufler, Balakrishna R. Iyer, and Gary R. Ricard. 1991. Merging multiple lists on hierarchical-memory multiprocessors. J. Parallel Distrib. Comput. 12, 2 (June 1991)
https://github.com/jqdocshare/do ... tiseq_partition.pdf

文章里解决的是稍微更general一点的问题：将每个有序数组都partition为左右两边，使得所有的左边合起来正好是前k小的数字。里面的细节我就不翻写一遍了，因为很麻烦.. 得贴图才能解释清楚，不过如果有难以理解的地方我可以跟帖。

此外上述的partition版本是一个有实际用途的算法，它是并行多路归并排序算法（Parallel Multiway Mergesort）中重要的一步。
我遇到这个问题是因为想找一个单机多核排序的实现（C++，无GPU，workload是10亿量级的64位整数），然后发现gcc的并行多路归并排序是最有效使用多CPU（4核 ~ 20核）并且是最快的。此外gcc和tbb都有Parallel Balanced Quicksort，然而相对较慢。

这里是gcc的libstdc++中对该题算法的实现：https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/parallel/multiseq_selection.h#L388
用了260行代码

PS:
关于如何使用gcc的并行库：https://stackoverflow.com/questions/28520720/c-parallel-sort
我猜大多数人都没用过.. 但是如果你手上的电脑有4核或者8核，然后原来处理某些数据要等个10分钟，用下并行说不定就两三分钟了，还是很爽的。