TopK 热搜怎么实现？

Question

百度、微博的大数据算法 Top10 热搜怎么实现？
大数据！！！
比如从 10000000000TB 的数据中得到结果。不用实时，定期就行。也就是一次性的意思。

有比 mapreduce 更好的吗？

不是leetcode算法题，给你一个小列表，然后xxxx那种。而是现实工程

Answer 1

简单点就Misra-Gries算法,取数据流中的topk,不过是近似的算法.

Answer 2

如果不借助大数据工具，那么给一个简单的方法吧。
如果k不是特别大，那么弄一个双向链表，最长节点数就是K，按顺序从大到小排列。
遍历这个数据集，跟这个链表的尾节点比较，如果大于尾节点，则从尾节点往上找，然后插入，然后删除尾节点。
这个算法最差是O(n*k),因为k是常数，所以实际算法复杂度是O(k)。
当然链表也可以用最小堆替代，效率略有提升。

但是在实际中，显然不可能这么麻烦，微博百度都是用大数据工具跑的，原理就是mapreduce。