Разница во времени для реализации генерации случайных чисел в Java против переполнения стека

Я пишу симуляцию Монте-Карло на Java, которая включает в себя генерацию множества случайных целых чисел. Я думал, что нативный код будет быстрее для генерации случайных чисел, поэтому я должен написать код на 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 {}
}

Все методы элемента (углерод, водород и т. Д.) Просто генерируют случайное число и возвращают двойное число.

Время выполнения составляет 77,471 секунды для кода Java и 121,777 секунды для C ++.

По общему признанию я не очень опытен в C ++, поэтому возможно, что причина — просто плохо написанный код.

1

Решение

Я подозреваю, что проблема производительности находится в органах вашего carbon(), hydrogen(), nitrogen(), oxygen(), а также sulfur() функции. Вы должны показать, как они производят случайные данные.

Или это может быть в if (sum < threshold) {} else {} код.

Я хотел продолжать устанавливать начальное значение, чтобы результаты не были детерминированными (ближе к тому, чтобы быть действительно случайными)

Так как вы используете результат 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;
}

выбирает одно из двух значений с определенной вероятностью. Предположительно, вы намеревались выбрать первое значение примерно в 107 раз из 10000 (хотя, используя % с 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 секунд.


Вот функтор для генерации сумм кислорода с использованием двух binomial_distributions. Может быть, один из других дистрибутивов может сделать это за один раз, но я не знаю.

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 {
}
}
}

Если значения для других элементов не могут быть отрицательными, то вероятность того, что сумма больше пяти, равна 100%. В этом случае вам даже не нужно генерировать случайные данные; выполните ветвь if в вашем коде 100 000 000 раз.

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

Другие решения

Java (на самом деле JIT), как правило, очень хорошо обнаруживает код, который не делает ничего полезного. Это потому, что JIT может получить информацию во время выполнения, которую не может определить статический компилятор. Для кода, который можно оптимизировать, Java на самом деле может быть быстрее, чем C ++. В целом, однако, хорошо настроенная программа на C ++ работает быстрее, чем на Java.

Короче говоря, при любом количестве времени C ++ будет быстрее для хорошо понятной, хорошо настроенной программы. Однако, учитывая ограниченные ресурсы, изменяющиеся требования и команды со смешанными возможностями, Java часто может значительно опережать C ++.

Все это говорит о том, что случайное в C ++ лучше, но дороже.

1

По вопросам рекламы [email protected]