获取Top 10热门搜索关键词算法设计

搜索引擎每天接收大量用户搜索请求把这些用户输入的搜索关键词记录再离线统计分析得到热门TopN搜索关键词。

现有一包含10亿个搜索关键词的日志文件如何快速获取热门榜Top 10搜索关键词
可用堆解决堆的几个应用优先级队列、求Top K和求中位数。

1 优先级队列

优先级队数据出队顺序按优先级优先级高的先出队。

堆实现最为直接、高效。堆和优先级队列相似。一个堆即可看作一个优先级队列。很多时候它们只是概念上的区分

• 往优先级队列中插入一个元素相当于往堆中插入一个元素
• 从优先级队列中取出优先级最高元素相当于取出堆顶

优先级队列应用场景赫夫曼编码、图最短路径、最小生成树算法等Java PriorityQueue。

2 合并有序小文件

• 100个小文件
• 每个文件100M
• 每个文件存储有序字符串

将这100个小文件合并成一个有序大文件就用到优先级队列。像归排的合并函数。从这100个文件中各取第一个字符串放入数组然后比较大小把最小的那个字符串放入合并后的大文件并从数组中删除。

假设这最小字符串来自13.txt这个小文件就再从该小文件取下一个字符串并放入数组重新比较大小并且选择最小的放入合并后的大文件并且将它从数组中删除。依次类推直到所有的文件中的数据都放入到大文件。

用数组存储从小文件中取出的字符串。每次从数组取最小字符串都需循环遍历整个数组能更高效吗
优先级队列即堆

• 将从小文件中取出的字符串放入小顶堆则堆顶元素就是优先级队列的队首即最小字符串
• 将这个字符串放入大文件并将其从堆中删除
• 再从小文件中取出下一个字符串放入到堆
• 循环该过程即可将100个小文件中的数据依次放入大文件

删除堆顶数据、往堆插数据时间复杂度都是$O(logn)$该案例$n=100$。

3 高性能定时器

维护很多定时任务每个任务都设定了一个执行时间点。
定时器每过一个单位时间如1s就扫描一遍任务看是否有任务到达设定执行时间。若到达则执行

显然这样每1s就扫描一遍任务列表很低效

• 任务约定执行时间离当前时间可能还很久很多次扫描无意义
• 每次都扫描整个任务列表若任务列表很大耗时多

这时就该优先级队列。按任务设定的执行时间将这些任务存储在优先级队列队首即小顶堆的堆顶存储最先执行的任务。定时器就无需每隔1s就扫描一遍任务列表。

$队首任务执行时间点-当前时间点相减=时间间隔T$

T就是从当前时间开始需等待多久才会有第一个任务要被执行。
定时器就能设定在T秒后再来执行任务。
当前时间点 ~ $T-1s$ 时间段定时器无需做任何事情。

当Ts时间过去后定时器取优先级队列中队首任务执行再计算新的队首任务执行时间点与当前时间点差值将该值作为定时器执行下一个任务需等待时间。

定时器

• 既不用间隔1s就轮询一次
• 也无需遍历整个任务列表

4 利用堆求Top K

Top K问题抽象成两类

4.1 静态数据集合

数据集合事先确定不会再变。

可维护一个大小为K的小顶堆顺序遍历数组从数组中取数据与堆顶元素比较

• ＞堆顶
  删除堆顶并将该元素插入堆
• ＜堆顶
  do nothing继续遍历数组

等数组中的数据都遍历完堆中数据就是Top K。

遍历数组需$O(n)$一次堆化操作需$O(logK)$最坏情况n个元素都入堆一次即$O(nlogK)$。

4.2 动态数据集合

数据集合事先并不确定有数据动态地加入到集合中也就是求实时Top K。
一个数据集合中有两个操作

• 添加数据
• 询问当前TopK数据

若每次询问Top K大数据都基于当前数据重新计算则时间复杂度$O(nlogK)$n表示当前数据的大小。
可一直都维护一个K大小的小顶堆当有数据被添加到集合就拿它与堆顶元素对比

• ＞堆顶
  就把堆顶元素删除并且将这个元素插入到堆中
• ＜堆顶
  do nothing。无论何时需查询当前的前K大数据都可以里立刻返回给他

5 利用堆求中位数

求动态数据集合中的中位数

• 数据个数奇数
  把数据从小到大排列第$\frac{n}{2}+1$个数据就是中位数
• 数据个数是偶数
  处于中间位置的数据有两个第$\frac{n}{2}$个、第$\frac{n}{2}+1$个数据可随意取一个作为中位数比如取两个数中靠前的那个即第$\frac{n}{2}$个数据

一组静态数据的中位数是固定的可先排序第$\frac{n}{2}$个数据就是中位数。
每次询问中位数直接返回该固定值。所以尽管排序代价大但边际成本小。但若动态数据集合中位数在不停变动如再用先排序的方法每次询问中位数都要先排序效率就不高。

利用堆不用排序即可高效实现求中位数操作需维护两个堆

• 大顶堆
  存储前半部分数据
• 小顶堆
  存储后半部分数据 && 小顶堆数据都 ＞ 大顶堆数据

即若有n偶数个数据从小到大排序则

• 前 $\frac{n}{2}$ 个数据存储在大顶堆
• 后$\frac{n}{2}$个数据存储在小顶堆

大顶堆中的堆顶元素就是我们要找的中位数。

n是奇数也类似

• 大顶堆存储$\frac{n}{2}+1$个数据
• 小顶堆中就存储$\frac{n}{2}$个数据

数据动态变化当新增一个数据时如何调整两个堆让大顶堆堆顶继续是中位数 若

• 新加入的数据 ≤ 大顶堆堆顶则将该新数据插到大顶堆
• 新加入的数据大于等于小顶堆的堆顶元素我们就将这个新数据插入到小顶堆。

这时可能出现两个堆中的数据个数不符合前面约定的情况若

• n是偶数两个堆中的数据个数都是 $\frac{n}{2}$
• n是奇数大顶堆有 $\frac{n}{2}+1$ 个数据小顶堆有 $\frac{n}{2}$ 个数据

即可从一个堆不停将堆顶数据移到另一个堆以使得两个堆中的数据满足上面约定。

插入数据涉及堆化所以时间复杂度$O(logn)$但求中位数只需返回大顶堆堆顶所以时间复杂度$O(1)$。

利用两个堆还可快速求其他百分位的数据原理类似。

“如何快速求接口的99%响应时间

中位数≥前50%数据类比中位数若将一组数据从小到大排列这个99百分位数就是大于前面99%数据的那个数据。

假设有100个数据123……100则99百分位数就是99因为≤99的数占总个数99%。

维护两个堆

• 一个大顶堆
• 一个小顶堆

假设当前总数据的个数是n大顶堆中保存n99%个数据小顶堆中保存n1%个数据。大顶堆堆顶的数据就是我们要找的99%响应时间。

每插入一个数据时要判断该数据跟大顶堆、小顶堆堆顶的大小关系以决定插入哪个堆

• 新插入数据 ＜ 大顶堆的堆顶插入大顶堆
• 新插入的数据 ＞ 小顶堆的堆顶插入小顶堆

但为保持大顶堆中的数据占99%小顶堆中的数据占1%每次新插入数据后都要重新计算这时大顶堆和小顶堆中的数据个数是否还符合99:1

• 不符合则将一个堆中的数据移动到另一个堆直到满足比例
  移动的方法类似前面求中位数的方法

如此每次插入数据可能涉及几个数据的堆化操作所以时间复杂度$O(logn)$。
每次求99%响应时间时直接返回大顶堆中的堆顶即可时间复杂度$O(1)$。

6 10亿个搜索关键词日志文件获取Top 10

很多人说MapReduce但若将场景限定为单机可使用内存为1GB咋办

用户搜索的关键词很多是重复的所以先统计每个搜索关键词出现频率。
可通过散列表、平衡二叉查找树或其他一些支持快速查找、插入的数据结构记录关键词及其出现次数。

假设散列表。
顺序扫描这10亿个搜索关键词。当扫描到某关键词去散列表中查询

• 存在对应次数加一
• 不存在插入散列表并记录次数1

等遍历完这10亿个搜索关键词后散列表就存储了不重复的搜索关键词及出现次数。

再根据堆求Top K方案建立一个大小为10小顶堆遍历散列表依次取出每个搜索关键词及对应出现次数然后与堆顶搜索关键词对比

• 出现次数 ＞ 堆顶搜索关键词的次数
  删除堆顶关键词将该出现次数更多的关键词入堆。

以此类推当遍历完整个散列表中的搜索关键词之后堆中的搜索关键词就是出现次数最多的Top 10搜索关键词了。

但其实有问题。10亿的关键词还是很多的。
假设10亿条搜索关键词中不重复的有1亿条如果每个搜索关键词的平均长度是50个字节那存储1亿个关键词起码需要5G内存而散列表因为要避免频繁冲突不会选择太大的装载因子所以消耗的内存空间就更多了。
而机器只有1G可用内存无法一次性将所有的搜索关键词加入内存。

何解

因为相同数据经哈希算法后的哈希值相同可将10亿条搜索关键词先通过哈希算法分片到10个文件

• 创建10个空文件00~09
• 遍历这10亿个关键词并通过某哈希算法求哈希值
• 哈希值同10取模结果就是该搜索关键词应被分到的文件编号

10亿关键词分片后每个文件都只有1亿关键词去掉重复的可能就剩1000万每个关键词平均50个字节总大小500M1G内存够。

针对每个包含1亿条搜索关键词的文件

• 利用散列表和堆分别求Top 10
• 10个Top 10放一起取这100个关键词中出现次数Top 10关键词即得10亿数据的Top 10热搜关键词