for処理とリスト内包表記とmapとnumpy（とついでにC++）での速度比較

# 結論

　数値計算は`numpy`を使うと圧倒的に速い。リスト内包表記を使ったデータ処理は、可読性が悪くなるかもしれないが、コードが短くなり、`for`ループを回すよりも高速になるので、メリットが多い。

# 本論

　プログラムにおいて計算速度は極めて重要です。あるリストに対して一括して処理を行いたい、という場面は多くあると思いますが、例えばリストの生成については`for`ループで逐次処理するよりもリスト内包表記を使う方が速いという[報告](https://qiita.com/intermezzo-fr/items/43f90e07e4cebe63aeb6)があります。一括処理の場合はどうでしょうか。

　ここで、`0`以上`1000000`未満の整数に対し、`500000`を引いた後絶対値を取る、という操作を想定し、実際に計算させてみることにします。

```python
limit = int(1e6)
numbers = list(range(1, limit))
np_numbers = np.array(numbers) #numpy用にも
```

# 愚直ループ

　一番簡単な方法は、`for`ループを回すことです。

```python
processed_numbers0 = []
for n in numbers:
    processed_numbers0.append(abs(n-limit/2))
```

　いちいちループを組むのが不格好な感じがありますが、やっている意図は一番伝わりやすいです。

# 配列サイズを確保

　配列のサイズを逐次変更していくのはなんだか遅そうな感じします。先に配列を確保していく書き方にします。

```python
processed_numbers1 = [0 for n in numbers]
for j,n in enumerate(numbers):
    processed_numbers1[j] = abs(numbers[j]-limit/2)
```

# リスト内包表記

　Pythonに慣れている人だったらリスト内包表記を使いそうです。

```python
processed_numbers2 = [n-limit/2 for n in numbers]
```

　スッキリしているような、可読性が悪いような、なんとも言えない感じです。

# map関数

　リストに対して一括作業をする場合。`map`関数を使うことも考えられます。イテラブルなオブジェクトに対して一括して関数（正確にはコーラブルなオブジェクト）を作用させる関数です。

```python
processed_numbers3 = list(map(lambda n: abs(n-limit/2), numbers))
```

　ここでは作用させる関数が組み込み関数1つだけでは表現できないため、ラムダ式を使って独自に定義しています。ラムダ式というと物々しいですが、上のプログラムは下と同値です。

```python
def process(n):
    return abs(n-limit/2)

processed_numbers3 = list(map(process, numbers))
```
　
　要は、いちいち別に関数を定義するのがめんどくさいので、その場で関数を定義しようぜ、というお気持ちです。書いている方は混乱しないとは思いますが、正直可読性が良いとは言えないでしょう。

# numpy

　Pythonで数値計算と言えばnumpyです。

```python
processed_numbers4 = np.abs(np_numbers-limit/2)
```

　今までのメソッドとの比較で言うと、いちいち`for`を回したり、リストの存在を意識しなくても計算ができていることがわかります。上のコードでいう`numbers`は配列であり、`limit/2`は変数です。型に厳しい言語ではまず許されないですが、そこら辺は`numpy`が[ブロードキャスト](https://note.nkmk.me/python-numpy-broadcasting/)していい感じに型変換をしてくれています。numpyが本質的に便利な部分はここなのではないか、とコードを常日頃から書く身としては思います。

# 計測

　さて、大事なのは計算速度です。早速比較してみましょう。

```python
import random
import numpy as np
import time
import matplotlib.pyplot as plt

limit = int(1e6)
numbers = list(range(1, limit))
np_numbers = np.array(numbers)

labels = ['loop','static', 'compre', 'map', 'numpy']
time_data = [[] for _ in range(5)]

for _ in range(10):
    for i in range(5):
        start = time.time()
        if i == 0:
            processed_numbers0 = []
            for n in numbers:
                processed_numbers0.append(abs(n-limit/2))
        if i == 1:
            processed_numbers1 = [0] * limit
            for j,n in enumerate(numbers):
                processed_numbers1[j] = abs(numbers[j]-limit/2)
        if i == 2:
            processed_numbers2 = [n-limit/2 for n in numbers]
        if i == 3:
            processed_numbers3 = list(map(lambda n: abs(n-limit/2), numbers))
        if i == 4:
            processed_numbers4 = np.abs(np_numbers-limit/2)
        elapsed_time = time.time() - start
        elapsed_time *= 1000
        elapsed_time = int(elapsed_time)
        print("{} {}".format(labels[i].rjust(6, ' '), str(elapsed_time).rjust(4,' ')))
        time_data[i].append(elapsed_time)

print(time_data)

plotrange = range(1, 11)
for i in range(5):
    plt.plot(plotrange, time_data[i], label=labels[i])
plt.legend()
plt.show()


```

上のコードを走らせると以下のような結果が出ます。

```python
  loop  169
static  184
compre   76
   map  134
 numpy    4
  loop  172
static  194
compre   87
   map  144
 numpy    3
...
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/a1de8d3f-3767-3da0-6ff2-437cd08b5c3e.png)


（横軸はイテレーション、縦軸はミリ秒）

　`numpy`が圧倒的に速いという結果になりました。

　また、ループを回すでは、動的にリストを拡張していく方式と、最初にサイズを確保する方式では、ほとんど処理速度は変わりませんでした。対して、リスト内包表記を使う方法とでは、リスト内包表記の方が倍近く速いという結果になりました。これは既存の実験結果とも一致します。リスト内包表記はコードの記述量を減らす働きもあるので、可読性はさておき、メリットは多いと言えます。

　
一番遅いのは`map`を使う方法で、なんとリスト内包表記の倍近く時間がかかりました。これは余談ですが、ループを回す方法でも、同じ処理を別関数に定義する方法だと同様に遅くなりました。**別関数を呼び出すこと自体**がボトルネックになっているようです。
　この現象はVSCodeのデバッグモードで実行していたからでした。正確には、愚直ループより少し速いかも程度でした。訂正いたします。（**2020/03/13 追記**）

　**数値の配列ならnumpy一択。**それ以外のデータも扱うような配列であれば、リスト内包表記にすれば速くなりそう、という評価になりました。今回は入力ケースが`10^6`程度なので僅かな差ですが、これが2重ループ3重ループになれば無視できない、いや場合によっては致命的な差になってきます。

# C++で追加実験

　追加実験として、実行速度が速いことに定評のあるC++でも同様の実験をやってみました。こちらでも、動的に配列を変更していく方法（dynamic）と、最初に確保していく方法（static）を試しています。

　の2通りを試しました。

```c++
#include <chrono>
#include <iostream>
#include <vector>

using namespace std;
using namespace std::chrono;

int main() {
  vector<int> dynamic_vector_time, static_vector_time;
  int limit = 1e6;
  for (int _ = 0; _ < 10; _++) {
    vector<int> numbers;
    for (int i = 0; i < limit; i++) {
      numbers.push_back(i);
    }
    system_clock::time_point start, end;
    start = system_clock::now();
    vector<int> processed_numbers;
    for (int i = 0; i < limit; i++) {
      processed_numbers.push_back(abs(numbers[i] - limit / 2));
    }
    end = system_clock::now();
    double elapsed = duration_cast<milliseconds>(end - start).count();
    cout << "dynamic method elapsed time is " << elapsed << endl;
    dynamic_vector_time.push_back(elapsed);

    start = system_clock::now();
    vector<int> processed_numbers2(limit);
    for (int i = 0; i < limit; i++) {
      processed_numbers2[i] = numbers[i] - limit / 2;
    }
    end = system_clock::now();
    elapsed = duration_cast<milliseconds>(end - start).count();
    cout << "static method elapsed time is " << elapsed << endl;
    static_vector_time.push_back(elapsed);
  }
  cout << "dynamic vector needed" << endl;
  for (int i : dynamic_vector_time) {
    cout << i << endl;
  }
  cout << "static vector needed" << endl;
  for (int i : static_vector_time) {
    cout << i << endl;
  }
}
```

```c++
dynamic method elapsed time is 17
static method elapsed time is 6
dynamic method elapsed time is 17
static method elapsed time is 6
dynamic method elapsed time is 16
static method elapsed time is 5
...
```

　`numpy`と同じぐらい速いです。そして、C++では配列のサイズを最初に確保する方法の方が速いことが確認されました。