投稿日: 投稿者: admin_wp

c++とPythonの実行速度差

ほんの一面に過ぎませんが、速度比較をしてみた。

やってみたことは整数100万までの素数を求める。ロジックはどちらも同じで平方根までの割り算でどこかで割り切れる（非素数）で判定、割り切れた時点で素数では無いから計算量削減のため打ち切り、しています。求めた素数はvector(c++)、list(python)に保存しています。

計算量（時間）は一桁増えるとほぼ30倍（10の2分の3乗）になるから、桁数の多い因数分解の計算量を現在の暗号原理とするのも理解できます。

<c++ code>

sqrtは本来は不動小数点ですが、clang +17では暗黙変換（出力も）されてます。コンパイラによってはエラーになるかも知れない。

#include <iostream>
#include <chrono>
#include <cmath>
#include <vector>

int main(){

int sqt;
bool flag;
std::vector vec{};

std::chrono::system_clock::time_point  start, end;
start = std::chrono::system_clock::now();

for (int i = 2; i <= 1000000; ++i){         // check prime numbers
    flag = false;
    sqt = sqrt(i);
    for (int j = 2; j <= sqt; ++j){
        if (i%j == 0){
            flag = true;
            break;
        }
    } 
    if (flag != true){
        vec.push_back(i);
    }
}

end = std::chrono::system_clock::now();
double elapsed = std::chrono::duration_cast(end-start).count();
std::cout << "elapsed time : " << elapsed << " ms" << std::endl;

std::cout << std::endl;
std::cout << "number of prime integers(up to 1M) : " << vec.size() << std::endl;
std::cout << std::endl;
std::cout << "last five prime integers " << std::endl;

for (auto itr = (vec.end() - 5); itr != vec.end(); ++itr){
    std::cout << *itr << std::endl;
}
}

<Python code>

c++とpython(for in range)ではループの上限値の捉え方が違うのでループ回数に+1しないと正しい結果が出ない。

それは、内部ループのforで素数の二乗（例えば9, 25, 49)が素数判定されてしまうから。

import time
import math

start = time.time()
set = list()

flag = False
sqt = 0;
for i in range(2, 1000001):        # check prime numbers
    flag = False;
    sqt = math.sqrt(i)
    for j in range(2, int(sqt) + 1):
        if i%j == 0:
            flag = True
            break
    if flag != True:
        set.append(i)


end = time.time()
print("elapsed time : ",'{:.0f}'.format((end-start)*1000)+ " ms")
print("number of prime integers(up to 1M) : ",len(set))
print("")
print("last five prime integers")
for i in range(5):
    print(set[-5 + i])

以下に最後部分の素数と実行時間を記載しています。

c++

elapsed time : 268 ms

number of prime integers(up to 1M) : 78498

last five prime integers 
999953
999959
999961
999979
999983


Python

elapsed time :  9433 ms
number of prime integers(up to 1M) :  78498

last five prime integers
999953
999959
999961
999979
999983

その差はおよそ40倍近くc++の方が高速で、実際のアプリでの体感速度ももちろん種類によるけど、概ね一桁は違うんだろうと思う。

もちろんPythonも全てインタプリタ処理されるわけではなく、例えばループ処理はキャッシュされているだろうけど、やはり実行効率は比較にならない。

 

admin

カテゴリーc++