#We simulate the parallel algorithm with priority
import random
import math
#The principal variables are defined here
max_load = 2
n = 1000000
#Balls[i]=j means that the ball i is in the bin j (if j is -1 then i hasn't committed)
Balls = range(n)
#Bins[i] is the load of the bin i
Bins = range(n)
#Bins_round[i] is the list of the balls that have sent a message to bin i during the round simulated
bins_round = range(n)
#Balls_round[i] is the list of bins that have answered to the ball i during the round simulated
balls_round = range(n)
#An useful list
l = range(n)
#It puts k in all the cases of the list l
def place(k,l):
for i in range(len(l)):
l[i] = k
#It allows to begin a new simulation
def remise_zero():
place(-1,Balls)
place(0,Bins)
#It begins a simulation by defining the different lists according to the number of balls
def change_n(k):
global n
global Balls
global Bins
global bins_round
global balls_round
global l
n = k
l = range(n)
Balls = range(n)
Bins = range(n)
bins_round = range(n)
balls_round = range(n)
l = range(n)
#This function simulates a round of the algorithm with priority
#nb_balls is the number of balls left
#Current_ball lists the balls that are still here : we have nb_balls = len(current_balls)
#nb_c is the number of messages sent per round
def round(nb_balls,current_balls,nb_c):
#Answers[b] counts the number of answers that ball b has done during this round
answers = range(n)
place(0,answers)
for p in range(nb_c):
#Here we simulate what happens to the messages of priority p
#For this priority, the choices hasn't been made so far
place([],balls_round)
place([],bins_round)
#Each ball chooses one ball for its message of priority p
for i in range(nb_balls):
choice_i = random.choice(l)
#We add the ball i to bins_round[choice_i]
bins_round[choice_i] = bins_round[choice_i] + [current_balls[i]]
#Each bin answers to a certain number of messages
for i in range(n):
#max_i is the number of answer to messages of priority p that the ball i can do
max_i = min(max_load-Bins[i]-answers[i],len(bins_round[i]))
#Balls_i lists the balls that the bin i answered to
balls_i = random.sample(bins_round[i],max_i)
for j in balls_i:
#We add the bin i to the list of the bins that j can commit into
balls_round[j] = balls_round[j] + [i]
#Each ball commits if it can
for i in range(n):
#If it can commit and it hasn't commited so far then it does
if len(balls_round[i]) != 0 and Balls[i] == -1:
choice_commit = random.choice(balls_round[i])
Balls[i] = choice_commit
Bins[choice_commit] = Bins[choice_commit] + 1
else:
#The number of answers that the bin b can do has to be decreased either by incrementing Bins[b] or by increasing answer[b]
for b in (balls_round[i]):
answers[b] = answers[b]+1
#It sumulates one time the algorithm
def simulation():
global max_load
current_balls = range(n)
remise_zero()
nb_balls = n
nb_rounds = 0
#Here we choose the first parameter : the number of messages during the first round
nb_c = 1
#Here is the second : the max_load during the first round
max_load = 2
while nb_rounds < 3:
round(nb_balls,current_balls,nb_c)
#Current_balls are the non-commited balls
current_balls = [b for b in range(n) if Balls[b] == -1]
nb_balls = len(current_balls)
nb_rounds = nb_rounds+1
#Parameters for the second round
if nb_rounds == 1:
max_load = 2
nb_c = 1
#Parameter for the third round
if nb_rounds == 2:
max_load = 3
nb_c = 1
print(nb_balls)
return(nb_balls)
#Allow to repeat simulations and get an average number of what returns simulations.
#Simulation can easily be changed to return the number of bins with a certain load, the number of remaining balls after 1,2 or three rounds.
def nb_moy(essais):
nb_balls_moy = 0.
for i in range(essais):
remise_zero()
nb_balls_moy = nb_balls_moy + (float(simulation()))/(float(essais))
print(nb_balls_moy)
nb_moy(100)