初心者のPythonが速くなる〇〇の方法【numpyとか】

* 2018/04/20 in list について追記

本当は〇〇にはちゃんと数字を入れてビジネス書っぽくキメたかったのですが、
ちゃんと数を決めて無かったことと今後も随時追加することを考えて〇〇にしました :innocent: 。

### 注意
こちらは Python を始めたばかりの初心者や、
 numpy とか scipy を最近知った方を対象としてます。
ですので Python に慣れ親しんだ方々はむしろアドバイスとか
他のケースとかもっと良い方法を教えてくださるとうれしいです :smiley: 。

あと実行環境は **Python 3.5.3** でしたので、特に **Python 2系列** を使ってる方は気を付けてください。
（map とか filter の返り値が違ったりしますので）

# 概要
最近の機械学習ブームもあり、Python を学び始めた人は多いのではないのでしょうか。特に簡単な数値処理や実際のデータを扱おうとすると numpy といったライブラリの存在に気付くのかと思います。

ただある程度のサイズのデータを扱うと実感するのですが、書き方を工夫しないと実行するのに時間がかかる場合があります（個人の所感ですが、初めてプログラミングする場合や Python の前に静的型付け言語やってると起きやすい気がします）。

特に学習してる時などはいろいろ変えて試したいわけで、いちいち実行に時間がかかったらやってられません。プログラミングが嫌いになります:angry:。 

そこでここでは **numpy** などを使ったりして、「比較的簡単」に高速化できそうなケースに
ついて紹介していきます。


※ Cython などは導入（個々の変数への型付け等）が大変なので今回は扱いません。

# 大雑把な方針
個人的に気を付けているところです。
書き方の問題で遅い場合、大体以下のいずれかに引っかかってることが多いと思います。

以下の部分を守れている人にとっては下記の例は不要です。

* **for 文は避ける** <- 大事
  * Python の for 文は速くない
  * 3重ループなどにすると悲しくなる :cry:
* 動的にメモリを確保していないか注意する
  * append などでリストに追加すると遅くなりやすい
* 一気に処理できないか検討する
  * for 文使わなくてもできる場合が多い
* すでにある関数を使う  ←　超大事
  * 速い（中身がCとかで実装されてる等、最適化されていることが多い）
  * （他の人が読む際に）分かりやすい
     * メジャーな関数はだいたい通じたりする（map 関数とか）

# 具体例
### 前準備
事前に以下のライブラリを import してます。

```py3
import numpy as np
import pandas as pd
import scipy as sp
```

## Case 1: for 文回した結果をリストに格納したい

```py3:Sample.py
def func1(n):
    a = []
    for i in range(n):
        a.append(i)
    return a

def func2(n):
    a = [0 for i in range(n)]  # 0 で初期化した長さ n のリスト
    for i in range(n):
        a[i] = i
    return a

def func3(n):
    a = [i for i in range(n)]  # 初めに内包記法で初期化
    return a

def func4(n):
    return [i for i in range(n)]  # 直接定義して返す

%time a = func1(10000000)
%time b = func2(10000000)
%time c = func3(10000000)
%time d = func4(10000000)
```

```text:result
CPU times: user 660 ms, sys: 100 ms, total: 760 ms
Wall time: 762 ms
CPU times: user 690 ms, sys: 60 ms, total: 750 ms
Wall time: 760 ms
CPU times: user 290 ms, sys: 90 ms, total: 380 ms
Wall time: 388 ms
CPU times: user 320 ms, sys: 90 ms, total: 410 ms
Wall time: 413 ms
```

予め返すリストの長さが分かる場合は、内包記法使うと
速くなります。実際、これだけでも実行時間が半分くらいになっています。
特に長いリストに対してfor文を回す際は意識すると良いと思います。


## Case 2: ベクトル内のすべての要素に同じ値を四則演算したい

ここでは以下のようなベクトルが予め定義されているとします。

```py3
a = np.array([i for i in range(10000000)])
```

このベクトルに対して、ベクトル内のすべての要素を2倍にして返す関数を考えます。

```py3:Sample.py
def func1(x):
    y = x.copy()
    for i in range(len(y)):
        y[i] *= 2
    return y

def func2(a):
    return a * 2

%time b = func1(a)
%time c = func2(a)
```

```text:result
CPU times: user 2.33 s, sys: 0 ns, total: 2.33 s
Wall time: 2.33 s
CPU times: user 10 ms, sys: 10 ms, total: 20 ms
Wall time: 13 ms
```

このように numpy はベクトル毎四則演算できたりするので、
for 文回さないように気を付けましょう。


## Case 4: ベクトルのある要素だけ取り出したい
上記と同じベクトルを用います。
例えば上記のベクトルのうち、3の倍数の要素だけ取ってきたいとします。
すると「もう for 文回して中で if 文使うしかないじゃない!!」と思うかもしれませんが、
以下のような書き方もできます。

```py3:Sample.py
def func1(a):
    ans  = []
    for i in range(len(a)):
        if a[i] % 3 == 0:
            ans.append(a[i])
    return np.array(ans)

def func2(a):
    return a[a % 3 == 0]

%time b = func1(a)
%time c = func2(a)
```

```text:result
CPU times: user 3.44 s, sys: 10 ms, total: 3.45 s
Wall time: 3.45 s
CPU times: user 120 ms, sys: 10 ms, total: 130 ms
Wall time: 131 ms
```

#### 追記
ベクトルではなくリストから取り出したい場合は、**filter** 関数を使う方法があります。
**numpy** を使えない、使いたくない場合はこちらを検討してみましょう。

サンプル内の `lambda x:y` は、`x` を引数に `y` を返す名前の無い関数だと思ってもらえれば大丈夫です。

```py3:Sample.py
x = [i for i in range(10000000)]
%time y = list(filter(lambda x: x % 3 == 0, x))
```
```text:result
CPU times: user 1.67 s, sys: 10 ms, total: 1.68 s
Wall time: 1.68 s
```
**numpy** を使うよりは遅いですが、for文で append回すよりは速いですね！

## Case 5: ベクトルの各要素に関数を適用したい

次はリストの各要素に関数を適用する場合について考えます。
ここでは **map** 関数について紹介します。
これはリスト内の各要素に指定した関数を適用した結果（Python3 だと map オブジェクト）を返す関数です。

また下記の `func` は $x^2 + 2x + 1$ を返す関数です。

```py3:Sample.py
a = np.array([i for i in range(10000000)])
def func(x):
    return x**2 + 2*x + 1

def func1(a):
    return np.array([func(i) for i in a])

def func2(a):
    return np.array(list(map(func, a.tolist())))

%time b = func1(a)
%time c = func2(a)
%time d = a**2 + 2*a + 1
```

```text:result
CPU times: user 5.14 s, sys: 90 ms, total: 5.23 s
Wall time: 5.23 s
CPU times: user 4.95 s, sys: 170 ms, total: 5.12 s
Wall time: 5.11 s
CPU times: user 20 ms, sys: 30 ms, total: 50 ms
Wall time: 51.2 ms
```

map 関数を紹介しておいてあれですが、内包記法とそこまで時間変わりませんでした :cry: 。
あとここまで読んで方は途中で気づかれたかもですが、上記の例の場合は、簡単な関数だったので直接ベクトル演算した方が圧倒的に速いです！

## Case 6: 行列の各要素（数値）を任意のスコア（離散値）に変換したい
ここまでは1次元の配列（ベクトル）を扱ってきました。
以下の例では2次元の配列（行列）を扱ってみたいと思います。

下記のケースでは機械学習などの前処理で各数値をスコアに変換したい場合等を想定しています。
まず以下のような行列を定義します。

```py3
a = np.array([[i % 100 for i in range(1000)] for j in range(10000)])
```

次にスコアに変換するためのリストを用意します。
下記のリストの場合、元の数値が20未満の場合は0、20以上50未満の場合は1、90以上の場合は4
といったように行列内の数値を変換したいことを表しているとします。

```py3
scores = [20, 50, 70, 90]
```

まず頭を空っぽにして素直に実装してみたいと思います。

```py3:Sample.py
def func1(x):
    y = np.zeros(x.shape)
    for s in scores:
        for i in range(x.shape[0]):
            for j in range(x.shape[1]):
                if x[i, j] >= s:
                    y[i, j] += 1
    return y

%time b = func1(a)
```

その結果見事三重ループになりました :innocent: 。
（ループが深いと、遅くなりやすいだけでなく読んでてループ変数を追うのが辛くなりやすいです。人間のためにも深いループはあまり作らないようにしましょう）

関数の中身としては、行列内の各要素ごとに、指定のスコアより大きければ値を1増やしています。




```text:result1
CPU times: user 14 s, sys: 10 ms, total: 14 s
Wall time: 14 s
```

案の定実行時間も**10秒**を超えました :cry: 。

次に、一工夫いれた関数を紹介します。

```py3:Sample2.py
def func2(x):
    y = np.zeros(x.shape)
    for s in scores:
        y += (x >= s)
    return y

%time c = func2(a)
```

やってることは以下の通りです。

*  `x` と同じ形（行列数）をした全て `0` の行列 `y` を用意する
*  各スコア毎に、`(x >= s)` を `y` に足している
  *  `x >= s` は、行列 `x` の各要素に対して、 `要素 >= s` なら **True**、違うなら **False** となる **行列**
  *  同じ形の行列 `n` と `m` に対して `n + m` とすると、各要素同士を足し合わせることになる
  *  `y` の中身は数値であり、数値に対して **True** や **False** を足そうとすると **1** と **0** になる

上記のようにコードは短いですがいろんな要素が入っています。
ですがfor文をガッツリ回さなくなった分 **100倍以上** 速くなりました :smile: 。

```text:result
CPU times: user 90 ms, sys: 20 ms, total: 110 ms
Wall time: 111 ms
```

#### 追記 (2017/08/30)
ここまで来たら「全ての **for** 文を生まれる前に消し去りたい :angry: 」という気持ちが湧くかもしれません。
ですので試しに書いてみました。

```py3:Sample3.py
def func3(x):
    len_score = len(scores)
    y = x * np.array([[np.ones(len_score)]]).T
    s = np.array(scores).reshape(len_score, 1, 1)
    z = (y >= s)
    return z.sum(axis=0)
```

```text:result
CPU times: user 200 ms, sys: 30 ms, total: 230 ms
Wall time: 235 ms
```

・・・遅くなりました :cry: （書き方が悪いせいかも）
こちらは遅い上に、メモリも大量に要するし（先に全部展開してしまうため）、何より分かりづらくなってしまうので無理してまで for 文を消せば良いというものではないことが分かりました。

※ 0次元の配列をスカラー、1次元の配列をベクトル、2次元の配列を行列というのに対して3次元以上はテンソルというそうです。
※ 上記の実装はテンソル計算？によってもっとスマートに書けるかもしれないので詳しい人教えてください :innocent:  

## Case 7: リスト要素への存在チェック(2018/04/20 追加)

最近の記事を見て思い出したのでメモ。

Python ですとある要素がリスト内にあるかどうかを確認したいときは `in` が使えます。

しかしこれをリストに対して適用すると、リストの長さ $n$ に対して $O(n)$ ですので、一歩間違えると事故が起きます。

繰り返し何度も存在チェックを行う場合は、下記のように `set` などで置き換えた方が良いです。

```py:JupyterNotebook(GoogleColaboratory)で確認しました
L = 100000
x = list(range(L))

def sample1(list_tmp):
    j = 0
    for i in list_tmp:
        if i in list_tmp:
            j += 1
    print("sample1 j: ", j)


def sample2(list_tmp):
    j = 0
    set_tmp = set(list_tmp)  # set に変換
    for i in list_tmp:
        if i in set_tmp:     # set 内にあるかをチェック
            j += 1
    print("sample2 j: ", j)
    
%time sample1(x)
print("----------------------------------------")
%time sample2(x)
```

```text:結果
sample1 j:  100000
CPU times: user 1min 7s, sys: 16 ms, total: 1min 7s
Wall time: 1min 7s
----------------------------------------
sample2 j:  100000
CPU times: user 8 ms, sys: 6 ms, total: 14 ms
Wall time: 14 ms
```

## Extra 1 「それでも僕は for文を使いたいんだ」
上ではあれだけ for文使うなと言ってきましたが、
それでも使わざるを得ない、使った方が分かりやすいといった場面はあると思います。

そういった場合は開き直って *numba* を使いましょう。*numba* とはちょっとしたコンパイラです。

「え、コンパイラってことは変数全部型指定するの？コンパイルコマンド打たなきゃいけないの？」

と思われるかもしれませんが、安心してください。1行追加するだけです（`import` 含むなら 2行）。

実際に使用例を見ていきましょう。


```py3

import numba

def sample1(n):
    ans = 0
    for i in range(n):
        ans += i
    return ans

@numba.jit
def sample2(n):
    ans = 0
    for i in range(n):
        ans += i
    return ans

@numba.jit('i8(i8)', nopython=True)
def sample3(n):
    ans = 0
    for i in range(n):
        ans += i
    return ans

%time a = sample1(100000000)  # 何もしない場合
%time b = sample2(100000000)  # jit 使う場合
%time c = sample3(100000000)  # jit(型指定)使う場合
```

上から順に、「何もしていない」「numba 使った」「numba（型指定）使った」
関数です。関数の中は 0 から $n - 1$ までを足して返す関数となります。

型指定については [Python高速化　Numba入門　その2 - tkm2261's blog](http://yutori-datascience.hatenablog.com/entry/2014/12/10/123157) などを参照しましょう。

実行時間は以下のようになります。何もしないと5秒ですが、「numba（型指定）」を使うと 約5.5マイクロ秒になってますね。まさしく桁が違います（この例だと **約94万倍** 速くなりました :innocent: ）。

```
CPU times: user 5.16 s, sys: 0 ns, total: 5.16 s
Wall time: 5.16 s
CPU times: user 30 ms, sys: 0 ns, total: 30 ms
Wall time: 25.9 ms
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 5.48 µs
```

※ 上記の結果は関数定義後の初実行時の結果です。sample2 はコンパイルされたこともあって次回実行時には 6μs 程度で実行できます。それでも sample3 の方がわずかに速かったですが。sample2が初回実行時に時間がかかるのは、おそらくコンパイル時の型推定に時間がかかってるためだと思います。
※ numba は numpy や scipy は対応していますが、pandas は対応していないので注意

# おわりに
いろいろ書いた気がしますが、上記のCase だと「for文使うな」で終わってしまった気がします。
今後は **scipy** とか **pandas** についてもいろいろまとめて載せていきたいと思います。