寒いのが苦手なバスクリンです。
今日はプログラムのパフォーマンスとオーダ記法についてざっくり書いてみようと思います。
パフォーマンスは作る人によって変わる
ことの発端はあるログ解析のプログラムをチームメンバーに依頼したことでした。業界経験も豊富なこのエンジニアさんに2日かけて組んでもらいましたが、解析終了までに15分かかりました。期待していたパフォーマンスではなかったため、一から一緒にペアプロして2時間で完成、所要時間は6秒で終わりました。
また、前の会社の上司が作ったバッチ処理が1時間以上かかるので、作り直して欲しいと依頼があったので作り直してみると0.6秒になりました。
どちらの方もそれなりに経験豊富な世間一般にSEと言われる人たちですが、作る人が違うとここまでパフォーマンスは変わります。
二人に共通していることは、書籍やネットを見て勉強して言われたことは作れるが、データ構造やクラス設計、自分の書いたプログラムがどれくらいの計算量になるかイメージができていなかったことです。また、二人の作ったコードは、要求に対して非常に複雑でした。複雑ということは当然バグや考慮漏れも多く混在しています。
こんなSEにシステムを依頼すると、モノはできたが使い物にならないくらい遅いという結果になります。では、そんなエンジニアにならないために、どのようなことに気をつけて設計・開発すれば良いか考えてみましょう。
パフォーマンスの良いコードを書くためには
いきなり乱暴な言い方をすれば、「どのようなアセンブリになるか考えて組めば遅くはならない」です。簡単に書きましたが、これはかなり難しいことです。
自分の書くプログラムがどのように翻訳され、どのようなアルゴリズムが使われて、どのような最適化がされて、実際のメモリ配置がどのようになるか。これらを考えて設計することになります。
データ構造とアルゴリズムの選択でパフォーマンスは劇的に変わります。私がまずコードを書く前は、要求されている仕様について、どれくらいの計算量とメモリの使用量のコストがかかるか概算します。その後で、どのようなコンポーネント設計やレイヤー設計、クラス設計をして、どのような関数や変数、使用するデータ構造を用意するかを考えていきます。
お客様の要求を満たす、良い品質で作るは当たり前です。それを踏まえた上でコストパフォーマンスの良いシステムを構築できるのが良いエンジニアだと思います。
書籍やネットからの受け売りの理解や知識だけで設計・コーディングをする人がいますが、その奥にどのような処理があるか理解をしないで組んでしまう人はちょっと要注意です。
データ量とオーダー記法
オーダー記法はランダウの記号と言い、主要な記号O(オーダーのO、オミクロン)を使うことから「オーダー記法」と呼ばれています。
「どれくらいの計算量かをざっくり表す」記号です。
計算機科学、アルゴリズム論、暗号理論ではよくこのオーダー記法を用います。
情報システムでは、以下のオーダー記法がよく用いられるので覚えておきましょう。
記号中に出てくるNはデータ量になります。
O(1)定数時間
データ量に依存せず1回で終わる処理。
配列の添え字によるアクセスや連結リストの追加・削除がこれに該当します。
O(N)線形時間
データの量に影響される処理。データ量が増えると増加します。
配列の探索がこれに該当します。For文で全要素を走査する場合はこれに該当します。探索より、生成した順番が重要になるような配列はこちらを使用します。
O(logN)対数時間
データの量にあまり左右されず、少ない回数で終わる処理。
二分木やAVL木の探索などががこれに該当します。これらのコンテナは一般的に追加・挿入時にコストが発生しますが、高速な探索ができるので、探索処理が多い配列はこちらをよく使用します。
O(NlogN)準線形、線形対数時間
データの並びに関係なくある程度の計算量を確保できる処理。データ量に影響されます。
ヒープソートや高速フーリエ変換、最近のソートでよく採用されているデータ分布を数回の探索で求めてから並べ替えのアルゴリズムを切り替えるイントロソートなどがこれに該当します。
探索速度は最速ではないですが、最悪計算時間を抑えることができるのが特徴です。
O(N^2)二乗時間
同じ要素からすべての組み合わせを抜き出すような処理。
挿入ソートやバブルソート、離散フーリエ変換がこれに該当します。事前に前処理を行っておくことで高速化が期待できたりします。
O(N^3)多項式時間
三重のループを伴う配列の操作。
画像の拡大・縮小や回転などをするような行列計算を必要とする処理がこれに該当します。普段あまり気にしない処理の向こう側で走ってったりします。
O(N!)階乗時間
全ての組み合わせによるNの階乗に比例する処理。
巡回セールスマン問題の総当たり法などがこれに該当します。
まとめ
いかがだったでしょうか？これらのパフォーマンスに関わる部分は、普段は言語やライブラリの奥で処理されるため、普段のプログラムではあまり意識しないことが多い部分です。ただし、言語や使用しているフレームワークがバージョンアップすると、裏でこっそり変わったりしています。
近年ではこのアルゴリズムにもキャッシュや分散化の考えが進み、イントロソートやOracle Exadataのような分散化ストレージ管理も登場しています。普段あまり気を付けていない配列やソートアルゴリズム、探索や追加・削除処理でも、正しいものを選択すると大きなパフォーマンス改善につながります。
自分の書いたプログラムが遅いなと感じた場合は、このオーダー表記を思い出して、どれくらいの計算量が妥当で、それに合ったデータ構造とアルゴリズムが使えているか見直してみましょう。
