コンパイル時FizzBuzz【とても地球にやさしい】

コンパイル時計算FizzBuzz

以下の様な実行コードをコンパイル時に生成します。

// 実行されるコードのイメージ
int main() {
  char string[] = {'1', '\n', '2', '\n', 'F', 'i', 'z', 'z', ..., '\0'};
  printf(string);
}

プログラム実行時には事前に計算されている結果を出力するだけなので、超高速で動作します。

ゼロオーバーヘッドFizzBuzz

思っていたよりもコンパクトに書けました。C++14に感謝です。

おそらく世界最速のFizzBuzzになると思います。

#include <cstdio>
#define CX static constexpr

CX int len(int v, int _n = 1) { return (v = v / 10) ? len(v, _n + 1) : _n; }
CX int pow(int e) { return e ? e == 1 ? 10 : pow(e - 1) * 10 : 1; }
CX int chr(int v, int e) { return '0' + v / pow(e) % 10; }

CX long group(int v) { return -((v % 3 ? 0 : 1) + (v % 5 ? 0 : 2)) ?: len(v); }
CX long count(const char* s) { return *s ? 1 + count(1 + s) : 0; }

template<int P, int V, int... A> struct FizzedBuzzed              { // Mixing
  CX auto ary = FizzedBuzzed<P - 1, V, chr(V + 1, len(V + 1) - P), A...>::ary; };
template<       int V, int... A> struct FizzedBuzzed<0, V, A...>  { // EntryPoint
  CX auto ary = FizzedBuzzed<group(V), V - 1, '\n', A...>::ary;                };
template<              int... A> struct FizzedBuzzed<0, 0, A...>  { // Closing
  CX char ary[] = {A..., '\0'};                                                };
template<       int V, int... A> struct FizzedBuzzed<-1, V, A...> { // Fizz
  CX auto ary = FizzedBuzzed< 0, V, 'F', 'i', 'z', 'z', A...>::ary;            };
template<       int V, int... A> struct FizzedBuzzed<-2, V, A...> { // Buzz
  CX auto ary = FizzedBuzzed< 0, V, 'B', 'u', 'z', 'z', A...>::ary;            };
template<       int V, int... A> struct FizzedBuzzed<-3, V, A...> { // FizzBuzz
  CX auto ary = FizzedBuzzed<-1, V, 'B', 'u', 'z', 'z', A...>::ary;            };
template<int... A> constexpr char FizzedBuzzed<0, 0, A...>::ary[];

int main() {
  constexpr auto ary = FizzedBuzzed<0, 100>::ary;
  constexpr long len = count(ary);
  fwrite(ary, len/*1*/, 1/*len*/, stdout);
  // write(STDOUT_FILENO, ary, len); // #include <unistd.h>
}

Nyarlathotep:work $ clang++ -std=c++14 fizzbuzz.cpp; ./a.out
1
2
Fizz
4
...(以下省略)

地球にやさしいFizzBuzzですね。

技術的には再帰テンプレートで可変長テンプレート引数を構築し、再帰完了時に構築されたパラーメータパックを配列要素として展開しているだけの単純なロジックです。FizzBuzzの判定と文字列の構築は再帰中・可変長引数構築時に特殊化を用いて行っています。

簡単な解説

group関数によるFizzBuzz判定とその特殊化が今回のロジックの肝になっており、これには以前のFizzBuzz記事で紹介した数値のグループ化（0:数字 1:Fizz 2:Buzz 3:FizzBuzz）のアイディアが応用されています。実際には（d:桁数 -1:Fizz -2:Buzz -3:FizzBuzz）というグループ化を行っています。

グループ化された数値によって特殊化の対象が切り替わっている点が重要です。-1の場合はFizzedBuzzed<-1, V, A...>が機能し、文字列Fizzが追加されます。-2の場合はBuzzが追加されます。追加後は特殊化によってFizzedBuzzed<0, V, A...>が機能するので再度グループ判定が行われます。これが延々と繰り返されるわけです。

グループ-3の場合は少し面白い事をしており、Buzzを追加した後にFizz追加用の特殊化FizzedBuzzed<-1, V, A...>を機能させています。これがBuzzFizzではなくきちんとFizzBuzzとして追加されます。今回の再帰テンプレートは数値100から0までの逆向きにループするイメージなので、これでよいのです（今回のパラメータパックはある種のスタック的な役割を担っています）。またここでFizzが追加されると再度グループ判定に戻ります。

if文やgoto文をテンプレートの世界で実現しているみたいで面白いですね。

広告
広告