NumPy テンソルの結合時間を比較してみる

## 疑問

NumPy のテンソル ndarray は``concatenate``や``stack``を用いて結合することができます。 ここで、テンソルを随時生成してそれらを結合した新しいテンソルを求めたいと思ったとき、

1. 一度リストに放り込んでから最後にまとめて結合するのか、
2. 生成したテンソルを順次結合していくのか、

どちらが早いでしょうか。普通に考えれば一気に結合したほうが早そうな気はしますが、リストはなんか遅いというイメージもあります。 どっから生まれたイメージなんだコレ。

では、実験してみましょう。

## 大量生成のコード

以下のコードを``num``を 5000 ずつ増加させてその実行時間を比較してみます。

```python
from typing import List
import datetime
import random
import time

import numpy as np

num = 5000

def listing(num: int) -> np.ndarray:
    random.seed(0)
    arr_list: List[np.ndarray] = []
    for i in range(num):
        rand1: List[List[float]] = []
        for i in range(3):
            rand1.append([random.random(), random.random(), random.random(),])
        now_arr = np.asarray(rand1)
        arr_list.append(now_arr[np.newaxis, ...])
    return np.vstack(arr_list)

def stacking(num: int) -> np.ndarray:
    random.seed(0)
    rand2: List[List[float]] = []
    for i in range(3):
        rand2.append([random.random(), random.random(), random.random(),])
    ret_arr = np.asarray(rand2)[np.newaxis, ...]
    for i in range(num - 1):
        rand3: List[List[float]] = []
        for i in range(3):
            rand3.append([random.random(), random.random(), random.random(),])
        now_arr = np.asarray(rand3)
        ret_arr = np.vstack((ret_arr,now_arr[np.newaxis, ...],))
    return ret_arr

list_start_time = time.time()
list_arr = listing(num)
list_end_time = time.time()
list_elapsed_time = list_end_time - list_start_time

stack_start_time = time.time()
stack_arr = stacking(num)
stack_end_time = time.time()
stack_elapsed_time = stack_end_time - stack_start_time

print('list time: ' + str(datetime.timedelta(seconds=list_elapsed_time)))
print('stack time: ' + str(datetime.timedelta(seconds=stack_elapsed_time)))

```

結果は以下のようになります。 やはり一度に結合したほうが早いようですね。 みてのとうりよね。

|      |  list   |  stack  |
|-----:|--------:|--------:|
|  5000|00:00.021|00:00.068|
| 10000|00:00.041|00:00.186|
| 15000|00:00.059|00:00.618|
| 20000|00:00.080|00:02.843|
| 25000|00:00.105|00:06.640|
| 30000|00:00.118|00:09.918|
| 35000|00:00.136|00:13.639|
| 40000|00:00.157|00:18.389|
| 45000|00:00.176|00:24.626|
| 50000|00:00.196|00:30.691|
| 55000|00:00.216|00:37.342|
| 60000|00:00.234|00:44.673|
| 65000|00:00.259|00:52.917|
| 70000|00:00.273|01:02.477|
| 75000|00:00.295|01:11.633|
| 80000|00:00.317|01:21.016|
| 85000|00:00.334|01:31.909|
| 90000|00:00.350|01:43.772|
| 95000|00:00.372|01:58.346|
|100000|00:00.409|02:09.706|

一度に結合する方は処理時間が線形に増加するのに対し、都度結合では 2 乗に比例しているように見えます。 オーダの観点からは、生成数が多くなればなるほど、都度結合が不利になっていきます。

![一度に結合した場合の処理時間の推移。 おおむね生成数に比例している。](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/241027/49318afc-5ffe-b7bb-1410-8573f4219ff7.png)
![都度結合した場合の処理時間の推移。 おおむね生成数の2乗に比例している。](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/241027/93606d84-8f32-38d4-4343-10aa2ef2a238.png)


## 少量生成のコード

では、生成数が少ない場合はどうでしょう。 ``num``は 3 回に抑え、それを 100000 回繰り返して時間を計測してみます。

```python
# 前略

times = 100000

list_start_time = time.time()
for i in range(times):
    list_arr = listing(num)
list_end_time = time.time()
list_elapsed_time = list_end_time - list_start_time

stack_start_time = time.time()
for i in range(times):
    stack_arr = stacking(num)
stack_end_time = time.time()
stack_elapsed_time = stack_end_time - stack_start_time

print('list time: ' + str(datetime.timedelta(seconds=list_elapsed_time)))
print('stack time: ' + str(datetime.timedelta(seconds=stack_elapsed_time)))

# list time: 0:00:02.036575
# stack time: 0:00:02.294834

```

この場合では、先程ほど差は露骨ではありませんが、やはり一度に結合したほうが若干早いですね。

## まとめ

いかがでしたか???????????????? というお決まりのフレーズは置いておいて、リストが遅いっぽいイメージとは関係なくリストに放り込んでから一度に結合したほうがやっぱり早いです。

考えてみれば、リストが遅そうなのは途中に挿入されたりとかしたときにインデックスたどるのが云々みたいな話が大本な気がするので速攻で消費するなら別に問題ない気もしますね。

とはいえ、私は Python や NumPy に関しては初心者もいいところなので、こういう場合のより良いプラクティスがありそうな気はします。