1、们就将这个新数据插入到 小顶堆。 这个时候就有可能出现，两个堆中的数据个数不符合前面约定的情况：如果n是偶数，两个堆中的数据个数都是$fracn2$；如果n是奇数，大顶堆有$fracn 2+1$个数据，小顶堆有$fracn2$个数据。这个时候，我们可以从一个堆中不停地将堆顶元素移动到另一个堆，通过这样的调整，来让两个堆中的数据满足上 面的约定。 29|堆的应用：如何快速获取到Top10最热门的搜索关键词？ file:/F/temp/geektime/数据结构与算法之美/29堆的应用：如何快速获取到Top10最热门的搜索关键词？.html2019/1/15 15:36:04 于是，我们就可以利用
2、两个堆，一个大顶堆、一个小顶堆，实现在动态数据集合中求中位数的操作。插入数据因为需要涉及堆化，所以时间复杂度变成 了O(logn)，但是求中位数我们只需要返回大顶堆的堆顶元素就可以了，所以时间复杂度就是O(1)。 29|堆的应用：如何快速获取到Top10最热门的搜索关键词？ file:/F/temp/geektime/数据结构与算法之美/29堆的应用：如何快速获取到Top10最热门的搜索关键词？.html2019/1/15 15:36:04 实际上，利用两个堆不仅可以快速求出中位数，还可以快速求其他百分位的数据，原理是类似的。还记得我们在“为什么要学习数据结构与算法”里的这个问题 吗？“如何快
3、速求接口的99%响应时间？”我们现在就来看下，利用两个堆如何来实现。 在开始这个问题的讲解之前，我先解释一下，什么是“99%响应时间”。 中位数的概念就是将数据从小到大排列，处于中间位置，就叫中位数，这个数据会大于等于前面50%的数据。99百分位数的概念可以类比中位数，如果将一组数据 从小到大排列，这个99百分位数就是大于前面99%数据的那个数据。 如果你还是不太理解，我再举个例子。假设有100个数据，分别是1，2，3，100，那99百分位数就是99，因为小于等于99的数占总个数的99%。 弄懂了这个概念，我们再来看99%响应时间。如果有100个接口访问请求，每个接口请求的响应时间都不同，比如
4、55毫秒、100毫秒、23毫秒等，我们把这100个接 口的响应时间按照从小到大排列，排在第99的那个数据就是99%响应时间，也叫99百分位响应时间。 我们总结一下，如果有n个数据，将数据从小到大排列之后，99百分位数大约就是第n*99%个数据，同类，80百分位数大约就是第n*80%个数据。 弄懂了这些，我们再来看如何求99%响应时间。 我们维护两个堆，一个大顶堆，一个小顶堆。假设当前总数据的个数是n，大顶堆中保存n*99%个数据，小顶堆中保存n*1%个数据。大顶堆堆顶的数据就是我们要 找的99%响应时间。 每次插入一个数据的时候，我们要判断这个数据跟大顶堆和小顶堆堆顶数据的大小关系，然后决定插
5、入到哪个堆中。如果这个新插入的数据比大顶堆的堆顶数据 小，那就插入大顶堆；如果这个新插入的数据比小顶堆的堆顶数据大，那就插入小顶堆。 但是，为了保持大顶堆中的数据占99%，小顶堆中的数据占1%，在每次新插入数据之后，我们都要重新计算，这个时候大顶堆和小顶堆中的数据个数，是否还符 合99:1这个比例。如果不符合，我们就将一个堆中的数据移动到另一个堆，直到满足这个比例。移动的方法类似前面求中位数的方法，这里我就不啰嗦了。 通过这样的方法，每次插入数据，可能会涉及几个数据的堆化操作，所以时间复杂度是O(logn)。每次求99%响应时间的时候，直接返回大顶堆中的堆顶数据即 可，时间复杂度是O(1)。
6、29|堆的应用：如何快速获取到Top10最热门的搜索关键词？ file:/F/temp/geektime/数据结构与算法之美/29堆的应用：如何快速获取到Top10最热门的搜索关键词？.html2019/1/15 15:36:04 解答开篇 学懂了上面的一些应用场景的处理思路，我想你应该能解决开篇的那个问题了吧。假设现在我们有一个包含10亿个搜索关键词的日志文件，如何快速获取到Top 10最热门的搜索关键词呢？ 处理这个问题，有很多高级的解决方法，比如使用MapReduce等。但是，如果我们将处理的场景限定为单机，可以使用的内存为1GB。那这个问题该如何解决呢？ 因为用户搜索的关键词，有很多可
7、能都是重复的，所以我们首先要统计每个搜索关键词出现的频率。我们可以通过散列表、平衡二叉查找树或者其他一些支持快 速查找、插入的数据结构，来记录关键词及其出现的次数。 假设我们选用散列表。我们就顺序扫描这10亿个搜索关键词。当扫描到某个关键词时，我们去散列表中查询。如果存在，我们就将对应的次数加一；如果不存 在，我们就将它插入到散列表，并记录次数为1。以此类推，等遍历完这10亿个搜索关键词之后，散列表中就存储了不重复的搜索关键词以及出现的次数。 然后，我们再根据前面讲的用堆求Top K的方法，建立一个大小为10的小顶堆，遍历散列表，依次取出每个搜索关键词及对应出现的次数，然后与堆顶的搜索关键 词
8、对比。如果出现次数比堆顶搜索关键词的次数多，那就删除堆顶的关键词，将这个出现次数更多的关键词加入到堆中。 以此类推，当遍历完整个散列表中的搜索关键词之后，堆中的搜索关键词就是出现次数最多的Top 10搜索关键词了。 不知道你发现了没有，上面的解决思路其实存在漏洞。10亿的关键词还是很多的。我们假设10亿条搜索关键词中不重复的有1亿条，如果每个搜索关键词的平均长 度是50个字节，那存储1亿个关键词起码需要5GB的内存空间，而散列表因为要避免频繁冲突，不会选择太大的装载因子，所以消耗的内存空间就更多了。而我们 的机器只有1GB的可用内存空间，所以我们无法一次性将所有的搜索关键词加入到内存中。这个时
9、候该怎么办呢？ 我们在哈希算法那一节讲过，相同数据经过哈希算法得到的哈希值是一样的。我们可以哈希算法的这个特点，将10亿条搜索关键词先通过哈希算法分片到10个文 件中。 具体可以这样做：我们创建10个空文件00，01，02，09。我们遍历这10亿个关键词，并且通过某个哈希算法对其求哈希值，然后哈希值同10取模，得到的 结果就是这个搜索关键词应该被分到的文件编号。 对这10亿个关键词分片之后，每个文件都只有1亿的关键词，去除掉重复的，可能就只有1000万个，每个关键词平均50个字节，所以总的大小就是500MB。1GB的 内存完全可以放得下。 我们针对每个包含1亿条搜索关键词的文件，利用散列表和堆
10、，分别求出Top 10，然后把这个10个Top 10放在一块，然后取这100个关键词中，出现次数最多的10个 关键词，这就是这10亿数据中的Top 10最频繁的搜索关键词了。 内容小结 我们今天主要讲了堆的几个重要的应用，它们分别是：优先级队列、求Top K问题和求中位数问题。 优先级队列是一种特殊的队列，优先级高的数据先出队，而不再像普通的队列那样，先进先出。实际上，堆就可以看作优先级队列，只是称谓不一样罢了。求Top K问题又可以分为针对静态数据和针对动态数据，只需要利用一个堆，就可以做到非常高效率的查询Top K的数据。求中位数实际上还有很多变形，比如求99百分 位数据、90百分位数据等
11、，处理的思路都是一样的，即利用两个堆，一个大顶堆，一个小顶堆，随着数据的动态添加，动态调整两个堆中的数据，最后大顶堆的 堆顶元素就是要求的数据。 课后思考 29|堆的应用：如何快速获取到Top10最热门的搜索关键词？ file:/F/temp/geektime/数据结构与算法之美/29堆的应用：如何快速获取到Top10最热门的搜索关键词？.html2019/1/15 15:36:04 有一个访问量非常大的新闻网站，我们希望将点击量排名Top 10的新闻摘要，滚动显示在网站首页banner上，并且每隔1小时更新一次。如果你是负责开发这个功 能的工程师，你会如何来实现呢？ 欢迎留言和我分享，我会第
12、一时间给你反馈。 精选留言： 29|堆的应用：如何快速获取到Top10最热门的搜索关键词？ file:/F/temp/geektime/数据结构与算法之美/29堆的应用：如何快速获取到Top10最热门的搜索关键词？.html2019/1/15 15:36:04 feifei 2018-12-02 08:48:11 有一个访问量非常大的新闻网站，我们希望将点击量排名 Top 10 的新闻摘要，滚动显示在网站首页 banner 上，并且每隔 1 小时更新一次。如果你是负责开 发这个功能的工程师，你会如何来实现呢？ 我的思路是这样子， 1，对每篇新闻摘要计算一个hashcode，并建立摘要与hash
13、code的关联关系，使用map存储，以hashCode为key，新闻摘要为值 2，按每小时一个文件的方式记录下被点击的摘要的hashCode 3，当一个小时结果后，上一个小时的文件被关闭，开始计算上一个小时的点击top10 4，将hashcode分片到多个文件中，通过对hashCode取模运算，即可将相同的hashCode分片到相同的文件中 5，针对每个文件取top10的hashCode，使用Map的方式，统计出所有的摘要点击次数，然后再使用小顶堆（大小为10）计算top10, 6，再针对所有分片计算一个总的top10,最后合并的逻辑也是使用小顶堆，计算top10 7，如果仅展示前一个小时的t
14、op10,计算结束 8，如果需要展示全天，需要与上一次的计算按hashCode进行合并，然后在这合并的数据中取top10 9，在展示时，将计算得到的top10的hashcode，转化为新闻摘要显示即可 老师，你讲的这些例子，我觉得对我的工作和学习很有帮助，于是我花了一个周末将这一章节，将你所讲的堆的应用示例，全部翻译成了代码，并做了相关 的验证，感觉自己收获很多，我也将这块代码上传了github，欢迎老师你的指正，需要的同学，也可以一起交流， 1，合并有序小文件 2，高性能定时器的应用 3，求topk 4，求中位数 5 ,大文件的关键字的统计 31赞 Miletos 2018-11-27 23
15、:47:43 “如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；如果新加入的数据大于等于小顶堆的堆顶元素，我们就将这个新数据 29|堆的应用：如何快速获取到Top10最热门的搜索关键词？ file:/F/temp/geektime/数据结构与算法之美/29堆的应用：如何快速获取到Top10最热门的搜索关键词？.html2019/1/15 15:36:04 插入到小顶堆。” 1. 这里不太对劲，前文中说到，小顶堆的堆顶大于大顶堆的堆顶。 如果新进元素在小顶堆堆顶和大顶堆堆顶元素值之间，没有规定插入哪个堆。 我觉得，是不是只要判断一次就可以了。新进元素值大于等于小顶堆堆顶
16、元素的，插入小顶堆，否则插入大顶堆。 当某一个堆数据过多时再重新移动堆顶元素。 2. 求中位数的源数据中，是否允许重复数据？ 25赞 作者回复2018-11-28 11:08:48 1 你说的对 我改下 多谢指正 2 可以重复 豪华 2018-11-28 00:14:20 老师，分片求取前十是不是有bug，如果有一个关键词在每一组分片中都是前第十一位，在整个十亿中个数总和是第一位，是不是用分片求出了错误的结果 呢？ 9赞 作者回复2018-11-28 01:58:31 不会的 相同的关键词经过哈希之后只会到一台机器 守着云开 2018-11-28 09:20:27 10亿关键词分片之后 每个文
17、件并不一定有1亿的关键词吧 老师 7赞 蔷薇骑士 2018-12-14 11:35:12 定时任务这个例子感觉有问题吧，定时任务是动态加入的，假设当前堆顶的任务是一个小时后的，难道这一个小时都不做扫描吗，随时可能会加入需要更早 执行的任务 6赞 辉哥 2018-12-02 03:49:37 思考题：1，维护两个散列表，一个是一小时新增的点击量的散列表，以新闻id为键，点击次数为值。一个是全部点击量的散列表。每隔一小时把新增的散列 表的数据同步到全部点击量的散列表。然后把这小时内有变化的全部点击量的散列表的数据（即此小时有新增点击量的新闻数据）和我们维护的10个元素小 顶堆堆顶进行比较，比堆顶的
18、点击量大的，则使用该元素替换堆顶，再进行堆化。比堆顶点击量小的则不做处理。然后比较完，根据堆顶的10个元素的id， 从数据库读取相应的新闻摘要显示在banner上。除此之外，还要把变化后的全部点击量散列表同步到数据库。因为保存的是新闻id，所以散列表长度不会很 大，所占用的内存也不会很大。而每个小时新增的访问量的新闻id数也不会很多，毕竟很多人只会阅读热门消息。所以新增的点击量的新闻数据假设为k,则 每小时同步小顶堆的时间负责度为o(klg 10); 4赞 29|堆的应用：如何快速获取到Top10最热门的搜索关键词？ file:/F/temp/geektime/数据结构与算法之美/29堆的应用
19、：如何快速获取到Top10最热门的搜索关键词？.html2019/1/15 15:36:04 ALAN 2018-11-28 11:15:14 1:建一个散射列表，key为点击网址，value为点击次数。散射列表通过从log中计算得来。 2:建一个10个数据的小顶堆，数据值为点击次数，扫描散射列表，新元素次数比堆顶元素大则删除堆顶元素，插入新元素，小则继续扫描散射列表。 3:扫描完整个散射列表后，即得到top 10点击量，将点击网址存储在数组A中。数组A一个小时更新一次。 4:散射列表实时更新，小顶堆也实时更新，以一小时为间隔，将小顶堆结果更新到数组A中。 4赞 oatlmy 2018-11-
20、28 04:41:50 老师，请问为什么评价算法性能是根据时间和空间复杂度，而不是别的参数？是因为计算机结构是冯诺依曼体系，除了输入输出设备和控制器，就剩下运算 器和存储器了吗？ 3赞 作者回复2018-11-28 11:17:24 你理解的没错 小新是也 2018-12-09 14:23:25 如果我要1%到99%响应时间，这样建的堆就有点多了 2赞 作者回复2018-12-10 01:56:00 这需求.具体问题具体分析吧 geektime learn 2018-11-28 02:19:14 Hadoop、Spark入门demowordcount了解下 2赞 S(PMOS)管导通, 不会形
21、成电源到地的直流通路. (至于防止静电造成损坏, 因芯片管脚设计中一般会加保护电路, 反而无此必要).2. 对于输出管脚:1)正常的输出管脚(push-pull型), 一般没有必要接上拉或下拉电阻.2)OD或OC(漏极开路或集电极开路)型管脚,这种类型的管脚需要外接上拉电阻实现线与功能(此时多个输出可直接相连. 典型应用是: 系统板上多个芯片的INT(中断信号)输出直接相连, 再接上一上拉电阻, 然后输入MCU的INT引脚, 实现中断报警功能).其工作原理是: 在正常工作情况下, OD型管脚内部的NMOS管关闭, 对外部而言其处于高阻状态, 外接上拉电阻使输出位于高电平(无效中断状态); 当有
22、中断需求时, OD型管脚内部的NMOS管接通, 因其导通电阻远远小于上拉电阻, 使输出位于低电平(有效中断状态). 针对MOS 电路上下拉电阻阻值以几十至几百K为宜.儀儀事不抓住主要问题，而专顾细枝末节。3、对科学精神的其他认识：尊重事实、一丝不苟、敢于质疑、不断创新更多免费资料，请关注公众号：阅乐课堂20|散列表（下）：为什么散列表和链表经常会一起使用？ file:/F/temp/geektime/数据结构与算法之美/20散列表（下）：为什么散列表和链表经常会一起使用？.html2019/1/15 15:35:45 20|散列表（下）：为什么散列表和链表经常会一起使用？ 我们已经学习了20节
23、内容，你有没有发现，有两种数据结构，散列表和链表，经常会被放在一起使用。你还记得，前面的章节中都有哪些地方讲到散列表和链表 的组合使用吗？我带你一起回忆一下。 在链表那一节，我讲到如何用链表来实现LRU缓存淘汰算法，但是链表实现的LRU缓存淘汰算法的时间复杂度是O(n)，当时我也提到了，通过散列表可以将这个 时间复杂度降低到O(1)。 在跳表那一节，我提到Redis的有序集合是使用跳表来实现的，跳表可以看作一种改进版的链表。当时我们也提到，Redis有序集合不仅使用了跳表，还用到了散列 表。 除此之外，如果你熟悉Java编程语言，你会发现LinkedHashMap这样一个常用的容器，也用到了散
24、列表和链表两种数据结构。 今天，我们就来看看，在这几个问题中，散列表和链表都是如何组合起来使用的，以及为什么散列表和链表会经常放到一块使用。 LRU缓存淘汰算法 在链表那一节中，我提到，借助散列表，我们可以把LRU缓存淘汰算法的时间复杂度降低为O(1)。现在，我们就来看看它是如何做到的。 首先，我们来回顾一下当时我们是如何通过链表实现LRU缓存淘汰算法的。 我们需要维护一个按照访问时间从大到小有序排列的链表结构。因为缓存大小有限，当缓存空间不够，需要淘汰一个数据的时候，我们就直接将链表头部的结点 删除。 当要缓存某个数据的时候，先在链表中查找这个数据。如果没有找到，则直接将数据放到链表的尾部；
25、如果找到了，我们就把它移动到链表的尾部。因为查找数 据需要遍历链表，所以单纯用链表实现的LRU缓存淘汰算法的时间复杂很高，是O(n)。 实际上，我总结一下，一个缓存（cache）系统主要包含下面这几个操作： 往缓存中添加一个数据； 从缓存中删除一个数据； 在缓存中查找一个数据。 这三个操作都要涉及“查找”操作，如果单纯地采用链表的话，时间复杂度只能是O(n)。如果我们将散列表和链表两种数据结构组合使用，可以将这三个操作的时间 复杂度都降低到O(1)。具体的结构就是下面这个样子： 20|散列表（下）：为什么散列表和链表经常会一起使用？ file:/F/temp/geektime/数据结构与算法之
26、美/20散列表（下）：为什么散列表和链表经常会一起使用？.html2019/1/15 15:35:45 我们使用双向链表存储数据，链表中的每个结点处理存储数据（data）、前驱指针（prev）、后继指针（next）之外，还新增了一个特殊的字段hnext。这个hnext有 什么作用呢？ 因为我们的散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是刚刚我们提到的双向链表，另一个链是散列表中的拉链。前驱和后继指 20|散列表（下）：为什么散列表和链表经常会一起使用？ file:/F/temp/geektime/数据结构与算法之美/20散列表（下）：为什么散列表和链表经常会一起使用？
27、.html2019/1/15 15:35:45 针是为了将结点串在双向链表中，hnext指针是为了将结点串在散列表的拉链中。 了解了这个散列表和双向链表的组合存储结构之后，我们再来看，前面讲到的缓存的三个操作，是如何做到时间复杂度是O(1)的？ 首先，我们来看如何查找一个数据。我们前面讲过，散列表中查找数据的时间复杂度接近O(1)，所以通过散列表，我们可以很快地在缓存中找到一个数据。当找 到数据之后，我们还需要将它移动到双向链表的尾部。 其次，我们来看如何删除一个数据。我们需要找到数据所在的结点，然后将结点删除。借助散列表，我们可以在O(1)时间复杂度里找到要删除的结点。因为我们 的链表是双向
28、链表，双向链表可以通过前驱指针O(1)时间复杂度获取前驱结点，所以在双向链表中，删除结点只需要O(1)的时间复杂度。 最后，我们来看如何添加一个数据。添加数据到缓存稍微有点麻烦，我们需要先看这个数据是否已经在缓存中。如果已经在其中，需要将其移动到双向链表的尾 部；如果不在其中，还要看缓存有没有满。如果满了，则将双向链表头部的结点删除，然后再将数据放到链表的尾部；如果没有满，就直接将数据放到链表的尾 部。 这整个过程涉及的查找操作都可以通过散列表来完成。其他的操作，比如删除头结点、链表尾部插入数据等，都可以在O(1)的时间复杂度内完成。所以，这三个 操作的时间复杂度都是O(1)。至此，我们就通过
29、散列表和双向链表的组合使用，实现了一个高效的、支持LRU缓存淘汰算法的缓存系统原型。 Redis有序集合 在跳表那一节，讲到有序集合的操作时，我稍微做了些简化。实际上，在有序集合中，每个成员对象有两个重要的属性，key（键值）和score（分值）。我们不仅 会通过score来查找数据，还会通过key来查找数据。 举个例子，比如用户积分排行榜有这样一个功能：我们可以通过用户的ID来查找积分信息，也可以通过积分区间来查找用户ID或者姓名信息。这里包含ID、姓名 和积分的用户信息，就是成员对象，用户ID就是key，积分就是score。 所以，如果我们细化一下Redis有序集合的操作，那就是下面这样：
30、 添加一个成员对象； 按照键值来删除一个成员对象； 按照键值来查找一个成员对象； 按照分值区间查找数据，比如查找积分在100, 356之间的成员对象； 按照分值从小到大排序成员变量； 如果我们仅仅按照分值将成员对象组织成跳表的结构，那按照键值来删除、查询成员对象就会很慢，解决方法与LRU缓存淘汰算法的解决方法类似。我们可以再 按照键值构建一个散列表，这样按照key来删除、查找一个成员对象的时间复杂度就变成了O(1)。同时，借助跳表结构，其他操作也非常高效。 实际上，Redis有序集合的操作还有另外一类，也就是查找成员对象的排名（Rank）或者根据排名区间查找成员对象。这个功能单纯用刚刚讲的这种
31、组合结构就无 法高效实现了。这块内容我后面的章节再讲。 Java LinkedHashMap 20|散列表（下）：为什么散列表和链表经常会一起使用？ file:/F/temp/geektime/数据结构与算法之美/20散列表（下）：为什么散列表和链表经常会一起使用？.html2019/1/15 15:35:45 前面我们讲了两个散列表和链表结合的例子，现在我们再来看另外一个，Java中的LinkedHashMap这种容器。 如果你熟悉Java，那你几乎天天会用到这个容器。我们之前讲过，HashMap底层是通过散列表这种数据结构实现的。而LinkedHashMap前面比HashMap多了一 个“
32、Linked”，这里的“Linked”是不是说，LinkedHashMap是一个通过链表法解决散列冲突的散列表呢？ 实际上，LinkedHashMap并没有这么简单，其中的“Linked”也并不仅仅代表它是通过链表法解决散列冲突的。关于这一点，在我是初学者的时候，也误解了很久。 我们先来看一段代码。你觉得这段代码会以什么样的顺序打印3，1，5，2这几个key呢？原因又是什么呢？ HashMap m = new LinkedHashMap(); m.put(3, 11); m.put(1, 12); m.put(5, 23); m.put(2, 22); for (Map.Entry e : m
33、.entrySet() System.out.println(e.getKey(); 我先告诉你答案，上面的代码会按照数据插入的顺序依次来打印，也就是说，打印的顺序就是3，1，5，2。你有没有觉得奇怪？散列表中数据是经过散列函数打 乱之后无规律存储的，这里是如何实现按照数据的插入顺序来遍历打印的呢？ 你可能已经猜到了，LinkedHashMap也是通过散列表和链表组合在一起实现的。实际上，它不仅支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据。你 可以看下面这段代码： / 10是初始大小，0.75是装载因子，true是表示按照访问时间排序 HashMap m = new LinkedHa
34、shMap(10, 0.75f, true); m.put(3, 11); m.put(1, 12); m.put(5, 23); m.put(2, 22); m.put(3, 26); m.get(5); for (Map.Entry e : m.entrySet() System.out.println(e.getKey(); 这段代码打印的结果是1，2，3，5。我来具体分析一下，为什么这段代码会按照这样顺序来打印。 每次调用put()函数，往LinkedHashMap中添加数据的时候，都会将数据添加到链表的尾部，所以，在前四个操作完成之后，链表中的数据是下面这样： 20|散列表（下）：为
35、什么散列表和链表经常会一起使用？ file:/F/temp/geektime/数据结构与算法之美/20散列表（下）：为什么散列表和链表经常会一起使用？.html2019/1/15 15:35:45 在第8行代码中，再次将键值为3的数据放入到LinkedHashMap的时候，会先查找这个键值是否已经有了，然后，再将已经存在的(3,11)删除，并且将新的(3,26)放到 链表的尾部。所以，这个时候链表中的数据就是下面这样： 当第9行代码访问到key为5的数据的时候，我们将被47|向量空间：如何实现一个简单的音乐推荐系统？ file:/F/geektime/ebook/数据结构与算法之美/47向量空
36、间：如何实现一个简单的音乐推荐系统？.html2019/1/22 18:48:33 47|向量空间：如何实现一个简单的音乐推荐系统？ 很多人都喜爱听歌，以前我们用MP3听歌，现在直接通过音乐App在线就能听歌。而且，各种音乐App的功能越来越强大，不仅可以自己选歌听，还可以根据你听 歌的口味偏好，给你推荐可能会喜爱的音乐，而且有时候，推荐的音乐还非常适合你的口味，甚至会惊艳到你！如此智能的一个功能，你知道它是怎么实现的 吗？ 算法解析 实际上，要解决这个问题，并不需要特别高深的理论。解决思路的核心思想非常简单、直白，用两句话就能总结出来。 找到跟你口味偏好相似的用户，把他们爱听的歌曲推荐给你；
37、 找出跟你喜爱的歌曲特征相似的歌曲，把这些歌曲推荐给你。 接下来，我就分别讲解一下这两种思路的具体实现方法。 1.基于相似用户做推荐 如何找到跟你口味偏好相似的用户呢？或者说如何定义口味偏好相似呢？实际上，思路也很简单，我们把跟你听类似歌曲的人，看做口味相似的用户。你可以看 我下面画的这个图。我用“1”表示“喜爱”，用“0”笼统地表示“不发表意见”。从图中我们可以看出，你跟小明共同喜爱的歌曲最多，有5首。于是，我们就可以说， 小明跟你的口味非常相似。 47|向量空间：如何实现一个简单的音乐推荐系统？ file:/F/geektime/ebook/数据结构与算法之美/47向量空间：如何实现一个简
38、单的音乐推荐系统？.html2019/1/22 18:48:33 我们只需要遍历所有的用户，对比每个用户跟你共同喜爱的歌曲个数，并且设置一个阈值，如果你和某个用户共同喜爱的歌曲个数超过这个阈值，我们就把这个 用户看作跟你口味相似的用户，把这个用户喜爱但你还没听过的歌曲，推荐给你。 不过，刚刚的这个解决方案中有一个问题，我们如何知道用户喜爱哪首歌曲呢？也就是说，如何定义用户对某首歌曲的喜爱程度呢？ 实际上，我们可以通过用户的行为，来定义这个喜爱程度。我们给每个行为定义一个得分，得分越高表示喜爱程度越高。 47|向量空间：如何实现一个简单的音乐推荐系统？ file:/F/geektime/eboo
39、k/数据结构与算法之美/47向量空间：如何实现一个简单的音乐推荐系统？.html2019/1/22 18:48:33 还是刚刚那个例子，我们如果把每个人对每首歌曲的喜爱程度表示出来，就是下面这个样子。图中，某个人对某首歌曲是否喜爱，我们不再用“1”或者“0”来表示， 而是对应一个具体的分值。 47|向量空间：如何实现一个简单的音乐推荐系统？ file:/F/geektime/ebook/数据结构与算法之美/47向量空间：如何实现一个简单的音乐推荐系统？.html2019/1/22 18:48:33 有了这样一个用户对歌曲的喜爱程度的对应表之后，如何来判断两个用户是否口味相似呢？ 显然，我们不能
40、再像之前那样，采用简单的计数来统计两个用户之间的相似度。还记得我们之前讲字符串相似度度量时，提到的编辑距离吗？这里的相似度度 量，我们可以使用另外一个距离，那就是欧几里得距离（Euclidean distance）。欧几里得距离是用来计算两个向量之间的距离的。这个概念中有两个关键词，向量 和距离，我来给你解释一下。 一维空间是一条线，我们用1，2，3这样单个的数，来表示一维空间中的某个位置；二维空间是一个面，我们用（1，3）（4，2）（2，2）这样的两个 数，来表示二维空间中的某个位置；三维空间是一个立体空间，我们用（1，3，5）（3，1，7）（2，4，3）这样的三个数，来表示三维空间中的某个
41、位置。 一维、二维、三维应该都不难理解，那更高维中的某个位置该如何表示呢？ 类比一维、二维、三维的表示方法，K维空间中的某个位置，我们可以写作（$X_1$，$X_2$，$X_3$，$X_K$）。这种表示方法就是向 量（vector）。我们知道，二维、三维空间中，两个位置之间有距离的概念，类比到高纬空间，同样也有距离的概念，这就是我们说的两个向量之间的距离。 47|向量空间：如何实现一个简单的音乐推荐系统？ file:/F/geektime/ebook/数据结构与算法之美/47向量空间：如何实现一个简单的音乐推荐系统？.html2019/1/22 18:48:33 那如何计算两个向量之间的距离呢
42、？我们还是可以类比到二维、三维空间中距离的计算方法。通过类比，我们就可以得到两个向量之间距离的计算公式。这个计 算公式就是欧几里得距离的计算公式： 我们把每个用户对所有歌曲的喜爱程度，都用一个向量表示。我们计算出两个向量之间的欧几里得距离，作为两个用户的口味相似程度的度量。从图中的计算可 以看出，小明与你的欧几里得距离距离最小，也就是说，你俩在高维空间中靠得最近，所以，我们就断定，小明跟你的口味最相似。 47|向量空间：如何实现一个简单的音乐推荐系统？ file:/F/geektime/ebook/数据结构与算法之美/47向量空间：如何实现一个简单的音乐推荐系统？.html2019/1/22
43、18:48:33 2.基于相似歌曲做推荐 刚刚我们讲了基于相似用户的歌曲推荐方法，但是，如果用户是一个新用户，我们还没有收集到足够多的行为数据，这个时候该如何推荐呢？我们现在再来看另 外一种推荐方法，基于相似歌曲的推荐方法，也就是说，如果某首歌曲跟你喜爱的歌曲相似，我们就把它推荐给你。 如何判断两首歌曲是否相似呢？对于人来说，这个事情可能会比较简单，但是对于计算机来说，判断两首歌曲是否相似，那就需要通过量化的数据来表示了。我 们应该通过什么数据来量化两个歌曲之间的相似程度呢？ 47|向量空间：如何实现一个简单的音乐推荐系统？ file:/F/geektime/ebook/数据结构与算法之美/4
44、7向量空间：如何实现一个简单的音乐推荐系统？.html2019/1/22 18:48:33 最容易想到的是，我们对歌曲定义一些特征项，比如是伤感的还是愉快的，是摇滚还是民谣，是柔和的还是高亢的等等。类似基于相似用户的推荐方法，我们给 每个歌曲的每个特征项打一个分数，这样每个歌曲就都对应一个特征项向量。我们可以基于这个特征项向量，来计算两个歌曲之间的欧几里得距离。欧几里得距 离越小，表示两个歌曲的相似程度越大。 但是，要实现这个方案，需要有一个前提，那就是我们能够找到足够多，并且能够全面代表歌曲特点的特征项，除此之外，我们还要人工给每首歌标注每个特征 项的得分。对于收录了海量歌曲的音乐App来说
45、，这显然是一个非常大的工程。此外，人工标注有很大的主观性，也会影响到推荐的准确性。 既然基于歌曲特征项计算相似度不可行，那我们就换一种思路。对于两首歌，如果喜欢听的人群都是差不多的，那侧面就可以反映出，这两首歌比较相似。如图 所示，每个用户对歌曲有不同的喜爱程度，我们依旧通过上一个解决方案中定义得分的标准，来定义喜爱程度。 你有没有发现，这个图跟基于相似用户推荐中的图几乎一样。只不过这里把歌曲和用户主次颠倒了一下。基于相似用户的推荐方法中，针对每个用户，我们将对 各个歌曲的喜爱程度作为向量。基于相似歌曲的推荐思路中，针对每个歌曲，我们将每个用户的打分作为向量。 47|向量空间：如何实现一个简单的音乐推
