演算数と高速化

高速化プログラミング   
トップ  > 演算数と高速化

演算数と高速化

■ 演算数と高速化

プログラムは演算の集まりといっても過言ではありません。演算数が多いと当然プログラムが遅くなります。プログラムを高速化する一番手っ取り早い方法はこの演算数を減らすことです。

しかしプログラムを目的となる機能はあります。単純に演算を減らすだけではプログラムがおかしくなり、目的の機能がしなくなります。演算数を減らすときは計算結果を変えないように注意しないといけません。ここでは結果を変えないような演算数の減らし方をご紹介します。

■ 演算の重さ

プログラミングでよく使う演算は多種あります。足し算、掛け算、ビット演算など。さらに数値解析のプログラムを書くときは使う演算の種類がさらに増え、乗算、対数、正弦関数などしばしば現れます。管理者の大学時代の研究では普段知られていないベッセル関数なども使ったことがあります。

CPUはどのように対数や正弦関数など複雑な演算を行うか考えたことがあるでしょうか。実はCPUはビット演算や足し算などの単純の演算しかできません。CPUによっては掛け算できるものもあります。割り算も乗算も対数もCPUは直接計算できません。しかしCやFORTRANなどの高水準言語では簡単に割り算や乗算を計算できます。実はこれらの複雑な演算は簡単な演算の組み合わせで表されてライブラリ化されます。プログラムをコンパイルするときは割り算などの演算は自動的にライブラリから割り算のための関数に置き換えているわけです。

そこで演算の重さという概念が出てきます。CPUが直接計算できる演算はもっとも軽い演算になります。足し算、引き算、ビット演算はこれに当たります。掛け算はCPUによっては専用の機能はあるものの、結局掛け算は複数の足し算の組み合わせで表現されているので、掛け算は足し算より重いです。ほかの演算は足し算や掛け算で表されているので、さらに重い演算になります。表1に演算の軽い順に並べています。

表1 軽い順に並べた演算
演算記号
ビット演算、プラスマイナスの符号変更and, or, not, -
足し算、引き算+, -
掛け算*
割り算/
対数、正弦関数などその他関数化されている演算log, sin, cos, tan

■ 演算数を減らして高速化する

演算数を減らす方法には2種類あります。一つは演算自体を減らすことです。ここでは因数分解など中学数学に習った公式が役に立ちます。もう一つは重い演算をより軽い演算に変えることです。これは一部の演算にしか適用できませんが、適用できればかなり効果的です。ここではサンプルを交えながらどんな方法があるかをご紹介します。知っていると苦労せずプログラムの高速化ができるのでぜひプログラムを書くときは習慣にしてください。



はじめに

演算数を減らす

メモリジャンプを減らす

高性能のアルゴリズム

その他



3 5 2 9 3 7