Code, compares single random choice to multiple random choices or a random choice with adjacent choice(s):

x

10 bins, 500 runs per sample, code written in a few minutes by guiding GPT-4.

simulation.c

Compile with gcc -shared -o simulation.so -fPIC simulation.c:

#include <stdlib.h>

// Function for a single random choice
void single_random_choice(int* bins, int n_bins, int objects) {
    for(int i = 0; i < objects; i++) {
        int choice = rand() % n_bins;
        bins[choice] += 1;
    }
}

// Function for random choices strategy
void random_choices(int* bins, int n_bins, int objects, int choices) {
    for(int i = 0; i < objects; i++) {
        int min_choice = rand() % n_bins;
        for(int j = 1; j < choices; j++) {
            int choice = rand() % n_bins;
            if (bins[choice] < bins[min_choice]) {
                min_choice = choice;
            }
        }
        bins[min_choice] += 1;
    }
}

// Function for adjacent choices strategy
void adjacent_choices(int* bins, int n_bins, int objects, int choices) {
    for(int i = 0; i < objects; i++) {
        int start_choice = rand() % n_bins;
        int min_choice = start_choice;
        for(int j = 1; j < choices; j++) {
            int choice = (start_choice + j) % n_bins;
            if (bins[choice] < bins[min_choice]) {
                min_choice = choice;
            }
        }
        bins[min_choice] += 1;
    }
}

two_random_choices.py

from ctypes import CDLL, c_int, POINTER
import numpy as np
import matplotlib.pyplot as plt

# Load the C library
simulation = CDLL("./simulation.so")

# Specify argument types for the functions
simulation.single_random_choice.argtypes = (POINTER(c_int), c_int, c_int)
simulation.random_choices.argtypes = (POINTER(c_int), c_int, c_int, c_int)
simulation.adjacent_choices.argtypes = (POINTER(c_int), c_int, c_int, c_int)

# Configuration
n_bins = 10
runs_per_sample = 500
max_choices = 3
min_balls = 1
max_balls = 1000
skip_value = 50

# Initialize storage
deltas_single_random = []
deltas_random = [[] for _ in range(max_choices - 1)]
deltas_adjacent = [[] for _ in range(max_choices - 1)]

# Iterate over different numbers of choices and compute the deltas
for choices in range(2, max_choices + 1):
    for n_objects in range(min_balls, max_balls, skip_value):
        delta_single_random_sum = 0
        delta_random_sum = 0
        delta_adjacent_sum = 0
        for _ in range(runs_per_sample):
            bins_single_random = np.zeros(n_bins, dtype=np.int32)
            bins_random = np.zeros(n_bins, dtype=np.int32)
            bins_adjacent = np.zeros(n_bins, dtype=np.int32)
            simulation.single_random_choice(
                bins_single_random.ctypes.data_as(POINTER(c_int)), n_bins, n_objects
            )
            simulation.random_choices(
                bins_random.ctypes.data_as(POINTER(c_int)), n_bins, n_objects, choices
            )
            simulation.adjacent_choices(
                bins_adjacent.ctypes.data_as(POINTER(c_int)), n_bins, n_objects, choices
            )
            delta_single_random_sum += max(bins_single_random) - min(bins_single_random)
            delta_random_sum += max(bins_random) - min(bins_random)
            delta_adjacent_sum += max(bins_adjacent) - min(bins_adjacent)

        # Compute average deltas
        delta_single_random_avg = delta_single_random_sum / runs_per_sample
        delta_random_avg = delta_random_sum / runs_per_sample
        delta_adjacent_avg = delta_adjacent_sum / runs_per_sample

        if choices == 2:
            deltas_single_random.append(delta_single_random_avg)
        deltas_random[choices - 2].append(delta_random_avg)
        deltas_adjacent[choices - 2].append(delta_adjacent_avg)

# Plot the results
plt.plot(
    range(min_balls, max_balls, skip_value),
    deltas_single_random,
    label="Single Random Choice",
)
for choices in range(2, max_choices + 1):
    plt.plot(
        range(min_balls, max_balls, skip_value),
        deltas_random[choices - 2],
        label=f"{choices} Random Choices",
    )
    plt.plot(
        range(min_balls, max_balls, skip_value),
        deltas_adjacent[choices - 2],
        label=f"{choices} Adjacent Choices",
    )

plt.xlabel("Number of Balls")
plt.ylabel("Average Delta Between Lowest and Highest Value Bin")
plt.title("Comparison of Unbalanced Load Likelihood")
plt.legend()
plt.savefig("unbalanced_load_comparison.png")
Edit
Pub: 18 Aug 2023 09:55 UTC
Edit: 18 Aug 2023 10:00 UTC
Views: 629