forループを使わない【高速化】"boolean行列"を使おう！

forループの中にforループを連ね（いわゆるネスト）、さらにそこでif文を使うなんてことはやたらと時間がかかるため、やってはいけない、と言われている。

やってはいけない、ということは知っているけど、

「じゃあ、どうすればいいの？」と、GPUに逃げ、見てみぬふりをしてきたのですが、そうも言ってられない状況になりましたので、同僚に教えていただきました。

追記（2020年8月31日）

内容に関してよりわかりやすい説明の加筆・修正を施したものを以下で公開しました。ぜひこちらもご覧ください！

やりたいこと：特定のクラスごとに得点の合計点を求めたい！
（例えばk平均法）

Klass  = [0, 1, 2, 3]
temp_K = [3, 1, 1, 3, 2, 0, 0, 0]
value  = [0, 1, 0, 1, 0, 1, 0, 1]

状況としては上のように、8の長さの配列が2つあり（temp_Kとvalue）、temp_Kは各インデックスごとのクラスを保持し、temp_Kとvalueのインデックスは連動している。

この時、求めたいものは以下となる。

[2, 1, 0, 1] # インデックスがクラスに対応

これをforループを2つ使い、さらにifを使って書くと、

#in python
for i in range(len(Klass)):      # クラスの数だけループを回し、
   for j in range(len(temp_K)):  # そのループごとにtemp_Kの中身を参照 
       if (temp_K[j] == i):      # その値がi (あるクラス値)と同じなら
           total[i] += value[j]  # そのインデックスに対応するvalue値をその都度加える

このようになるかと思います。

これを高速化のためにforループもif文も使わないで書いてみよう、というのが本エントリーの主旨です。

"boolean行列"を使おう！

だらだらと文字で書くよりも具体例の示した方が早いので、以下です！←

|0 0 0 0 0 1 1 1|
|0 1 1 0 0 0 0 0| * |0 1 0 1 0 1 0 1|.T = |2 1 0 1|.T
|0 0 0 0 1 0 0 0|　　　↑ value配列の転置　　　　↑ 求めたかったもの
|1 0 0 1 0 0 0 0| ← temp_Kを基に"boolean行列"を作成。行がクラスに列はデータのインデックス

pythonコード
（Jupyter Notebookで書いたものの画像）

余計なものが含まれていますがあしからず（わかりやすさを重視しました）。。。ご容赦ください。

あまりにもデータ数が小さいとパッとしないのでデータ数は1000万、クラス数は5としました。

547ms * 547ms = 299209ms ≒ 29. 9 s ですから計算量はforループ+if文の場合はO(N^2)で"boolean行列"はO(N)となるかと思います。

ずいぶんと速くなりました！