如何设计最近最新使用的缓存？
假设您访问了一些项目.您需要设计一个数据结构来保存这些项目.每个项目都与最近访问的时间相关联.
每次访问项目时,请在数据结构中进行检查.如果该项目已在缓存中,请更新其访问时间.否则,将其插入缓存中.高速缓存大小是固定的,如果已满,则删除最旧的项目.
我的解决方案
使用地图<item,visitTime>
初始化:使用f(visitTime)按降序对地图进行排序.O(nlg n)
如果访问了某个项目,请使用O(lg n)在地图中搜索该项目.
如果它已在地图中,则更新时间O(1).对地图O(lg n)进行排序.
如果没有,请将其插入地图然后排序.O(lg n)
如果地图大小>固定大小,则删除最后一个元素O(1).
另一种方案:
使用哈希表<item,visitTime>
将它排序为O(n lgn).
如果访问了某个项目,请使用O(1)在该项目中进行搜索.
如果它已在表中,则更新时间O(1).对表O(n lg n)进行排序.
如果没有,请将其插入表中然后排序.O(n lg n)
如果表大小>固定大小,则删除最后一个元素O(1).
有更好的解决方案吗？上) ？
有人知道基于Redis LRU的驱逐/删除的内部.
Redis如何确保首先删除旧的(较少使用的)密钥(如果我们没有易失性密钥且我们没有设置TTL到期)？
我确信Redis有一个配置参数"maxmemory-samples"来管理它用于删除键的样本大小 - 所以如果你设置一个样本大小为10,那么它会对10个密钥进行采样并从中删除最旧的密钥.
我不知道的是它是否完全随机地对这些密钥进行采样,或者它是否有某种机制允许它自动从相当于"较旧/较少使用的代"中采样？
假设redis实例中的所有键都有一个到期集,volatile-lru和allkeys-lru是相似的.但是当一个键被移除时,2之间是否存在显着的性能差异？
奖金问题:
在使用allkeys-lru策略配置的2个不同实例之间,具有相同的内容和相同的配置,除了:
除了由于过期位而在实例A中的内存开销之外,当通过allkeys-lru算法删除密钥时,2之间是否存在性能差异？
在这两种情况下,我都在谈论linux 64位上的redis 2.4.x的实例,当达到maxmemory时,maxmemory = 3Gb和4-5000个键(大多数键都是哈希值).
谢谢
我在Android中实现了一个存储对象的标准LRUCache.每个键都是与存储的Object关联的唯一ObjectId.我的问题是从缓存中检索Object的唯一方法是ObjectId(没有迭代器).实现getAll()方法的最佳方法是什么？另一种选择是将所有ObjectIds存储在某个列表的列表中,因此我可以迭代列表并获取所有对象 - 但是保存所有ObjectIds的最佳方法是什么？
谢谢!
我说的是用 C 实现的 LRU 内存页面替换算法，而不是用 Java 或 C++ 实现。
根据操作系统课程笔记：
好的，那么我们如何实际实现 LRU 呢？想法1）：用时间戳标记我们接触过的一切。每当我们需要驱逐页面时，我们都会选择最旧的页面（=最近最少使用）。事实证明，这个简单的想法并不那么好。为什么？因为对于每个内存加载，我们都必须读取时钟的内容并执行内存存储！因此很明显，保留时间戳将使计算机速度至少慢一倍。我
内存加载和存储操作应该非常快。真的有必要摆脱这些微小的操作吗？
在内存替换的情况下，从磁盘加载页面的开销应该比内存操作大很多。为什么要真正关心内存存储和加载？
如果注释所说的不正确，那么使用时间戳实现 LRU 的真正问题是什么？
编辑：
当我深入挖掘时，我能想到的原因如下。这些内存存储和加载操作在页面命中时发生。在这种情况下，我们没有从磁盘加载页面，因此比较无效。
由于预计命中率会非常高，因此更新与LRU相关的数据结构应该非常频繁。这就是为什么我们关心更新过程中重复的操作，例如内存加载和存储。
但我仍然无法相信内存加载和存储的开销有多大。周围应该有一些测量值。有人可以指点我吗？谢谢！
我在我的 redis 服务器中使用了 5 个数据库。我想使用 LRU 机制驱逐属于特定数据库的键。是否可以 ？
我读到：how-to-make-redis-choose-lru-eviction-policy-for-only-some-of-the-keys。
但是我所有的数据库都在使用时间来保存它们的条目。所以不能使用volatile-lru策略。
我尝试了volatile-ttl策略，但其他数据库的密钥的 ttl 较少。所以他们会被驱逐，这是我不想要的。
我有一个带有 method/property 的对象multiplier。这个方法在我的程序中被调用了很多次，所以我决定使用lru_cache()它来提高执行速度。正如预期的那样，它要快得多：
以下代码显示了问题：
from functools import lru_cache
class MyClass(object):
def __init__(self):
self.current_contract = 201706
self.futures = {201706: {'multiplier': 1000},
201712: {'multiplier': 25}}
@property
@lru_cache()
def multiplier(self):
return self.futures[self.current_contract]['multiplier']
CF = MyClass()
assert CF.multiplier == 1000
CF.current_contract = 201712
assert CF.multiplier == 25
第二个assert失败，因为缓存值为 1000，因为lru_cache()不知道底层属性current_contract已更改。
更新 self.current_contract 时有没有办法清除缓存？
谢谢！
我试图lru_cache在Python3中使用,以加快我们的Salesforce数据库中的常见查询.下面是相关的代码,它应该a)将不可散列的参数转换为可散列的参数,以及b)为这些对象启用lru缓存.
当我尝试这个代码时,缓存适用于调用没有参数的函数,但它似乎没有用参数缓存函数调用.另外,我不知道如何为装饰函数订购装饰器.
注意,我在这里使用类和静态方法的类,所以我可以覆盖不同子类的get和get_all方法Resource.
请解释我做错了什么或者做得更好.
from functools import lru_cache
from functools import wraps
class Resource(object):
def hash_dict(func):
"""Transform mutable dictionnary
Into immutable
Useful to be compatible with cache
"""
class HDict(dict):
def __hash__(self):
return hash(frozenset(self.items()))
@wraps(func)
def wrapped(*args, **kwargs):
args = tuple([HDict(arg) if isinstance(arg, dict) else arg for arg in args])
kwargs = {}
for k, v in kwargs.items():
if isinstance(v, dict):
kwargs[k] = HDict(v)
elif isinstance(v, list):
kwargs[k] = tuple(v)
else:
kwargs[k] …给出函数定义的文档lru_cache:
Run Code Online (Sandbox Code Playgroud)@functools.lru_cache(maxsize=128, typed=False)
这对我说maxsize是可选的.
但是,它不喜欢没有参数调用:
Python 3.6.3 (default, Oct 24 2017, 14:48:20)
[GCC 7.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import functools
>>> @functools.lru_cache
... def f(): ...
...
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/lib/python3.6/functools.py", line 477, in lru_cache
raise TypeError('Expected maxsize to be an integer or None')
TypeError: Expected maxsize to be an integer or None
>>>
使用参数调用很好:
>>> @functools.lru_cache(8)
... …作为并行化某些现有代码（使用多处理）的一部分，我遇到了需要对类似于下面的类的内容进行腌制的情况。
从...开始：
import pickle
from functools import lru_cache
class Test:
def __init__(self):
self.func = lru_cache(maxsize=None)(self._inner_func)
def _inner_func(self, x):
# In reality this will be slow-running
return x
呼叫
t = Test()
pickle.dumps(t)
回报
_pickle.PicklingError: Can't pickle <functools._lru_cache_wrapper object at 0x00000190454A7AC8>: it's not the same object as __main__.Test._inner_func
我不太明白。顺便说一句，我还尝试了一种变体，其中 _inner_func 的名称也为 func，但这并没有改变任何事情。