Belady

#!/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)