テンプレート再帰深度
-
- いいね！0
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
どうやら IndexTuple idiom が標準でサポートされるようだ。 | 本の虫 C++ 2013-01 mailingの簡易レビュー http://t.co/bhZ8bHY0
2013-01-24 08:12:33
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
ところで、std::make_integer_seq の実装は、テンプレート再帰深度が高々 Ο(logN) であるという要件を加えるべきだと思う。でなければ、数百以上の要素のシーケンスに対しての実用ができなくなる。
2013-01-24 08:16:09
beepcap
@beepcap
@bolero_MURAKAMI それやると、組み込み環境にlibcが移植できないとかになるから、ダメ。言語の標準化では性能を縛るべきではない
2013-01-24 08:19:00
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
これは、ランタイムの問題ではなく、単に標準ライブラリヘッダのコーディング上の問題です。C++03のコンパイラですら、Ο(logN) で実装できる。 RT @beepcap: @bolero_MURAKAMI それやると、組み込み環境にlibcが移植できないとかになるから、ダメ。
2013-01-24 08:23:08
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
sprout::index_range を見ればよい。単にこれだけで実装できる。 https://t.co/zDs7F0JS
2013-01-24 08:25:41
beepcap
@beepcap
@bolero_MURAKAMI メモリ量的な問題や8bitCPUなどで常に実現可能なアルゴリズムがあるかを吟味しないと、やはり演算性能で縛るのは良いやり方だとは思えないなぁ・・・
2013-01-24 08:28:04
江添亮
@EzoeRyou
陶芸家はC++標準化委員会のMLで議論してくるべきなんじゃないだろうか・・・しかしなぁ、テンプレートの再帰深度のOrderの規定なんて。
2013-01-24 08:28:27
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
. @beepcap 完全にコンパイル時のみで解決される処理なので、ランタイムの環境は関係ないです。同一環境でコンパイルされるとしても、少なくともスタックの消費は Ο(N) の実装より遙かに効率的です。メモリはコンパイラの実装次第だが、大きく変わる要素はない。
2013-01-24 08:32:39
江添亮
@EzoeRyou
というか、通常は、普通の実行時関数に何百個も実引数を渡さない以上、Variadic Templatesでtupleを使って再帰深度なんて考える必要はないしなぁ。
2013-01-24 08:33:40
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
だいたい、<algorithm> からして、想定される実用上の実装から、性能の要件を定義しているので（検証は必要だが）要件を加えるのは問題ないはずだ。問題は、再帰深度のオーダーが、定義するに値するかどうかだけだ。
2013-01-24 08:36:39
beepcap
@beepcap
@bolero_MURAKAMI ふうむ・・・例えばの話、線形探索が許されるのならTupleを単に要素のみの構造体の配列としても良いわけだ。このばあいスタックの消費はほぼゼロとなる。このような実装が許されなくなりそうじゃない？
2013-01-24 08:37:20
江添亮
@EzoeRyou
まー、なんだかんだいっても、実行時関数に何百個も実引数を渡したりしないからなぁ。プリプロセッサ実装のboost::functionがデフォルトで10個ぐらいしか生成してなくても、それほど問題にはならない。
2013-01-24 08:41:30
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
. @beepcap タプルの実装とは直交した問題です。integer_seq<N...> クラスが、make_integer_seq によってどう導出されるかというだけの問題です。これは、テンプレート操作のみで解決され、タプルの実装が何であれ変わりません。
2013-01-24 08:42:12
江添亮
@EzoeRyou
make_integer_seqの私の記事の実装は、テンプレート再帰深度の増加が某陶芸家が発狂するO(N)な実装となっている。http://t.co/vPdbyUrO
2013-01-24 08:46:06
beepcap
@beepcap
@bolero_MURAKAMI なるほど。データ構造のレイヤに依存しない探索アルゴリズムだと言いたいのか。・・・それが真なら一理あるなぁ。ただ、それは『ランダムアクセスが可能なデータ構造』が前提なのではないだろうかと思うのだけど、あってる？
2013-01-24 08:46:56
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
. @beepcap そもそも、make_integer_seq (いわゆる IndexTuple idiom) はランダムアクセス可能な構造に対するイディオムです。
2013-01-24 08:49:01
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
make_integer_seq の Ο(logN) な実装の、Ο(N) な実装に対する想定されるデメリットは、コンパイル時間が僅少増える(かもしれない)程度。もちろんレイトレーシングで2secの処理が72minに増えると言った類でなく、本当に僅少なものだ。
2013-01-24 08:52:46
beepcap
@beepcap
@bolero_MURAKAMI それはそうだwwwそもそも、資源が厳しい環境でTupleを使うなんて言い出したら、その時点で止める。しかしながら言語の仕様でそれが『出来ない』ように縛る事とは別問題ではないだろうか。
2013-01-24 09:06:44
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
. @beepcap どうもよく伝わっていないようですが、テンプレート再帰深度の実装が Ο(logN) か Ο(N) かで、ライブラリユーザに対するインタフェースやその他の要件が変わったり劣化することは、まったくない。本当にまったくない。
2013-01-24 09:11:44