If文なしで2値のmax関数書ける?Python数値計算の高速化

小さなテーブルに花束を
こんにちは。土曜の午さん会より神長です。
個人でもnoteを運用しているのでぜひいらしてください。

小さなテーブルに花束を/神長広樹｜note

僕たちは“土曜の午さん会（仮）”と称して、毎週土曜日15時オンラインにて勉強会を内々で行っています。会の質を高め、振り返りとして記録に残すためにもこの度毎週noteに会の様子をまとめていく運びとなりました。第一回目の本稿は「pythonでの数値計算の高速化」をテーマにしております。よろしくお願いします。

ケース1：If文なしでmax関数書ける?

はじめに後述の導入としましてタイトルにありました問の答えを見ていきたいと思います。ここでいうmax関数とは今回は

「引数として2つの数字を受け取り大きい方を返す」

関数と限定させていただきます。

さて、If文を使っても良い、となれば答えはこうなるかと思います（else文もアリの場合）。

def larger (num1, num2):
    if num1 < num2:
        return num2
    else:
        return num1

早速答えになりますが、If文を使わない場合は以下のようになります。

def larger_WO_if (num1, num2):
    return (num1 > num2) * (num1 - num2) + num2

どうなっているのか?
答えのポイントとしては型変換を行い、2値の比較真偽値booleanを数値に変換することによってIfでの場合分けの代わりを務めることです。

pythonでは上記のようにboolean型と数値の対応は「True→1」、「False↔0」となっています（数値からboolean値への変換は0であればFalseに、0以外であればTrueになります）。return文の（num1 > num2）の部分がこれに相当します。言語によってはfloat（num1 > num2）のように明示的に型変換を宣言する必要がありますが、pythonではよしなに対応してくれます。

以下では具定例を通して、その先を見ていきます。

# 引数が（2,3）の場合
(num1 > num2) * (num1 - num2) + num2
= (2 > 3) * (2 - 3) + 3
= (False) * (-1) + 3
= (0) * (-1) + 3
= 3

# 引数が（3, 2）の場合
(num1 > num2) * (num1 - num2) + num2
= (3 > 2) * (3 - 2) + 2
= (True) * (1) + 2
= (1) * (1) + 2
= 3

引数の順番に関わらず計算結果はしっかりと大きい方が採択されますね。ポイントとしては「大きい数は小さい数との差に小さい数を足したもの」という「辺の移行」を使うことです。

num1 + num2 = num1 + num2
num1 = num1 + num2 - num2
num1 = (num1 - num2) + num2

そして、この（）の部分を採択するかしないかをbooleanで判断しています。このレベルではまだ算数の範囲ですが、数値計算の高速化を達成する上で重要なことは「如何にしてコードの中に数学を忍ばせるか」、そしてそれにより、「如何に計算しないか（ループ等を回さないか）」に尽きると思っています。

落とし穴

導入のためとしてタイトルにある問と答えを解説して来ましたが、実はこの例ではIf文使ったほうが計算時間的にも速いです。。。

If文なしのほうが1.5倍ほど余計に時間がかかっていますね。。。ここでは

「If文はbooleanを型変換することで対応できることもあるよ！」

ということを伝えたかったので見逃してください。次の例でその真価をご覧いただけるかと思います。

ケース2：クラスごとの合計値

以下のような行列（表）があるとします。

| 3 0 |
| 1 1 |
| 1 0 |
| 3 1 |
| 2 0 |
| 0 1 |
| 0 0 |
| 0 1 |

1列目はクラス番号、2列目は値を表しています。例えば1行目ですと「クラス番号：3、値：0」といった感じです。今、問題としては「クラスごとの値の合計値」を求めたいとします。

なお、答えは[2, 1, 0, 1]です。それぞれのインデックスがクラス番号に対応してます。これを問題文そのままpython（numpy使用）で書くと以下のようになるかと思います。

ans = np.zeros(4)              # 答えを入れる箱を用意
for i in range(len(mat)):      # matは上記の行列。その長さ8回分ループ
    ans[mat[i, 0] += mat[i, 1] # クラス番号はインデックスに対応

これをForループを使わずに書いていきます。ポイントとしてはOne-Hot表現（ダミー変数）を使うことです。One-Hot表現と言えば機械学習でよく使います（余談ですが、ケース2の問題設定はK平均法に似せました）。機械学習の分野ではカテゴリーデータを数値に変換する際によく使用されます。今回の例ですと。。。

# mat１列目のクラス番号[3 1 1 3 2 0 0 0]に対応するOne-Hot表現
[[0 0 0 1],
 [0 1 0 0],
 [0 1 0 0],
 [0 0 0 1],
 [0 0 1 0],
 [1 0 0 0],
 [1 0 0 0],
 [1 0 0 0]]

1行目のクラス番号は3でした。これはOne-Hot表現だと、「インデックス3の部分だけ1」に相当します。つまりOne-Hot表現とは「各行において、対応するインデックス1つ（One）だけ発火（Hot）している状態」のことです。なおpython（numpy）ですと

np.eye(len(mat), 4)[mat[:,0]]

だけで上記のmat1列目に対応するOne-Hot“行列”が得られます。

すると、求めたい合計値は

np.matmul(np.eye(len(mat), 4)[mat[:,0]].T, mat[:,1])

で求めることができます（.Tは転置の意味）。行列の中身を書くと以下の通りです。

|0 0 0 0 0 1 1 1|   |0|   |2|
|0 1 1 0 0 0 0 0| X |1| = |1|
|0 0 0 0 1 0 0 0|   |0|   |0|
|1 0 0 1 0 0 0 0|   |1|   |1|
                    |0|
                    |1|
                    |0|
                    |1|

いかがでしょうか?Forループを使わずに実質的な計算も一行でスッキリとまとまっています。実行時間を図ってみましょう。

...って、あれ??? 遅いじゃないか!って？。。。
安心してください。対象の行列が100行にもなれば一気に逆転します。

1000万行にもなれば圧倒的な差を生みます。

まとめ

今回はpythonを使って具体的に数値計算の高速化を見てきました。まとめポイントとしては

・If文は0/1に変換できないか検討する
・Forループは行列として1度に処理できないか検討する
・両者の組み合わせ、特にOne-Hot“行列”のような0と1で構成される行列（他の例として隣接行列なども）を利用できないか検討する

が挙げられるかと思います。場合によっては上・下三角行列など特殊な行列を利用できる場合もあり、さらに計算量を減らし、高速化できることもあります。これらは特にpythonに限った話ではありませんが、Jupyter Notebookなどのインタラクティブな実行環境はこういう気づきを与えてくれるので試行錯誤の段階ではpython x Jupyter Notebookがおすすめです。

投稿が「ためになった」、「面白かったよー」と思っていただけましたら、ぜひ「スキ」を押していただけると励みになります。シェアもしていただけたら有頂天です！