Renzo: Created page with " #!/usr/bin/env python3 import sys class fifomem: def init(self,size): self.mem = [None for _ in range(size)] self.pf = 0 def str..."

2017-03-28T12:12:59Z

Created page with "<syntaxhighlight lang=python> #!/usr/bin/env python3 import sys class fifomem: def __init__(self,size): self.mem = [None for _ in range(size)] self.pf = 0 def __str__..."

New page

<syntaxhighlight lang=python>
#!/usr/bin/env python3
import sys

class fifomem:
def __init__(self,size):
self.mem = [None for _ in range(size)]
self.pf = 0

def __str__(self):
return "|".join(["__" if x == None else "{:2}".format(x) for x in self.mem])

def ref(self, x):
if x not in self.mem:
self.mem.pop(0)
self.mem.append(x)
self.pf += 1
return True
else:
return False

class fifomem_ref(fifomem):
def __init__(self,size):
fifomem.__init__(self,size)
self.refstring = []

def append(self,n):
self.refstring.append(n)
self.ref(n)

def anomaly(m,M,q):
def min_not_in(s):
for i in range(M+1):
if i not in s:
return i
S = fifomem_ref(m)
for k in range(M):
S.append(k)
for i in range(len(q)):
if q[i] in S.mem:
while q[i] in S.mem:
S.append(min_not_in(S.mem))
while q[0] in S.mem:
S.append(min_not_in(S.mem + [q[i]]))
for x in q[:i]:
S.append(x)
S.append(q[i])
return S.refstring

def mstring(M):
return [((M*M) - (i*(M+1)//2)) % M for i in range(2,M)]

def runref(ref, size, verbose = False):
mem = fifomem(size)
for x in ref:
pf = mem.ref(x)
if verbose:
print("{:2}->".format(x),mem," **" if pf else "")
print("PF: ",size,"->",mem.pf)
return mem.pf

if __name__ == "__main__":
if len(sys.argv) < 2:
sys.exit(1)
M = int(sys.argv[1])
if M % 2 == 0:
sys.exit(1)
if M < 5:
sys.exit(1)
ref = anomaly(M-2, M-1, mstring(M))
if len(sys.argv) < 4:
print(M,mstring(M),ref)
print()
if len(sys.argv) > 2:
count = int(sys.argv[2])
ref += list(range(M)) * count
smallpf = runref(ref, M-2, len(sys.argv) < 4)
print()
largepf = runref(ref, M-1, len(sys.argv) < 4)
print("Ratio: ", largepf/smallpf)
</syntaxhighlight>

Belady - Revision history

Renzo: Created page with " #!/usr/bin/env python3 import sys class fifomem: def __init__(self,size): self.mem = [None for _ in range(size)] self.pf = 0 def __str__..."

Renzo: Created page with " #!/usr/bin/env python3 import sys class fifomem: def init(self,size): self.mem = [None for _ in range(size)] self.pf = 0 def str..."