怎样在分布式系统上找出出现频次最高的前100个数?
需要按照范围ceiling(2^16/N)划分数字到不同的server，统计每个数字出现的次数，然后在通过一个server来比较。不通过全局统计据我所知是不行的，有个著名的挑战叫TeraSort，讨论过这个问题。
■网友
不考虑取值范围的一种通用解法:1. 收集局部信息：所有N个server分别统计出各自数字集合上的top 100结果，并发送给其他Server。2. 计算频次下界：每个Server在汇总所有N个Server发送的top 100结果后，对这些结果做merge（即相同数字对应的频次相累加），merge以后取排在第100位的数字的频次，记为K。得到一个下界，即全局top 100的数字的频次都不小于K。3. 产生候选集：所有Server向其他Server发送本地 频次\u0026gt;=K/N的所有数字（及其频次）给其他结点，对这些数字集合取并集，得到总的候选集。（全局频次top 100的数字必定都在这个候选集中，否则其全局频次将\u0026lt;K) 4. 收集候选集频次：各Server向其他Server发送本地所有在该候选集中的数字的频次。5. 汇总结果并排序：各Server上对发回的数字频次进行Merge并排序，即可得到最终top 100结果。整体解法的性能主要取决于第3步产生的候选集大小。以上过程中，如果允许选定一个Server来做收集汇总与调度，则可以减少总的网络带宽和避免各结点上不必要的重复计算。
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 吉林丰满鱼道系统就绪静待松花江鱼类洄游产卵
- 互联网怎样解决“家政服务上门速度慢”的问题
- 银行系统的研发岗(程序员)是不是很难进(校招)推广到国企的研发岗(程序员)呢
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾
- 5.1声道片源对于没有5.1硬件系统的用户来说有意义吗