コンパイル時マージソートの話

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ http://t.co/7Fa2usFRBz コンパイル時に512要素のマージソート、通った。しかしもはやコードが正しくても通るかどうかは処理系のポテンシャルに拠る…。

— 蔵人紗音のじ (@fimbul11) 2014, 7月 6

constexpr evaluation hit maximum step limit; で死ぬ。要素数が増えれば再帰深度を抑えないとダメだし、再帰深度を抑えるためには往々にして遠回りな実装になってステップ数が増えるし、このエラーはもう詰みかなって感じある。

— 蔵人紗音のじ (@fimbul11) 2014, 7月 6

まぁidiomとか色々発達した結果、スタックオーバーフローさせずに再帰だけでステップ数の上限叩けるようになったのは一定の成果なんじゃないですかね…。

— 蔵人紗音のじ (@fimbul11) 2014, 7月 6

お前は何を言っているんだ感がすごい漂うが、コンパイル時に512要素のマージソートの話。C++11の規格でconstexprは再帰深度が云々って話なので再帰深度オーダーがO(N)だとダメなわけで。で、とりあえず整列済みの2つの配列をマージさせる関数を書いたわけですが。

gccだとメモリ食いつぶした [Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ http://t.co/aW4tzzOjN2

— plasma_effect (@plasma_effector) 2014, 7月 6

もうちょっとチューンしたらメモリ効率よくなるか知らないがそもそも上であるようにconstexprのステップ数上限に引っかかってるのでどうしようもなかったりする。ステップ数はどんな実装でも平等に増えていくし。

で、今回の記事はその「メモリ効率とかステップ数とか全てを無視して再帰深度のオーダーだけを考えた整列済みの2つの配列をマージする関数」の解説を書きたいとかいう話。
コード読みゃいいじゃねぇかって話な気がするがそれは気にしない気にしない。

2つの配列をマージする方法としてぱっと思いつくものといえば「片方のもう片方の要素を順に追加していく」「2つの配列から順に返り値に追加していく」の2つ(他にもあるかしらないがとりあえずはこの2つ)
前者はともかく後者とはどういうこっちゃって話だが、C++14constexprで書いたらこんな感じ。

#include<sprout/array.hpp>
#include<utility>

template<class T,std::size_t N,std::size_t M>
constexpr sprout::array<T,N+M> array_merge(
sprout::array<T,N> const& A,
sprout::array<T,M> const& B)
{
sprout::array<T,N+M> ret{};
int a=0;
int b=0;
for(std::size_t i=0;i<N+M;++i)
{
    if(a==N)
    {
        ret[i]=B[b];
        ++b;
    }
    else if(b==M)
    {
        ret[i]=A[a];
        ++a;
    }
    else if(A[a]<B[b])
    {
        ret[i]=A[a];
        ++a;
    }
    else
    {
        ret[i]=B[b];
        ++b;
    }
}
return ret;
}

constexpr sprout::array<int,8> x = {{0,2,4,6,8,10,12,14}};
constexpr sprout::array<int,8> y = {{1,3,5,7,9,11,13,15}};
constexpr auto z = array_merge(x,y);

#include<iostream>
int main()
{
for(auto i:z)
    std::cout<<i<<std::endl;
}

つまりこれをC++11constexprでシミュレートするって話。
変数a,bと途中結果のsprout::arrayをtupleに入れて、新しくオブジェクトを作るのを繰り返すことで「ローカル変数の値を変更するかのように関数を書く」ことが可能となる。
for文の部分はコンパイル時には回す回数が決っているはずなのでtemplate引数を利用した分割統治法でOK。今回のマージ関数の実装では使いまわすtupleの型がどんどん変わっていったが全く同じ型を使いまわすのであれば多分倍分再帰使ったら無限ループ作れるんじゃないかなぁ。(ていうかtemplateのインスタンス量的に型一致させたほうがいい気がする…)

あ、あとこれのメモリ効率どうなってんだって話だがもう深く考えないことにする。ていうか正直考えたくない。参考として0x100要素の配列2つだとclangは通るがgccではメモリを食いつぶした。

sprout::tupleをローカル変数チックに扱うテクニックは他にも使えそうな気がするがメモリ効率どうなんだって話なのであまりオススメはしない。