hash.py

import numpy as np
import matplotlib.pyplot as plt
from tqdm import tqdm
from bisect import bisect_left

def main():
  print(strat1variation(300000, 300000))
  data = np.ndarray((200000, 3))

  N = 150000
  trials = 50
  print("Running %d trials with N: %d" % (trials, N))

  for i in tqdm(range(trials)):
    data[strat1variation(N, N), 0] += 1

  for i in tqdm(range(trials)):
    data[strat2variation(N, N), 1] += 1

  for i in tqdm(range(trials)):
    data[strat3variation(N, N), 2] += 1

  """
  for i in tqdm(range(trials)):
    data[strat4(N, N), 2] += 1
  """

  plot_histogram3(data)




def strat1(numBalls : int, numBins : int) -> int:
  data = np.random.randint(low=0, high=numBins, size=(numBalls,))
  unique, counts = np.unique(data, return_counts=True)
  return max(counts)

def strat2(numBalls : int, numBins : int) -> int:
  counts = [0 for i in range(numBins)]
  for i in range(numBalls):
    x = np.random.randint(low=0, high=numBins)
    y = (np.random.randint(low=0, high=numBins - 1) + x + 1) % numBins
   
    if counts[x] <= counts[y]:
      counts[x] += 1
    else:
      counts[y] += 1
  return max(counts)

def strat3(numBalls : int, numBins : int) -> int:
  counts = [0 for i in range(numBins)]
  for i in range(numBalls):
    x = np.random.randint(low=0, high=numBins)
    y = (np.random.randint(low=0, high=numBins - 1) + x + 1) % numBins
    z = y
    while z == y or z == x:
      z = np.random.randint(low=0, high=numBins)

    if counts[x] <= counts[y] and counts[x] <= counts[z]:
      counts[x] += 1
    elif counts[y] <= counts[x] and counts[y] <= counts[z]:
      counts[y] += 1
    else:
      counts[z] += 1
  return max(counts)
 
def strat4(numBalls : int, numBins : int) -> int:
  counts = [0 for i in range(numBins)]
  for i in range(numBalls):
    x = np.random.randint(low=0, high=numBins / 2)
    y = np.random.randint(low=0, high=numBins - int(numBins / 2)) + int(numBins / 2)

    if counts[x] < counts[y]:
      counts[x] += 1
    else:
      counts[y] += 1
  return max(counts)




def strat1variation(numBalls : int, numBins : int) -> int:
  s = [np.random.randint(low=0, high=2 ** 32) for i in range(numBins)]
  s.sort()
  counts = [0 for i in range(numBins)]
  
  for i in range(numBalls):
    x = np.random.randint(low=0, high=2 ** 32)
    idx = bisect_left(s, x) % numBins
    counts[idx] += 1

  return max(counts)


def strat2variation(numBalls : int, numBins : int) -> int:
  s = [np.random.randint(low=0, high=2 ** 32) for i in range(numBins)]
  s.sort()
  counts = [0 for i in range(numBins)]
  
  for i in range(numBalls):
    x = np.random.randint(low=0, high=2 ** 32)
    idx = bisect_left(s, x) % numBins

    idy = idx
    while idx == idy:
      idy = bisect_left(s, np.random.randint(low=0, high=2 ** 32)) % numBins

    if counts[idx] <= counts[idy]:
      counts[idx] += 1
    else:
      counts[idy] += 1

  return max(counts)

def strat3variation(numBalls : int, numBins : int) -> int:
  s = [np.random.randint(low=0, high=2 ** 32) for i in range(numBins)]
  s.sort()
  counts = [0 for i in range(numBins)]
  
  for i in range(numBalls):
    x = np.random.randint(low=0, high=2 ** 32)
    idx = bisect_left(s, x) % numBins
    idy = idx
    while idx == idy:
      idy = bisect_left(s, np.random.randint(low=0, high=2 ** 32)) % numBins

    idz = idx
    while idx == idz or idy == idz:
      idz = bisect_left(s, np.random.randint(low=0, high=2 ** 32)) % numBins

    if counts[idx] <= counts[idy] and counts[idx] <= counts[idz]:
      counts[idx] += 1
    elif counts[idy] <= counts[idx] and counts[idy] <= counts[idz]:
      counts[idy] += 1
    else:
      counts[idz] += 1

  return max(counts)




def plot_histogram(bins, filename = None):
	"""
	This function wraps a number of hairy matplotlib calls to smooth the plotting 
	part of this assignment.

	Inputs:
	- bins: 	numpy array of shape max_bin_population X num_strategies numpy array. For this 
				assignment this must be 200000 X 4. 
				WATCH YOUR INDEXING! The element bins[i,j] represents the number of times the most 
				populated bin has i+1 balls for strategy j+1. 
	
	- filename: Optional argument, if set 'filename'.png will be saved to the current 
				directory. THIS WILL OVERWRITE 'filename'.png
	"""
	assert bins.shape == (200000,4), "Input bins must be a numpy array of shape (max_bin_population, num_strategies)"
	assert np.array_equal(np.sum(bins, axis = 0),(np.array([50,50,50,50]))), "There must be 40 runs for each strategy"

	thresh =  max(np.nonzero(bins)[0])+3
	n_bins = thresh
	bins = bins[:thresh,:]
	print("\nPLOTTING: Removed empty tail. Only the first non-zero bins will be plotted\n")

	ind = np.arange(n_bins) 
	width = 1.0/6.0

	fig, ax = plt.subplots()
	rects_strat_1 = ax.bar(ind + width, bins[:,0], width, color='yellow')
	rects_strat_2 = ax.bar(ind + width*2, bins[:,1], width, color='orange')
	rects_strat_3 = ax.bar(ind + width*3, bins[:,2], width, color='red')
	rects_strat_4 = ax.bar(ind + width*4, bins[:,3], width, color='k')

	ax.set_ylabel('Number Occurrences in 50 Runs')
	ax.set_xlabel('Number of Balls In The Most Populated Bin')
	ax.set_title('Histogram: Load on Most Populated Bin For Each Strategy')

	ax.set_xticks(ind)
	ax.set_xticks(ind+width*3, minor = True)
	ax.set_xticklabels([str(i+1) for i in range(0,n_bins)], minor = True)
	ax.tick_params(axis=u'x', which=u'minor',length=0)

	ax.legend((rects_strat_1[0], rects_strat_2[0], rects_strat_3[0], rects_strat_4[0]), ('Strategy 1', 'Strategy 2', 'Strategy 3', 'Strategy 4'))
	plt.setp(ax.get_xmajorticklabels(), visible=False)
	
	if filename is not None: plt.savefig(filename+'.png', bbox_inches='tight')

	plt.show()

def plot_histogram3(bins, filename = None):
	"""
	This function wraps a number of hairy matplotlib calls to smooth the plotting 
	part of this assignment.

	Inputs:
	- bins: 	numpy array of shape max_bin_population X num_strategies numpy array. For this 
				assignment this must be 200000 X 4. 
				WATCH YOUR INDEXING! The element bins[i,j] represents the number of times the most 
				populated bin has i+1 balls for strategy j+1. 
	
	- filename: Optional argument, if set 'filename'.png will be saved to the current 
				directory. THIS WILL OVERWRITE 'filename'.png
	"""
	assert bins.shape == (200000,3), "Input bins must be a numpy array of shape (max_bin_population, num_strategies)"
	assert np.array_equal(np.sum(bins, axis = 0),(np.array([50,50,50]))), "There must be 40 runs for each strategy"

	thresh =  max(np.nonzero(bins)[0])+3
	n_bins = thresh
	bins = bins[:thresh,:]
	print("\nPLOTTING: Removed empty tail. Only the first non-zero bins will be plotted\n")

	ind = np.arange(n_bins) 
	width = 1.0/6.0

	fig, ax = plt.subplots()
	rects_strat_1 = ax.bar(ind + width, bins[:,0], width, color='yellow')
	rects_strat_2 = ax.bar(ind + width*2, bins[:,1], width, color='orange')
	rects_strat_3 = ax.bar(ind + width*3, bins[:,2], width, color='red')

	ax.set_ylabel('Number Occurrences in 50 Runs')
	ax.set_xlabel('Number of Balls In The Most Populated Bin')
	ax.set_title('Histogram: Load on Most Populated Bin For Each Strategy')

	ax.set_xticks(ind)
	ax.set_xticks(ind+width*3, minor = True)
	ax.set_xticklabels([str(i+1) for i in range(0,n_bins)], minor = True)
	ax.tick_params(axis=u'x', which=u'minor',length=0)

	ax.legend((rects_strat_1[0], rects_strat_2[0], rects_strat_3[0]), ('Strategy 1 Variation', 'Strategy 2 Variation', 'Strategy 3 Variation'))
	plt.setp(ax.get_xmajorticklabels(), visible=False)
	
	if filename is not None: plt.savefig(filename+'.png', bbox_inches='tight')

	plt.show()

if __name__ == "__main__":
  main()