• はてなアカウントでログイン
• 無料ユーザー登録

みんなの回答

• nobu007t

  2020/02/22 20:34:05

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

      @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
  
  

nobu007t

2020/02/23 13:02:24

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

a-kuma32020/02/24 23:50:07

満足150pt

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

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

スター

pyopyopyo2020/02/29 16:07:02

満足150pt

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

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


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

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ミリ秒まで高速化できました

スター
• その他の回答を読む

この質問へのコメント

質問の情報

登録日時

2020-02-22 20:32:58

終了日時

2020-02-29 20:35:07

回答条件

1人1回まで

この質問のカテゴリ

• ゲーム

この質問に含まれるキーワード

人気の質問

• ヤフーを検索していたら、たまに写真…つまり、サムネイルが表示されている事があります。知恵袋の履歴をそ…igorsan1日前
• 学芸会の動画を編集しています。8K解像度舞台全体を撮影しています。この動画素材で動画を切り出して編集し…mai_mai_mail11日前
• プラ容器の問題 醤油、蜂蜜、油脂類などのプラ容器が多いですが、プラ材質の化学有害物質が内容物に汚染す…iquestion21日前
• 思春期で親がうざいときどうすればいいですか。匿名質問者413日前
• 二重整形って最小何歳でできるんですか匿名質問者1113日前

メニュー

• 質問一覧
• カテゴリ一覧
• 無料ユーザー登録
• 人力検索はてなトップ

PC版

• お問い合わせ
• ヘルプ
• お知らせ
• はてなトップ