（今更感）
目的
非負整数値を取る関数があるとする。そしてそれを実行中に非常に多くの回数呼ぶ（数百兆回とか）、ということは、科学技術計算ではよく見られる光景である。
整数値を取るので、恐らく何度もピッタリ同じ値を計算することになるだろう。
すると、何度も呼びそうな範囲は先に表にしておいて、それを見に行くことで計算時間を短縮する、という発想は自然なものに思える。
配列アクセスが計算より早い場合はこのテクニックは非常に有用だ。ルックアップテーブルという名前まで付いている。
これが実数値を取る関数だと全く同じ浮動小数点数が来る確率は低いので単純なルックアップテーブル作成は難しくなる。
その場合、メモリが足りるなら十分小さい幅ごとの代表値を表にしておくとか、計算が本当に重くて簡単な補間の方が早い場合は、一定値おきの値を使って引数での値を補間するとかいった方法を用いたりする。
さて、C++ではコンパイル時に計算ができる。つまり、コンパイル時にルックアップテーブルが作れるのだ。
ルックアップテーブルを作るとき、普通はビルドスクリプトの中で適当なスクリプト言語から何かライブラリを呼び出してヘッダファイルを生成するのだが、面白いのでコンパイル時に作ってみよう。
例：階乗関数
インターフェース
例として、単純なので階乗関数を考えてみたい。N=100くらいまでのルックアップテーブルをコンパイル時に作ることを考える。
普通に実装すると以下のようになるfactorialだが、
template<typename Real>
constexpr Real factorial_impl(std::uint32_t i) noexcept
{
return i==0 ? 1 : static_cast<Real>(i) * factorial_impl(i-1);
}
ルックアップテーブルが完成すれば、factorialは以下のような実装になるだろう。
template<typename Real>
constexpr Real factorial(std::size_t i) noexcept
{
return factorial_table<Real>::get(i);
}
では中身について考えていきたい。factorial_tableは以下のようになっていると考えられる。
template<typename Real, std::size_t N>
struct factorial_table
{
constexpr static std::size_t size = N;
constexpr static std::array<Real, N> value = ;
constexpr static Real get(std::size_t i) noexcept
{
return factorial_table<Real, N>::value[i];
}
};
template<typename Real, std::size_t N>
constexpr std::size_t factorial_table<Real, N>::size;
template<typename Real, std::size_t N>
constexpr Real factorial_table<Real, N>::value[N];
/* ...???... */の部分をどうするかだ。
配列生成
こういうときのために、C++14にはstd::index_sequenceなるものが存在している。これは整数シーケンスを表現する型、integer_sequenceのsize_tに対する特殊化である。
cpprefjpによると以下のようなものだ。
integer_sequence - cpprefjp C++日本語リファレンス
namespace std {
template <class T, T... I>
struct integer_sequence {
using value_type = T;
static constexpr size_t size() noexcept { return sizeof...(I); }
};
}
これを使うと、variadic templateで渡した整数値を関数内で展開できる。
variadic template argumentの展開は、関数を噛ましつつ行うことができるので、以下のような関数が書ける。
template<typename Real, typename Integer, Integer ... vals>
std::array<Real, sizeof...(vals)>
generate_array(std::integer_sequence<Integer, vals...>)
{
return {{factorial_impl(vals)...}};
}
パラメータパックの展開により、この関数を以下のようにして呼ぶと
constexpr auto a = generate_array<double>(
std::integer_sequence<std::uint32_t, 0,1,2,3,4,5>{});
このaは{factorial(0), factorial(1), factorial(2), factorial(3), factorial(4), factorial(5)}になるのだ。
これを使うことで、コンパイル時に好きな整数シーケンスを好きな関数で変換した静的配列を生成できる。
しかしこのままだと手でinteger_sequence<std::uint32_t, 0, 1, 2, 3, 4, 5, 6, ..., 100>みたいなのを書く必要があり、無理になってしまう。
もちろんC++がそんなことを許すはずはない。std::make_integer_sequence<Int, N>なるものがあり、これは<Int, 0, 1, ... , N>を一発で作ってくれる。
これにより、
constexpr auto a = generate_array<double>(
std::make_integer_sequence<std::uint32_t, 100>{});
と書くことができるのだ。
make_integer_sequence - cpprefjp C++日本語リファレンス
ただ、C++11だとこのinteger_sequenceは存在しない。縛りプレイのために、一応、これをどのように作るか少し考えてみよう。
少々面倒なことが起きるので、まずsize_t決め打ちでindex_sequenceを作る。integer_sequenceは、その後中身をstatic_castすることで作れる。
負の長さを持つ列、というのはないので、深く気にしなくていいのは楽だ。
template<std::size_t ... vs>
struct index_sequence{};
template引数だけが必要なので、中身は別にいらない（sizeとvalue_typeくらいは定義すべきだが、煩雑になるのでやめた）。
0, ... Nみたいなのをつくりたいので、再帰で{0, 1, ..., N-1} + {N} -> {0, 1, ..., N-1, N}のようにしていくことを考えた。
そのためには、まず2つのindex_sequenceを結合する必要がある。
template<typename T1, typename T2>
struct index_sequence_concatenator;
template<std::size_t ... v1, std;;size_t ... v2>
struct index_sequence_concatenator<
index_sequence<v1...>, index_sequence<v2...>>
{
typedef index_sequence<v1 ..., v2 ...> type;
};
これを使って{0, ..., N}を生成しよう。
template<std::size_t N>
struct index_sequence_generator
{
typedef typename index_sequence_concatenator<
typename index_sequence_generator<N-1>::type,
index_sequence<N>
>::type type
};
template<>
struct index_sequence_generator<0>
{
typedef index_sequence<0> type
};
というわけでできた。使いやすいようにエイリアスを定義しよう。
長さがNで0始まりなので{0, 1, ..., N-1}になることをすっかり忘れていたのでエイリアスでこっそり修正しておこう。
template<std::size_t N>
using make_index_sequence =
typename index_sequence_generator<N-1>::type;
というわけで、C++11でもindex_sequenceが作れて、コンパイル時ルックアップテーブルができた。
