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

# 問題設定
:::note info
2点 A,B間の距離を pythonで **高速に** 計算したい。

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

# 測定方法
jupyter notebookを使用。
座標a,bは `np.random.rand(3)`でランダムで生成した [^1]。
[^1]:a,bは毎ループ生成するのではなく、このプロジェクトを通してずっと同じものを使用。つまり、全く同じ計算をループさせて計測した。

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


# 比較したコード
`numpy`しか使わない方法は、`numba`の `jit`で高速化できる。
これも試した。

1. `np.linalg.norm( a-b)`
   `np.linalg.norm( a-b)` + `jit`

1. `np.sqrt( np.sum( np.square( a-b)))`
   `np.sqrt( np.sum( np.square( a-b)))` + `jit`

1. `np.sqrt( np.dot( (a-b).T, a-b))`
   `np.sqrt( np.dot( (a-b).T, a-b))` + `jit`

1. `distance.euclidean( a,b)`
1. `math.dist( a,b)`


これらのコードは [DelftStack](https://www.delftstack.com/ja/howto/numpy/calculate-euclidean-distance/) から拝借した。
DelftStackのライセンスは[コチラ](https://www.delftstack.com/ja/about-us/)。


# 結果をお先に。
まず、上で紹介した順番で平均時間を書くと
| コード | 平均計算時間 |
|:--------------------------------------------:|:-:|
| `np.linalg.norm(a-b)`                      | 6000 ns  |
| `np.linalg.norm(a-b)` + `jit`              | 1040 ns  |
| `np.sqrt(np.sum(np.square(a-b)))`          | 7570 ns  |
| `np.sqrt(np.sum(np.square(a-b)))` + `jit`  | 692 ns  |
| `np.sqrt(np.dot( (a-b).T, a-b))`           | 3480 ns  |
| `np.sqrt(np.dot( (a-b).T, a-b))` + `jit`   | 368 ns  |
| `distance.euclidean(a,b)`                  | 7340 ns  |
| `math.dist(a,b)`                           | 1720 ns  |


では、 <font color="red"> **速いもの順** </font> に並べ替えてみましょう。
| コード | 平均計算時間 | 最速時間との比 |
|:------------------------------------------:|:--------:|:-:|
| `np.sqrt(np.dot( (a-b).T, a-b))` + `jit`   | 368 ns   | 1 |
| `np.sqrt(np.sum(np.square(a-b)))` + `jit`  | 692 ns   | 1.9 |
| `np.linalg.norm(a-b)` + `jit`              | 1040 ns  | 2.8 |
| `math.dist(a,b)`                           | 1720 ns  | 4.7 |
| `np.sqrt(np.dot( (a-b).T, a-b))`           | 3480 ns  | 9.5 |
| `np.linalg.norm(a-b)`                      | 6000 ns  | 16.3 |
| `distance.euclidean(a,b)`                  | 7340 ns  | 20.0 |
| `np.sqrt(np.sum(np.square(a-b)))`          | 7570 ns  | 20.6 |

:::note info
- TOP3 を全て `jit`が占めている。
  ➡ `math`や `scipy`を使うよりも、`numpy + jit`の方が高速ということか。
- `jit`を使わない場合、`math.dist`が最速。
- 最速と最遅の比は 20倍。
- 1番手と2番手でも 2倍の差がある。
:::
:::note warn
`平均と標準偏差`は10万回のループにかかる時間を100回計算して算出した。
標準偏差は平均値の 5～20% 程度だった。一番上の桁は 1以上変わらない。
:::

# 実際のコード

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


```python
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)
```

## 1. np.linalg.norm(a-b)


```python
%%timeit -r 100 -n 100000

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


#### jit


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


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

    

## 2. np.sqrt( np.sum( np.square(a-b)))


```python
%%timeit -r 100 -n 100000

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


    

#### jit


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


```python
%%timeit -r 100 -n 100000

calc_distance2(a,b)
```



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


```python
diff = a-b
```


```python
%%timeit -r 100 -n 100000

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


    

#### jit


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


```python
%%timeit -r 100 -n 100000

calc_distance3(diff)
```

    

## 4. distance.euclidean()


```python
%%timeit -r 100 -n 100000

distnce = distance.euclidean(a,b)
```

    

## 5. math.dist()


```python
%%timeit -r 100 -n 100000

distnce = math.dist(a,b)
```