忍者ブログ

どっかのゆとりのチラシの裏

plasma_effectのメモ帳的ブログのようなsomething

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

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

お前は何を言っているんだ感がすごい漂うが、コンパイル時に512要素のマージソートの話。C++11の規格でconstexprは再帰深度が云々って話なので再帰深度オーダーがO(N)だとダメなわけで。で、とりあえず整列済みの2つの配列をマージさせる関数を書いたわけですが。もうちょっとチューンしたらメモリ効率よくなるか知らないがそもそも上であるように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をローカル変数チックに扱うテクニックは他にも使えそうな気がするがメモリ効率どうなんだって話なのであまりオススメはしない。
PR

コメント

お名前
タイトル
文字色
メールアドレス
URL
コメント
パスワード Vodafone絵文字 i-mode絵文字 Ezweb絵文字

カレンダー

07 2017/08 09
S M T W T F S
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31

フリーエリア

最新CM

[02/12 kariya_mitsuru]
[10/14 どっかの京大生o]
[10/04 どっかのZ会生y]
[07/31 どっかのZ会生y]
[07/31 GNR]

プロフィール

HN:
plasma_effect
性別:
非公開

バーコード

ブログ内検索

最古記事

(06/08)
(06/18)
(06/21)

P R