読者です 読者をやめる 読者になる 読者になる

FutureInsight.info

AI、ビッグデータ、ライフサイエンス、テクノロジービッグプレイヤーの動向、これからの働き方などの「未来」に注目して考察するブログです。

アルゴリズムチューニングについての私的メモ

メモ

「珠玉のプログラミング」を読み終わったので、私的メモ。
http://www.amazon.co.jp/exec/obidos/ASIN/4894712369/
まず、アルゴリズムチューニングについて。以下のことを最低気にしながらコードを書く。特にオーダーについては常に気をつける。

  • 過去の変数の状態を記録することで再計算を避ける。
  • データを前処理してまとめる。部分配列、計算可能な部分はまとめて計算しておき、違う配列で保持しておく。
  • 「分割して征服アルゴリズム」を意識する。巨大な配列は分割して処理する。特に検索、最大値探索は、細かくしてものを計算し、次に分割した配列をまたがっているものがあるか調べる。
  • 「走査アルゴリズム」を意識する。オーダーをO(n)にするキーとなるアルゴリズム。多くのO(n)のアルゴリズムは走査アルゴリズムのテクニックを利用している。走査アルゴリズムとはつまり、「分割して征服」アルゴリズムと過去の変数の状態を記録するテクニックを利用し、常に最小の単位で分割を行うアルゴリズムである。
  • アルゴリズムの実行時間が常にこれより下がらないことを意識する。複雑な問題では、これは難しいが、上記のことを意識することで、O(n)の単位までアルゴリズムを改良したとき、そのアルゴリズムは最速である可能性が高い。といか、O(n)まで下がったら、あとはそこまでがりがりにチューニングするより可読性を重視する。STLの各アルゴリズムのオーダーはEffective STLに書いてあるので、チェックするとよい。