40初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?.pdf
《40初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?.pdf》由会员分享,可在线阅读,更多相关《40初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?.pdf(17页珍藏版)》请在文库网上搜索。
1、访问到的数据移动到链表的尾部。所以,第9行代码之后,链表中的数据是下面这样: 20|散列表(下):为什么散列表和链表经常会一起使用? file:/F/temp/geektime/数据结构与算法之美/20散列表(下):为什么散列表和链表经常会一起使用?.html2019/1/15 15:35:45 所以,最后打印出来的数据是1,2,3,5。从上面的分析,你有没有发现,按照访问时间排序的LinkedHashMap本身就是一个支持LRU缓存淘汰策略的缓存系统? 实际上,它们两个的实现原理也是一模一样的。我也就不再啰嗦了。 我现在来总结一下,实际上,LinkedHashMap是通过双向链表和散列表这两
2、种数据结构组合实现的。LinkedHashMap中的“Linked”实际上是指的是双向链表,并 非指用链表法解决散列冲突。 解答开篇&内容小结 弄懂刚刚我讲的这三个例子,开篇的问题也就不言而喻了。我这里总结一下,为什么散列表和链表经常一块使用? 散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作,但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说,它无法支持按照 某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据,那我们需要将散列表中的数据拷贝到数组中,然后排序,再遍历。 因为散列表是动态数据结构,不停地有数据的插入、删除,所以每当我们希望按顺序遍历散列表中的数据
3、的时候,都需要先排序,那效率势必会很低。为了解决 这个问题,我们将散列表和链表(或者跳表)结合在一起使用。 课后思考 1. 今天讲的几个散列表和链表结合使用的例子里,我们用的都是双向链表。如果把双向链表改成单链表,还能否正常工作呢?为什么呢? 2. 假设猎聘网有10万名猎头,每个猎头都可以通过做任务(比如发布职位)来积累积分,然后通过积分来下载简历。假设你是猎聘网的一名工程师,如何在内 存中存储这10万个猎头ID和积分信息,让它能够支持这样几个操作: 根据猎头的ID快速查找、删除、更新这个猎头的积分信息; 20|散列表(下):为什么散列表和链表经常会一起使用? file:/F/temp/gee
4、ktime/数据结构与算法之美/20散列表(下):为什么散列表和链表经常会一起使用?.html2019/1/15 15:35:45 查找积分在某个区间的猎头ID列表; 查找按照积分从小到大排名在第x位到第y位之间的猎头ID列表。 欢迎留言和我分享,我会第一时间给你反馈。 精选留言: 20|散列表(下):为什么散列表和链表经常会一起使用? file:/F/temp/geektime/数据结构与算法之美/20散列表(下):为什么散列表和链表经常会一起使用?.html2019/1/15 15:35:45 Smallfly 2018-11-05 03:56:15 通过这 20 节课学习下来,个人感觉其
5、实就两种数据结构,链表和数组。 数组占据随机访问的优势,却有需要连续内存的缺点。 链表具有可不连续存储的优势,但访问查找是线性的。 散列表和链表、跳表的混合使用,是为了结合数组和链表的优势,规避它们的不足。 我们可以得出数据结构和算法的重要性排行榜:连续空间 时间 碎片空间。 PS:跟专业的书籍相比,老师讲的真的是通俗易懂不废话,篇篇是干货。如果这个课程学不下去,学其它的会更加困难。暂时不懂的话反复阅读复习,外加 查阅,一定可以的! 145赞 作者回复2018-11-06 01:38:23 大牛 Smallfly 2018-11-05 06:03:58 1. 在删除一个元素时,虽然能 O(1)
6、 的找到目标结点,但是要删除该结点需要拿到前一个结点的指针,遍历到前一个结点复杂度会变为 O(N),所以用双链表 实现比较合适。 (但其实硬要操作的话,单链表也是可以实现 O(1) 时间复杂度删除结点的)。 iOS 的同学可能知道,YYMemoryCache 就是结合散列表和双向链表来实现的。 2. 以积分排序构建一个跳表,再以猎头 ID 构建一个散列表。 1)ID 在散列表中所以可以 O(1) 查找到这个猎头; 2)积分以跳表存储,跳表支持区间查询; 3 20|散列表(下):为什么散列表和链表经常会一起使用? file:/F/temp/geektime/数据结构与算法之美/20散列表(下):
7、为什么散列表和链表经常会一起使用?.html2019/1/15 15:35:45 )这点根据目前学习的知识暂时无法实现,老师文中也提到了。 60赞 作者回复2018-11-06 01:37:32 其他同学可以看看这条留言 姜威 2018-11-16 13:42:35 带着问题去学习: 1.为什么散列表和链表经常放在一起使用? 2.散列表和链表如何组合起来使用? 一、为什么散列表和链表经常放在一起使用? 1.散列表的优点:支持高效的数据插入、删除和查找操作 2.散列表的缺点:不支持快速顺序遍历散列表中的数据 3.如何按照顺序快速遍历散列表的数据?只能将数据转移到数组,然后排序,最后再遍历数据。
8、4.我们知道散列表是动态的数据结构,需要频繁的插入和删除数据,那么每次顺序遍历之前都需要先排序,这势必会造成效率非常低下。 5.如何解决上面的问题呢?就是将散列表和链表(或跳表)结合起来使用。 二、散列表和链表如何组合起来使用? 1.LRU(Least Recently Used)缓存淘汰算法 1.1.LRU缓存淘汰算法主要操作有哪些?主要包含3个操作: 往缓存中添加一个数据; 从缓存中删除一个数据; 在缓存中查找一个数据; 总结:上面3个都涉及到查找。 1.2.如何用链表实现LRU缓存淘汰算法? 需要维护一个按照访问时间从大到小的有序排列的链表结构。 缓冲空间有限,当空间不足需要淘汰一个数据
9、时直接删除链表头部的节点。 当要缓存某个数据时,先在链表中查找这个数据。若未找到,则直接将数据放到链表的尾部。若找到,就把它移动到链表尾部。 前面说了,LRU缓存的3个主要操作都涉及到查找,若单纯由链表实现,查找的时间复杂度很高为O(n)。若将链表和散列表结合使用,查找的时间复杂度 会降低到O(1)。 1.3.如何使用散列表和链表实现LRU缓存淘汰算法? 使用双向链表存储数据,链表中每个节点存储数据(data)、前驱指针(prev)、后继指针(next)和hnext指针(解决散列冲突的链表指针)。 散列表通过链表法解决散列冲突,所以每个节点都会在两条链中。一条链是双向链表,另一条链是散列表中的
10、拉链。前驱和后继指针是为了将节点串在双 向链表中,hnext指针是为了将节点串在散列表的拉链中。 LRU缓存淘汰算法的3个主要操作如何做到时间复杂度为O(1)呢? 20|散列表(下):为什么散列表和链表经常会一起使用? file:/F/temp/geektime/数据结构与算法之美/20散列表(下):为什么散列表和链表经常会一起使用?.html2019/1/15 15:35:45 首先,我们明确一点就是链表本身插入和删除一个节点的时间复杂度为O(1),因为只需更改几个指针指向即可。 接着,来分析查找操作的时间复杂度。当要查找一个数据时,通过散列表可实现在O(1)时间复杂度找到该数据,再加上前面
11、说的插入或删除的时间复杂度是 O(1),所以我们总操作的时间复杂度就是O(1)。 2.Redis有序集合 2.1.什么是有序集合? 在有序集合中,每个成员对象有2个重要的属性,即key(键值)和score(分值)。 不仅会通过score来查找数据,还会通过key来查找数据。 2.2.有序集合的操作有哪些? 举个例子,比如用户积分排行榜有这样一个功能:可以通过用户ID来查找积分信息,也可以通过积分区间来查找用户ID。这里用户ID就是key,积分就是scor e。所以,有序集合的操作如下: 添加一个对象; 根据键值删除一个对象; 根据键值查找一个成员对象; 根据分值区间查找数据,比如查找积分在10
12、0.356之间的成员对象; 按照分值从小到大排序成员变量。 这时可以按照分值将成员对象组织成跳表结构,按照键值构建一个散列表。那么上面的所有操作都非常高效。 3.Java LinkedHashMap 和LRU缓存淘汰策略实现一模一样。支持按照插入顺序遍历数据,也支持按照访问顺序遍历数据。 三、课后思考 1.上面所讲的几个散列表和链表组合的例子里,我们都是使用双向链表。如果把双向链表改成单链表,还能否正常工作?为什么呢? 2.假设猎聘网有10万名猎头,每个猎头可以通过做任务(比如发布职位)来积累积分,然后通过积分来下载简历。假设你是猎聘网的一名工程师,如何在内 存中存储这10万个猎头的ID和积分
13、信息,让它能够支持这样几个操作: 1)根据猎头ID查收查找、删除、更新这个猎头的积分信息; 2)查找积分在某个区间的猎头ID列表; 3)查找按照积分从小到大排名在第x位到第y位之间的猎头ID列表。 8赞 莫问流年 2018-11-05 01:55:18 怎么判断缓存已满,是要维护一个计数变量吗 8赞 作者回复2018-11-06 01:42:32 是的 Keep-Moving 2018-11-05 01:27:00 LRU查找数据,查找到之后,不是应该把数据放到链表的头部吗?为什么这里说是尾部? 6赞 20|散列表(下):为什么散列表和链表经常会一起使用? file:/F/temp/geekt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 40 初识 动态 规划 如何 巧妙 解决 十一 购物 问题