Swift -- LRU算法实现和简单的缓存示例
2017-12-15 本文已影响111人
奇董
双链表
image.png
来看双向链表的实现
首先定义Node
/// 双向列表的节点
class linkedNode<T> {
var value: T
var previous: linkedNode?
var next: linkedNode?
init(_ value: T) {
self.value = value
}
}
List
class linkedList<T> {
typealias Node = linkedNode<T>
private var head: Node?
private var tail: Node?
/// 判断是否为空
var isEmpty: Bool {
return head == nil
}
/// 获取头节点
var first: Node?{
return head
}
///获取尾节点
var last: Node? {
return tail
}
///获取 链表数量
var count: Int = 0
// 下标语法糖
subscript(index: Int) -> T? {
var i = index
var next = head
while i > 0 {
i -= 1
next = next?.next
}
return next?.value
}
}
尾插法
1 tail.next = new Node
2 new Node.previous = tail
这里主要注意 头尾节点的问题
/// 尾插
func append(_ value: T) {
let newNode = Node(value)
if let lastNode = tail {
lastNode.next = newNode
newNode.previous = lastNode
tail = newNode
}else {
head = newNode
tail = newNode
}
//修改数量
count += 1
}
中插
image.png
///插入 node
func insert(value: T, atIndex index: Int) {
let (pre,next) = nodesBeforeAndAfter(index: index)
let newNode = Node(value)
pre?.next = newNode
next?.previous = newNode
newNode.previous = pre
newNode.next = next
if pre == nil {
head = newNode
}
if count == index - 1 {
tail = newNode
}
count += 1
}
///获取某节点的头结点和尾节点
private func nodesBeforeAndAfter(index: Int) -> (Node?,Node?) {
var next = head
var previous: Node?
var i = index
while i > 0 && next?.next != nil{
i -= 1
previous = next
next = next?.next
}
return (previous,next)
}
删除节点
///删除最后一个
func removeLast() {
removeNode(node: last!)
}
/// 移除某一个node
func removeNode(node: Node) {
let pre = node.previous
let next = node.next
pre?.next = next
next?.previous = pre
if pre == nil {
head = node.next
}
if next == nil {
tail = node.previous
}
count -= 1
}
移动到头结点
/// node 移动到头节点
func moveToHead(node: Node) {
let pre = node.previous
let next = node.next
pre?.next = next
next?.previous = pre
node.next = head
head?.previous = node
head = node
if pre == nil {
return
}
if next == nil {
tail = pre
}
}
LRU
准备工作差不多了
我来看下LRU的定义
image.png
-
新数据插入到链表头部；
-
每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
-
当链表满的时候，将链表尾部的数据丢弃。
【命中率】
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。
【复杂度】
实现简单。
【代价】
命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。
LRU 实践
我们客户端关于LRU算法 最先想到，肯定是图片缓存系统
为了方便
我们存的数据 为["1": "我是一张图片"] 这种【String: Stirng】
首先我们定义一个简单的缓存类
/// LRU 实现
class CacheLRU<T> {
var limit: Int
var cache: linkedList<T>
init(cacheNumber: Int) {
self.limit = cacheNumber
self.cache = linkedList<T>()
}
//增
func add(some: T) {
if cache.count == limit {
cache.removeLast()
}
cache.append(some)
}
//删
func clearCache() {
cache.removeAll()
}
//移
func move(value: linkedNode<T>) {
cache.moveToHead(node: value)
}
}
// 1 先从缓存系统查看是否有缓存
extension linkedList where T == Dictionary<String, String> {
func contains(name: String) -> Node? {
var next = head
var index = 0
while index < count {
if next?.value[name] != nil {
return next
}
index += 1
next = next?.next
}
return nil
}
}
extension CacheLRU where T == Dictionary<String, String> {
func fetchImage(name: String) {
let node = cache.contains(name: name)
if let dic = node?.value {
// 1.内存存在 直接取内存中的数据
print(dic[name] ?? "😁")
// 2.lru 访问的数据成为头结点
move(value: node!)
}else {
//网络获取 并且 add
}
}
}
我们来看结果
1 创建缓存类 存贮图片
这里设置存贮上线为2张图片（实际肯定是内存为标准）
let cacheMnager = CacheLRU<Dictionary<String,String>>.init(cacheNumber: 2)
let image1 = ["1": "我是一张图片"]
let image2 = ["2": "我是一张图片"]
let image3 = ["3": "我是一张图片"]
cacheMnager.add(some: image1)
cacheMnager.add(some: image2)
cacheMnager.add(some: image3)
因为上线是2 导致 第二张图片被清除
image.png
2 访问已有图片
cacheMnager.fetchImage(name: "3")
访问已有图片的 已有图片的node 会移到头部
image.png
LRU-K
image.png
LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。
实现上： LRU-K 的其实就是 在LRU的基础上多维护一条历史链表。链表里面的数据多一个访问次数属性。当访问次数打到K次。就存到缓存队列里 这里和LRU一样
【命中率】
LRU-K降低了“缓存污染”带来的问题，命中率比LRU要高。
【复杂度】
LRU-K队列是一个优先级队列，算法复杂度和代价比较高。
【代价】
由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象，因此内存消耗会比LRU要多；当数据量很大的时候，内存消耗会比较可观。
LRU-K需要基于时间进行排序（可以需要淘汰时再排序，也可以即时排序），CPU消耗比LRU要高。
我们看代码实现
class CacheLRU_K<T,E> {
let cache: CacheLRU<E>
let cacheHistory: CacheLRU<T>
let limit: Int
let K: Int
init(limit: Int,K: Int) {
self.K = K
self.limit = limit
self.cache = CacheLRU.init(cacheNumber: limit)
self.cacheHistory = CacheLRU.init(cacheNumber: limit)
}
}
extension linkedList where T == Dictionary<String,Any> {
func contains(name: String) -> T? {
var next = head
var index = 0
while index < count {
if next?.value[name] != nil {
return next?.value
}
index += 1
next = next?.next
}
return nil
}
}
extension CacheLRU_K where T == Dictionary<String,Any>, E == [String: String] {
func add(some: T) {
var data: [String: Any] = some
let name = some.first!.key
let temp = cacheHistory.cache.contains(name: name)
if let temp = temp {
data = temp
}
if data["number"] == nil {
data["number"] = 0
}
var number = data["number"] as! Int
data["number"] = number + 1
number += 1
if number == K {
data["number"] = nil
let temp = data as! [String: String]
cache.add(some: temp)
//cacheHistory remove
//下班了 以后补上0.0
}else {
if cacheHistory.cache.count == limit {
cacheHistory.cache.removeLast()
}
cacheHistory.add(some: data)
}
}
func fetchImage(name: String) {
let node = cache.cache.contains(name: name)
if let dic = node?.value {
// 1.内存存在 直接取内存中的数据
print(dic[name] ?? "😁")
// 2.lru 访问的数据成为头结点
cache.move(value: node!)
}else {
//这里和lru 不同
//网络请求
// lru_k add
}
}
}
这里 基本和LRU 一样就是维护一条历史队列
这里初始化 K 为2 意思
只有连续add 2次才能真正的假如到缓存链表中
let manager = CacheLRU_K<[String:Any],[String:String]>.init(limit: 2, K: 2)
let image11 = ["1": "我是一张图片"]
manager.add(some: image11)
缓存和 历史缓存的结果
image.png
继续add
manager.add(some: image11)
这时候内存中就存在了我要要缓存的数据
image.png
历史缓存中就应该删除这条记录
下班了 溜了。。实现过程可能没讲清楚。但是代码都注释的听明白的。有时间补上
