LRU Cache
基本概念
- Least Recently Used(最近最少使用) 。他是一个缓存替换算法
- Cache有固定大小，当有一个新值被set的时候，会需要替换各种位置
- 一般使用双向链表来实现，O(1)查询， O(1)修改、更新
复习链表和数组
打印一个链表如何打印
while node != None:
print(node.val)
print("->")
node = node.next
print("null")
Tagged in
算法
BloomFilter布隆过滤器以及其他去重方法
哈希表解决某一个value是否存在的问题
- 哈希表一般采用链地址法实现：即出现碰撞之后，在位置上增加单链表
- 哈希表的复杂度为平均O(1)，因为假设有很大的碰撞，会导致某一个链过长，则会导致遍历时间变长
- 所以哈希表时间复杂度其实是和具体的哈希算法相关
bitmap
- 如果只是为了判断一个值是否存在，那么比方说用md5算法，然后存储的值直接用一个bool表示就可以，也就是0-1值表示是否重复
- 一个整形为32位，如果按照bitmap的方式存储整形数据，那么只需要2^32bit=2^29byte=512MB的大小
- 这样非常省内存，而且存储空间也会比较大，缺点就是md5碰撞
5TB的硬盘上放满了数据，请写一个算法将这些数据进行排重。如果这些数据是一些32bit大小的数据该如何解决？如果是64bit的呢？，需要计算，因为64bit和32bit完全不是一个量级，如果用bitmap的话
bloomfilter
- 思想为：将一个元素按照k个哈希函数对应到k个比特位上，当检查的时候，检查这k个比特位是否都为1，如果在，那么很有可能元素在集合中
- 图示 …
pelican中添加数学公式
在博客中添加数学公式，只需要添加render_math插件就可以了。在pelican_conf中添加此插件，并且在博客目录的plugins目录中添加render_math
render_math的语法为mathjax语法，
具体可以参考如下文章
直接在markdown中添用$...$ 或者 $$...$$来再当前行和另外一行来插入数学符号