c++ - 如何高效生成Zipf分布数？

Question

我目前正在对 C++ 中的一些数据结构进行基准测试，我想在处理 Zipf 分布式数字时测试它们。

我正在使用本网站提供的生成器:http://www.cse.usf.edu/~christen/tools/toolpage.html

我调整了实现以使用 Mersenne Twister 生成器。

它运行良好，但它真的很慢。在我的例子中，范围可能很大(大约一百万)并且生成的随机数的数量可能是几百万。

alpha 参数不会随时间改变，它是固定的。

我试图预先计算所有的 sum_prob。它要快得多，但在大范围内仍然会变慢。

有没有更快的方法生成 Zipf 分布数？即使是不太精确的内容也会受到欢迎。

谢谢

Answer 1

单独的预计算并没有多大帮助。但很明显 sum_prob 是累积的并且具有升序。因此，如果我们使用二进制搜索来查找 zipf_value，我们会将生成 Zipf 分布数的顺序从 O(n) 降低到 O(log(n))。效率提升如此之大。

在这里，只需将 genzipf.c 中的 zipf() 函数替换为以下函数:

int zipf(double alpha, int n)
{
  static int first = TRUE;      // Static first time flag
  static double c = 0;          // Normalization constant
  static double *sum_probs;     // Pre-calculated sum of probabilities
  double z;                     // Uniform random number (0 < z < 1)
  int zipf_value;               // Computed exponential value to be returned
  int    i;                     // Loop counter
  int low, high, mid;           // Binary-search bounds

  // Compute normalization constant on first call only
  if (first == TRUE)
  {
    for (i=1; i<=n; i++)
      c = c + (1.0 / pow((double) i, alpha));
    c = 1.0 / c;

    sum_probs = malloc((n+1)*sizeof(*sum_probs));
    sum_probs[0] = 0;
    for (i=1; i<=n; i++) {
      sum_probs[i] = sum_probs[i-1] + c / pow((double) i, alpha);
    }
    first = FALSE;
  }

  // Pull a uniform random number (0 < z < 1)
  do
  {
    z = rand_val(0);
  }
  while ((z == 0) || (z == 1));

  // Map z to the value
  low = 1, high = n, mid;
  do {
    mid = floor((low+high)/2);
    if (sum_probs[mid] >= z && sum_probs[mid-1] < z) {
      zipf_value = mid;
      break;
    } else if (sum_probs[mid] >= z) {
      high = mid-1;
    } else {
      low = mid+1;
    }
  } while (low <= high);

  // Assert that zipf_value is between 1 and N
  assert((zipf_value >=1) && (zipf_value <= n));

  return(zipf_value);
}