【高速化しない！？】高速化の観点３選
30年以上プログラマーをしているムンペイです。学生時代に高速化プログラミングにハマり、そのまま仕事にしてしまいました。
高速化と一口に言っても、高速になってほしい部分によっていくつかに分類ができます。目的をしっかり分類することで適切なアプローチを選ぶ助けになります。私が高速化を考える場合に用いる観点を３つご紹介します。
1. 大量のデータ処理を短時間で処理する
大量のデータを扱う場合は、データ並列のアプローチが効果的です。もっとも高速化の成果が出やすく、楽しく取り組めるパターンです。並列処理、データ構造の選択、アルゴリズムの最適化を行います。
計算機を多数使って計算を同時に実行する並列処理は、最もわかりやすい概念だと思います。マルチスレッドという言葉でよく耳にすることでしょう。なお、マルチプロセス、マルチノードなど少し違う用語もありますが、計算機の物理的な形態が違うだけで並列処理としての考え方はよく似ています。
この方式は、物理的に計算機を多数用意する必要があります。今どきのＰＣならば16並列くらいまでは内蔵していますが、それ以上は特別な（高価な）ＰＣ、サーバーの世界に入ってきます。スーパーコンピュータは並列度のお化けで、10万個以上の計算機（コア）を内蔵しています。
データ構造の選択は極めて重要です。計算を速くするためには、データの準備で計算機を待たせないということが必要です。必要なデータをすぐ取り出せるデータ構造を考えましょう。よく使われるのは、ハッシュテーブル（Pythonならば辞書、セット）や木（Pythonの標準にはないが、networkxなどのライブラリがある）でしょう。しかし、データサイズが均等でかつ連続的なアドレスでアクセスができるなら（線形）リストが最も高速でしょうし、処理を待ち行列で管理するといった場合はキュー（Queue、FIFOとも）も有効です。データ構造は書籍などで一通り目を通しておくとよいでしょう。
そして、最も効果的なのは、適切なアルゴリズムの選択です。同じことをするのに計算の回数が少なく済むなら、それに越したことはありません。少し学術的な部分でもありますが、一般のプログラマと高速化プログラマの違いが最も現れる部分と言えるでしょう。
2. 多くの工程からなる処理を早く終える
多くの工程を経て処理が完了するというケースを高速化したいでも、基本的には大量のデータ処理と同じ並列処理、データ構造、アルゴリズムの強化が必要なのですが、前の工程が終わってから次の工程を行うという依存関係があるため少し違うテクニックが必要です。
このケースは工程の依存関係を明確にすることから始めます。
そして、不要な工程がみつかれば削除します。必要な工程は、データ構造の見直し、アルゴリズムの最適化を行い、工程自体の時間短縮を行います。
次に依存関係がある工程をできるだけ減らします。うまく工程を分割したり統合したりすることで、依存関係を変えることができるかもしれません。依存関係がない工程は、並列処理が実行できます。違う工程を並列処理することをタスク並列といいます。
ここまでが１回分の処理に行える工夫ですが、もし「多くの工程を経て完了する処理」が多数ある場合は、それぞれを並列処理すればよいでしょう。
3. いったん応答する
レスポンスタイムと呼ぶこともあります。
このケースは、ユーザーエクスペリエンスの向上の側面が強いものになります。人間が待てる時間はせいぜい数10秒程度で、それ以上は集中力が切れて他のことに気持ちが移ってしまうでしょう。
前述の１と２が達成された結果として数10秒程度の範囲に収まるようになれば最もよいですが、そんなに早く終えられる処理ではない場合は人間を待たせない別の工夫が必要です。
この時に利用できるのが非同期処理の考え方です。コンピュータが計算に全集中してそれ以外には利用できなくなるのが同期処理ですが、計算は裏で実行し続けつつも他の処理も受け付けるようにするのが非同期処理です。
例えていえば、フリーレンがマハトの呪いを解析していたのが非同期処理です。解析をはじめてから２ヶ月間だんまりになってしまうと、待つ側も不安が募りますし、ほかの用事があったときに困ります。そこで、フリーレンは解析に能力を回したものの、喋ったりご飯を食べたりはできるように残していました。（しかし、間に合わず最後は同期実行に切り替えましたが）
計算時間（解析時間）の観点からは、能力をフル投入していない分延びてしまうのですが、コンピュータ（フリーレン）がその他のタスクに応答できるため、計算が終わったら知らせることもできるため、計算をお願いした側の時間を拘束を減らすことができます。
必要なことを必要なだけ組み合わせる
基本はデータ並列で述べた３つの技術です。複数の工程からなる長い処理の場合はタスク並列を検討します。工程間の依存関係を洗い出し、並列に実行できるところは並列に行います。各工程の時間短縮も行います。それでも応答までが長い処理は非同期処理にして、コンピュータから人間が離れることができるようにするとよいでしょう。
結局は、必要な処理を必要な分組み合わせるということです。何か１つのテクニックでいつも課題が解決するということはないですし、すごいコンピュータが１つあればということでもありません。
プログラマとしては、トリックのような巧いやり方で計算をこなすマジックのような方法こそが、グッとくるなぁと思っているのですが、この話はまたの機会に・・・。
これにて御免！
サポートのご検討ありがとうございます。 いただいたサポートは Code & Magic の開発運営などに使わせていただきます！