Edited at

色々な言語で計算速度を比較してみた

More than 1 year has passed since last update.


計算スピードの比較

ライプニッツ級数

$$

\sum_{n=0}^{\infty}\frac{(-1)^n}{2n+1} = \frac{\pi}{4}

$$

は収束が遅い.それを利用して言語毎に計算要する時間を評価する.和の上限を$10^8$(bashを除く)とする.

(別にfor文で回すだけなのでこの計算でなくても良いのだが,作ってしまったものは仕方がない)

$ cat /proc/cpuinfo  

model name : Intel(R) Xeon(R) CPU E5-1680 v3 @ 3.20GHz

gnu版のtimeはメモリーの使用量も計測できるのでgnu版を使う

注意としてubuntu(bash)のtimeコマンドにはbash版gnu版がありgnu版を使うためには

$ /usr/bin/time

もしくは

\time

とすれば良いようだ.フォーマットは以下のようにして出力する

$ fmt="\nreal:%e[sec]\nuser:%U[sec]\nsys:%S[sec]\nMemory:%M[KB]"

\time -f ${fmt} ./LeibnizFormula

どの言語を学ぶべきかは,このひとの解説が楽しい.

計算速度は実装の仕方にも依存するので,必ずしも最適なコードを書いたわけではないが,素朴にコードを書いた結果を以下に示す.

(修正)

ご指摘頂きありがとうございます.頂いたコメントに基づき逐次修正したいと思います.


C言語

なんだかんだ慣れ死んだC言語


LeibnizFormula.c

# include <stdio.h>

# include <math.h>
int main(void){
int i;
double s = 0.0;
for(i = 0; i<=1e8; i++){
s += pow(-1.0, i) / (2.0 * i + 1.0);
};
printf("Ans:%.16f\n",4*s);
return 0;

}


$ gcc -o LeibnizFormula LeibnizFormula.c -lm

$ \time -f ${fmt} ./LeibnizFormula
Ans:3.1415926635893259

real:3.68[sec]
user:3.67[sec]
sys:0.00[sec]
Memory:624[KB]

(加筆)

最適化の有無.最適化すると速度の誤差が大きくなる気がするので適当な試行での結果

$ gcc --version

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4

$ gcc -Ofast -o LeibnizFormula LeibnizFormula.c -lm

$ \time -f ${fmt} ./LeibnizFormula
Ans:3.1415926635893259

real:3.39[sec]
user:3.39[sec]
sys:0.00[sec]
Memory:620[KB]

$ gcc -Ofast -march=native -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
Ans:3.1415926635893259

real:3.23[sec]
user:3.23[sec]
sys:0.00[sec]
Memory:620[KB]


fortran

fortranは良い言語.優しく見守りたい.


LeibnizFormula.f90

program LeibnizFormula

implicit none
integer :: i = 0
real(8) :: s = 0.0
do i=0, 10**8
s = s + (-1.0)**i /(2.0*i + 1.0)
end do
print *, 'Ans:', s*4
end program LeibnizFormula

$ \time -f ${fmt} ./LeibnizFormula

Ans: 3.1415926653536932

real:4.99[sec]
user:4.99[sec]
sys:0.00[sec]
Memory:936[KB]

意外とCの方が早い

(加筆)

最適化の有無.最適化すると速度の誤差が大きくなる気がするので適当な試行での結果

$ gfortran --version

GNU Fortran (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4

$ gfortran -Ofast -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
Ans: 3.1415926653536932

real:4.83[sec]
user:4.83[sec]
sys:0.00[sec]
Memory:936[KB]

$ gfortran -Ofast -march=native -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
Ans: 3.1415926653536932

real:4.67[sec]
user:4.67[sec]
sys:0.00[sec]
Memory:936[KB]


python

本命だけど浮気中


LeibnizFormula.py

import math

import numpy as np
import numba

def LeibnizFormula1(nmax):
s = 0
for i in range(0,nmax+1):
a = (-1)**i * 1/(2*i + 1)
s += a
return 4*s

def LeibnizFormula2(nmax):
s = np.array([(-1)**i * 1/(2*i + 1) for i in range(0,nmax+1)])
return 4*np.sum(s)

def LeibnizFormula3(nmax):
s = np.sum([(-1)**i * 1/(2*i + 1) for i in range(0,nmax + 1)])
return 4*s

@numba.jit
def LeibnizFormula4(nmax):
s = 0
for i in range(nmax+1):
s += (-1)**i * 1/(2*i + 1)
return 4*s

if __name__ == "__main__":
import sys
f = eval(sys.argv[1])
pi = f(10**8)
print(pi)


結果 numbaが早い

$ \time -f ${fmt} python LeibnizFormula.py LeibnizFormula1

3.141592663589326
real:49.65[sec]
user:49.60[sec]
sys:0.03[sec]
Memory:44316[KB] = 43[MB]

$ \time -f ${fmt} python LeibnizFormula.py LeibnizFormula2
3.14159266359
real:51.82[sec]
user:50.76[sec]
sys:1.03[sec]
Memory:3990024[KB] = 3896[MB] = 3.8[GB]

$ \time -f ${fmt} python LeibnizFormula.py LeibnizFormula3
3.14159266359
real:50.18[sec]
user:49.13[sec]
sys:1.02[sec]
Memory:3989640[KB] = 3896[MB] = 3.8[GB]

$ \time -f ${fmt} python LeibnizFormula.py LeibnizFormula4
3.141592663589326
real:3.93[sec]
user:3.89[sec]
sys:0.03[sec]
Memory:52848[KB] = [51MB]


Wolfram言語 (Mathematica)

本妻


LeibnizFormula.wl

pi = 4*Sum[N[ (-1)^n / (2*n+1) ],{n,0,10^8}];

Print@pi

$ \time -f ${fmt} wolframscript -script LeibnizFormula.wl

3.141592663589326

real:4.99[sec]
user:4.88[sec]
sys:0.13[sec]
Memory:80456[KB] = 78[MB]

ParallelSumに書き直すともっと早くなるけどここでは試さない


Haskell

お堅い


LeibnizFormula.hs

main = do

print $ 4 * sum [ (-1)**n /(2*n+1) | n <- [0..10^8] ]

listを作ると,大量のメモリを食らってしまうのでlistを作らない書き方の方が良いと思う.

もっと賢い実装があると思うけど,まだ勉強中・・・

$ ghc -O -rtsopts -with-rtsopts=-K20G LeibnizFormula.hs

$ \time -f ${fmt} ./LeibnizFormula
3.141592663589326

real:36.90[sec]
user:32.70[sec]
sys:4.11[sec]
Memory:16264736[KB] = 15883[MB] = 15[GB]

(加筆)

メモリー大喰らいを回避する方法を教えて頂いた.コードをコピペで申し訳ないがこの方法では非常に早くまたメモリー使用量も申し分ない.

import Data.List (foldl')

main = do
print $ 4 * sum' [ (-1)**n /(2*n+1) | n <- [0..10^8] ]
where
sum' = foldl' (+) 0

$ \time -f ${fmt} ./LeibnizFormula2

3.141592663589326

real:13.16[sec]
user:13.10[sec]
sys:0.04[sec]
Memory:2284[KB]


Julia

このまとめきっかけを与えてくれた言語.現在勉強中.

(加筆)

コメントにもあるとおり,実行の方法や実装によって速度に影響が出そうなのでもう少しjuliaについて勉強します


LeibnizFormula.jl

s = 0

for n = 0:1:10^8
s += (-1)^n /(2n + 1)
end
print(4*s,"\n")

$ \time -f ${fmt} julia LeibnizFormula.jl

3.141592663589326

real:8.76[sec]
user:8.70[sec]
sys:0.89[sec]
Memory:182372[KB] = 178[MB]

噂通りCの2倍程度遅い.


Java

知らない言語


LeibnizFormula.java

public class LeibnizFormula {

public static void main(String[] args){
int i;
double s=0d;
for(i=0; i<=1e8; i++){
s += Math.pow(-1.0, i)/(2.0*i+1.0);
}
System.out.println("Ans:" + 4*s);
}
}

$ javac LeibnizFormula.java

$ \time -f ${fmt} java -cp . LeibnizFormula
Ans:3.141592663589326

real:8.18[sec]
user:8.18[sec]
sys:0.02[sec]
Memory:22596[KB]


Javascript

意外と早い娘


LeibnizFormula.js

var s = 0.0;

for (var i = 0; i<=1e8; i++){
s += Math.pow(-1.0, i) / (2*i + 1);
}
console.log('%d',4*s);

$ \time -f ${fmt} node LeibnizFormula.js

3.141592663589326

real:4.94[sec]
user:4.95[sec]
sys:0.02[sec]
Memory:10956[KB] = 10[MB]


bash

じつは計算できる娘だけど,めちゃくちゃ遅い.ここでは和の上限を$10^4$とした.


LeibnizFormula.sh

i=0

s=0
while [ ${i} -le `echo 10^4 | bc` ]; do
s=`echo "scale=18; ${s} + (-1)^${i}/(2*${i} + 1)" | bc`
i=$(( i + 1 ))
done
echo "scale=18; 4*$s" | bc

$ \time -f ${fmt} bash LeibnizFormula.sh

3.141692643590542976

real:44.47[sec]
user:4.99[sec]
sys:50.23[sec]
Memory:1548[KB]

演算の回数を減らした方が早い


LeibnizFormula.sh

s=0

#while [ ${i} -le `echo 10^4 | bc` ]; do
nmax=`echo 10^4 | bc`
for i in `seq 0 $nmax`; do
s=`echo "scale=18; ${s} + (-1)^${i}/(2*${i} + 1)" | bc`
done
echo "scale=18; 4*$s" | bc

$ \time -f ${fmt} bash LeibnizFormula.sh 

3.141692643590542976

real:23.80[sec]
user:2.49[sec]
sys:27.27[sec]
Memory:2480[KB]


Lisp

かっこかっこかっこ


LeibnizFormula.lsp

(setq s 0.0)

(dotimes (n (+ (expt 10 8) 1))
(setq s (+ s (/ (expt -1 n) (+ (* n 2) 1) ) ))
)
(print (* 4 s))


$ \time -f ${fmt} clisp LeibnizFormula.lsp

3.1415968

real:177.54
user:174.38
sys:3.05
Memory:6832[KB]


Scala

遅いかと思いきや案外そうでもない


LeibnizFormula.scala

var s=0.0;

for( n <- ( 0 to scala.math.pow(10,8).toInt ) ) s += scala.math.pow(-1.0,n)/(2.0*n + 1.0)
println(4*s)


$ \time -f ${fmt} scala LeibnizFormula.scala

3.141592663589326

real:8.14
user:7.97
sys:0.03
Memory:41892[KB]


Go

早いかと思いきやそーでもない


LeibnizFormula.go

package main

import "fmt"
import "math"

func main(){
n := 0
s := 0.0
nmax := int(math.Pow(10,8))
for n < nmax {
s += math.Pow(-1.0, float64(n))/ float64(2 * n + 1)
n += 1
}
fmt.Println(4 * s)
}


$ \time -f ${fmt} go run LeibnizFormula.go 

3.141592643589326

real:13.15[sec]
user:12.91[sec]
sys:0.06[sec]
Memory:39628[KB]

実装が悪いのか?


C++

(指摘を頂きプログラムミスを修正)


LeibnizFormula.cpp

#include <iostream>

#include <cmath>

using namespace std;

int main()
{
double s=0.0;
for(int n=0; n<=1e8; n++){
s += pow(-1, n) /(2.0 * n + 1.0);
}
cout << 4*s << endl;
}


$ \time -f ${fmt} ./LeibnizFormula

3.14159

real:4.33[sec]
user:4.31[sec]
sys:0.00[sec]
Memory:1268[KB]

(加筆)

最適化の有無

$ g++ --version

g++ (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4

$ g++ -Ofast -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
3.14159

real:3.27[sec]
user:3.27[sec]
sys:0.00[sec]
Memory:1264[KB]

$ g++ -Ofast -march=native -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
3.14159

real:3.18[sec]
user:3.18[sec]
sys:0.00[sec]
Memory:1264[KB]


ruby

コメントにあったプログラムを実行すると,sumがundefinedだった.rubyは触ったことが無いので適当に書いてみた


LeibnizFormula.rb

puts (0..(10**8)).inject(0) {|sum, i| sum + ((-1.0)**i)/(2.0*i + 1.0) } * 4


$ \time -f ${fmt} ruby2.0 LeibnizFormula.rb 

3.141592663589326

real:16.90[sec]
user:16.88[sec]
sys:0.00[sec]
Memory:6956[KB]