CODEWITHSUNDEEP
c
Nidal
Nidal

Reputation: 1883

rand() function in with probability in chossing variable number of IP's

I have 3 IPs and every IP has a weight, I want to return the IP's according to its weights using the random function,,,, for example if we have 3 IP's : X with weight 6,Y with weight 4 and Z with weight 2, I want to return X in 50% of cases and Y in 33% of cases and Z in 17% of cases, depending on random function in C.

This code is to the case of 3 IPs:

double r = rand() / (double)RAND_MAX;
double denom = 6 + 4 + 2;
if (r < 6 / denom) {
// choose X
} else if (r < (6 + 4) / denom) {
// choose Y 
} else {
// choose Z
}

what if I have n IPs how can I modify the code to deal with n IPs not a specific number of IPs?

Upvotes: 1

Views: 249

Answers (2)

Spudd86
Spudd86

Reputation: 3006

Build an array with the cumulative weight of the ip's

Something like this

// C99 code
int pick_ip(int weights[], int nweights)
{
    // note you can split this step out if you like (a good plan)
    int cum_weights[nweights];
    int tot_weight = 0;
    for(int i=0; i < nweights; i++)
    {
        tot_weight += weights[i];
        cum_weights[i] = tot_weight;
    }

    int t = (int)(tot_weight * rand() / (double)RAND_MAX);

    if(cum_weights[0] > t) { return 0; }

    // binary search for point that we picked
    int v = -1;
    int l = 0, u = nweights -1;
    int m = u/2;
    do { // binary search
        if(cum_weights[m] > t) u = m;
        else l = m;
        m = (u + l)/2;
        if(cum_weights[l+1] >  t) {v=l+1; break;}
        if(cum_weights[u-1] <= t) {v=u;   break;}
    } while(1);
}

Note: if you're doing lots of picking split out the building of the cumulative distribution array. Also if you want floating point weights you need to use a Khan sum to compute the cumulative weights (if you want code for doing that comment and I can add it to my example)

Upvotes: 0

beiller
beiller

Reputation: 3135

Here is an example of how to do this

Weighted random numbers

and from that post:

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}
assert(!"should never get here");

Upvotes: 1

Related Questions