simulation.cpp

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <sys/time.h>

/* Text color indicators */
#define COL_NULL "\33[0m"
#define COL_BOLD "\33[0;1m"
#define COL_YEL "\33[0;93m"

using namespace std;

bool check_params(int argc, char* argv[], int &n, int &m, int &d, int &d_rand, int &k, int &b);
vector<int> simulate(int &n, int &m, int &d, int &d_rand, int &k, int &b);

int main(int argc, char* argv[]) {
/* 
Set values for each parameter. If not specified in argv, use a default value.
Launch the simulation.
*/
	
    struct timeval time; 
    gettimeofday(&time,NULL);
    
    srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

    // Default values
    int n = 100; //Balls
    int m = 100; //Bins
    int d = 1; //Number of choice
    int d_rand = 0.0; //Fractional part of d *1000
    int k = 0; // Number of queries in the b-batched setting
    int b = 1; // Number of batches

    vector<int> result;
    if (check_params(argc, argv, n, m, d, d_rand, k, b)) {
    	if (d > m || (d == m && d_rand != 0)) { //More choice than bins
    		cout << "Invalid value : d must be >= m (" << d+((float)d_rand/1000) << " < " << m << ")" << endl;
    		return 0;
    	}
    	cout << "------------------------------------------------------" << endl;
        result = simulate(n, m, d, d_rand, k, b);
        cout << "------------------------------------------------------" << endl;
    }

    return 0;
}

void print_flag_line(const string& flag, const string& type, const string& description, const string& def) {
    /*
    Define the print format displayed by the --help flag.
    */
    cout << COL_YEL << left << setw(18) << flag << COL_NULL
         << setw(10) << type
         << setw(55) << description
         << def << "\n";
}

bool check_params(int argc, char* argv[], int &n, int &m, int &d, int &d_rand, int &k, int &b) {
    /*
    Check flag values from user call.
    */
	
    bool valid = true;
    string arg;
    for (int i = 1; i < argc; i++) {
        arg = argv[i];
        if ((arg == "-m" || arg == "--bins") && i+1 < argc) {
            m = stoi(argv[i+1]);
            i++;
        }
        else if ((arg == "-n" || arg == "--balls") && i+1 < argc) {
            n = stoi(argv[i+1]);
            i++;
        }
        else if ((arg == "-d" || arg == "--sample") && i+1 < argc) {
            d = stoi(argv[i+1]);
            d_rand = 1000*(stod(argv[i+1]) - d);
            i++;
        }
        else if ((arg == "-k" || arg == "--queries") && i+1 < argc) {
            k = stoi(argv[i+1]);
            i++;
        }
        else if ((arg == "-b" || arg == "--batches") && i+1 < argc) {
            b = stoi(argv[i+1]);
            i++;
        }
        else {
            cout << "Unknown parameter \"" << arg << "\"" << endl;
            valid = false;
        }
    }

    if (!valid) {
        cout << COL_BOLD << left << setw(18) << "FLAG" << setw(10) << "TYPE" << setw(55) << "DESCRIPTION" << "DEFAULT" << COL_NULL << "\n";
        print_flag_line("-m/--bins", "<int>", "Number of bins", "100");
        print_flag_line("-n/--balls", "<int>", "Number of balls", "100");
        print_flag_line("-d/--sample", "<double>", "Number of bins for d-choice criteria (1<=d)", "1");
        print_flag_line("-k/--queries", "<int>", "Number of binary queries to use in b-batched setting", "0");
        print_flag_line("-b/--batches", "<int>", "Number of batches (b>0) for the b-batched setting", "1");
    }

    return valid;
}

int least_balls(vector<int> &bins, int &n, int &m, int &d){
    int index = 0;
    int min_index = 0;
    int min = n;
    for (int i = 0; i<d; i++){
        index = rand() % m; // random value between 0 and m
        if(bins[index] < min){
            min_index = index;
            min = bins[index];
        }
    }
    return min_index;
}

int k_selection(const vector<int> &bins, int m, int d, int k) {
    // Pick d candidate bins at random
    vector<int> bin_subset;
    for (int i = 0; i < d; ++i) {
        bin_subset.push_back(rand() % m);
    }

    // Since bins is already sorted, we can just compute percentile indices
    double percentile = 0.5; // start at median
    for (int step = 0; step < k && bin_subset.size() > 1; ++step) {
        int threshold_idx = static_cast<int>(percentile * m);
        threshold_idx = max(0, min(m - 1, threshold_idx));
        int threshold = bins[threshold_idx];

        vector<int> best_bins, worst_bins;
        for (int idx : bin_subset) {
            if (bins[idx] <= threshold) best_bins.push_back(idx);
            else worst_bins.push_back(idx);
        }

        if (!best_bins.empty()) {
            bin_subset = best_bins;
            percentile = max(0.0, percentile / 2.0); // zoom toward lighter half
        } else {
            bin_subset = worst_bins;
            percentile = min(1.0, percentile + (1.0 - percentile) / 2.0); // zoom toward heavier half
        }
    }

    return bin_subset[rand() % bin_subset.size()];
}


vector<int> simulate(int &n, int &m, int &d, int &d_rand, int &k, int &b){
    vector bins(m, 0);
    int index, max = 0, n_balls = 0;
    int d_;

    for (int i = 0; i < b; i++) {
        if (k != 0) sort(bins.begin(), bins.end());
        vector<int> snapshot = bins;

        n_balls = (n / b) + ((n % b) > i);
        for (int j = 0; j < n_balls; j++) {
            if (k != 0)
                index = k_selection(snapshot, m, d, k);
            else {
                d_ = d;
                if ((rand() % 1000) < d_rand) d_ += 1;
                index = least_balls(bins, n, m, d_);
            }

            bins[index]++;
            if (bins[index] > max) max = bins[index];
        }
    }

    for (int x : bins) cout << x << ";";
    cout << endl;
    cout << "max(Xi) = " << max << endl;
    cout << "average/bin = " << ((float)n / m) << endl;
    cout << "Gn = " << (float)max - ((float)n / m) << endl;

    return bins;
}