[PYTHON] Comparaison de vitesse de chaque langue par la méthode de Monte Carlo

introduction

[Méthode de Monte Carlo](https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%AB%E3% 83% AD% E6% B3% 95) La comparaison de vitesse de chaque langue est effectuée en calculant le rapport de circonférence dans chaque langue à l'aide de la méthode de Monte Carlo. La méthode de Monte Carlo consiste à déposer un point arbitraire (nombre aléatoire) à 1.0> = x> = 0, 1.0> = y> = 0, et le point déposé tombe dans le cercle à partir de l'origine (0,0). Le rapport entre la chose et la chose qui est tombée en dehors du cercle est calculé, et ce rapport devient le rapport de circonférence. Bien sûr, bien qu'il soit proche du rapport de circonférence obtenu par calcul, cela ne donne pas une valeur précise, mais je pense qu'il est logique de l'implémenter dans un langage de programmation. La raison est -La vitesse de calcul en virgule flottante peut être comparée. ・ La vitesse de boucle peut être comparée. -L'utilisation de la mémoire est faible et la pagination ne se produit pas (probablement). -Puisque DiskIO ne se produit pas, il n'est pas facilement affecté par les périphériques de stockage externes. -Le rapport de circonférence de la bonne réponse est une information connue, ce qui facilite le débogage. Etc.

28 juin 2020 ruby a été ajouté. 28 juin 2020 Changement de la méthode de calcul de python. 28 juin 2020 La spécification du nombre de boucles de rouille était incorrecte et a été corrigée. 28 juin 2020 Mesure supplémentaire de la source de la version Xoroshiro fournie par @ tatsuya6502 pour la rouille

Ci-dessous, chaque source de langue perl

Comme perl avait une image très rapide que j'avais essayée jusqu'à présent, je l'ai préparée comme référence (standard ≒). Étant donné que la source est simple, elle doit fonctionner à grande vitesse sans aucune surcharge due à l'orientation de l'objet.

montecarlo.pl


use Time::HiRes qw( gettimeofday tv_interval);

local $ave = 0;

local $time_start, $time_end, $time_split = 0;

local $max_times    = 10000000;
local $test_times   = 100;

local $cnt = 0;

for ( $i = 1 ; $i <= $test_times ; $i++ ) {

    print($i."\n");

    $time_start = [gettimeofday];
    $cnt = 0;
    for ( $j = 0 ; $j < $max_times ; $j++) {
        $x = rand();
        $y = rand();

        if ( $x * $x + $y * $y <= 1) {
            $cnt++;
        }
    }

    $time_split = tv_interval($time_start);
    print("pi ".(4 * $cnt / $max_times)."\n");
    print("split:".$time_split."\n");

    $ave += $time_split;
}

print("AVE:".($ave / $test_times)."\n");
~                                                                                                                    ~                                                                                                                    

langage c

Pour le moment, je l'ai préparé parce que "C est rapide, n'est-ce pas?" Cela peut être plus rapide si vous le réglez bien, J'ai essayé de le supprimer à ce niveau en raison de la facilité de codage.

montecarlo.c


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

float montecarlo();

void main() {

    float ave = 0;
    int times = 100;

    for (int i = 1 ; i <= times ; i++){
        printf("%03d\n", i );
        ave += montecarlo();
    }

    printf("AVE %f\n\n", ave / times);

}

float montecarlo() {

    clock_t time_start, time_end;
    double  time_split;
    int times = 10000000;
    float x, y;

    time_start = clock();

    int cnt = 0;
    for ( int i = 0; i < times ; i++) {
        x = (float)rand() / (float)RAND_MAX;
        y = (float)rand() / (float)RAND_MAX;

        if ( (x * x + y * y) <= 1) {
            cnt++;
        }
    }

    time_end = clock();

    time_split = (double)(time_end - time_start) / 1000000;
    printf("%f\n", 4.0 * cnt / times);
    printf("time_split : %lf\n", time_split);

    return(time_split);

}

aller langue

Comme go avait une bonne réputation auparavant, je l'ai préparé comme une référence différente de perl. Puisqu'il s'agit d'un langage de compilation, à quel point peut-il être mince en langage C? Cela m'intéresse également.

montecarlo.go


package main

import (
        "fmt"
        "time"
        "math/rand"
)

var i, j, cnt int
var x, y float64
var time_start, time_end int64
var ave, time_split float64

const MAX_TIMES = 10000000
const TEST_TIMES = 100

func main() {
        //fmt.Printf("%03d\n", 10)

        //fmt.Printf("%d\n", time.Now())
        //fmt.Printf("%f\n", float64(time.Now().UnixNano()) / 1000000000.0)
        //fmt.Printf("%f\n", float64(time.Now().UnixNano()) / 1000000000.0)
        //fmt.Printf("%f\n", float64(time.Now().UnixNano()) / 1000000000.0)

        rand.Seed(time.Now().UnixNano())

        ave := 0.0
        for i := 1 ; i <= TEST_TIMES ; i++ {

                fmt.Printf("%03d times\n", i)

                time_start      := time.Now().UnixNano()
                cnt := 0
                for j := 0 ; j <  MAX_TIMES ; j++ {

                        x := rand.Float64()
                        y := rand.Float64()

                        if x * x + y * y <= 1 {
                                cnt++
                        }

                }
                fmt.Printf("pi : %f\n", 4 * float64(cnt) / float64(MAX_TIMES))

                time_end        := time.Now().UnixNano()
                time_split      := float64(time_end - time_start) / 1000000000
                fmt.Printf("time : %f\n", time_split)
                ave += time_split
                //ave := time_split

        }

        fmt.Printf("AVE : %f\n", ave / TEST_TIMES)

}

Java

En tant que langage de compilation, je pense qu'il se positionne actuellement comme une plaque de fer. (Bien qu'il puisse y avoir des opinions pour chacun ...) Il devrait être plus lent que le langage C en raison de la VM intervenante, mais dans l'expérience passée, il semble qu'il ne soit pas fatalement lent.

montecarlo.java


import java.util.Random;
import java.util.*;


class Montecarlo {
    public static void main(String[] args) {

        //System.out.println( getNowTime() );

                //Spécifiez le rayon du cercle
                double iR = 1.0;

                //Spécifiez le nombre de tirages
                int MAX_POINT = 10000000;

        //Précisez le nombre de tests
        int TEST_TIMES = 100;

                //Définition d'objet aléatoire
                Random rand = new Random();

        //Heures de début et de fin
        long time_start, time_end = 0;

        double time_split;
        double ave = 0.0;

                //Définition de la variable de sauvegarde pour une valeur aléatoire
                double ranValue = 0.0;
                double POS_X = 0.0;
                double POS_Y = 0.0;

        for ( int j = 1 ; j <= TEST_TIMES ; j ++) {

            //System.out.println("%03d", j);
            System.out.printf("%03d\n", j);

            //Heure de début
            time_start = System.nanoTime();
                //System.out.println( "start : " + time_start );

            //Comptez le nombre de cas tombés dans un arc
            int HIT_COUNT = 0;

            //Initialisation des variables de travail pour la sortie
            for ( int i = 0 ; i < MAX_POINT ; i++ ) {

                POS_X = rand.nextDouble();
                POS_Y = rand.nextDouble();

                if ( iR >= POS_X * POS_X + POS_Y * POS_Y )  {
                    HIT_COUNT++;
                }

            }
            // System.out.println(HIT_COUNT );
            System.out.println( (  4 * HIT_COUNT  / (double)MAX_POINT ) );

            //Heure de fin
            time_end = System.nanoTime();

                //System.out.println( "end   : " + time_end );

            time_split = (double)(time_end - time_start) / 1000000000.0;

                //System.out.println( "split : " + (time_end - time_start) );
                System.out.println( "split : " + time_split );

            ave += time_split;

        }

        //System.out.println( getNowTime() );
        System.out.println( "AVE : " + ave / TEST_TIMES );

    }

        ///Heure actuelle aaaa/mm/dd hh:mm:ss(jpn)Mettez-vous au format
        public static String getNowTime() {

                return(String.format("%1$tF %1$tT" ,Calendar.getInstance()));

        }

}

lua Il a la réputation d'être léger en tant que langage de script, alors je l'ai ajouté. En tant que spécification de langage, c'est une image qu'elle est rapide car elle utilise des instructions proches de l'OS.

montecarlo.lua


local socket = require("socket")

math.randomseed(os.time())

MAX_LOOP = 10000000
TEST_TIMES = 100

ave = 0.0
for i = 1, TEST_TIMES do
    print(string.format("%03d times", i))
    time_start  = socket.gettime()

    cnt = 0
    for j = 1 , MAX_LOOP do
        x = math.random()
        y = math.random()

        if x * x + y * y <= 1 then
            cnt = cnt + 1
        end

    end

    time_end    = socket.gettime()

    time_split  = time_end - time_start

    print(string.format("pi    : %f", 4 * cnt / MAX_LOOP))
    print(string.format("split : %f", time_split))

    ave = ave + time_split

end

print(string.format("ave : %f", ave / TEST_TIMES))

python Inutile de dire que c'est python. Cette fois, nous comparerons avec les 2e et 3e séries, ainsi qu'avec pypy.

montecarlo.py


import random
import time
import math

_times = 10000000

def pi():
    _time_start = time.time()

    _cnt = 0
    for i in range(_times):

        _x = random.random()
        _y = random.random()

        #if  _x ** 2 + _y **2 <= 1:
        if  _x * _x + _y * _y <= 1:

            _cnt += 1

    print( 4.0 * _cnt / _times )

    _time_end = time.time()

    _time_split = _time_end - _time_start
    print(_time_split)

    return _time_split

_test = 100

_ave = 0.0
for _i in range(_test):
    print('{:03d} times'.format(_i+1))
    _ave += pi()

print('ave: {} s'.format(_ave/_test))

Rust Rust est un langage qui attire l'attention dans l'IA et l'apprentissage automatique. C'est un langage plus rapide que python et plus facile à développer que C.

Cargo.toml


[package]
name = "montecarlo"
version = "0.1.0"
authors = ["ubuntu"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
rand = "0.6"
floating-duration="0.1.2"

src/main.rs


fn main() {

    use rand::Rng;                  //Pour les nombres aléatoires
    use std::time::Instant;         //Pour l'acquisition du temps
    use floating_duration::TimeAsFloat; //Pour la conversion du temps au flottant

    println!("Hello, world!");

    let loop_max = 10000000;        //Nombre de visites
    let test_max = 100;             //Boucle pour obtenir la moyenne

    let mut x: f32;
    let mut y: f32;

    let mut rng = rand::thread_rng();//paramètres Randseed

    let mut split_time: f32 = 0.0;
    //for _test_count in 1..test_max {
    for _test_count in 1..=test_max {
        println!("times:{:?}", _test_count );
        let start_time = Instant::now();

        let mut count = 0;
        //for _loot_count in 1..loop_max {
        for _loot_count in 1..=loop_max {
            x = rng.gen_range(0., 1.);  //Nombre aléatoire 0.0~1.0
            y = rng.gen_range(0., 1.);

            if x * x + y * y <= 1.0 {
                count = count + 1;
            }

        }
        println!("pi:{}", 4.0 * count as f32 / loop_max as f32); //car f32 est un type cast
        let end_time = start_time.elapsed().as_fractional_secs();//Convertir le temps en secondes
        println!("time:{:?}", end_time );

        split_time = split_time + end_time as f32;

    }

    println!("AVE:{}", split_time / test_max as f32);

}

Source de la version Xoroshiro fournie par @ tatsuya6502

Cargo.toml


[package]
name = "montecarlo"
version = "0.1.0"
authors = ["ubuntu"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
rand = "0.7"
rand_xoshiro = "0.4"

src/main.rs


//Pour les nombres aléatoires
use rand::Rng;
use rand_xoshiro::{rand_core::SeedableRng, Xoroshiro128Plus};

//Pour l'acquisition du temps
use std::time::{Instant, SystemTime};

const LOOP_MAX: usize = 10_000_000; //Nombre de visites
const TEST_MAX: usize = 100; //Boucle pour obtenir la moyenne

fn main() -> Result<(), Box<dyn std::error::Error>> {
    //Définir une graine aléatoire
    let now = SystemTime::now().duration_since(SystemTime::UNIX_EPOCH)?;
    let mut rng = Xoroshiro128Plus::seed_from_u64(now.as_millis() as u64);

    let mut split_time: f32 = 0.0;
    for _test_count in 1..=TEST_MAX {
        println!("times:{}", _test_count);
        let start_time = Instant::now();

        let mut count = 0;
        for _loot_count in 0..LOOP_MAX {
            //Générer des nombres aléatoires[0.0, 1.0)・ ・ 0.0 ou plus 1.Moins de 0
            let x: f32 = rng.gen_range(0.0, 1.0);
            let y: f32 = rng.gen_range(0.0, 1.0);

            if x * x + y * y <= 1.0 {
                count += 1;
            }
        }
        println!("pi:{}", 4.0 * count as f32 / LOOP_MAX as f32); //car f32 est un type cast
        let end_time = start_time.elapsed().as_secs_f32(); //Convertir le temps en secondes
        println!("time:{}", end_time);

        split_time += end_time as f32;
    }

    println!("AVE:{}", split_time / TEST_MAX as f32);
    Ok(())
}

Nim En comparaison ...

montecarlo.nim


import random
import times

randomize()

const TEST_MAX = 10000000
const LOOP_MAX = 100

var x, y = 0.0

var ave = 0.0

for loop in 1..LOOP_MAX:
    echo $loop & " times"

    var time_start = cpuTime()
    var count = 0
    for test in 1..TEST_MAX:

        x = rand(0.0..1.0)
        y = rand(0.0..1.0)

        # echo $x
        # echo $y

        if ( x * x + y * y <= 1):
            count += 1

    echo "pi:" &  repr(float(4.0 * float(count) / float(TEST_MAX)))

    var time_split = cpuTime() - time_start

    echo "split" & repr(time_split)
    ave += time_split

echo "AVE:" & repr(ave / float(LOOP_MAX))
                                                                                                                    ~                                                                                                                    

Ruby J'ai ajouté ruby parce que @scivola a fourni la source.

montecarlo.rb


TIMES = 10000000

def pi
  time_start = Time.now

  cnt = 0
  TIMES.times do
    x = rand
    y = rand

    if  x * x + y * y <= 1
      cnt += 1
    end
  end

  puts 4.0 * cnt / TIMES

  time_end = Time.now

  time_split = time_end - time_start
  puts time_split

   time_split
end

test = 100

ave = 0.0

test.times do |i|
    puts "%03d times" % (i + 1)
    ave += pi
end

puts "ave: #{ ave / test } s"

résultat

perl 5.30
	AVE:8.93247789s

java 14.0.1
	AVE: 1.4161036380199996s

c
	gcc 9.3.0

	gcc montecarlo.c -o pi

pas d'optimisation gcc
	AVE:1.501472s

optimisation de la vitesse d'exécution gcc-O3
	AVE:1.425400s

python 2.7.18
	AVE:14.216013s

pypy 7.3.1 with GCC 9.3.0
	ave: 0.983056025505

python 3.8.2
	AVE:12.485190s
pypy3 7.3.1 with GCC 9.3.0
	ave: 1.1475282835960388 s

go 1.13.8
	AVE:2.132493

lua 5.3
	AVE:6.715329

rust (cargo 1.44.0)
	cargo run --release
	AVE 0.507196783
	
	cargo run
	AVE 16.449156

Nim 1.0.6
    nim c -r montecarlo.nim
    AVE 7.2063023393
    
    nim c -r -d:release montecarlo.nim
    AVE:0.3236947073200001

Ajouté le 28 juin 2020

Rubis ajouté.
 Ruby 2.7.0dev (2019-12-25 master e1e1d92277) [aarch64-linux]
    ave: 7.5495061204099985 s

Correction de la source python.
 if  _x ** 2 + _y **2 <= 1:    ①
 ↓
 if  _x * _x  + _y * _y <= 1:  ②

 ※python 3.8.Mesure de 2
① Ré-acquisition
    ave: 11.132939925193787 s
 ②
    ave: 9.153075976371765 s
* Mesure de pypy3
① Ré-acquisition
    ave: 1.0760090994834899 s
 ②
    ave: 1.3655683732032775 s
cette?

Correction d'une boucle de rouille.
    for _test_count in 1..test_max {
        for _loot_count in 1..loop_max { ①
     ↓
    for _test_count in 1..=test_max {
        for _loot_count in 1..=loop_max { ②

 cargo run --Mesure du rejet
① Ré-acquisition
    AVE:0.5022585
 ②
    AVE:0.51400733

Avec de la rouille@Nous avons mesuré la source de la version Xoroshiro fournie par tatsuya6502.

 AVE:0.21163946

Conclusion

À ce niveau, la rouille ~~ Nim ~~ était considérée comme la plus rapide. En termes de vitesse

~~ Nim> rust> pypy> C = java> pypy3> go> lua> ruby> perl> série python2> série python3 ~~ rust (version Xoroshiro)> Nim> rust> pypy> C = java> = pypy3> go> lua> ruby> perl> python2 series> python3 series

est devenu. C'est un langage correctement compilé> un langage scripté. Bien sûr, mon codage peut être mauvais et "de cette façon, ce sera plus rapide". Cependant, il est peu probable qu'il y ait un changement significatif dans le classement, même si une certaine ingéniosité est faite, et une seule étape changera.

Il convient de noter en particulier python, et en utilisant pypy, il a été confirmé (possible) qu'il fonctionne à une vitesse proche du langage C (bien sûr, la source telle qu'elle est peut ne pas fonctionner avec pypy, et la bibliothèque devient pypy Cela peut ne pas être pris en charge). Cependant, je pense que cela vaut la peine d'essayer si vous pouvez l'accélérer avec la description flexible de python.

Ajouté le 28 juin 2020 Le rubis est plus rapide que prévu et je ne peux cacher ma surprise. Quand je l'ai essayé avant, il s'agissait de c: ruby = 1:20, donc je m'y attendais aussi cette fois, mais j'ai été trahi avec brio. Si je ne donnais pas de suggestion à @scivola, je l'ignorerais. Merci beaucoup.

Le résultat mystérieux de ce correctif source est que python est plus rapide lorsqu'il est démarré avec python3, mais plus lent lorsqu'il est démarré avec pypy3. (Demande de commentaires d'experts) D'ailleurs, dans la source de cet article, j'ai commenté pour montrer la différence, mais comme je l'ai remplacé dans la source de mesure réelle, l'évaluation du commentaire n'a pas ralenti. (Je pense qu'il y avait une telle chose dans l'ancien Basic ...)

La différence entre la rouille et le générateur de nombres pseudo-aléatoires est évidente. Selon la source de la version Xoroshiro fournie par @ tatsuya6502, il a été constaté que le générateur de nombres pseudo aléatoires est également au bon endroit. Merci d'avoir souligné.

Cet article sera mis à jour occasionnellement. S'il y a un langage qui semble bon, je l'ajouterai.

Recommended Posts

Comparaison de vitesse de chaque langue par la méthode de Monte Carlo
Comparaison de la vitesse de traitement de la pile par langue
Estimation de π par la méthode de Monte Carlo
Méthode de Monte Carlo
Trouvez le ratio de la superficie du lac Biwa par la méthode de Monte Carlo
Jeu de compression Dominion analysé par la méthode de Monte Carlo
La première méthode de Monte Carlo en chaîne de Markov par PyStan
Calcul de l'itinéraire le plus court selon la méthode de Monte Carlo
Introduction à la méthode Monte Carlo
[Calcul scientifique / technique par Python] Simulation de Monte Carlo par la méthode metropolis de la thermodynamique du système de spin ascendant 2D
Simuler la méthode Monte Carlo en Python
Comparaison de la vitesse de calcul en implémentant python mpmath (calcul de précision arbitraire) (Note)
Comparaison de la vitesse de la perspective XML Python
Amélioration de la vitesse grâce à l'auto-implémentation de numpy.random.multivariate_normal
Je n'ai pas pu installer pypy3.6-7.3.1 avec macOS + pyenv, mais je pourrais installer pypy3.6-7.3.0. J'ai senti le vent du pypy par la méthode Monte Carlo.
Comparaison de vitesse lors du changement de groupe par pandas
Résumé des pages d'hébergement de la bibliothèque par langue
Essayez la comparaison de vitesse de l'API BigQuery Storage
Résumé de la méthode de connexion par DB de SQL Alchemy
IA à cinq yeux en recherchant les arbres de Monte Carlo
Comparaison de vitesse de murmurhash3, md5 et sha1
[Statistiques] Je vais expliquer l'échantillonnage par la méthode de Monte Carlo en chaîne de Markov (MCMC) avec animation.
Méthode #Monte Carlo pour trouver le rapport de circonférence en utilisant Python
[Python3] Comparaison de vitesse, etc. sur la privation de numpy.ndarray
Une vérification des performances du kit AWS SDK par langue
Essayez d'implémenter la méthode Monte Carlo en Python