AuRa Random

AuRa.cpp

#include <iostream>
#include <vector>
#include <math.h>
#include <numeric>
#include <tuple>
#include <algorithm>

std::tuple<std::vector<int>,int> selectRandom1(std::vector<int> likehoods, int sum, uint m) {

    const uint n = likehoods.size();

    std::vector<int> validators(m);
    std::vector<bool> used(n);

    int its = 0;
    for (int j = 0; j < m; j++) {
        int value = rand() % sum;
        
        for (int i = 0; i < n; i++, its++) {
            if (used[i]) {
                continue;
            }

            if (value < likehoods[i]) {
                validators[j] = i;
                sum -= likehoods[i];
                used[i] = true;
                break;
            }
            
            value -= likehoods[i];
        }
    }

    return std::make_tuple(validators, its);
}

std::tuple<std::vector<int>,int> selectRandom2(std::vector<int> likehoods, int sum, uint m) {

    const uint n = likehoods.size();

    std::vector<std::tuple<double,int> > randoms(n);
    for (int i = 0; i < n; i++) {
        randoms[i] = std::make_tuple(
            log((1 + rand()%9999)/10000.0)/likehoods[i],
            i
        );
    }

    std::sort(randoms.begin(), randoms.end(), [](const std::tuple<double,int> & a, const std::tuple<double,int> & b) {
        return std::get<0>(a) < std::get<0>(b);
    });

    std::vector<int> validators(m);
    for (int i = 0; i < m; i++) {
        validators[i] = std::get<1>(randoms[n - 1 - i]);
    }

    return std::make_tuple(validators, n);
}

std::tuple<std::vector<int>,int> selectRandom3(std::vector<int> likehoods, int sum, uint m) {

    const uint n = likehoods.size();

    std::vector<int> validators(m);
    std::vector<bool> used(n);

    int j = 0;
    int its = 0;
    for (int i = rand() % n; j < m; i++, its++) {
        int value = rand() % sum;
        //int threshold = likehoods[i % n];
        int threshold = sum - sum * pow(1.0 - likehoods[i % n]*1.0/sum, m);
        if (!used[i % n] && value <= threshold) {
            validators[j++] = i % n;
            used[i % n] = true;
        }
    }

    return std::make_tuple(validators, its);
}

std::tuple<std::vector<int>,int> selectRandom4(std::vector<int> likehoods, int sum, uint m) {

    const uint n = likehoods.size();

    std::vector<int> validatorsWithRepeatsForStats;
    std::vector<int> validators(m);
    std::vector<int> weights(n);
    int totalSteps = 0;
    
    for (int j = 0; j < m; j++) {
        int value = rand() % sum;
        for (int i = 0; i < n; i++) {
            if (value < likehoods[i]) {
                weights[i]++;
                if (weights[i] == 1) {
                    validators[j] = i;
                } else {
                    j--;
                }
                validatorsWithRepeatsForStats.push_back(i);
                break;
            }
            
            value -= likehoods[i];
            totalSteps++;
        }
    }

    return std::make_tuple(validatorsWithRepeatsForStats, totalSteps);
}

std::tuple<std::vector<int>,int> selectRandom5(std::vector<int> likehoods, int sum, uint m) {

    const uint n = likehoods.size();

    std::vector<int> validatorsWithRepeatsForStats;
    std::vector<int> validators(m);
    std::vector<int> weights(n);
    int totalSteps = 0;

    std::vector<int> accumulatedLikehoods(n);
    for (int i = 0; i < likehoods.size(); i++) {
        accumulatedLikehoods[i] = (i ? accumulatedLikehoods[i - 1] : 0) + likehoods[i];
    }

    int j = 0;
    while (j < m) {
        int value = rand() % sum;

        int a = 0;
        int b = n;
        while (a < b) {
            int m = (a + b) / 2;
            totalSteps++;

            if (value > accumulatedLikehoods[m]) {
                a = m + 1;
            }
            else if (m > 0 && value < accumulatedLikehoods[m - 1]) {
                b = m - 1;
            } else {
                a = m;
                break;
            }
        }

        if (weights[a] == 0) {
            validators[j++] = a;
        }
        weights[a]++;
        validatorsWithRepeatsForStats.push_back(a);
    }

    return std::make_tuple(validatorsWithRepeatsForStats, totalSteps);
}

int main() {
    const int m = 3;
    const int s = 100000;
    std::vector<int> likehoods = {15, 15, 50, 77, 106, 106, 123, 174, 242, 288, 463, 500, 700, 10000};
    //std::vector<int> likehoods = {106, 242, 311, 406, 739};
    //std::vector<int> likehoods = {10, 20, 30, 40, 50};
    const int n = likehoods.size();
    int sum = std::accumulate(likehoods.begin(), likehoods.end(), 0);
 
    // int sumPro = 0;
    // std::vector<int> likehoodsPro(n);
    // for (int i = 0; i < n; i++) {
    //     likehoodsPro[i] = sum - sum * pow(1.0 - likehoods[i]*1.0/sum, 1.0/(m*m));
    //     sumPro += likehoodsPro[i];
    // }

    int its1 = 0;
    std::vector<int> probs1(n);
    for (int i = 0; i < s; i++) {
        std::vector<int> selected;
        int its;
        std::tie(selected, its) = selectRandom1(likehoods, sum, m);
        for (int j = 0; j < m; j++) {
            probs1[selected[j]]++;
        }
        its1 += its;
    }

    int its1r = 0;
    std::vector<int> probs1r(n);
    for (int i = 0; i < s; i++) {
        std::vector<int> selected;
        int its;
        std::tie(selected, its) = selectRandom1(std::vector<int>(likehoods.rbegin(), likehoods.rend()), sum, m);
        for (int j = 0; j < m; j++) {
            probs1r[selected[j]]++;
        }
        its1r += its;
    }
 
    int its2 = 0;
    std::vector<int> probs2(n);
    for (int i = 0; i < s; i++) {
        std::vector<int> selected;
        int its;
        std::tie(selected, its) = selectRandom2(likehoods, sum, m);
        for (int j = 0; j < m; j++) {
            probs2[selected[j]]++;
        }
        its2 += its;
    }

    int its2r = 0;
    std::vector<int> probs2r(n);
    for (int i = 0; i < s; i++) {
        std::vector<int> selected;
        int its;
        std::tie(selected, its) = selectRandom2(std::vector<int>(likehoods.rbegin(), likehoods.rend()), sum, m);
        for (int j = 0; j < m; j++) {
            probs2r[selected[j]]++;
        }
        its2r += its;
    }

    int its3 = 0;
    std::vector<int> probs3(n);
    for (int i = 0; i < s; i++) {
        std::vector<int> selected;
        int its;
        std::tie(selected, its) = selectRandom3(likehoods, sum, m);
        for (int j = 0; j < m; j++) {
            probs3[selected[j]]++;
        }
        its3 += its;
    }

    int its3r = 0;
    std::vector<int> probs3r(n);
    for (int i = 0; i < s; i++) {
        std::vector<int> selected;
        int its;
        std::tie(selected, its) = selectRandom3(std::vector<int>(likehoods.rbegin(), likehoods.rend()), sum, m);
        for (int j = 0; j < m; j++) {
            probs3r[selected[j]]++;
        }
        its3r += its;
    }

    int its4 = 0;
    std::vector<int> probs4(n);
    for (int i = 0; i < s; i++) {
        std::vector<int> selected;
        int its;
        std::tie(selected, its) = selectRandom4(likehoods, sum, m);
        for (int j = 0; j < selected.size(); j++) {
            probs4[selected[j]]++;
        }
        its4 += its;
    }

    int its4r = 0;
    std::vector<int> probs4r(n);
    for (int i = 0; i < s; i++) {
        std::vector<int> selected;
        int its;
        std::tie(selected, its) = selectRandom4(std::vector<int>(likehoods.rbegin(), likehoods.rend()), sum, m);
        for (int j = 0; j < selected.size(); j++) {
            probs4r[selected[j]]++;
        }
        its4r += its;
    }

    int its5 = 0;
    std::vector<int> probs5(n);
    for (int i = 0; i < s; i++) {
        std::vector<int> selected;
        int its;
        std::tie(selected, its) = selectRandom5(likehoods, sum, m);
        for (int j = 0; j < selected.size(); j++) {
            probs5[selected[j]]++;
        }
        its5 += its;
    }

    int its5r = 0;
    std::vector<int> probs5r(n);
    for (int i = 0; i < s; i++) {
        std::vector<int> selected;
        int its;
        std::tie(selected, its) = selectRandom5(std::vector<int>(likehoods.rbegin(), likehoods.rend()), sum, m);
        for (int j = 0; j < selected.size(); j++) {
            probs5r[selected[j]]++;
        }
        its5r += its;
    }

    std::cout << "Algo1: AuRa O(mn) random with asc/desc iterations: " << its1*1.0/s << " / " << its1r*1.0/s << std::endl;
    std::cout << "Algo2: Log O(n) random with asc/desc iterations: " << its2*1.0/s << " / " << its2r*1.0/s << std::endl;
    std::cout << "Algo3: 1-pass O(m) random with asc/desc iterations: " << its3*1.0/s << " / " << its3r*1.0/s << std::endl;
    std::cout << "Algo4: AuRa over decomputed probs with asc/desc iterations: " << its4*1.0/s << " / " << its4r*1.0/s << std::endl;
    std::cout << "Algo5: BinSearch with asc/desc iterations: " << its5*1.0/s << " / " << its5r*1.0/s << std::endl;
    std::cout << std::endl;
    std::cout << "[ W/sumW ]   [ Algo1A ] [ Algo1D ]   [ Algo2A ] [ Algo2D ]   [ Algo3A ] [ Algo3D ]   [ Algo4A ] [ Algo4D ]   [ Algo5A ] [ Algo5D ]" << std::endl;
    for (int i = 0; i < n; i++) {
        std::cout << std::fixed
                  << " " << likehoods[i] * 1.0 / sum
                  << "  |  " << probs1[i] * 1.0 / s / m
                  << "   " << probs1r[n - 1 - i] * 1.0 / s / m
                  << "  |  " << probs2[i] * 1.0 / s / m
                  << "   " << probs2r[n - 1 - i] * 1.0 / s / m
                  << "  |  " << probs3[i] * 1.0 / s / m
                  << "   " << probs3r[n - 1 - i] * 1.0 / s / m
                  << "  |  " << probs4[i] * 1.0 / std::accumulate(probs4.begin(), probs4.end(), 0)
                  << "   " << probs4r[n - 1 - i] * 1.0 / std::accumulate(probs4r.begin(), probs4r.end(), 0)
                  << "  |  " << probs5[i] * 1.0 / std::accumulate(probs5.begin(), probs5.end(), 0)
                  << "   " << probs5r[n - 1 - i] * 1.0 / std::accumulate(probs5r.begin(), probs5r.end(), 0)
                  << std::endl;
    }
}