0
Help us understand the problem. What are the problem?

posted at

updated at

pypyはC言語並に早かった(素数編) cython-annotationの例有

Pythonが大好きなのですが、処理が遅くて頭を悩ませています。

どうにか早くならないかとpypyとcython(pure python mode)でやってみました。

...すみません、ソースコードはこちらの方のを使わせていただきました。
https://qiita.com/L_A_P_119611/items/40f6c71c136fbe3cf32a

環境

MacOS: catalina
CPU: i9

  • それぞれ3回計測した結果を載せています。

pythonの結果

python3.9での実行結果は下記通りでした。
(arrangeをnumpyのに変えたら早くなるのだろうか...)
python3 src_sosu1.py 123456789
123456789 = 3 * 3 * 3607 * 3803
所要時間は39.019531秒です
所要時間は34.007243秒です
所要時間は35.707815秒です

javaの結果

java Factrization 123456789
123456789 = 3803 * 3607 * 3 * 3
所要時間は762ミリ秒です。
所要時間は687ミリ秒です。
所要時間は771ミリ秒です。

C言語の結果

./a.out 123456789
123456789 = 3 * 3 * 3607 * 3803
所要時間は1.180174秒です。
所要時間は1.189351秒です。
所要時間は1.208539秒です。

pypyでは?

使用したpypy: [PyPy 7.3.8 with GCC Apple LLVM 12.0.0 (clang-1200.0.32.29)]
homebrewでインスト。

下記とおり、ほぼC言語と同じ処理時間となりました。

pypy3 -O src_sosu1.py 123456789
123456789 = 3 * 3 * 3607 * 3803
所要時間は1.269355秒です
所要時間は1.333231秒です
所要時間は1.378345秒です

cython (annotation mode)

.so(windowsならdll相当)化したのに、期待した程、早くならなかった。
PurePythonから4倍位早くなった。

下記はdll(MacOSでは.so)化します。
cythonize -i -3 src_sosu2_with_cython1.py

src_sosu2_with_cython1.py

"""
https://qiita.com/L_A_P_119611/items/40f6c71c136fbe3cf32a
"""
import sys
import time
import cython
# from cython.cpython.cimport import array
# import array
# 素因数分解


@cython.cfunc
@cython.inline
# def factrization(n: cython.int) -> array.array:
# def factrization(n: cython.int)->array.array[cython.int]:
def factrization(n: cython.int):
    # 与えられた数値までの整数を定義する
    p: array.array[cython.int] = list(range(n+1))
    a: cython.int
    b: cython.int
    m: cython.int
    n: cython.int
    # 2から初めて、倍数を削除する
    # 最大値の半分までやればOK
    for a in range(2, int(n/2)):
        # aが素数ではないことが決まっていたら次へ
        if p[a] == 0:
            continue
        # 素数にかける数
        b = 2
        m = a * b
        # aの倍数(つまり素数ではない数)を0とする
        while m < n:
            p[m] = 0
            b += 1
            m = a * b
        # nがaの倍数であれば
        if m == n:
            # n=a*bが確定
            # print('%d = %d * %d' % (n, a, b))
            # bをさらに素因数分解する
            fact: array.array = factrization(b)
            # 確定したaは素数なので出力する
            return [a] + fact
    # nが0にならなかったらnが素数
    return [n]


def main() -> cython.void:
    # コマンドライン引数で自然数を渡す
    num: cython.int = eval(sys.argv[1])
    # num: cython.int = 123456789
    # before: cython.float = time.time()
    before = time.time()
    # 素因数分解を実行する
    f = factrization(num)
    # after: cython.float = time.time()
    after = time.time()
    # 実行結果を表示する
    print('%d = %d' % (num, f[0]), end='')
    for p in f[1:]:
        print(' * %d' % p, end='')

    print('\n所要時間は%f秒です' % (after - before))


if __name__ == "__main__":
    main()

上記.so化したコードを呼び出します。
python src_sosu2_main4cython.py 123456789
123456789 = 3 * 3 * 3607 * 3803
所要時間は11.296245秒です
所要時間は11.296245秒です
所要時間は11.102219秒です

import src_sosu2_with_cython1

src_sosu2_with_cython1.main()

結論

単にC言語化しても速度は、期待した程は向上しない。
C言語化で良いこともあれば、pypyのJITの方が良い事も多いのだろう。
これを使い分ける事で、速度挙げられるとよいのだけど。

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
0
Help us understand the problem. What are the problem?