黄良懿的博客
总有一些美好，期待着我们去发现
-
也说海量数据的快速排序 发表于 2010年07月11日 没有评论年初的时候就有同事面完以后回来和我聊过，5000万无重复32位无符号整数中取出10000个数字的时间+空间最优排序方法，以及存在重复数字时的最优方法。 今天正好有空，把当时考虑的解决思路写下来：
首先肯定是空间换时间，方法基于位运算创建一个大内存区，单次接受数据，每个数字设置其所属的bit，随后遍历输出。这样子的话所需要的内存空间是32-3=29位，也就是512M。这个算法时间性能是足够保证了，毕竟无迭代，空间通过分块的方式来降低是一个思路，但4亿数据（32位）中有5000万，稀疏的程度远不足够，只能作罢。 这个方案的好处是即使进行全排序，其时间性能和空间性能也不会发生改变。 空间最优则应该是通过维护一个红黑树，先丢10000个数字进去，然后遍历剩下的数，从红黑树中汰选最小值替换之即可，遍历红黑树进行汰选前先比较预存的树中最小数在正常分布下能有效减少性能损失。
重复数字的简单解决方法是增加一次遍历，首次遍历将需要取出的10000个数字汇总后构建哈希表，再次遍历时仅只计算哈希表中元素的出现次数，最后按照10000个数字的次序遍历，并累计哈希表中的计数至10000次即可。 空间最优方案依然还是选择红黑树。
从综合考虑上来说当然是红黑树的实现在时间和空间上都有不俗的表现，但实际应用起来还是位运算靠谱，毕竟再怎么高效查找也好，碰上一个悲观分布（数据本来就是有序的且和要求输出序同向），那就是5000万次树遍历了。而位运算的空间占用是恒定的，时间则和总数据量等比，非常稳定。
当然，如果是有重复，全排序，基本上也只能考虑MapReduce了。
相关日志：
相关日志：
最近评论