时钟更换政策

Question

我的时钟缓存坏了。我在做什么：

如果输入self.items\到\索引：将位设置为1，返回自动缓冲器. 你知道吗

如果没有：

对输入调用函数以获取newval。你知道吗

调用self.\u increment（）直到在自动缓冲器位设置为0。你知道吗

你知道吗自动缓冲器[self.\u p]现在等于[newval，1]

删除\u p等于该条目的词典条目。你知道吗

那就做吧self.items\到\索引[k] =\u p

增量p

我上面描述的代码是：[不工作]

def __getitem__(self, k):
    """
    Returns func(k) using the buffer to cache limited results.

    :param k: Value to be evaluated

    >>> clock = ClockMap(4, lambda x: x ** 2)
    >>> clock[4]
    16
    >>> clock[3]
    9
    >>> clock._p
    2
    """
    #when clock[index] is queried, this _getitem__ function is called
    if k in self.items_to_index:
        #hit
        index = self.items_to_index[k]
        entry = self.buffers[index]
        entry[1] = 1
        return entry[0]
    else:
        val = self.fn(k)
        while self.buffers[self._p][1] == 1:
            self.buffers[self._p][1] = 0
            self._increment()
        self.buffers[self._p] = [val, 1]

        for inputx, bufflocation in self.items_to_index.iteritems():
            if bufflocation == self._p:
                self.items_to_index.pop(inputx)
                self.items_to_index[k] = bufflocation
                break

        self._increment()
        return val

全班附文供参考：

class ClockMap:

def __init__(self, cacheSize, func):
    """
    Do not change existing variables.
    [Optional] You are free to add additional items and methods.
    """
    self.cacheSize = cacheSize #number of buffers
    self.fn = func #function whose results that you will be caching
    self._p = 0 # pointer
    self._increments = 0
    self._miss_count = 0
    self.buffers = [[None, 0] for x in range(cacheSize)] #actual output vals of the func passed in
    #hit: retrieve the value from the cache. Miss: reevaluate func with input, write to cache
    self.items_to_index = {} # dict,  input to buffer location, self.items_to_index[x] = buffer_index

def _increment(self):
    """
    Do not change this method.
    Updates the clock pointer. The modulo maintains the clock nature.
    """
    self._increments += 1
    self._p = (self._p + 1) % self.cacheSize

我如何测试这个和我的测试结果：

def test3ClockMap(ClockMap):
check_dir()
clock = ClockMap(4, lambda x: x ** 2)
requests = [1, 2, 3, 4, 1, 6, 1, 4, 7, 4, 7, 5, 4, 6]
with open(your_output + "task3ClockMap.txt", "wb") as f:
    writer = csv.writer(f)
    writer.writerow(["Request", "Result", "Pointer", "Increments"])
    for r in requests:
        writer.writerow([r, clock[r], clock._p, clock._increments])
diff_against_reference("task3ClockMap.txt", 3)

差异文件：

6,15c6,15
< 1,1,1,9
< 6,36,2,10
< 1,1,3,11
< 4,16,0,12
< 7,49,1,17
< 4,16,2,18
< 7,49,3,19
< 5,25,0,20
< 4,16,1,25
< 6,36,2,26
---
> 1,1,0,4
> 6,36,1,9
> 1,1,2,10
> 4,16,2,10
> 7,49,3,11
> 4,16,3,11
> 7,49,3,11
> 5,25,0,16
> 4,16,1,17
> 6,36,2,18

Answer 1

我相信是因为那条线

for inputx, bufflocation in self.items_to_index.iteritems():

你知道吗self.items\到\索引初始化为空，并且没有在上述循环外更新，因此循环内的任何代码都不会运行。你知道吗

Answer 2

值永远不会添加到self.items_to_index字典，因此值永远不会从缓存返回。您可以通过更改ClockMap.__getitem__()来解决当前指针不在索引中的情况：

        for inputx, bufflocation in self.items_to_index.iteritems():
            if bufflocation == self._p:
                self.items_to_index.pop(inputx)
                self.items_to_index[k] = bufflocation
                break
        else:
            self.items_to_index[k] = self._p

注意添加到for循环的else块。这将处理当前指针不在索引中的情况，如果在索引中则添加它。你知道吗

---

您的缓存类似于LRU缓存。如果您使用的是python3，那么您可能需要查看^{}装饰器，例如

from functools import lru_cache

@lru_cache()
def f(x):
    return x**3

>>> f.cache_info()
CacheInfo(hits=0, misses=0, maxsize=128, currsize=0)
>>> f(2)
8
>>> f.cache_info()
CacheInfo(hits=0, misses=1, maxsize=128, currsize=1)
>>> f(2)
8
>>> f.cache_info()
CacheInfo(hits=1, misses=1, maxsize=128, currsize=1)