LRU算法python代码
时间: 2023-03-30 13:02:21 浏览: 88
以下是 LRU 算法的 Python 代码:
```python
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.order = []
def get(self, key: int) -> int:
if key in self.cache:
self.order.remove(key)
self.order.append(key)
return self.cache[key]
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.order.remove(key)
elif len(self.cache) == self.capacity:
del self.cache[self.order.pop()]
self.cache[key] = value
self.order.append(key)
```
希望对你有帮助!
相关问题
pythonLRU算法
Python LRU算法是一种缓存淘汰策略,它基于最近最少使用原则,即当缓存满时,会优先淘汰最近最少使用的缓存。
下面是一个简单的Python LRU算法实现:
```python
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
```
在上述实现中,我们使用了Python中的OrderedDict类来实现LRU算法。该类内部维护了一个有序字典,其中最近访问的元素会被移动到字典的末尾,而最久未访问的元素会被移动到字典的开头。当缓存已满时,我们可以通过popitem()方法将字典开头的元素删除,从而实现缓存淘汰的目的。在get()和put()方法中,我们都会将访问的元素移动到字典的末尾,以保证最近访问的元素永远在字典的末尾。
页面置换算法python代码实现
以下是常见的两种页面置换算法的 Python 代码实现:
1. 先进先出(FIFO)算法
```python
def FIFO(pages, capacity):
page_faults = 0
frames = []
for page in pages:
if page not in frames:
if len(frames) < capacity:
frames.append(page)
else:
frames.pop(0)
frames.append(page)
page_faults += 1
return page_faults
```
2. 最近最少使用(LRU)算法
```python
def LRU(pages, capacity):
page_faults = 0
frames = []
used = []
for page in pages:
if page not in frames:
if len(frames) < capacity:
frames.append(page)
else:
index = used.index(frames[0])
frames.pop(index)
used.pop(index)
frames.append(page)
page_faults += 1
else:
index = frames.index(page)
used.pop(index)
used.append(page)
return page_faults
```
以上代码实现仅供参考,具体实现还需根据实际情况进行调整和优化。