在10分钟内建立Go快取
缓存是计算机科学的最大创新之一。 它显着减少了CPU的工作量,并在速度方面提供了可观的性能提升。 ????
它通过保存以后可能需要的计算结果来工作。 例如:假设您有一个服务,给定一个字符串,该服务生成一个哈希。 缓存可以通过检查接收到的字符串的哈希值是否已经生成来节省时间和资源。 如果它仍然存在并且仍在高速缓存中,则将其返回,而无需再次运行哈希算法。
今天,我们将构建一个LRU ( 最近使用过的 )缓存,该缓存存储固定数量的strings
并在缓存已满时弹出最近使用的项目。
这将不是您要在生产中运行的任何东西。 但是它将清楚地说明使这种类型的缓存起作用的data structures
和algorithms
。
获取并运行最终结果:
git clone https://github.com/Lebonesco/go_lru_cache.git
go run main.go
让我们跳入一些代码!
我们将从定义data structures
。 这些将包括Node
, Queue
, Hash
和Cache
。 我们的Queue
将是从Hash
映射到的Node
指针的双向链接列表。 这将允许O(1) 插入和删除值。 ????
注意:我们是 只是现在缓存strings
,但是任何data type
都可以替换它。
接下来,我们将为Cache
和Queue
设置构造函数。 虽然, Hash
开始为空,但需要初始化,否则稍后将导致“空指针错误” 。 另外,我们为Head和Tail创建两个空Nodes
。 当我们转到Add()
和Remove()
方法时,这将更有意义。
进入缓存的主代码。
缓存具有使其工作所需的三种方法 : Check()
(从用户处接收字符串并返回结果), Add()
(向缓存中添加字符串), Remove()
(从缓存中弹出字符串Remove()
缓存)。
在Check()
内部,如果string
已经存在于缓存中,我们首先将其删除,然后再次添加回该string
,以使该string
移至Queue
。
Add()
和Remove()
都涉及类似的操作,这些操作会重新分配Queue
中的Left
和Right
Node
指针。
太好了,我们现在有一个有效的缓存! ????????????
最后一步是添加main()
和一些显示方法来演示我们的结果。
要查看运行中的代码,请运行:
go run main.go
START CACHE
add: cat
1 - [{cat}]
add: blue
2 - [{blue} <--> {cat}]
add: dog
3 - [{dog} <--> {blue} <--> {cat}]
add: tree
4 - [{tree} <--> {dog} <--> {blue} <--> {cat}]
add: dragon
5 - [{dragon} <--> {tree} <--> {dog} <--> {blue} <--> {cat}]
add: potato
remove: cat
5 - [{potato} <--> {dragon} <--> {tree} <--> {dog} <--> {blue}]
add: house
remove: blue
5 - [{house} <--> {potato} <--> {dragon} <--> {tree} <--> {dog}]
remove: tree
add: tree
5 - [{tree} <--> {house} <--> {potato} <--> {dragon} <--> {dog}]
add: cat
remove: dog
5 - [{cat} <--> {tree} <--> {house} <--> {potato} <--> {dragon}]
感谢您抽出宝贵的时间阅读本文。
如果您觉得它有用或有趣,请告诉我me。
From: https://hackernoon.com/build-a-go-cache-in-10-minutes-c908a8255568