427 lines
13 KiB
Python
Executable file
427 lines
13 KiB
Python
Executable file
#!/usr/bin/python3
|
|
from random import random
|
|
from math import floor, sqrt, factorial,exp
|
|
from statistics import mean, variance
|
|
from matplotlib import pyplot as plt
|
|
from pylab import *
|
|
import numpy as np
|
|
|
|
|
|
def simulate_NFBP(N):
|
|
"""
|
|
Tries to simulate T_i, V_i and H_n for N items of random size.
|
|
"""
|
|
i = 0 # Nombre de boites
|
|
R = [0] # Remplissage de la i-eme boite
|
|
T = [0] # Nombre de paquets de la i-eme boite
|
|
V = [0] # Taille du premier paquet de la i-eme boite
|
|
H = [] # Rang de la boite contenant le n-ieme paquet
|
|
for n in range(N):
|
|
size = random()
|
|
if R[i] + size >= 1:
|
|
# Il y n'y a plus de la place dans la boite pour le paquet.
|
|
# On passe a la boite suivante (qu'on initialise)
|
|
i += 1
|
|
R.append(0)
|
|
T.append(0)
|
|
V.append(0)
|
|
R[i] += size
|
|
T[i] += 1
|
|
if V[i] == 0:
|
|
# C'est le premier paquet de la boite
|
|
V[i] = size
|
|
H.append(i)
|
|
|
|
return {"i": i, "R": R, "T": T, "V": V, "H": H}
|
|
|
|
|
|
# unused
|
|
def stats_NFBP(R, N):
|
|
"""
|
|
Runs R runs of NFBP (for N items) and studies distribution, variance, mean...
|
|
"""
|
|
print("Running {} NFBP simulations with {} items".format(R, N))
|
|
I = []
|
|
H = [[] for _ in range(N)] # List of empty lists
|
|
|
|
for i in range(R):
|
|
sim = simulate_NFBP(N)
|
|
I.append(sim["i"])
|
|
for n in range(N):
|
|
H[n].append(sim["H"][n])
|
|
|
|
print("Mean number of bins : {} (variance {})".format(mean(I), variance(I)))
|
|
|
|
for n in range(N):
|
|
print("Mean H_{} : {} (variance {})".format(n, mean(H[n]), variance(H[n])))
|
|
|
|
|
|
def stats_NFBP_iter(R, N):
|
|
"""
|
|
Runs R runs of NFBP (for N items) and studies distribution, variance, mean...
|
|
Calculates stats during runtime instead of after to avoid excessive memory usage.
|
|
"""
|
|
Hmean=0
|
|
Var=[]
|
|
H=[]
|
|
Exp=0
|
|
P = R * N # Total number of items
|
|
print("## Running {} NFBP simulations with {} items".format(R, N))
|
|
# number of bins
|
|
ISum = 0
|
|
IVarianceSum = 0
|
|
# index of the bin containing the n-th item
|
|
HSum = [0 for _ in range(N)]
|
|
HSumVariance = [0 for _ in range(N)]
|
|
# number of items in the i-th bin
|
|
Sum_T = [0 for _ in range(N)]
|
|
TSumVariance = [0 for _ in range(N)]
|
|
# size of the first item in the i-th bin
|
|
Sum_V = [0 for _ in range(N)]
|
|
|
|
for i in range(R):
|
|
sim = simulate_NFBP(N)
|
|
ISum += sim["i"]
|
|
IVarianceSum += sim["i"] ** 2
|
|
for n in range(N):
|
|
HSum[n] += sim["H"][n]
|
|
HSumVariance[n] += sim["H"][n] ** 2
|
|
T = sim["T"]
|
|
V = sim["V"]
|
|
# ensure that T, V have the same length as Sum_T, Sum_V
|
|
for i in range(N - sim["i"]):
|
|
T.append(0)
|
|
V.append(0)
|
|
Sum_T = [x + y for x, y in zip(Sum_T, T)]
|
|
TSumVariance = [x + y**2 for x, y in zip(TSumVariance, T)]
|
|
Sum_V = [x + y for x, y in zip(Sum_V, V)]
|
|
|
|
Sum_T = [x / R for x in Sum_T]
|
|
print(min(Sum_T[0:20]))
|
|
print(mean(Sum_T[0:35]))
|
|
print(Sum_T[0])
|
|
TVariance = sqrt(TSumVariance[0] / (R - 1) - Sum_T[0]**2) # Variance
|
|
print(TVariance)
|
|
|
|
Sum_V = [round(x / R, 2) for x in Sum_V]
|
|
# print(Sum_V)
|
|
I = ISum / R
|
|
IVariance = sqrt(IVarianceSum / (R - 1) - I**2)
|
|
print("Mean number of bins : {} (variance {})".format(I, IVariance), "\n")
|
|
# TODO clarify line below
|
|
print(" {} * {} iterations of T".format(R, N), "\n")
|
|
for n in range(N):
|
|
Hn = HSum[n] / R # moyenne
|
|
HVariance = sqrt(HSumVariance[n] / (R - 1) - Hn**2) # Variance
|
|
Var.append(HVariance)
|
|
H.append(Hn)
|
|
print(
|
|
"Index of bin containing the {}th item (H_{}) : {} (variance {})".format(
|
|
n, n, Hn, HVariance
|
|
)
|
|
)
|
|
print(HSum)
|
|
print(len(HSum))
|
|
for x in range(len(HSum)):
|
|
Hmean+=HSum[x]
|
|
Hmean=Hmean/P
|
|
print("Hmean is : {}".format(Hmean))
|
|
Exp=np.exp(1)
|
|
HSum = [x / R for x in HSum]
|
|
HSumVariance = [x / R for x in HSumVariance]
|
|
print(HSumVariance)
|
|
# Plotting
|
|
fig = plt.figure()
|
|
# T plot
|
|
x = np.arange(N)
|
|
# print(x)
|
|
ax = fig.add_subplot(221)
|
|
ax.bar(
|
|
x,
|
|
Sum_T,
|
|
width=1,
|
|
label="Empirical values",
|
|
edgecolor="blue",
|
|
linewidth=0.7,
|
|
color="red",
|
|
)
|
|
ax.set(
|
|
xlim=(0, N), xticks=np.arange(0, N,N/10), ylim=(0, 3), yticks=np.linspace(0, 3, 4)
|
|
)
|
|
ax.set_ylabel("Items")
|
|
ax.set_xlabel("Bins (1-{})".format(N))
|
|
ax.set_title("T histogram for {} items (Number of items in each bin)".format(P))
|
|
ax.legend(loc="upper left", title="Legend")
|
|
# V plot
|
|
bx = fig.add_subplot(222)
|
|
bx.bar(
|
|
x,
|
|
Sum_V,
|
|
width=1,
|
|
label="Empirical values",
|
|
edgecolor="blue",
|
|
linewidth=0.7,
|
|
color="orange",
|
|
)
|
|
bx.set(
|
|
xlim=(0, N), xticks=np.arange(0, N,N/10), ylim=(0, 1), yticks=np.linspace(0, 1, 10)
|
|
)
|
|
bx.set_ylabel("First item size")
|
|
bx.set_xlabel("Bins (1-{})".format(N))
|
|
bx.set_title("V histogram for {} items (first item size of each bin)".format(P))
|
|
bx.legend(loc="upper left", title="Legend")
|
|
# H plot
|
|
# We will simulate this part for a asymptotic study
|
|
cx = fig.add_subplot(223)
|
|
cx.bar(
|
|
x,
|
|
HSum,
|
|
width=1,
|
|
label="Empirical values",
|
|
edgecolor="blue",
|
|
linewidth=0.7,
|
|
color="green",
|
|
)
|
|
cx.set(
|
|
xlim=(0, N), xticks=np.arange(0, N,N/10), ylim=(0, 10), yticks=np.linspace(0, N, 5)
|
|
)
|
|
cx.set_ylabel("Bin ranking of n-item")
|
|
cx.set_xlabel("n-item (1-{})".format(N))
|
|
cx.set_title("H histogram for {} items".format(P))
|
|
xb = linspace(0, N, 10)
|
|
xc=linspace(0,N,50)
|
|
yb = [Hmean for n in range(N)]
|
|
db =(( HSum[30] - HSum[1])/30)*xc
|
|
wb =(( HSumVariance[30] - HSumVariance[1])/30)*xc
|
|
cx.plot(xc, yb, label="Experimental Hn_Mean", color="brown")
|
|
cx.plot(xc, H, label="Experimental E(Hn)", color="red")
|
|
cx.plot(xc, Var, label="Experimental V(Hn)", color="purple")
|
|
cx.legend(loc="upper left", title="Legend")
|
|
|
|
|
|
plt.show()
|
|
|
|
def simulate_NFDBP(N):
|
|
"""
|
|
Tries to simulate T_i, V_i and H_n for N items of random size.
|
|
Next Fit Dual Bin Packing : bins should overflow
|
|
"""
|
|
i = 0 # Nombre de boites
|
|
R = [0] # Remplissage de la i-eme boite
|
|
T = [0] # Nombre de paquets de la i-eme boite
|
|
V = [0] # Taille du premier paquet de la i-eme boite
|
|
H = [] # Rang de la boite contenant le n-ieme paquet
|
|
for n in range(N):
|
|
size = random()
|
|
if R[i] >= 1:
|
|
# Il y n'y a plus de la place dans la boite pour le paquet.
|
|
# On passe a la boite suivante (qu'on initialise).
|
|
i += 1
|
|
R.append(0)
|
|
T.append(0)
|
|
V.append(0)
|
|
if V[i] == 0:
|
|
# C'est le premier paquet de la boite
|
|
V[i] = size
|
|
H.append(i)
|
|
R[i] += size
|
|
T[i] += 1
|
|
|
|
return {"i": i, "R": R, "T": T, "V": V, "H": H}
|
|
|
|
|
|
def stats_NFDBP(R, N, t_i):
|
|
"""
|
|
Runs R runs of NFDBP (for N items) and studies distribution, variance, mean...
|
|
"""
|
|
print("## Running {} NFDBP simulations with {} items".format(R, N))
|
|
# TODO comment this function
|
|
T1=[]
|
|
P = N * R # Total number of items
|
|
I = []
|
|
H = [[] for _ in range(N)] # List of empty lists
|
|
T = []
|
|
Tk = [[] for _ in range(N)]
|
|
Ti = []
|
|
T_maths = []
|
|
# First iteration to use zip after
|
|
sim = simulate_NFDBP(N)
|
|
Sum_T = [0 for _ in range(N)]
|
|
for i in range(R):
|
|
sim = simulate_NFDBP(N)
|
|
I.append(sim["i"])
|
|
for k in range(N):
|
|
T.append(0)
|
|
T = sim["T"]
|
|
T1.append(sim["T"][0])
|
|
for n in range(N):
|
|
H[n].append(sim["H"][n])
|
|
Tk[n].append(sim["T"][n])
|
|
Ti.append(sim["T"])
|
|
Sum_T = [x + y for x, y in zip(Sum_T, T)]
|
|
Sum_T = [x / R for x in Sum_T] # Experimental [Ti=k]
|
|
Sum_T = [
|
|
x * 100 / (sum(Sum_T)) for x in Sum_T
|
|
] # Pourcentage de la repartition des items
|
|
T1=[x/100 for x in T1]
|
|
print("Mean number of bins : {} (variance {})".format(mean(I), variance(I)))
|
|
|
|
for n in range(N):
|
|
print("Mean H_{} : {} (variance {})".format(n, mean(H[n]), variance(H[n])))
|
|
# TODO variance for T_k doesn't see right
|
|
print("Mean T_{} : {} (variance {})".format(k, mean(Sum_T), variance(Sum_T)))
|
|
# Loi math
|
|
for u in range(N):
|
|
u = u + 2
|
|
T_maths.append(1 / (factorial(u - 1)) - 1 / factorial(u))
|
|
E = 0
|
|
sigma2 = 0
|
|
# print(T_maths)
|
|
T_maths = [x * 100 for x in T_maths]
|
|
for p in range(len(T_maths)):
|
|
E = E + (p + 1) * T_maths[p]
|
|
sigma2 = ((T_maths[p] - E) ** 2) / (len(T_maths) - 1)
|
|
print(
|
|
"Mathematical values : Empiric mean T_{} : {} Variance {})".format(
|
|
t_i, E, sqrt(sigma2)
|
|
)
|
|
)
|
|
# T_maths = [x * 100 for x in T_maths]
|
|
# Plotting
|
|
fig = plt.figure()
|
|
# T plot
|
|
x = np.arange(N)
|
|
print(x)
|
|
print(Sum_T)
|
|
ax = fig.add_subplot(221)
|
|
ax.bar(
|
|
x,
|
|
Sum_T,
|
|
width=1,
|
|
label="Empirical values",
|
|
edgecolor="blue",
|
|
linewidth=0.7,
|
|
color="red",
|
|
)
|
|
ax.set(
|
|
xlim=(0, N), xticks=np.arange(0, N), ylim=(0, 20), yticks=np.linspace(0, 20, 2)
|
|
)
|
|
ax.set_ylabel("Items(n) in %")
|
|
ax.set_xlabel("Bins (1-{})".format(N))
|
|
ax.set_title(
|
|
"Items percentage for each bin and {} items (Number of items in each bin)".format(
|
|
P
|
|
)
|
|
)
|
|
ax.legend(loc="upper right", title="Legend")
|
|
|
|
# TODO fix the graph below
|
|
# Mathematical P(Ti=k) plot. It shows the Ti(t_i) law with the probability of each number of items.
|
|
print(len(Tk[t_i]))
|
|
bx = fig.add_subplot(222)
|
|
bx.hist(
|
|
Tk[t_i],
|
|
bins=10,
|
|
width=1,
|
|
label="Empirical values",
|
|
edgecolor="blue",
|
|
linewidth=0.7,
|
|
color="red",
|
|
)
|
|
bx.set(
|
|
xlim=(0, N),
|
|
xticks=np.arange(0, N),
|
|
ylim=(0, len(Tk[t_i])),
|
|
yticks=np.linspace(0, 1, 1),
|
|
)
|
|
bx.set_ylabel("P(T{}=i)".format(t_i))
|
|
bx.set_xlabel("Bins i=(1-{}) in %".format(N))
|
|
bx.set_title(
|
|
"T{} histogram for {} items (Number of items in each bin)".format(t_i, P)
|
|
)
|
|
bx.legend(loc="upper right", title="Legend")
|
|
|
|
# Loi mathematique
|
|
print("ici")
|
|
print(T_maths)
|
|
cx = fig.add_subplot(223)
|
|
cx.bar(
|
|
x,
|
|
T_maths,
|
|
width=1,
|
|
label="Theoretical values",
|
|
edgecolor="blue",
|
|
linewidth=0.7,
|
|
color="red",
|
|
)
|
|
cx.set(
|
|
xlim=(0, N),
|
|
xticks=np.arange(0, N),
|
|
ylim=(0, 100),
|
|
yticks=np.linspace(0, 100, 10),
|
|
)
|
|
cx.set_ylabel("P(T{}=i)".format(t_i))
|
|
cx.set_xlabel("Bins i=(1-{})".format(N))
|
|
cx.set_title("Theoretical T{} values in %".format(t_i))
|
|
cx.legend(loc="upper right", title="Legend")
|
|
|
|
dx = fig.add_subplot(224)
|
|
dx.hist(
|
|
T1,
|
|
bins=10,
|
|
width=1,
|
|
label="Empirical values",
|
|
edgecolor="blue",
|
|
linewidth=0.7,
|
|
color="black",
|
|
)
|
|
dx.set(
|
|
xlim=(0, 10),
|
|
xticks=np.arange(0, 10,1),
|
|
ylim=(0, 100),
|
|
yticks=np.linspace(0, 100, 10),
|
|
)
|
|
dx.set_ylabel("Number of items in T1 for {} iterations")
|
|
dx.set_xlabel("{} iterations for T{}".format(R,1))
|
|
dx.set_title(
|
|
"T{} items repartition {} items (Number of items in each bin)".format(1, P)
|
|
)
|
|
dx.legend(loc="upper right", title="Legend")
|
|
|
|
plt.show()
|
|
|
|
|
|
# unused
|
|
def basic_demo():
|
|
N = 10**1
|
|
sim = simulate_NFBP(N)
|
|
|
|
print("Simulation NFBP pour {} packaets. Contenu des boites :".format(N))
|
|
for j in range(sim["i"] + 1):
|
|
remplissage = floor(sim["R"][j] * 100)
|
|
print(
|
|
"Boite {} : Rempli a {} % avec {} paquets. Taille du premier paquet : {}".format(
|
|
j, remplissage, sim["T"][j], sim["V"][j]
|
|
)
|
|
)
|
|
|
|
print()
|
|
stats_NFBP(10**3, 10)
|
|
|
|
N = 10**1
|
|
sim = simulate_NFDBP(N)
|
|
print("Simulation NFDBP pour {} packaets. Contenu des boites :".format(N))
|
|
for j in range(sim["i"] + 1):
|
|
remplissage = floor(sim["R"][j] * 100)
|
|
print(
|
|
"Boite {} : Rempli a {} % avec {} paquets. Taille du premier paquet : {}".format(
|
|
j, remplissage, sim["T"][j], sim["V"][j]
|
|
)
|
|
)
|
|
|
|
|
|
stats_NFBP_iter(10**5, 50)
|
|
print("\n\n")
|
|
stats_NFDBP(10**3, 10, 1)
|
|
|
|
print("Don't run code you don't understand or trust without a sandbox")
|