More than 1 year has passed since last update.

2点間距離の計算速度（pythonコード比較）（3次元空間のみ）

Last updated at 2022-07-09Posted at 2022-05-26

問題設定

2点 A,B間の距離を pythonで 高速に 計算したい。

A,Bそれぞれの座標は変数a,bで表す。

jupyter notebookを使用。
座標a,bは np.random.rand(3)でランダムで生成した ¹。

時間の測定には %%timeitを使用した。
これは、そのセル内のコードを何度か繰り返して、計算時間の 平均 ± 標準偏差を表示してくれる。

numpyしか使わない方法は、numbaの jitで高速化できる。
これも試した。

np.linalg.norm( a-b)
np.linalg.norm( a-b) + jit
np.sqrt( np.sum( np.square( a-b)))
np.sqrt( np.sum( np.square( a-b))) + jit
np.sqrt( np.dot( (a-b).T, a-b))
np.sqrt( np.dot( (a-b).T, a-b)) + jit
distance.euclidean( a,b)
math.dist( a,b)

これらのコードは DelftStack から拝借した。
DelftStackのライセンスはコチラ。

まず、上で紹介した順番で平均時間を書くと

では、 速いもの順 に並べ替えてみましょう。

平均と標準偏差は10万回のループにかかる時間を100回計算して算出した。
標準偏差は平均値の 5～20% 程度だった。一番上の桁は 1以上変わらない。

jupyter nbconvert --to markdown Untitled.ipynbを使ってマークダウンに変換したものをコピペしただけです。

import numpy as np
import math
from scipy.spatial import distance
from numba import jit

a = np.random.rand(3)
b = np.random.rand(3)

%%timeit -r 100 -n 100000

distnce = np.linalg.norm(a-b)

@jit
def calc_distance1(p,q):
    distnce = np.linalg.norm(p-q)

%%timeit -r 100 -n 100000
calc_distance1(a,b)

%%timeit -r 100 -n 100000

distnce = np.sqrt( np.sum( np.square(a-b)))

@jit
def calc_distance2(p,q):
    distnce = np.sqrt( np.sum( np.square(p-q)))

%%timeit -r 100 -n 100000

calc_distance2(a,b)

２. と似ていますが、距離の2乗 ($r^2$) を np.dot を用いて計算しています。
内積を計算するために、転置 (.T) が必要です。

diff = a-b

%%timeit -r 100 -n 100000

distnce = np.sqrt( np.dot( diff.T, diff))

@jit
def calc_distance3(diff):
    distnce = np.sqrt( np.dot( diff.T, diff))

%%timeit -r 100 -n 100000

calc_distance3(diff)

%%timeit -r 100 -n 100000

distnce = distance.euclidean(a,b)

%%timeit -r 100 -n 100000

distnce = math.dist(a,b)