Почему моя реализация python 3 намного быстрее, чем тот, который я написал на C++?

Question

Я знаю, что C++ должен быть намного быстрее, чем Python 3, потому что это скомпилированный язык, а не интерпретируемый язык.

Я написал 2 две программы, которые используют Монте-Карло вычислить Pi, один в Python 3, а другой в C++.

Python оказался примерно в 16 раз быстрее, чем C++. Как видно на фотографиях ниже, с значением повторения(), Python занимает 8,5 секунды, а C++ занимает 137,4 секунды.

Я новичок в C++, но я не могу найти сообщения в Интернете, объясняющие это поведение.

Согласно this post C++ вообще должен быть в 10 раз быстрее, чем на Python, что явно не так.

Пожалуйста, помогите мне понять, почему Python значительно быстрее, чем C++ в моем случае.

Мои результаты:

Монте-Карло (оценка Pi) в C++

Монте-Карло (оценка Pi) в Python 3

Python Исходный код:

from random import random 
import time 
import sys 

class MonteCarloSimulator(object): 

    def __init__(self, value): 
     self.value = value 

     if sys.platform == "win32": 
      self.G = '' 
      self.R = '' 
      self.END = '' 
     else: 
      self.G = '\033[92m' 
      self.R = '\033[1;31m' 
      self.END = '\033[0m' 

    def unit_circle(self, x, y): 
     if (x ** 2 + y ** 2) <= 1: 
      return True 
     else: 
      return False 

    def simulate(self): 
     print("\nProcessing calculations with a repetition value of " + self.R + 
     str(self.value) + self.END + " times.") 

     area_of_circle = 0 
     area_of_square = 0 

     start = time.clock() 

     for i in range(1, self.value): 
      x = random() 
      y = random() 

      if self.unit_circle(x, y): 
       area_of_circle += 1 
      area_of_square += 1 

     pi = (area_of_circle * 4)/area_of_square 

     runtime = time.clock() - start 

     print("\tCalculated Pi = " + self.G + str(pi) + self.END + 
     " ({0} seconds, {1} minutes)".format(round(runtime, 10), 
     round(runtime/60, 10))) 

     print("Estimated Num of Pi is off by", abs(pi - 3.14159265359)) 

def main(): 
    values = [1000, 10000, 100000, 1000000, 10000000, 100000000,1000000000, 10000000000] 
    for value in values: MonteCarloSimulator(value).simulate() 
if __name__ == "__main__": 
    try: 
     main() 
    except KeyboardInterrupt: 
     print("\nQuitting...") 
     sys.exit(1) 

C++ Исходный код:

#include <iostream>      // std library 
#include <random>      // random number generator 
#include <ctime>      // calculating runtime 
#include <cmath>      // absolute value function 
#include "MonteCarloSimmulation.hpp" // function prototypes 

using namespace std; 

const double g_PI {3.141592653589793238463}; 

int main() 
{ 
    // repitition values 
    long values[5] = {1000, 10000, 100000, 1000000, 10000000};//, 100000000, 1000000000, 10000000000}; 

    // runs the simulation with the different repetition values 
    for (auto value : values) 
     simulate(value); 

    cout << "\nPress return to exit"; 
    cin.get(); 

    return 0; 
} 

/** 
* The actual simulation 
*/ 
void simulate(unsigned long value) 
{ 
    // start time for calculating runtime 
    const clock_t startTime = clock(); 

    // area's variables 
    unsigned long area_of_circle = 0; 
    unsigned long area_of_square = 0; 

    // print the repitiion value 
    cout << "\nProcessing calculations with a repetition value of " << value << 
    " times." << endl; 

    for (unsigned long i = 0; i != value; i++) 
    { 
     // gets random values from 0 to 1 for (x) and (y) 
     float x = randomFloat(); 
     float y = randomFloat(); 

     // checks if (x, y) are in a unit circle, if so increment circle area 
     if (unit_circle(x, y)) 
      area_of_circle++; 
     area_of_square++; 
    } 

    // pi = area of circle * 4/area of square 
    double calculatedPi = static_cast<double>(area_of_circle * 4)/area_of_square; 

    float endTime = static_cast<float>(clock() - startTime)/CLOCKS_PER_SEC; 

    // prints the value of calculated pi 
    cout << "\tCalculated Value of Pi: " << calculatedPi << 
    " (" << endTime << " seconds, " << endTime/60 << " minutes)" << endl; 

    // difference between the calc value and pi 
    cout << "Estimated Num of Pi is off by " << abs(calculatedPi - g_PI) << '\n'; 
} 

/** 
* returns a random number from 0 to 1 
*/ 
float randomFloat() 
{ 
    random_device rd; 
    default_random_engine generator(rd()); // rd() provides a random seed 
    uniform_real_distribution<float> distribution(0,1); 

    float x = distribution(generator); 

    return x; 
} 

/** 
* checks if the two input parameters are inside a unit circle 
*/ 
bool unit_circle(float x, float y) 
{ 
    if ((x*x + y*y) <= 1) 
     return true; 
    else 
     return false; 
} 

Answer 1

Основная проблема заключается в том, что вы пересев генератор случайных чисел для каждого случайного числа в коде C++. Кроме того, вы не компилируете с включенными оптимизациями (-O3).

Я переместил инициализации генератора случайных чисел вне randomFloat функции (в равной степени, вы могли бы использовать static переменные внутри функции):

random_device rd; 
default_random_engine generator(rd()); // rd() provides a random seed 
uniform_real_distribution<float> distribution(0,1); 

float randomFloat() { 
    float x = distribution(generator); 
    return x; 
} 

и скомпилированные с -O3 и теперь C++ значительно быстрее, чем Python

является

---

Другая возможность может заключаться в том, что на языке python и C++ используется другой генератор случайных чисел. Python random module (C code here) использует генератор случайных чисел MT19937 Mersenne Twister, который является быстрым PRNG, оптимизированным специально для таких числовых задач, как Monte Carlo; алгоритм default_random_engine в C++ определяется реализацией.Как отметил Melak47, вы можете принудительно использовать MT19937 ПСЧ в C++ с:

mt19937 generator(rd()); 

или

mt19937_64 generator(rd()); 

---

приписка, Python превосходя C++ не неслыханное; алгоритмы C++ имеют общую ценность, тогда как алгоритмы Python часто довольно оптимизированы для некоторых случаев использования. См. Например, этот вопрос на substring matching.

Answer 2

Основная стоимость - ваш метод randomFloat() C++.

здание random_device, default_random_engine и uniform_real_distribution, каждая итерация невероятно расточительна.

Сделав эти статические, я смог увеличить скорость реализации C++ более чем в 100 раз. Но вам лучше было бы их вводить или обертывать в класс и делать их экземплярами.

#include <iostream>      // std library 
#include <random>      // random number generator 
#include <ctime>      // calculating runtime 
#include <cmath>      // absolute value function 

using namespace std; 

const double g_PI {3.141592653589793238463}; 

void simulate(unsigned long value); 
float randomFloat(); 
bool unit_circle(float x, float y); 

int main() 
{ 
    // repitition values 
    long values[5] = {1000, 10000, 100000, 1000000, 10000000};//, 100000000, 1000000000, 10000000000}; 

    // runs the simulation with the different repetition values 
    for (auto value : values) 
     simulate(value); 

    cout << "\nPress return to exit"; 
    cin.get(); 

    return 0; 
} 

/** 
* The actual simulation 
*/ 
void simulate(unsigned long value) 
{ 
    // start time for calculating runtime 
    const clock_t startTime = clock(); 

    // area's variables 
    unsigned long area_of_circle = 0; 
    unsigned long area_of_square = 0; 

    // print the repitiion value 
    cout << "\nProcessing calculations with a repetition value of " << value << 
    " times." << endl; 

    for (unsigned long i = 0; i != value; i++) 
    { 
     // gets random values from 0 to 1 for (x) and (y) 
     float x = randomFloat(); 
     float y = randomFloat(); 

     // checks if (x, y) are in a unit circle, if so increment circle area 
     if (unit_circle(x, y)) 
      area_of_circle++; 
     area_of_square++; 
    } 

    // pi = area of circle * 4/area of square 
    double calculatedPi = static_cast<double>(area_of_circle * 4)/area_of_square; 

    float endTime = static_cast<float>(clock() - startTime)/CLOCKS_PER_SEC; 

    // prints the value of calculated pi 
    cout << "\tCalculated Value of Pi: " << calculatedPi << 
    " (" << endTime << " seconds, " << endTime/60 << " minutes)" << endl; 

    // difference between the calc value and pi 
    cout << "Estimated Num of Pi is off by " << abs(calculatedPi - g_PI) << '\n'; 
} 

/** 
* returns a random number from 0 to 1 
*/ 
float randomFloat() 
{ 
    static random_device rd; 
    static default_random_engine generator(rd()); // rd() provides a random seed 
    static uniform_real_distribution<float> distribution(0,1); 

    float x = distribution(generator); 

    return x; 
} 

/** 
* checks if the two input parameters are inside a unit circle 
*/ 
bool unit_circle(float x, float y) 
{ 
    if ((x*x + y*y) <= 1) 
     return true; 
    else 
     return false; 
} 

---

Оригинал implmentation Вход

Processing calculations with a repetition value of 1000 times. 
    Calculated Value of Pi: 3.08 (0.019227 seconds, 0.00032045 minutes) 
Estimated Num of Pi is off by 0.0615927 

Processing calculations with a repetition value of 10000 times. 
    Calculated Value of Pi: 3.124 (0.162044 seconds, 0.00270073 minutes) 
Estimated Num of Pi is off by 0.0175927 

Processing calculations with a repetition value of 100000 times. 
    Calculated Value of Pi: 3.14568 (1.72181 seconds, 0.0286968 minutes) 
Estimated Num of Pi is off by 0.00408735 

//Couldn't be bothered to wait :P 

Используя статический генератор случайных

Processing calculations with a repetition value of 1000 times. 
    Calculated Value of Pi: 3.136 (0.000144 seconds, 2.4e-06 minutes) 
Estimated Num of Pi is off by 0.00559265 

Processing calculations with a repetition value of 10000 times. 
    Calculated Value of Pi: 3.1824 (0.000596 seconds, 9.93333e-06 minutes) 
Estimated Num of Pi is off by 0.0408073 

Processing calculations with a repetition value of 100000 times. 
    Calculated Value of Pi: 3.14044 (0.005889 seconds, 9.815e-05 minutes) 
Estimated Num of Pi is off by 0.00115265 

Processing calculations with a repetition value of 1000000 times. 
    Calculated Value of Pi: 3.14278 (0.058896 seconds, 0.0009816 minutes) 
Estimated Num of Pi is off by 0.00118335 

Processing calculations with a repetition value of 10000000 times. 
    Calculated Value of Pi: 3.14165 (0.589034 seconds, 0.00981723 minutes) 
Estimated Num of Pi is off by 6.09464e-05 

Answer 3

Непонятно, как ответ на ваш вопрос, почему python работает быстрее, просто чтобы показать, что python может быстрее и быстрее получать события для этой проблемы.

Для возможности ускорить вещи в питоне:

Используйте Numpy векторизации:

import numpy as np 

def pi(N): 
    x, y = np.random.uniform(-1, 1, size=(2, N)) 
    in_circle = np.sum(x**2 + y**2 <= 1) 
    return 4 * in_circle/N 

и/или Numba только во времени компиляции:

from numba import jit 
import random 

@jit 
def pi(N): 
    in_circle = 0 
    for i in range(N): 
     x = 2 * random.random() - 1 
     y = 2 * random.random() - 1 

     if x**2 + y**2 <= 1: 
      in_circle += 1 
    return 4 * in_circle/N