プログラムの高速化の話

後輩にどんな内容でもいいから書けといわれた。
ちなみに、11月末の方に発表があるんで将棋の話などしてる余裕は基本ありません。
っていうか、何もしてないような感じなので書きようもありません。

と、いうことで、今最近学んだプログラムを高速化する方法に関して簡素に書きます。
使える人もいるかも?・・・まぁ。ほぼ使わないでしょう。


****演算子の高速順****

コンピュータは、基本的に加算しかできません。
本当の話ですよ?

でも加算が使えれば、乗算が使える。
a × b  → (aをb回足しただけ)
例 : 5 × 3 = 5 + 5 + 5 = 15

同様に減算ができれば、除算も。
a÷b → (aがb以下となるまでbを引いた回数)
例: 16÷4 → 16-4=12(1回目) 12-4 =8(2回目) 8-4=4(3回目) 4-4=0(4回目) 0は4未満なので終了。

同様に拡張すれば、対数、べき乗もできます。

ちなみに、これだけでは整数しかでませんが。
実数はちょっと拡張すればできます。


で。なぜこんな話をするのか?一般的に、演算子には難しさが存在します。

(簡単)ビット演算・シフト演算子 → 加算・減算 → 乗算 → 除算・乗除 → 累乗・平方根・三角関数など(難しい)

で、この難易度は、計算の速度に関わってきます。
もちろん。100回くらいの計算なら、どのように書いたって基本的には変わりません。

高速なプロセッサ、例えば自分のCPU(Intel Core i7 3770K 3.5GHz)とかだったら、理論上1秒間に
0.2857ナノ秒×(演算子の単位当たりの命令量)で1命令を実行します。
加算一回であればナノ秒レベル。そんなの100回やっても何百ナノ秒です。
すぐ終わります。

しかし。例えば。通常意味のある計算は、一回の演算では終わりません。
例えば5個の要素の平均を求めるには?
(x0+x1+x2+x3+x4)÷5
つまり。加算4回、除算1回というふうになるわけです。

難しいものを計算しようとすればするほど、一回あたりの計算も増えて。。。。
これを仮に10000回やって。。。
このように多くの繰り返し処理になると、単位当たりの計算時間の高速化が大きな効果をうみます。


例えば。
x^3 + 3x^2 + 3x + 1 = (x+1)^3
について考えてみましょう。

左辺 = x^3 + 3x^2 + 3x + 1 = x*x*x + 3*x*x + 3*x + 1
つまり、乗算5回、加算3回。

右辺 = (x+1) * (x+1) * (x+1)
乗算2回、加算3回(x+1は同じ変数に入れれば加算は減ります)

この動作をN回繰り返すとすれば、左辺と右辺では同じ式ですが
プログラムの速度は (一回当たりの高速率)*N 早くなります。


このテクニックは因数分解の話だけではない。
例えば、演算子の難しさは。乗算<除算 なので
さきほどの平均値なんて、(x0+x1+x2+x3+x4)÷5 より
(x0+x1+x2+x3+x4)×0.2 の方が少し早い。


まだまだあります。
ビット演算子というを最初でいいましたが。(1100(12)は、2進数で1100で10進数で12ってことです。)

これらは、**ビットごと**にAND演算(1と1のときのみ1)、OR演算(1が少なくとも1個あれば1)などを行う演算です。
例えば、 1010(10) と 1100(12) のビットAND演算だったら、ビットごとのANDなら
は、1000(8)となります。

こんなわけわからない演算をどこで使うかって?
いやいや、普通に今見ているインターネットでも使われてますよ?
コマンドプロンプトを開いて、
ipconfig
って打ってみりゃネットワークに関する設定が出てきます。ここのサブネットマスクってので使われていますよ!

ま、簡単にいえば、IPアドレスに関するもんです。
なら、始めっからそう言えって?
すいません。


あと、シフト演算。
これは、桁をシフトする演算。1010(10)を1ビット右シフトすると 101(5)。
逆に1ビット左シフトすりゃ。。仮に正の数なら、10100(20)になります。


これらを使えば、奇数か偶数か判断したいときに楽になる。

普通の人が思うのは、あるxを2で割った時の余りが0なら偶数!1なら奇数!っていう回答。
しかし、それには乗除を用いなければいけません。

しかし。実際はビットAND演算一回だけでいけます。(例:N(確認する数) bitAND 1 → 0(偶数)か1(奇数))


他には。2^iで除算とか乗算とか。
これらは、たった1回のシフト演算だけでいけます。iビット右シフトすれば2^iで除算、
左シフトなら2^iで乗算になるのだ!

あ、もちろんそれ以外はめんどくさいことなるけどね?
まぁ、6の乗算くらいなら、6*N = (4+2)*N = 4N + 2N 使えば結構簡単になるけどね?



さてさて!
これ以外にもあるけど、キリがないので!

ここで、ある程度ぶっちゃけたこと言いますと、
ある程度は実は、コンピュータが最適化してくれます。
まぁ、ここまで出た一部はやってくれちゃうんですね。勝手に。


じゃあ、こんな知識いらないじゃないかって?


ノンノン♪


例えば。コンピュータは言われたことしかできないから、
例えば、さっきいった2^iで割られるかどうかなんて、知ったこっちゃない。
(だって、仮に違ってたらプログラム自体が書き換わってしまう。)


つまり、この部分はプログラマーの腕の見せどころなんですね。
ちなみに、高速化としては、こんなの氷山の一角です。

他には、
1. マルチコアを生かした並列処理
2. メモリの局所参照性を生かしたデータ構造
3. ループの内部の最適化・並列化
4. よりよいアルゴリズム(計算順序・計算方法)の開発

とかがある。
こういうのは、プログラムする言語にも依存してしまうし、コンピュータの構造にも依存してしまう。
特にマルチコアを生かした並列処理なんて、全体のデータの在り方を見直す可能性すらありえる。


3Dのゲームのプログラマーを私がすごいと思うのは、自分が作った高々6万回程度の計算を繰り返し行うプログラムですら、苛立ちを覚える反応性の悪さを生み出してしまう。
それに比べ、現在のデスクトップパソコンのモニターの主流は1920×1080=207万3600個の画素を更新し続けていても、それ相応に反応性の良いゲームを実現する。
いくらビデオカード(グラフィックボード)が高速でも6万とは比べ物にならない。


ゲームクリエイターになろうとは思わないが、この技術だけはいづれ手に入れてみたいものではある。
スポンサーサイト

COMMENT

- 山口孝志華 #mQop/nM.

わかるなぁ~

2012.11.21(Wed) 09:37 | URL | EDIT

TRACKBACK

↑
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。