java - Java 与 C++ 中随机数生成实现的时间差异

Question

我正在用 Java 编写蒙特卡洛模拟，其中涉及生成大量随机整数。我的想法是 native 代码生成随机数会更快，所以我应该用 C++ 编写代码并通过 JNI 返回输出。但是当我用 C++ 编写相同的方法时，它实际上比 Java 版本需要更长的时间来执行。以下是代码示例:

Random rand = new Random();
int threshold = 5;
int[] composition = {10, 10, 10, 10, 10};
for (int j = 0; j < 100000000; j++) {
    rand.setSeed(System.nanoTime());
    double sum = 0;
    for (int i = 0; i < composition[0]; i++) sum += carbon(rand);
    for (int i = 0; i < composition[1]; i++) sum += hydrogen(rand);
    for (int i = 0; i < composition[2]; i++) sum += nitrogen(rand);
    for (int i = 0; i < composition[3]; i++) sum += oxygen(rand);
    for (int i = 0; i < composition[4]; i++) sum += sulfur(rand);
    if (sum < threshold) {}//execute some code
    else {}//execute some other code
}

C++ 中的等效代码:

int threshold = 5;
int composition [5] = {10, 10, 10, 10, 10};
for (int i = 0; i < 100000000; i++)
{
    srand(time(0));
    double sum = 0;
    for (int i = 0; i < composition[0]; i++) sum += carbon();
    for (int i = 0; i < composition[1]; i++) sum += hydrogen();
    for (int i = 0; i < composition[2]; i++) sum += nitrogen();
    for (int i = 0; i < composition[3]; i++) sum += oxygen();
    for (int i = 0; i < composition[4]; i++) sum += sulfur();
    if (sum > threshold) {}
    else {}
}

所有的元素方法(碳、氢等)都只是生成一个随机数并返回一个 double 值。

Java 代码的运行时间为 77.471 秒，C++ 代码的运行时间为 121.777 秒。

诚然，我在 C++ 方面经验不足，所以原因可能只是代码编写不当。

Answer 1

我怀疑性能问题出在您的 carbon() 的正文中, hydrogen() , nitrogen() , oxygen() , 和 sulfur()功能。您应该展示它们如何生成随机数据。

或者它可以在 if (sum < threshold) {} else {} 中代码。

I wanted to keep setting the seed so the results would not be deterministic (closer to being truly random)

由于您使用的是 time(0) 的结果作为种子，您不会以任何方式获得特别随机的结果。

而不是使用 srand()和 rand()你应该看看 <random>库并选择具有满足您需求的性能/质量特征的引擎。如果您的实现支持它，您甚至可以从 std::random_device 获取非确定性随机数据。 (生成种子或作为引擎)。

此外 <random>提供预制发行版，例如 std::uniform_real_distribution<double>这可能比普通程序员根据 rand() 的结果手动计算所需分布的方法要好。 .

---

好的，下面介绍了如何从代码中消除内部循环并显着加快代码速度(在 Java 或 C++ 中)。

您的代码:

double carbon() {
  if (rand() % 10000 < 107)
    return 13.0033548378;
  else
    return 12.0;
}

以特定概率选择两个值之一。大概您打算从 10000 次中选择第一个值大约 107 次(尽管使用 % 和 rand() 并不能完全满足您的要求)。当您在循环中运行它并对结果求和时:

for (int i = 0; i < composition[0]; i++) sum += carbon();

你基本上会得到 sum += X*13.0033548378 + Y*12.0;其中 X 是随机数保持在阈值以下的次数，Y 是 (trials-X)。碰巧你可以模拟运行一堆试验并使用二项分布计算成功次数，<random>恰好提供二项分布。

给定一个函数 sum_trials()

std::minstd_rand0 eng; // global random engine

double sum_trials(int trials, double probability, double A, double B) {
  std::binomial_distribution<> dist(trials, probability);
  int successes = dist(eng);
  return successes*A + (trials-successes)*B;
}

您可以替换您的 carbon()循环:

sum += sum_trials(composition[0], 107.0/10000.0, 13.003354378, 12.0); // carbon trials

我没有你使用的实际值，但你的整个循环看起来像这样:

  for (int i = 0; i < 100000000; i++) {
     double sum = 0;
     sum += sum_trials(composition[0], 107.0/10000.0, 13.003354378, 12.0); // carbon trials
     sum += sum_trials(composition[1], 107.0/10000.0, 13.003354378, 12.0); // hydrogen trials
     sum += sum_trials(composition[2], 107.0/10000.0, 13.003354378, 12.0); // nitrogen trials
     sum += sum_trials(composition[3], 107.0/10000.0, 13.003354378, 12.0); // oxygen trials
     sum += sum_trials(composition[4], 107.0/10000.0, 13.003354378, 12.0); // sulfur trials

     if (sum > threshold) {
     } else {
     }
   }

现在要注意的一件事是，在函数内部，我们用相同的数据一遍又一遍地构建分布。我们可以通过替换函数 sum_trials() 来提取它使用一个函数对象，我们在循环之前用适当的数据构造一次，然后重复使用仿函数:

struct sum_trials {
  std::binomial_distribution<> dist;
  double A; double B; int trials;

  sum_trials(int t, double p, double a, double b) : dist{t, p}, A{a}, B{b}, trials{t} {}

  double operator() () {
    int successes = dist(eng);
    return successes * A + (trials - successes) * B;
  }
};

int main() {
  int threshold = 5;
  int composition[5] = { 10, 10, 10, 10, 10 };

  sum_trials carbon   = { composition[0], 107.0/10000.0, 13.003354378, 12.0};
  sum_trials hydrogen = { composition[1], 107.0/10000.0, 13.003354378, 12.0};
  sum_trials nitrogen = { composition[2], 107.0/10000.0, 13.003354378, 12.0};
  sum_trials oxygen   = { composition[3], 107.0/10000.0, 13.003354378, 12.0};
  sum_trials sulfur   = { composition[4], 107.0/10000.0, 13.003354378, 12.0};


  for (int i = 0; i < 100000000; i++) {
     double sum = 0;

     sum += carbon();
     sum += hydrogen();
     sum += nitrogen();
     sum += oxygen();
     sum += sulfur();

     if (sum > threshold) {
     } else {
     }
   }
}

代码的原始版本花费了我的系统大约一分 30 秒。这里的最后一个版本需要 11 秒。

---

这是一个使用两个二项式分布生成氧气总和的仿函数。也许其他发行版之一可以一次做到这一点，但我不知道。

struct sum_trials2 {
  std::binomial_distribution<> d1;
  std::binomial_distribution<> d2;
  double A; double B; double C;
  int trials;
  double probabilty2;

  sum_trials2(int t, double p1, double p2, double a, double b, double c)
    : d1{t, p1}, A{a}, B{b}, C{c}, trials{t}, probability2{p2} {}

  double operator() () {
    int X = d1(eng);
    d2.param(std::binomial_distribution<>{trials-X, p2}.param());
    int Y = d2(eng);

    return X*A + Y*B + (trials-X-Y)*C;
  }
};

sum_trials2 oxygen{composition[3], 17.0/1000.0, (47.0-17.0)/(1000.0-17.0), 17.9999, 16.999, 15.999};

---

如果您可以计算总和低于您的 threshold 的概率，您可以进一步加快速度。 :

int main() {
  std::minstd_rand0 eng;
  std::bernoulli_distribution dist(probability_sum_is_over_threshold);

  for (int i=0; i< 100000000; ++i) {
    if (dist(eng)) {
    } else {
    }
  }
}

除非其他元素的值可以为负，否则总和大于 5 的概率为 100%。在那种情况下，您甚至不需要生成随机数据；执行代码的“if”分支 100,000,000 次。

int main() {
  for (int i=0; i< 100000000; ++i) {
    //execute some code
  }
}