top K 问题
在大规模数据处理中，经常会遇到的一类问题：在海量数据中找出出现频率最好的前k个数，或者从海量数据中找出最大的前k个数，这类问题通常被称为top K问题。例如，在搜索引擎中，统计搜索最热门的10个查询词；在歌曲库中统计下载最高的前10首歌等。
针对top K类问题，通常比较好的方案是分治+Trie树/hash+小顶堆（就是上面提到的最小堆），即先将数据集按照Hash方法分解成多个小数据集，然后使用Trie树或 Hash 统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。
何谓海量数据处理？
所谓海量数据处理，无非就是基于海量数据上的存储、处理、操作。何谓海量，就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。
那解决办法呢？针对时间，我们可以采用巧妙的算法搭配合适的数据结构，如：
- 分而治之（hash映射+取模） + hashmap统计 + 堆/快速/归并排序
- 双层桶划分
- Bloom filter/Bitmap
- Trie树/数据库/倒排索引
- 外排序
- 分布式处理之Hadoop/Mapreduce
针对空间，无非就一个办法：大而化小，分而治之（hash映射），你不是说规模太大嘛，那简单啊，就把规模大化为规模小的，各个击破不就完了嘛。
至于所谓的单机及集群问题，通俗点来讲，单机就是处理装载数据的机器有限（只要考虑 CPU，内存，硬盘的数据交互），而集群，机器有多辆，适合分布式处理，并行计算（更多考虑节点和节点间的数据交互）。
Reference
- 《编程之法：面试和算法心得》
FEATURED TAGS
algorithm
algorithmproblem
architecturalpattern
architecture
aws
c#
cachesystem
codis
compile
concurrentcontrol
database
dataformat
datastructure
debug
design
designpattern
distributedsystem
django
docker
domain
engineering
freebsd
git
golang
grafana
hackintosh
hadoop
hardware
hexo
http
hugo
ios
iot
java
javaee
javascript
kafka
kubernetes
linux
linuxcommand
linuxio
lock
macos
markdown
microservices
mysql
nas
network
networkprogramming
nginx
node.js
npm
oop
openwrt
operatingsystem
padavan
performance
programming
prometheus
protobuf
python
redis
router
security
shell
software testing
spring
sql
systemdesign
truenas
ubuntu
vmware
vpn
windows
wmware
wordpress
xml
zookeeper