簡単なpythonプログラムをnumbaを使って高速化するサンプルを教えてください。


プログラムが遅いので何とかしたいですが、
pythonのnumbaの使い方が分かりません。
他にもプログラムを高速化する方法(numpy化が早い?、cython?、pypy?)
があるかもしれませんが、
こちらで確認できた1万回あたりの最速プログラムにお礼をします。

知りたいポイントは下記です。
・座標(x,y)はどの型で受け渡すのが早いのか
・maxや並び替えなどのnumpy関数との併用ができるのか
・その他、テクニックなど

下記のプログラムを高速化したプログラム例を教えて下さい。
よろしくお願いいたします。

説明:
 x,yは0~2000のint(座標)
 paste_listは上記座標のリスト
 GPUはありますが、今は使ってないので使えるかどうかわかりません。(部分的にでも使えたら嬉しいです)

対象のプログラムはインデントが崩れるので追加質問に記載します。

回答の条件
  • 1人1回まで
  • 13歳以上
  • 登録:
  • 終了:2020/02/29 20:35:07
id:nobu007t

インデントが維持できないのでこちらに書きます。

    @staticmethod
    @jit(u4(u4, u4, u4[::]), nopython=True)
    # @jit
    def getNearestDistance(x, y, paste_list):
        min_distance = 9999
        if True:
            for p in paste_list:
                distance = np.abs(p[0] - x) + abs(p[1] - y)
                if min_distance > distance:
                    min_distance = distance
        else:
            all_distance = [abs(p[0] - x) + abs(p[1] - y) for p in paste_list]
            if len(all_distance) > 0:
                min_distance = min(all_distance)
        return min_distance

回答2件)

id:nobu007t

質問文を編集しました。詳細はこちら

id:a-kuma3 No.1

回答回数4949ベストアンサー獲得回数2142

ポイント150pt

性能改善の肝は、「一番時間がかかってるところを削る」です。

件のコードは、ぱっと見た感じだと全体の律速になるとは思えないですが、呼び出される回数が半端ないようなら、結果をキャッシュしておく、というのはひとつの手だと思います。

id:pyopyopyo No.2

回答回数377ベストアンサー獲得回数98

ポイント150pt

高速なプログラムを書くコツは「自分で書かないこと」です

getNearestDistance なら
たとえば sklearn の neighbors あたりに高速なモジュールが実装されています


これを使えば3行で実装できます

def getNearestDistance(x, y, paste_list):
    tree = sklearn.neighbors.KDTree(paste_list, metric='minkowski', p=1) 
    dist, ind = tree.query([[x,y]]) 
    return dist[0][0]

実際に動くコードはこんな感じです(jypyter-noteboolのIpython 上で動かしています)

import numpy as np
import sklearn

def getNearestDistance_pyopyopyo(x, y, paste_list):
    tree = sklearn.neighbors.KDTree(paste_list, metric='minkowski', p=1) 
    dist, ind = tree.query([[x,y]]) 
    return dist[0][0]

def getNearestDistance_original(x, y, paste_list):
    min_distance = 9999
    if True:
        for p in paste_list:
            distance = np.abs(p[0] - x) + abs(p[1] - y)
            if min_distance > distance:
                min_distance = distance
    else:
        all_distance = [abs(p[0] - x) + abs(p[1] - y) for p in paste_list]
        if len(all_distance) > 0:
            min_distance = min(all_distance)
    return min_distance

# ランダムな点列を作る
# x,y の値域は 0 から 2000 
N = 100000
rng = np.random.RandomState(0)
paste_list = rng.random_sample((N, 2)) 
paste_list *= 2000
paste_list.astype(np.int)

# 同じ結果になるか確認
print("original:", getNearestDistance_original(10, 2, paste_list) )
print("pyopyopyo:", getNearestDistance_pyopyopyo(10, 2, paste_list) )

# 実行時間を計測してみる
%timeit getNearestDistance_original(10, 2, paste_list) 

# 実行時間を計測してみる
%timeit  getNearestDistance_pyopyopyo(10, 2, paste_list) 

(時間計測にはipythonの%%timeitを使っています)


paste_list が毎回同じ場合は,さらに高速化できます

まず

tree = sklearn.neighbors.KDTree(paste_list, metric='minkowski', p=1) 

を一回だけじっこうして
あとは

def getNearestDistance(x, y, tree):
    dist, ind = tree.query([[x,y]]) 
    return dist[0][0]

となるようにします.これで劇的に早くなります

実際のコードはこちら

import numpy as np
import sklearn

def getNearestDistance_pyopyopyo_v2(x, y, tree):
    dist, ind = tree.query([[x,y]]) 
    return dist[0][0]

def getNearestDistance_original(x, y, paste_list):
    min_distance = 9999
    if True:
        for p in paste_list:
            distance = np.abs(p[0] - x) + abs(p[1] - y)
            if min_distance > distance:
                min_distance = distance
    else:
        all_distance = [abs(p[0] - x) + abs(p[1] - y) for p in paste_list]
        if len(all_distance) > 0:
            min_distance = min(all_distance)
    return min_distance

# ランダムな点列を作る
# x,y の値域は 0 から 2000 
N = 100000
rng = np.random.RandomState(0)
paste_list = rng.random_sample((N, 2)) 
paste_list *= 2000
paste_list.astype(np.int)

def original(loop):
    for i in range(0,loop):
        x=i+2
        y=1000-i
        getNearestDistance_original(x, y, paste_list) 

def pyopyopyo(loop):
    tree = sklearn.neighbors.KDTree(paste_list, metric='minkowski', p=1) 
    for i in range(0,loop):
        x=i+2
        y=1000-i
        getNearestDistance_pyopyopyo_v2(x, y, tree) 

        
loop=10
%timeit original(loop)

%timeit pyopyopyo(loop)

私の手元のマシンだとこれで

1.9 s ± 7.19 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
35.5 ms ± 6.88 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

つまりもともとが1.9秒で,それが35ミリ秒まで高速化できました

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

回答リクエストを送信したユーザーはいません