python实现线下缓存最优算法

对于现代计算机为了加快数据存储速度，一般会采用多级缓存的方法，以最简单的二级缓存来说，数据会存放在两个地方，一个地方就是存在内存当中，另一个存放的地方就是存放在硬盘当中，但是这两个地方数据读取的速度是完全不同的。

而CPU从内存中读取数据的速度是要远远快与从硬盘中读取数据的速度，但问题在于缓存的价格是要远远高于硬盘的价格的，所以缓存的内容就会远远小于硬盘的容量。当CPU需要读取特定的数据的时候，CPU就会现在内存当中进行查找，如果数据已经存储在内存中，它就可以直接读取。

而当数据是没有存储在内存当中的时候，那么CPU就会把数据从硬盘当中读取出来，然后存放在缓存当中，这里的问题主要在于如果内存已经被用完了，那么CPU就必须先将内存当中存储的某些数据输出到硬盘当中去，空出空间来以便存放要从硬盘当中读取的数据。

而当CPU从内存中得到他想要获取的数据的时候，我们就可以成为cache hit，当CPU发现内存中不存在想要读取的数据的时候，我们就称为cache miss，由于内存是有限的，我们就需要设计高效的缓存调度算法以便决定当需要把数据从内存输出到硬盘时，如何选择要调出的数据以便让cache miss的次数尽可能的少。

添加图片注释，不超过 140 字（可选）

添加图片注释，不超过 140 字（可选）

例如如上的例子，如何在已经装满了4条数据的情况下，要将某一条数据进行迁出，将空出来的位置留给下数据e的话，这就是缓存调度算法所需要解决的问题。

在这里可以考虑使用最远优先原则来进行算法实现，在已知未来数据访问的情况下，要调度内存中缓存的数据的时候，可以采用最远优先原则，也就是在决定从内存中迁出那条数据的时候，我们看当前在内存中的数据，在即将读取的数据中，哪一条离当前要写入的数据最远。

添加图片注释，不超过 140 字（可选）

添加图片注释，不超过 140 字（可选）

使用python实现的最远优先原则算法如下：

cache_size = 8
C = np.zeros((cache_size))
items = 16  #16种不同的数据
item_count = 100  #需要读取100条数据
R = np.zeros((item_count))
for i in range(item_count):
    R[i] = random.randint(1, 17)
item_map = {}
cache_miss = 0
for i in range(len(R)):
    if R[i] in item_map.keys():  #将数据与它在R中位置对应起来
        l = item_map[R[i]]  
        l.append(i)
    else:
        l = []
        l.append(i)
        item_map[R[i]] = l
for i in range(len(R)): #模拟读取每一条数据
    cache_hit = False
    item_save = False
    for c in C:  #检测缓存是否存在要读取的数据
        if c == R[i]:
            cache_hit = True
            break
    if cache_hit is False:
        cache_miss += 1
        for j in range(len(C)):  #如果缓存还有可用空间，将数据放入缓存
            if C[j] == 0:
                C[j] = R[i]
                item_save = True
                item_map[R[i]].pop(0)
                break
        if item_save is False:  #缓存已满，根据最远优先原则置换
            max_distance = 0
            item_selected = 0
            for j in range(len(C)):
                l = item_map[C[j]]
                if len(l) == 0:  #缓存中的元素不会再从R中被读取,因此将其置换出去
                    item_selected = j
                    break
                distance = item_map[C[j]][0]
                if distance > max_distance:
                    max_distance = distance
                    item_selected = j
            C[j] = R[i]  #将离要读取数据最远的缓存数据进行置换
            item_map[R[i]].pop(0)
print("the count of least cache miss is : ", cache_miss)