FizzBuzz 2つのパターン
- FizzBuzz 2つのパターン
- いざベンチ
- まとめ
- コード
- コンパイルオプション
- IO が遅いと id:Haaaa_N さんから指摘があったので試してみた
- Nim の文字全列連結版をもっと速く(情報提供 id:ytqwertyさん)
- id:siphilia さんが色々速くしてくれた結果 Rust がなんだか速い
- utaymd さんがやってくれました Nim で爆速に
- fujita nozomu さんの文字列連結板 C が Nim、Rust を置いてけぼりに
- fujita nozomu さんのコードがさらに謎の速さの領域へ
- 今のところの最速コード C言語
3で割り切れる場合は Fizz、5で割り切れる場合は Buzz、3と5で割り切れる場合は FizzBuzz、それ以外は数字を表示すると言う FizzBuzz の書き方って大きく分けて2種類ありますよね。
その2つのパターンを粗暴なプログラマーにオススメな言語だけど殆どの人達が見たこともないであろう Nim で書いてみます。
まぁやってることが簡単なんで言語が違えどわかりますよね。
1つは愚直に全ての条件を書いてしまうパターン。
let n = 600_000 for i in 1..n: if i mod 3 == 0 and i mod 5 == 0: echo "FizzBuzz" elif i mod 3 == 0: echo "Fizz" elif i mod 5 == 0: echo "Buzz" else: echo i
もう1は文字列連結を使って条件の被りを回避するパターン。
let n = 600_000 for i in 1..n: var str = "" if i mod 3 == 0: str = "Fizz" if i mod 5 == 0: str &= "Buzz" if str == "": echo i else: echo str
Wikipedia の例だと数値を出力文字列に代入しちゃってますが、なるべく軽くするために代入を避けるべく条件分岐で数値と文字列を吐き分けるているのがクソどうでも良いこだわりだったりします。
自分的にはこちらの方が好みなんですよね。なんか同じ条件を書くのが嫌なんですよ。わかります?この感覚。
前者の方はどうしてもバカっぽく見えちゃいます。見づらいですし、条件変える時に2箇所いじる必要ありますし。良い事無い気がするんですよね。
でも前者はモジュロ演算が2個多いとは言え文字列連結が無い分はえぇんじゃなかろうか?
気になっちゃったのでベンチしてみました。
いざベンチ
独断と偏見で前者を「愚直」、後者は「エレガント」として表記しています。
1回目
言語 | 愚直 | エレガント |
---|---|---|
C | 0.06 | 0.07 |
Crytal | 0.33 | 0.34 |
Perl | 0.35 | 0.38 |
Nim | 0.37 | 0.40 |
Rust | 0.44 | 0.48 |
PHP | 0.51 | 0.48 |
golang | 0.59 | 0.76 |
Ruby | 0.61 | 0.75 |
Node.JS | 13.59 | 13.73 |
2回目
言語 | 愚直 | エレガント |
---|---|---|
C | 0.07 | 0.08 |
Crytal | 0.35 | 0.36 |
Perl | 0.35 | 0.36 |
Nim | 0.37 | 0.38 |
Rust | 0.46 | 0.49 |
PHP | 0.49 | 0.47 |
golang | 0.62 | 0.72 |
Ruby | 0.60 | 0.84 |
Node.JS | 13.23 | 13.36 |
うーん、さすがに前者の方が若干早いですね・・・っておいPerl。
なんであんたが Crystal と競って Nim と Rust、golang より早いねん。コンパイルされてるやつらが負けるとか無いでしょ。
と言うか C との速度差はなんですか。不甲斐なさ過ぎでしょう。Rust なんて PHP といい勝負しちゃってますし golang に至っては負けちゃってます。あぁ情けなや。
Ruby と Crystal は同じコードですがさすがに倍以上 Crystal が早いですね。ですが Crystal はコンパイル速度が気絶するほど遅いんですよねぇ・・・そこがネック。
つぅか Node.js よ、お前どうなっとんじゃ。しゃれにならんでしょ、これ。v8.0.0 でやってたのでバージョン上げりゃ速くなるかなと思い v8.2.1 に上げてみましたが変わらず、と言うかむしろちょっと遅くなると言うね。
何がダメなんだろうかと思ってちょっと調べたら console.log がダメな模様。process.stdout.write に変えてみました。
言語 | 愚直 | エレガント |
---|---|---|
Node.JS(write) | 5.81 | 5.45 |
Node.JS(write) | 5.44 | 4.92 |
おおー!倍速くなった!ってやっぱおせぇし。他と比べて10倍遅いですからね。こう言う処理は Node.js 使うなって話ですね。
しかも他と違い愚直よりもエレガントの方が早いと言う良くわからない状況になりましたが、んなこたどうでも良いです。しょうもないレベルで遅いですから。
golang は []byte に append するともっと遅くなっちゃいました。流石に文字列が短いと + 演算子の方が強いです。
コード
今回ベンチ取ったコードを載せておきます。
C
#include <stdio.h> int main(void) { int n = 600000; int i = 1; for (i = 1; i <= n; i++) { if (i % 3 == 0 && i % 5 == 0) { printf("FizzBuzz\n"); } else if (i % 3 == 0) { printf("Fizz\n"); } else if (i % 5 == 0) { printf("Buzz\n"); } else { printf("\%d\n", i); } } return 0; }
#include <stdio.h> int main(void) { int n = 600000; int i = 1; for (i = 1; i <= n; i++) { char str[9] = ""; if (i % 3 == 0) { sprintf(str, "Fizz"); } if (i % 5 == 0) { sprintf(str, "%sBuzz", str); } if (*str) { puts(str); } else { printf("%d\n", i); } } return 0; }
Crystal + Ruby
n = 600000 (1..n).each do |i| if i % 3 == 0 && i % 5 == 0 puts "FizzBuzz" elsif i % 3 == 0 puts "Fizz" elsif i % 5 == 0 puts "Buzz" else puts i end end
n = 600000 (1..n).each do |i| str = "" str = "Fizz" if i % 3 == 0 str += "Buzz" if i % 5 == 0 if str == "" puts i else puts str end end
Perl
#!/usr/bin/perl use strict; my $n = 600_000; for (1..$n) { if ($_ % 3 == 0 and $_ % 5 == 0) { print "FizzBuzz\n"; } elsif ($_ % 3 == 0) { print "Fizz\n"; } elsif ($_ % 5 == 0) { print "Buzz\n"; } else { print "$_\n"; } }
#!/usr/bin/perl use strict; my $n = 600_000; for (1..$n) { my $str = ''; $_ % 3 == 0 and $str = "Fizz"; $_ % 5 == 0 and $str .= "Buzz"; print $str ? "$str\n" : "$_\n"; }
Nim
let n = 600_000 for i in 1..n: if i mod 3 == 0 and i mod 5 == 0: echo "FizzBuzz" elif i mod 3 == 0: echo "Fizz" elif i mod 5 == 0: echo "Buzz" else: echo i
let n = 600_000 for i in 1..n: var str = "" if i mod 3 == 0: str = "Fizz" if i mod 5 == 0: str &= "Buzz" if str == "": echo i else: echo str
Rust
fn main() { let n = 600000; for i in 1..n { if i % 3 == 0 && i % 5 == 0 { println!("FizzBuzz"); } else if i % 3 == 0 { println!("Fizz"); } else if i % 5 == 0 { println!("Buzz"); } else { println!("{}", i); } } }
fn main() { let n = 600000; for i in 1..n { let mut str = "".to_owned(); if i % 3 == 0 { str.push_str("Fizz"); } if i % 5 == 0 { str.push_str("Buzz"); } if str.len() > 0 { println!("{}", str); } else { println!("{}", i); } } }
PHP
#!/usr/bin/php <?php $n = 600000; for ($i = 1; $i <= $n; $i++) { if ($i % 3 == 0 && $i % 5 == 0) { echo "FizzBuzz\n"; } elseif ($i % 3 == 0) { echo "Fizz\n"; } elseif ($i % 5 == 0) { echo "Buzz\n"; } else { echo "$i\n"; } }
#!/usr/bin/php <?php $n = 600000; for ($i = 1; $i <= $n; $i++) { $str = ''; if ($i % 3 == 0) { $str = "Fizz"; } if ($i % 5 == 0) { $str .= "Buzz"; } echo $str != "" ? "$str\n" : "$i\n"; }
golang
package main import ( "fmt" ) func main() { n := 600000; for i := 1; i <= n; i++ { if i % 3 == 0 && i % 5 == 0 { fmt.Printf("FizzBuzz\n") } else if i % 3 == 0 { fmt.Printf("Fizz\n") } else if i % 5 == 0 { fmt.Printf("Buzz\n") } else { fmt.Printf("%d\n", i) } } }
package main import ( "fmt" ) func main() { n := 600000; for i := 1; i <= n; i++ { str := "" if i % 3 == 0 { str = "Fizz" } if i % 5 == 0 { str += "Buzz" } if str != "" { fmt.Printf("%s\n", str) } else { fmt.Printf("%d\n", i) } } }
Node.js
var n = 600000; for (var i = 1; i <= n; i++) { if (i % 3 == 0 && i % 5 == 0) { console.log("FizzBuzz"); } else if (i % 3 == 0) { console.log("Fizz"); } else if (i % 5 == 0) { console.log("Buzz"); } else { console.log(i); } }
var n = 600000; for (var i = 1; i <= n; i++) { var str = ""; if (i % 3 == 0) { str = "Fizz"; } if (i % 5 == 0) { str += "Buzz"; } console.log(str ? str : i); }
Node.js(write)
var n = 600000; for (var i = 1; i <= n; i++) { if (i % 3 == 0 && i % 5 == 0) { process.stdout.write("FizzBuzz\n"); } else if (i % 3 == 0) { process.stdout.write("Fizz\n"); } else if (i % 5 == 0) { process.stdout.write("Buzz\n"); } else { process.stdout.write(i + "\n");( } }
var n = 600000; for (var i = 1; i <= n; i++) { var str = ""; if (i % 3 == 0) { str = "Fizz"; } if (i % 5 == 0) { str += "Buzz"; } process.stdout.write(str ? str + "\n" : i + "\n"); }
コンパイルオプション
gcc -o fizzbuzz_c fizzbuzz.c nim c -d:release -o:fizzbuzz_nim fizzbuzz.nim crystal build --release -o fizzbuzz_cr fizzbuzz.cr rustc -O -o fizzbuzz_rs fizzbuzz.rs go build -o fizzbuzz_go fizzbuzz.go
IO が遅いと id:Haaaa_N さんから指摘があったので試してみた
文字列連結で全部連結して一発出力すると倍早くなった、と指摘があったので試してみました。
id:Haaaa_N さんが書いた Rust のコードはコレ
Nim も書いてみました。
var str = "" for i in 1..600_000: if i mod 3 == 0 and i mod 5 == 0: str.add "FizzBuzz\n" elif i mod 3 == 0: str.add "Fizz\n" elif i mod 5 == 0: str.add "Buzz\n" else: str.add $i & "\n" write stdout, str
結果
Rust | 0.05s |
---|---|
Nim | 0.07s |
倍どころじゃなかったですね。しかも Nim 負けましたね。メモリがいっぱいあるなら一気に出すのが一番ですね、やはり。
Nim の文字全列連結版をもっと速く(情報提供 id:ytqwertyさん)
「一番下のnimのコードはRustに習ってstr.add $i & "\n"をstr.add $i; str.add '\n'にすると少し速くなります。」とのことだったのでちょっと試してみたら Rust と並びましたね。& 演算子の呼び出しが足をひっぱるようです。
var str = "" for i in 1..600_000: if i mod 3 == 0 and i mod 5 == 0: str.add "FizzBuzz\n" elif i mod 3 == 0: str.add "Fizz\n" elif i mod 5 == 0: str.add "Buzz\n" else: str.add $i; str.add "\n" write stdout, str
id:siphilia さんが色々速くしてくれた結果 Rust がなんだか速い
試してみたんですが、自分の環境でも Rust が速くなりました。帝王 C が負けてる。printf が遅いと id:ytqwerty さんも言っていたので puts にしてみたんですが、イマイチでした。60万回程度のループだと流石にこのレベルの戦いでは意味が無いので、1000万回ループさせて試しました。
C | 1.000s |
---|---|
C(puts) | 0.96s |
Rust | 0.73s |
なんでしょう、この Rust の速さは。
ちなみに C の puts はこれです。
#include <stdio.h> int main() { int n = 10000000; int i = 1; for (i = 1; i <= n; i++) { if (i % 3 == 0 && i % 5 == 0) { puts("FizzBuzz"); } else if (i % 3 == 0) { puts("Fizz"); } else if (i % 5 == 0) { puts("Buzz"); } else { printf("%d\n", i); } } return 0; }
utaymd さんがやってくれました Nim で爆速に
https://gist.github.com/yuutayamada/fa9415503048ce58b6f47d6a049a8c81
100万回でも 0.001s で処理が終わります。static でやっちゃうとコードがガッツリ展開されるのでファイルサイズは 6.1M とパンチの効いたサイズになりますが、爆速目指すなら大いにアリだと思いました。ただ、ループ回数に限界がありはしますけども。
いやぁ大変参考になりました。
fujita nozomu さんの文字列連結板 C が Nim、Rust を置いてけぼりに
速いです。Nim と Rust の文字連結一発出力と比べてみました。1000万回ループです。
C | 0.27s |
---|---|
Rust | 0.94s |
Nim | 0.85s |
こんな感じです。3倍っくらい速いですね。
今のところの最速コード C言語
#define UseWrite 1 #if UseWrite #include <unistd.h> #else #include <stdio.h> #endif #include <string.h> #define n 10000000 #if defined(__GNUC__) || defined(__clang__) #define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0) #else #define likely(x) (x) #define unlikely(x) (x) #endif char s[10 * n]; char d[8] = "00000000"; int main() { char* p = s; int i = 0; int k = 0; #define num() \ do { \ switch (k) { \ case 7: __asm __volatile("/* 8 */\n"); *p++ = d[0]; \ case 6: __asm __volatile("/* 7 */\n"); *p++ = d[1]; \ case 5: __asm __volatile("/* 6 */\n"); *p++ = d[2]; \ case 4: __asm __volatile("/* 5 */\n"); *p++ = d[3]; \ case 3: __asm __volatile("/* 4 */\n"); *p++ = d[4]; \ case 2: __asm __volatile("/* 3 */\n"); *p++ = d[5]; \ case 1: __asm __volatile("/* 2 */\n"); *p++ = d[6]; \ case 0: __asm __volatile("/* 1 */\n"); *p++ = d[7]; \ } \ *p++ = '\n'; \ } while (0) #define fizz() do {memcpy(p, "Fizz\n", 5); p += 5;} while (0) #define buzz() do {memcpy(p, "Buzz\n", 5); p += 5;} while (0) #define fizzbuzz() do {memcpy(p, "FizzBuzz\n", 9); p += 9;} while (0) #define next() \ do { \ if (unlikely(++i > n)) goto end; \ if (unlikely(++d[7] > '9')) { \ d[7] = '0'; \ if (unlikely(++d[6] > '9')) { \ d[6] = '0'; \ if (unlikely(++d[5] > '9')) { \ d[5] = '0'; \ if (unlikely(++d[4] > '9')) { \ d[4] = '0'; \ if (unlikely(++d[3] > '9')) { \ d[3] = '0'; \ if (unlikely(++d[2] > '9')) { \ d[2] = '0'; \ if (unlikely(++d[1] > '9')) { \ d[1] = '0'; \ d[0]++; \ if (unlikely(k < 7)) {k = 7;} \ } \ if (unlikely(k < 6)) {k = 6;} \ } \ if (unlikely(k < 5)) {k = 5;} \ } \ if (unlikely(k < 4)) {k = 4;} \ } \ if (unlikely(k < 3)) {k = 3;} \ } \ if (unlikely(k < 2)) {k = 2;} \ } \ if (unlikely(k < 1)) {k = 1;} \ } \ } while (0) for (;;) { next(); num(); next(); num(); next(); fizz(); next(); num(); next(); buzz(); next(); fizz(); next(); num(); next(); num(); next(); fizz(); next(); buzz(); next(); num(); next(); fizz(); next(); num(); next(); num(); next(); fizzbuzz(); } end: #if UseWrite write(STDOUT_FILENO, s, p - s); #else *p = '0'; printf("%s", s); #endif }
(Author fujita nozomuさん)