probdist.h

   1 #ifndef ZZGO_PROBDIST_H
   2 #define ZZGO_PROBDIST_H
   3
   4 /* Tools for picking an item according to a probability distribution. */
   5
   6 /* The probability distribution structure is designed to be once
   7  * initialized, then each item sequentially assigned a value one,
   8  * then multiple times an item picked randomly. */
   9
  10 #include "move.h"
  11
  12 struct probdist {
  13         int n;
  14         float *items; // [n], probability pick<=i
  15 };
  16 #define probdist_total(pd) ((pd)->items[(pd)->n - 1])
  17 #define probdist_one(pd, i) ((pd)->items[i] - (__builtin_expect(i > 0, 1) ? (pd)->items[i - 1] : 0))
  18
  19 struct probdist *probdist_init(struct probdist *pd, int n);
  20 /* You must call this for all items, *in sequence* (0, 1, ...).
  21  * @val is probability of item @i (as opposed to items[i], which
  22  * is probability of item <=i, thus includes the sum of predecessors
  23  * as well). */
  24 static void probdist_set(struct probdist *pd, int i, float val);
  25 int probdist_pick(struct probdist *pd);
  26 void probdist_done(struct probdist *pd); // Doesn't free pd itself
  27
  28
  29 /* We disable the assertions here since this is quite time-critical
  30  * part of code, and also the compiler is reluctant to inline the
  31  * functions otherwise. */
  32
  33 static inline void
  34 probdist_set(struct probdist *pd, int i, float val)
  35 {
  36 #if 0
  37         assert(i >= 0 && i < pd->n);
  38         assert(val >= 0);
  39 #endif
  40         pd->items[i] = (__builtin_expect(i > 0, 1) ? pd->items[i - 1] : 0)
  41                        + val;
  42 }
  43
  44 #endif