sampling.h

   1 #ifndef SAMPLING
   2 #define SAMPLING
   3
   4 #include<ctime>
   5 #include<cstdio>
   6 #include<cassert>
   7 #include<vector>
   8
   9 #include "boost/random.hpp"
  10
  11 boost::mt19937 rng(time(NULL));
  12 boost::uniform_01<boost::mt19937> rg(rng);
  13
  14 // arr should be cumulative!
  15 // interval : [,)
  16 // random number should be in [0, arr[len - 1])
  17 // If by chance arr[len - 1] == 0.0, one possibility is to sample uniformly from 0...len-1
  18 int sample(std::vector<double>& arr, int len) {
  19   int l, r, mid;
  20   double prb = rg() * arr[len - 1];
  21
  22   l = 0; r = len - 1;
  23   while (l <= r) {
  24     mid = (l + r) / 2;
  25     if (arr[mid] <= prb) l = mid + 1;
  26     else r = mid - 1;
  27   }
  28
  29   if (l >= len) { printf("%d %lf %lf\n", len, arr[len - 1], prb); }
  30   assert(l < len);
  31
  32   return l;
  33 }
  34
  35 #endif