FizzBuzzっぽい何かから入る高速アルゴリズム?
このページは私が作ったいくつかのFizzBuzzっぽいプログラムの実行時間を比較するページです。
結果としてはやっぱif文(goto)や割り算が少ないほうがいいです。
1章 What is FizzBuzz？
＞http://ja.wikipedia.org/wiki/Fizz_Buzz
俺的には牛タンゲームの亜種（牛タンゲームが亜種？）
世界のなべあつも亜種らしい。
2章 What is important for FizzBuzz?
この前、FizzBuzzプログラムで大切なものとは何でしょう？と友達話してました。
もちろん答えは実行時間の短さ、なぜなら速度もまた特別な存在だからです。。
3章 comparison
プログラム方法によって実行時間がどう変わるのか比較してみました。(C言語)
一つ目のプログラムはすごい単純なやつ
二つ目は一つ目の改良
三つ目はバカ実装
1つ目のプログラム
ループごとにif文(goto文)3回、割り算4回ある。
#include <stdio.h>
int main(){
int i;
for(i = 1; i<1500000000; i++){
if(i%3==0){
printf("fizz");
}
if(i%5==0){
printf("buzz");
}
if(i%3 != 0 && i%5 != 0){
printf("%d",i);
}
printf("\n");
}
return0;
}
2つ目のプログラム
1つ目と比較したメリット:
ループごとのif文は3回のままだが、割り算が2回に減る（比較処理も1回減っている）。
#include <stdio.h>
int main(){
int i;
int Print_num=0;
for(i = 1; i<1500000000; i++){
if(i%3==0){
printf("fizz");
Print_num=1;
}
if(i%5==0){
printf("buzz");
Print_num=1;
}
if(Print_num==0){
printf("%d",i);
}
printf("\n");
Print_num=0;
}
return0;
}
3つ目のプログラム
2つ目と比較したメリット:
if文がなくなった(gotoが減った？)
割り算もしない
ループ回数も減る(メリット？)
2つ目と比較したデメリット:
空間的局所性とか減る（かわらんかな？）
15の倍数になるまでプログラムは動き続けるwww（馬鹿な実装）
このプログラムはもはやFizzBuzzなんだろうか？
#include <stdio.h>
int main(){
int i;
for(i = 1; i<1500000000; ){
printf("%d",i);//1
printf("\n");
i++;
printf("%d",i);//2
printf("\n");
i++;
printf("fizz");//3
printf("\n");
i++;
printf("%d",i);//4
printf("\n");
i++;
printf("buzz");//5
printf("\n");
i++;
printf("fizz");//6
printf("\n");
i++;
printf("%d",i);//7
printf("\n");
i++;
printf("%d",i);//8
printf("\n");
i++;
printf("fizz");//9
printf("\n");
i++;
printf("buzz");//10
printf("\n");
i++;
printf("%d",i);//11
printf("\n");
i++;
printf("fizz");//12
printf("\n");
i++;
printf("%d",i);//13
printf("\n");
i++;
printf("%d",i);//14
printf("\n");
i++;
printf("fizzbuzz");//15
printf("\n");
i++;
}
return0;
}
まとめてiをi=i+15で増やしたり、printf2つをまとめてprintf("fizzbuzz\n")
にしないのは、極力他のプログラムと同条件にして、if文とわり算だけを減らすためです。
4章 比較条件
OS:Unix,CPU:Sandy-eのi7 Memory:多い(ようは調べんのめんどいw)
実行結果は10試行の平均をとっています。
printfでボトルネックになるのが嫌なため、上記からprintfをコメントアウトし、実行時間を測る関数追加したもの。
つまり１つ目のプログラムはこうなる。
#include <stdio.h>
#include <sys/time.h>//unixで時間測る
inlinedouble get_dtime(void){//unix専用の命令
struct timeval tv;
gettimeofday(&tv, NULL);
return *1;
}
int main(){
double time1=get_dtime();
int i;
for(i = 1; i<1500000000; i++){
if(i%3==0){
//printf("fizz");
}
if(i%5==0){
//printf("buzz");
}
if(i%3 != 0 && i%5 != 0){
//printf("%d",i);
}
//printf("\n");
}
double time2=get_dtime();
printf("%f usecond", time2 - time1);
printf("\n");
return0;
}
ついでに3つ目はもはやfizzbuzzでもなんでもない。。たんなるi++するだけになる・・
こんなのってひどすぎる・・・
#include <stdio.h>
#include <sys/time.h>//unixで時間測る
inlinedouble get_dtime(void){//unix専用の命令
//上と同じなため省略
}
int main(){
double time1=get_dtime();
int i;
for(i = 1; i<1500000000; ){
//printf("%d",i);//1
//printf("\n");
i++;
//printf("%d",i);//2
//printf("\n");
i++;
//printf("fizz");//3
//printf("\n");
i++;
//printf("%d",i);//4
//printf("\n");
i++;
//以降省略wwwww
5章 consequence
単位はμ秒(だったかな？)
1つ目のプログラム：8052521.60
2つ目のプログラム：5429244.10
3つ目のプログラム：2444246.80
やっぱ割り算やif文ない方がダントツ早いです。
P.S.
いま気づいたけど3つ目のプログラムだけ１回多く処理してますね（1,2つめのプログラムはi==150000000のとき動いてないけど、3つ目だけ動いてる）1つ目と2つ目にプログラムを
for 文をfor(i = 1; i<=1500000000; i++)にすべきでした
あと、最適化オプションつけないでコンパイルしてるけど、最適化されてたりしないんだろうか。。
（追記）
そういえば，コンパイラオプションで，アセンブリ言語でコンパイル止めれましたよね．それでどの程度最適化されてるかわかるか・・
*1:double)(tv.tv_sec)*1000*1000 + (double)(tv.tv_usec
