正文
LRU Cache & Bloom Filter
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
Cache 缓存
1. 记忆
2. 空间有限
3. 钱包 - 储物柜
4. 类似背代码模板,O(n) 变 O(1)
LRU Cache
缓存替换算法
1. Least Recently Used(最近最少使⽤的淘汰掉)
2. Hash Table + Double LinkedList(哈希表 + 双向链表)
3. O(1) 查询 (cache只要查询第一个)
4. O(1) 修改、更新(同3;要是处理最中间的话就是O(n)了)
双向链表实现:
LFU Cache
也记录元素出现的频次,即使最近刚出现的,也未必就会挪到最前面。
缓存内始终按频次排序,如果超了缓存空间限制,还是新进的元素把原先频次最低的顶走。
1. LFU - least frequently used(最近最不常用⻚⾯置换算法,频次越高的放越前面)
2. LRU - least recently usd(最近最少使⽤页⾯置换算法)
Leetcode 146. LRU缓存机制 https://leetcode-cn.com/problems/lru-cache/
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作?
解:
考虑用 ordered dict 实现
1 import collections
2 class LRUCache:
3 def __init__(self, capacity: int):
4 self.dic = collections.OrderedDict()
5 self.remain = capacity
6
7 def get(self, key: int) -> int:
8 if key not in self.dic:
9 return -1
10 v = self.dic.pop(key)
11 self.dic[key] = v # 如果在key在dict中,就pop出来后再set成最新的key
12 return v
13
14 def put(self, key: int, value: int) -> None:
15 if key in self.dic:
16 self.dic.pop(key)
17 else:
18 if self.remain > 0:
19 self.remain -= 1
20 else: # 如果已经满了,就删除第一个key-value对(即最早put的键值对。令last=False即可)
21 self.dic.popitem(last=False)
22
23 self.dic[key] = value # put进去作为最新的键值对
24
25
26 # Your LRUCache object will be instantiated and called as such:
27 # obj = LRUCache(capacity)
28 # param_1 = obj.get(key)
29 # obj.put(key,value)
布隆过滤器 Bloom Filter
过滤器的作用:判断元素在还是不在。(如图查询 w 在不在集合中)
布隆过滤器:⼀个很长的二进制向量和一系列随机映射函数。
布隆过滤器可以用于检索一个元素是否在⼀个集合中(如果检测出元素不在集合中,那一定不在;如果检测出元素在集合中,有一定可能判断错误)。
它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。布隆过滤器后面一定要跟一个完备的搜索系统。
判断 C 不存在,一定正确;判断 B 存在,判断错了
案例
1. ⽐特币网络
2. 分布式系统(Map-Reduce)
LRU Cache & Bloom Filter的更多相关文章- 布隆过滤器(Bloom Filter)详解——基于多hash的概率查找思想
转自:http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html 布隆过滤器[1](Bloom Filter)是由布隆(Burton ...
- Bloom Filter 原理与应用
介绍 Bloom Filter是一种简单的节省空间的随机化的数据结构,支持用户查询的集合.一般我们使用STL的std::set, stdext::hash_set,std::set是用红黑树实现的,s ...
- 海量数据处理算法—Bloom Filter
海量数据处理算法—Bloom Filter 1. Bloom-Filter算法简介 Bloom-Filter,即布隆过滤器,1970年由Bloom中提出.它可以用于检索一个元素是否在一个集合中. Bl ...
- [转载] 布隆过滤器(Bloom Filter)详解
转载自http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html 布隆过滤器[1](Bloom Filter)是由布隆(Burton ...
- 布隆过滤器(Bloom Filter)详解
直观的说,bloom算法类似一个hash set,用来判断某个元素(key)是否在某个集合中.和一般的hash set不同的是,这个算法无需存储key的值,对于每个key,只需要k个比特位,每个存储一 ...
- Java Bloom filter几种实现比较
英文原始出处: Bloom filter for Scala, the fastest for JVM 本文介绍的是用Scala实现的Bloom filter. 源代码在github上.依照性能测试结 ...
- 大数据处理算法--Bloom Filter布隆过滤
1. Bloom-Filter算法简介 Bloom-Filter,即布隆过滤器,1970年由Bloom中提出.它可以用于检索一个元素是否在一个集合中. Bloom Filter(BF)是一种空间效率很 ...
- 【转】海量数据处理算法-Bloom Filter
1. Bloom-Filter算法简介 Bloom Filter(BF)是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合.它是一个判断元素是否存在于 ...
- 浅谈布隆过滤器Bloom Filter
先从一道面试题开始: 给A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL. 这个问题的本质在于判断一个元素是否在一个集合中.哈希表以O(1) ...
随机推荐- iconfont 图标字体
iconfont 技术的主要是将图标转化为字体来减少应用体积.如需在项目中使用iconfont技术,图标矢量图一开始都应合并转化为字体库. 优点: 减小体积,字体文件比图片要小 图标保真缩放,解决 ...
- RGB同步信号 DCLK/HS/VS/DE信号介绍
来源: http://www.cnblogs.com/general001/articles/3721683.html 只要是数字信号处理电路,就必须有时钟信号.在液晶面板中,像素时钟是一个非常重要 ...
- C++调用java
摘要: 1 java类生成c头文件和库文件 2 对于c/c++程序,启动时先启动jvm,然后获得对应的java类的对象和方法.然后正常使用. 最近正在做一个C/C++调用java的程序,这里说的调用j ...
- POJ3254(入门状态压缩dp)
Corn Fields Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 13203 Accepted: 6921 Desc ...
- cookie/session(过时的写法)
cookie存在客户端的浏览器中,不太安全,容易被窃取,,session被存在服务器中(类似于字典中的value,),服务器会给浏览器返回这个value的key值,下次进来直接根据key取value. ...
- sqlalchemy通过ssh连接远程mysql服务器
首先需要一个模块sshtunnel,如果没有直接pip install sshtunnel from sshtunnel import SSHTunnelForwarder from sqlalche ...
- eclipse版本对应名称以及下载地址
Eclipse 1.0 2001年11月7日(Win32/Linux32 Motif) Eclipse 2.0 2002年6月27日(Linux32 Motif ...
- haoop笔记
: //:什么是hadoop? hadoop是解决大数据问题的一整套技术方案 :hadoop的组成? 核心框架 分布式文件系统 分布式计算框架 分布式资源分配框架 hadoop对象存储 机器计算 :h ...
- struts2.0自定义类型转换
在Struts2.0框架中内置了类型转换器,可以很方便的实现在八大数据类型.Date类型之间的自动转换:此外也可以根据自己的需求自定义数据转换类.如下: 首先看一下项目工程中的目录 1.在新建的web ...
- result_charts
<%@ page language="java" contentType="text/html; charset=UTF-8" pageEncoding= ...
转自:http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html 布隆过滤器[1](Bloom Filter)是由布隆(Burton ...
介绍 Bloom Filter是一种简单的节省空间的随机化的数据结构,支持用户查询的集合.一般我们使用STL的std::set, stdext::hash_set,std::set是用红黑树实现的,s ...
海量数据处理算法—Bloom Filter 1. Bloom-Filter算法简介 Bloom-Filter,即布隆过滤器,1970年由Bloom中提出.它可以用于检索一个元素是否在一个集合中. Bl ...
转载自http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html 布隆过滤器[1](Bloom Filter)是由布隆(Burton ...
直观的说,bloom算法类似一个hash set,用来判断某个元素(key)是否在某个集合中.和一般的hash set不同的是,这个算法无需存储key的值,对于每个key,只需要k个比特位,每个存储一 ...
英文原始出处: Bloom filter for Scala, the fastest for JVM 本文介绍的是用Scala实现的Bloom filter. 源代码在github上.依照性能测试结 ...
1. Bloom-Filter算法简介 Bloom-Filter,即布隆过滤器,1970年由Bloom中提出.它可以用于检索一个元素是否在一个集合中. Bloom Filter(BF)是一种空间效率很 ...
1. Bloom-Filter算法简介 Bloom Filter(BF)是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合.它是一个判断元素是否存在于 ...
先从一道面试题开始: 给A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL. 这个问题的本质在于判断一个元素是否在一个集合中.哈希表以O(1) ...
- iconfont 图标字体
iconfont 技术的主要是将图标转化为字体来减少应用体积.如需在项目中使用iconfont技术,图标矢量图一开始都应合并转化为字体库. 优点: 减小体积,字体文件比图片要小 图标保真缩放,解决 ...
- RGB同步信号 DCLK/HS/VS/DE信号介绍
来源: http://www.cnblogs.com/general001/articles/3721683.html 只要是数字信号处理电路,就必须有时钟信号.在液晶面板中,像素时钟是一个非常重要 ...
- C++调用java
摘要: 1 java类生成c头文件和库文件 2 对于c/c++程序,启动时先启动jvm,然后获得对应的java类的对象和方法.然后正常使用. 最近正在做一个C/C++调用java的程序,这里说的调用j ...
- POJ3254(入门状态压缩dp)
Corn Fields Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 13203 Accepted: 6921 Desc ...
- cookie/session(过时的写法)
cookie存在客户端的浏览器中,不太安全,容易被窃取,,session被存在服务器中(类似于字典中的value,),服务器会给浏览器返回这个value的key值,下次进来直接根据key取value. ...
- sqlalchemy通过ssh连接远程mysql服务器
首先需要一个模块sshtunnel,如果没有直接pip install sshtunnel from sshtunnel import SSHTunnelForwarder from sqlalche ...
- eclipse版本对应名称以及下载地址
Eclipse 1.0 2001年11月7日(Win32/Linux32 Motif) Eclipse 2.0 2002年6月27日(Linux32 Motif ...
- haoop笔记
: //:什么是hadoop? hadoop是解决大数据问题的一整套技术方案 :hadoop的组成? 核心框架 分布式文件系统 分布式计算框架 分布式资源分配框架 hadoop对象存储 机器计算 :h ...
- struts2.0自定义类型转换
在Struts2.0框架中内置了类型转换器,可以很方便的实现在八大数据类型.Date类型之间的自动转换:此外也可以根据自己的需求自定义数据转换类.如下: 首先看一下项目工程中的目录 1.在新建的web ...
- result_charts
<%@ page language="java" contentType="text/html; charset=UTF-8" pageEncoding= ...