程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23440 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

46 | 缓存系统:如何通过哈希表和队列实现高效访问?

黄申 2019-04-01
你好,我是黄申。
经过前三大模块的学习,我带你纵览了数学在各个计算机编程领域的重要应用。离散数学是基础数据结构和编程算法的基石,而概率统计论和线性代数,是很多信息检索和机器学习算法的核心。
因此,今天开始,我会综合性地运用之前所讲解的一些知识,设计并实现一些更有实用性的核心模块或者原型系统。通过这种基于案例的讲解,我们可以融汇贯通不同的数学知识,并打造更加高效、更加智能的计算机系统。首先,让我们从一个缓存系统入手,开始综合应用篇的学习。

什么是缓存系统?

缓存(Cache)是计算机系统里非常重要的发明之一,它在编程领域中有非常非常多的应用。小到电脑的中央处理器(CPU)、主板、显卡等硬件,大到大规模的互联网站点,都在广泛使用缓存来提升速度。而在网站的架构设计中,一般不会像 PC 电脑那样采用高速的缓存介质,而是采用普通的服务器内存。但是网站架构所使用的内存容量大得多,至少是数个吉字节 (GB)。
我们可以把缓存定义为数据交换的缓冲区。它的读取速度远远高于普通存储介质,可以帮助系统更快地运行。当某个应用需要读取数据时,会优先从缓存中查找需要的内容,如果找到了则直接获取,这个效率要比读取普通存储更高。如果缓存中没有发现需要的内容,再到普通存储中寻找。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(6)

  • 铁丑-王立丰
    嗯嗯,我下午也在想,这个队列应该是一个双向链表,而且新加的哈希表可能还要解决队列节点的冲突问题。设计的再复杂一点这个结构应该能够和原有的那张缓存哈希表融合。这样还能节省内存。

    作者回复: 融合的概念很新颖,代码可读性会弱一点,但是效率很高👍

    2019-04-04
    2
  • 铁丑-王立丰
    查找数据是否在队列这个成本也不小啊

    作者回复: 这是个好问题,正常的情况下,我们假设哈希表和队列里的数据一致,除非发生了异常。
    如果是这样,我们可以利用链表来实现队列,然后使用哈希表存储每个被缓存结果所对应的队列结点,这样我们可以快速访问队列的结点,并使用链表结点的移动来实现队列内结点的移动。

    2019-04-03
    2
  • Paul Shan
    缓存意味着数据源有两个,而且这两个数据源访问成本和数据完备度不同。访问成本低的数据不完备,数据完备的访问成本高。要结合这两个数据源来设计访问成本尽可能低,同时数据又是完备的系统。基于队列和哈希表实现的LRU算法是经典算法之一。队列维护缓存大小,满的时候淘汰最近没用到的数据。哈希表提升查询效率。每次访问,先查哈希表,如果数据存在,将该数据放到队列尾部,让其远离被淘汰的位置,然后返回数据。如果数据不存在,就从完备的数据源中取得数据,将数据放入队列,如果队列已满,则淘汰掉最近最少用的数据,然后得到最新返回的数据。队列要面临频繁的插入和改位置操作,选用基于双向链表的队列较为高效。
    2019-10-14
  • qinggeouye
    # collections 的 OrderedDict()

    class LRUCache:

        def __init__(self, capacity):
            self.capacity = capacity
            self.queue = collections.OrderedDict()

        def get(self, key):
            if key not in self.queue:
                return -1 # 要找的数据不在缓存中则返回 -1
            value = self.queue.pop(key) # 将命中缓存的数据移除
            self.queue[key] = value # 将命中缓存的数据重新添加到头部
            return self.queue[key]

        def put(self, key, value):
            if key in self.queue: # 如果已经存在缓存中,则先移除老的数据
                self.queue.pop(key)
            elif len(self.queue.items()) == self.capacity:
                self.queue.popitem(last=False) # 如果不存在缓存并且达到最大容量 则把最后的数据淘汰
            self.queue[key] = value # 将新数据添加到头部

    作者回复: 这部分实现主要侧重于queue实现LRU策略,依赖于Python queue的查找机制,如果Python的queue也有类似哈希表的查询效率,那么也是一种更简洁的实现方式。

    2019-04-09
  • 失火的夏天
    class LRUCache {

        private Node head;// 最近最少使用,类似列队的头,出队
        private Node tail;// 最近最多使用,类似队列的尾,入队
        private Map<Integer,Node> cache;
        private int capacity;

        public LRUCache(int capacity) {
            this.cache = new HashMap<>();
            this.capacity = capacity;
        }

        public int get(int key) {
            Node node = cache.get(key);
            if(node == null){
                return -1;
            }else{
                moveNode(node);
                return node.value;
            }
        }

        public void put(int key, int value) {
            Node node = cache.get(key);
            if (node != null){
                node.value = value;
                moveNode(node);
            }else {
                removeHead();
                node = new Node(key,value);
                addNode(node);
            }
            cache.put(key,node);
        }

        private void removeHead(){
            if (cache.size() == capacity){
                Node tempNode = head;
                cache.remove(head.key);
                head = head.next;
                tempNode.next = null;
                if (head != null){
                    head.prev = null;
                }
            }
        }

        /**
         * 链表加入节点
         * @param node
         */
        private void addNode(Node node){
            if (head == null){
                head = node;
                tail = node;
            }else {
                addNodeToTail(node);
            }
        }

        private void addNodeToTail(Node node){
            node.prev = tail;
            tail.next = node;
            tail = node;
        }

        private void moveNode(Node node){
            if(head == node && node != tail){
                head = node.next;
                head.prev = null;
                node.next = null;
                addNodeToTail(node);
            }else if (tail == node){
                // 不做任何操作
            }else {
                // 普遍情况,node节点移除链表,加入到尾节点后面,tail指针指向node
                node.prev.next = node.next;
                node.next.prev = node.prev;
                node.next = null;
                addNodeToTail(node);
            }
        }
    }

    作者回复: 实现的很仔细👍

    2019-04-01
  • 失火的夏天

    因为篇幅不够,分段截出来了,这里先声明一个内部类,表示为队列(链表)的节点,接下来的Node节点是这个内部类
    private class Node{
            private Node prev;
            private Node next;
            private int key;
            private int value;

            Node(int key,int value){
                this.key = key;
                this.value = value;
            }
        }
    2019-04-01
收起评论
6
返回
顶部