0717-7821348
欢乐彩票平台

欢乐彩票平台

您现在的位置: 首页 > 欢乐彩票平台
百度、微博的大数据算法Top10热搜怎样完成?
2019-12-19 00:42:28

百度、微博等抢手查找排行榜功用你用过吗?你知道这个功用是怎样完成的吗?

实际上,它的完成并不杂乱。查找引擎每天会接纳许多的用户查找恳求,它会把这些用户输入的查找关键词记载下来,然后再离线地计算分析,得到最抢手的 Top 10 查找关键词。

那请你考虑下,假定现在咱们有一个包括 10 亿个查找关键词的日志文件,怎样能快速获取到抢手榜 Top 10 的查找关键词呢?

这个问题就能够用堆来处理,这也是堆这种数据结构一个十分典型的运用。堆这种数据结构几个十分重要的运用:优先级行列、求 Top K 和求中位数。

堆的运用一:优先级行列

首要,咱们来看榜首个运用场景:优先级行列。

优先级行列,望文生义,它首要应该是一个行列。咱们前面讲过,行列最大的特性便是先进先出。不过,在优先级行列中,数据的出队次序不是先进先出,而是依照优先级来,优先级最高的,最早出队。

怎样完成一个优先级行列呢?办法有许多,可是用堆来完成是最直接、最高效的。这是由于,堆和优先级行列十分相似。一个堆就能够看作一个优先级行列。许多时分,它们仅仅概念上的区别算了。往优先级行列中刺进一个元素,就相当于往堆中刺进一个元素;从优先级行列中取出优先级最高的元素,就相当于取出堆顶元素。

你可别小看这个优先级行列,它的运用场景十分多。比方,赫夫曼编码、图的最短途径、最小生成树算法等等。不只如此,许多语言中,都供给了优先级行列的完成,比方,Java 的 PriorityQueue,C++ 的 priority_queue 等。

只讲这些运用场景比较空泛,现在,我举两个详细的比方,感受一下优先级行列详细是怎样用的。

1. 兼并有序小文件

假定咱们有 100 个小文件,每个文件的巨细是 100MB,每个文件中存储的都是有序的字符串。咱们期望将这些 100 个小文件兼并成一个有序的大文件。这儿就会用到优先级行列。

全体思路有点像归并排序中的兼并函数。咱们从这 100 个文件中,各取榜首个字符串,放入数组中,然后比较巨细,把最小的那个字符串放入兼并后的大文件中,并从数组中删去。

假定,这个最小的字符串来自于 13.txt 这个小文件,咱们就再从这个小文件取下一个字符串,而且放到数组中,从头比较巨细,而且挑选最小的放入兼并后的大文件,而且将它从数组中删去。顺次类推,直到一切的文件中的数据都放入到大文件停止。

这儿咱们用数组这种数据结构,来存储从小文件中取出来的字符串。每次从数组中取最小字符串,都需求循环遍历整个数组,明显,这不是很高效。有没有愈加高效办法呢?百度、微博的大数据算法Top10热搜怎样完成?

这儿就能够用到优先级行列,也能够说是堆。咱们将从小文件中取出来的字符串放入到小顶堆中,那堆顶的元素,也便是优先级行列队首的元素,便是最小的字符串。咱们将这个字符串放入到大文件中,并将其从堆中删去。然后再从小文件中取出下一个字符串,放入到堆中。循环这个进程,就能够将 100 个小文件中的数据顺次放入到大文件中。

咱们知道,删去堆顶数据和往堆中刺进数据的时刻杂乱度都是 O(logn),n 表明堆中的数据个数,这儿便是 100。是不是比本来数组存储的办法高效了许多呢?

2. 高功能守时器

假定咱们有一个守时器,守时器中保护了许多守时使命,每个使命都设定了一个要触发履行的时刻点。守时器每过一个很小的单位时刻(比方 1 秒),就扫描一遍使命,看是否有使命抵达设定的履行时刻。假如抵达了,就拿出来履行。

可是,这样每过 1 秒就扫描一遍使命列表的做法比较低效,首要原因有两点:榜首,使命的约好履行时刻离当时时刻或许还有好久,这样前面许屡次扫描其实都是白费的;第二,每次都要扫描整个使命列表,假如使命列表很大的话,势必会比较耗时。

针对这些问题,咱们就能够用优先级行列来处理。咱们依照使命设定的履行时刻,将这些使命存储在优先级行列中,行列首部(也便是小顶堆的堆顶)存储的是最早履行的使命。

这样,守时器就不需求每隔 1 秒就扫描一遍使命列表了。它拿队首使命的履行时刻点,与当时时刻点相减,得到一个时刻距百度、微博的大数据算法Top10热搜怎样完成?离 T。

这个时刻距离 T 便是,从qq个性签名大全当时时刻开端,需求等候多久,才会有榜首个使命需求被履行。这样,守时器就能够设定在 T 秒之后,再来履行使命。从当时时刻点到(T-1)秒这段时刻里,守时器都不需求做任何事情。

当 T 秒时刻曩昔之后,守时器取优先级行列中队首的使命履行。然后再核算新的队首使命的履行时刻点与当时时刻点的差值,把这个值作为守时器履行下一个使命需求等候的时刻。

这样,守时器既不必距离 1 秒就轮询一次,也不必遍历整个使命列表,功能也就提高了。

堆的运用二:运用堆求 Top K

堆的别的一个十分重要的运用场景,那便是“求 Top K 问题”。

我把这种求 Top K 的问题笼统成两类。一类是针对静态数据调集,也便是说数据调集事前确认,不会再变。另一类是针对动态数据调集,也便是说数据调集事前并不确认,有数据动态地参加到调集中。

针对静态数据,怎样在一个包括 n 个数据的数组中,查找前 K 大数据呢?咱们能够保护一个巨细为 K 的小顶堆,次序遍历数组,从数组中取出取数据与堆顶元素比较。假如比堆顶元素大,咱们就把堆顶元素删去,而且将这个元素刺进到堆中;假如比堆顶元素小,则不做处理,持续遍历数组。这样等数组中的数据都遍历完之后,堆中的数据便是前 K 大数据了。

遍历数组需求 O(n) 的时刻杂乱度,一次堆化操作需求 O(logK) 的时刻杂乱度,所以最坏状况下,n 个元素都入堆一次,所以时刻杂乱度便是 O(nlogK)。

针对动态数据求得 Top K 便是实时 Top K。怎样了解呢?我举一个比方。一个数据调集中有两个操作,一个是增加数据,另一个问询当时的前 K 大数据。

假如每次问询前 K 大数据,咱们都依据当时的数据从头核算的话,那时刻杂乱度便是 O(nlogK),n 表明当时的数据的巨细。实际上,咱们能够一直都保护一个 K 巨细的小顶堆,当有数据被增加到调集中时,咱们就拿它与百度、微博的大数据算法Top10热搜怎样完成?堆顶的元素比照。假如比堆顶元素大,咱们就把堆顶元素删去,而且将这个元素刺进到堆中;假如比堆顶元素小,则不做处理。这样,不管任何时分需求查询当时的前 K 大数据,咱们都能够里马上回来给他。

堆的运用三:运用堆求中位数

前面咱们讲了怎样求 Top K 的问题,现在咱们来讲下,怎样求动态数据调集中的中位数。

中位数,望文生义,便是处在中心方位的那个数。假如数据的个数是奇数,把数据从小到大摆放,那第 n/2+1 个数据便是中位数;假如数据的个数是偶数的话,那处于中心方位的数据有两个,第n/2 个和第 n/2+1 个数据,这个时分,咱们能够随意取一个作为中位数,比方取两个数中靠前的那个,便是第 n/2 个数据。

关于一组静态数据,中位数是固定的,咱们能够先排序,第 n/2 个数据便是中位数。每次问询中位数的时分,咱们直接回来这个固定的值就好了。所以,虽然排序的价值比较大,可是边沿成本会很小。可是,假如咱们面临的是动态数据调集,中位数在不停地改变,假如再用先排序的办法,每次问询中位数的时分,都要先进行排序,那功率就不高了。

凭借堆这种数据结构,咱们不必排序,就能够十分高效地完成求中位数操作。咱们来看看,它是怎样做到的?

咱们需求保护两个堆,一个大顶堆,一个小顶堆。大顶堆中存储前半部分数据,小顶堆中存储后半部分数据,且小顶堆中的数据都大于大顶堆中的数据。

也便是说,假如有 n 个数据,n 是偶数,咱们从小到大排序,那前 n/2 个数据存储在大顶堆中,后 n/2 个数据存储在小顶堆中。这样,大顶堆中的堆顶元素便是咱们要找的中位数。假如 n 是奇数,状况是相似的,大顶堆就存储 n/2+1 个数据,小顶堆中就存储 n/2 个数据。

咱们前面也说到,数据是动态改变的,当新增加一个数据的时分,咱们怎样调整两个堆,让大顶堆中的堆顶元素持续是中位数呢?

假如新参加的数据小于等于大顶堆的堆顶元素,咱们就将这个新数据刺进到大顶堆;假如新参加的数据大于等于小顶堆的堆顶元素,咱们就将这个新数据刺进到小顶堆。

这个时分就有或许呈现,两个堆中的数据个数不契合前面约好的状况:假如 n 是偶数,两个堆中的数据个数都是n/2;假如 n 是奇数,大顶堆有 n/2+1 个数据,小顶堆有 n/2 个数据。这个时分,咱们能够从一个堆中不停地将堆顶元素移动到另一个堆,经过这样的调整,来让两个堆中的数据满意上面的约好。

所以,咱们就能够运用两个堆,一个大顶堆、一个小顶堆,完成在动态数据调集中求中位数的操作。刺进数据由于需求触及堆化,所以时刻杂乱度变成了 O(logn),可是求中位数咱们只需求回来大顶堆的堆顶元素就能够了,所以时刻杂乱度便是 O(1)。

实际上,运用两个堆不只能够快速求出中位数,还能够快速求其他百分位的数据,原理是相似的。还记得咱们在“为什么要学习数据结构与算法”里的这个问题吗?“怎样快速求接口的 99% 呼应时刻?”咱们现在就来看下,运用两个堆怎样来完成。

在开端这个问题的解说之前,我先解释一下,什么是“99% 呼应时刻”。

中位数的概念便是将数据从小到大摆放,处于中心方位,就叫中位数,这个数据会大于等于前面 50% 的数据。99 百分位数的概念能够类比中位数,假如将一组数据从小到大摆放,这个 99 百分位数便是大于前面 99% 数据的那个数据。

假如你仍是不太了解,我再举个比方。假定有 100 个数据,别离是 1,2,3,……,100,那 99 百分位数便是 99,由于小于等于 99 的数占总个数的 99%。

弄懂了这个概念,咱们再来看 99% 呼应时刻。假如有 100 个接口拜访恳求,每个接口恳求的呼应时刻都不同,比方 55 毫秒、100 毫秒、23 毫秒等,咱们把这 100 个接口的呼应时刻依照从小到大摆放,排在第 99 的那个数据便是 99% 呼应时刻,也叫 99 百分位呼应时刻。

咱们总结一下,假如有 n 个数据,将数据从小到大摆放之后,99 百分位数大约便是第 n*99% 个数据,同类,80 百分位数大约便是第 n*80% 个数据。

弄懂了这些,咱们再来看怎样求 99% 呼应时刻。

咱们保护两个堆,一个大顶堆,一个小顶堆。假定当时总数据的个数是 n,大顶堆中保存 n*99% 个数据,小顶堆中保存 n*1% 个数据。大顶堆堆顶的数据便是咱们要找的 99% 呼应时刻。

每次刺进一个数据的时分,咱们要判别这个数据跟大顶堆和小顶堆堆顶数据的巨细联系,然后决议刺进到哪个堆中。假如这个新刺进的数据比大顶堆的堆顶数据小,那就刺进大顶堆;假如这个新刺进的数据比小顶堆的堆顶数据大,那就刺进小顶堆。

可是,为了坚持大顶堆中的数据占 99%,小顶堆中的数据占 1%,在每次新刺进数据之后,咱们都要从头核算,这个时分大顶堆和小顶堆中的数据个数,是否还契合 99:1 这个份额。假如不契合,咱们就将一个堆中的数据移动到另一个堆,直到满意这个份额。移动的办法相似前面求中位数的办法,这儿我就不烦琐了。

经过这样的办法,每次刺进数据,或许会触及几个数据的堆化操作,所以时刻杂乱度是 O(logn)。每次求 99% 呼应时刻的时分,直接回来大顶堆中的堆顶数据即可,时刻杂乱度是 O(1)。

回答开篇

懂了上面的一些运用场景的处理思路,我想你应该能处理开篇的那个问题了吧。假定现在咱们有一个包括 10 亿个查找关键词的日志文件,怎样快速获取到 Top 10 最抢手的查找关键词呢?

处理这个问题,有许多高档的处理办法,比方运用 MapReduce 等。可是,假如咱们将处理的场景限定为单机,能够运用的内存为 1GB。那这个问题该怎样处理呢?

由于用户查找的关键词,有许多或许都是重复的,所以咱们首要要计算每个查找关键词呈现的频率。咱们能够经过散列表、平衡二叉查找树或许其他一些支撑快速查找、刺进的数据结构,来记载关键词及其呈现的次数。

假定咱们选用散列表。咱们就次序扫描这 10 亿个查找关键词。当扫描到某个关键词时,咱们去散列表中查询。假如存在,咱们就将对应的次数加一;假如不存在,咱们就将它刺进到散列表,并记载次数为 1。以此类推,等遍历完这 10 亿个查找关键词之后,散列表中就存储了不重复的查找关键词以及呈现的次数。

然后,咱们再依据前面讲的用堆求 Top K 的办法,树立一个巨细为 10 的小顶堆,遍历散列表,顺次取出每个查找关键词及对应呈现的次数,然后与堆顶的查找关键词比照。假如呈现次数比堆顶查找关键词的次数多,那就删去堆顶的关键词,将这个呈现次数更多的关键词参加到堆中。

以此类推,当遍历完整个散列表中的查找关键词之后,堆中的查找关键词便是呈现次数最多的 Top 10 查找关键词了。

不知道你发现了没有,上面的处理思路其实存在缝隙。10 亿的关键词仍是许多的。咱们假定 10 亿条查找关键词中不重复的有 1 亿条,假如每个查找关键词的均匀长度是 50 个字节,那存储 1 亿个关键词最少需求 5GB 的内存空间,而散列表由于要防止频频抵触,不会挑选太大的装载因子,所以耗费的内存空间就更多了。而咱们的机器只要 1GB 的可用内存空间,所以咱们无法一次性将一切的查找关键词参加到内存中。这个时分该怎样办呢?

咱们在哈希算法那一节讲过,相同数据经过哈希算法得到的哈希值是相同的。咱们能够哈希算法的这个特色,将 10 亿条查找关键词先经过哈希算法分片到 10 个文件中。

详细能够这样做:咱们创立 10 个空文件 00,01,02,……,09。咱们遍历这 10 亿个关键词,而且经过某个哈希算法对其求哈希值,然后哈希值同 10 取模,得到的成果便是这个查找关键词应该被分到的文件编号。

对这 10 亿个关键词分片之后,每个文件都只要 1 亿的关键词,去除去重复的,或许就只要 1000 万个,每个关键词均匀 50 个字节,所以总的巨细便是 500MB。1GB 的内存完全能够放得下。

咱们针对每个包括 1 亿条查找关键词的文件,运用散列表和堆,别离求出 Top 10,然后把这个 10 个 Top 10 放在一块,然后取这 100 个关键词中,呈现次数最多的 10 个关键词,这便是这 10 亿数据中的 Top 10 最频频的查找关键词了。

内容小结

咱们今日首要讲了堆的几个重要的运用,它们别离是:优先级行列、求 Top K 问题和求中位数问题。

优先级行列是一种特别的行列,优先级高的数据先出队,而不再像一般的行列那样,先进先出。实际上,堆就能够看作优先级行列,仅仅称谓不相同算了。求 Top K 问题又能够分为针对静态数据和针对动态数据,只需求运用一个堆,就能够做到十分高功率的查询 Top K 的数据。

求中位数实际上还有许多变形,比方求 99 百分位数据、90 百分位数据等,处理的思路都是相同的,即运用两个堆,一个大顶堆,一个小顶堆,跟着数据的动态增加,动态调整两个堆中的数据,最终大顶堆的堆顶元素便是要求的数据。