Roulette Wheel selection via stochastic acceptance

Complexity of this algorithm is O(1)

by Anik Islam Abhi

JavaScript

function object_prop() {
    this.p = Math.random(); // access frequency of the object
    this.l = Math.random(); // life time of the object
    this.s = Math.random(); // size of the object
}
// genrate dummy web objects
function genarate_web_objects(S) {
    while (S--) {
        objects.push(new object_prop());
    }
}
function select_via_roulette_via_stochastic_acceptance(max) {
    var startFinding = true;
    var index = -1;
    while (startFinding) {
        index = Math.floor(S * Math.random());
        if (Math.random() < (objects_ff[index].fitness / max)) {
            return objects_ff[index];
        }
    }

}
function getPrefetchedObjectList(n) {

    for (var i = 0; i < S; i++) {
        var obj = JSON.parse(JSON.stringify(objects[i]));
        obj.fitness = (a * obj.p * obj.l) / (a * obj.p * obj.l + 1);
        objects_ff.push(obj);
    }
    var max = Math.max.apply(Math, objects_ff.map(function (x) {
        return x.fitness;
    }));
    for (var i = 0; i < n; i++) {
        selected_objects.push(select_via_roulette_via_stochastic_acceptance(max));
        //console.log(obj);
    }
}
var objects = [];
var S = 10000; // total web objects
var n = 200; // number of web objects to be selected
var a = 0.75 // total access rate
//var objects = []; // web objects
var objects_ff = []; // freshness factor of the objects
var selected_objects = [];

genarate_web_objects(S);
getPrefetchedObjectList(n);
console.log(selected_objects.length);
console.log(selected_objects);