如何在 1s 内统计出 13 亿人口数据找出使用人数最多的十个姓名

1. 面向列的
2. 姓氏映射成一个 bit
3. bitmap

ClickHouse 应该很简单

这是哪个公司的面试题吗？

这个是静态数据，维护一份统计数据，每次更新静态数据时同时更新统计数据。
1s 内找出十个最多的人名，就是一条查询而已

查询模式固定的话可以考虑自己用 C++写索引和查询，13 亿短字符串对于单机而言也不是很大的量级

@Mohanson 使用最多，看清楚了兄弟。你还是要把整个树过一遍才能知道那些频率最高

@tiancaixiaoshuai 哈哈哈 牛逼

百家姓拿来干吗的，老祖宗都统计好了。。。

@786375312123 设计成父节点的 count 是其所有子节点的 count 和，即使不做任何优化，最多循环一个 3500*3 长度的数组就能找到最大值；找到最大值后排除该根节点继续找最大值，往复 10 次就是 3500*3*10 次循环。

这是我想到的没任何优化的算法，仔细设计的话提个数量级也不是不可能

使用字典树，循环一次就出来了。

如果在插入和移出数据时保证所有子树的顺序的话，那么查找一次最大值的时间复杂度就是 O(1)，代价是插入和删除的时候计算量会变大很多，不过不是大问题，毕竟是读优先的

插入的时候就排好了， 只需 0.0001 秒

@Mohanson 可是你依然需要遍历所有的名字以后才能知道某个子节点上对应的数字是多少。建立树的成本依然是 o(n)

结合实际情况，如果可行的话，预处理的时候，把那些独一无二的名字先全部踢掉，数据少一大半。

select * from top_names;

@cage111 建表的索引错了吧，应该是 order by name

感觉你是想做用户画像，精准推送

数据录入的时候不就统计好了吗？

@mapoor 你这个算法是错的

用 columnar 数据库

统计学方法，直接随机落点一百万次，再统计不就好
这题应该改一下，找出最少的十个姓