Python novice here. I am working on an assignment that has me a bit stumped.
The goal is set up a simple FIFO system, without using any imported libraries.
My attempt so far is incorrect and I am looking for some suggestions on how to fix it.
Attempt:
requests = [4, 32, 5, 8, 7, 4, 8] # Will be any random integer inputted by user, provided this list as an example
cache = []
def fifo():
for page in requests:
if page not in cache:
print(page, "miss")
cache.append(page) # This isn't right but not sure where to add?
if page in cache:
print(page, "hit")
cache.remove(page) # If a page is already in the cache, it doesn't need to be added again - not sure if this is correct either?
if len(cache) > 4: # max size of cache = 4
cache.pop(0) # Removes first indexed item until cache = 4 elements
print(cache)
return
# Each page should be printed as a hit/miss if included/not included in the cache
# Ignoring hits/miss being printed, the required output = print(cache) = [32, 5, 7, 8]
# i.e. the most recent 4 requests, previously requested pages (e.g. 4) shouldn't be included
How should I go about correcting the above? Open to alternative suggestions as I appreciate the above is likely far away from the optimal solution.
Thanks
Given the text in the comments at the bottom of your code, it would appear that this is closer to what is required:
def f(requests, cache):
for page in requests:
if page in cache:
cache.remove(page)
print(page, "hit")
else:
print(page, "miss")
if len(cache) > 3:
cache.pop(0)
cache.append(page)
requests = [4, 32, 5, 8, 7, 4, 8]
cache = []
f(requests, cache)
print(cache)
If would make a bit more sense for the function to operate on individual 'pages' though (also showing an approach using a global cache):
cache = []
def f(page):
global cache
if page in cache:
print(page, "hit")
cache.remove(page)
else:
print(page, "miss")
if len(cache) > 3:
cache.pop(0)
cache.append(page)
for page in [4, 32, 5, 8, 7, 4, 8]:
f(page)
print(cache)
However, note that both these solutions show a different outcome than the question: [5, 7, 4, 8]
instead of [32, 5, 7, 8]
.
The question seems to get the answer wrong itself, unless the actual maximum cache size isn't 4, but 5. Consider this: how can the cache still contain 4
, when it most recently got 32
, 5
, 8
, and 7
and its size would be 4? So, when 4
comes around again, it has no memory of it and should update to [5, 7, 4, 8]
. Where are you getting this assignment?
Also note that I wouldn't want to recommend using a global variable as in the second solution - however, all this seems to be a step up on the way to writing a Cache
class of sorts, which would make the cache a variable internal to the class or object, instead of a global. Such a class could look like this:
class Cache:
def __init__(self, size=4):
self._size = size
self._cache = []
def hit(self, page):
if (result := (page in self._cache)):
self._cache.remove(page)
if self._cache.__len__() == self._size:
self._cache.pop(0)
self._cache.append(page)
return result
def __str__(self):
return str(self._cache)
c = Cache(4)
for p in [4, 32, 5, 8, 7, 4, 8]:
if c.hit(p):
print('hit', p)
else:
print('miss', p)
print(c)