カテゴリー機能は終了いたしました。まとめ作成時にはタグをご活用ください。
6
Ryou Ezoe @EzoeRyou
本の虫: C++ 2013-01 mailingの簡易レビュー http://t.co/vPdbyUrO
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
どうやら IndexTuple idiom が標準でサポートされるようだ。 | 本の虫 C++ 2013-01 mailingの簡易レビュー http://t.co/bhZ8bHY0
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
ところで、std::make_integer_seq の実装は、テンプレート再帰深度が高々 Ο(logN) であるという要件を加えるべきだと思う。でなければ、数百以上の要素のシーケンスに対しての実用ができなくなる。
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap
@bolero_MURAKAMI それやると、組み込み環境にlibcが移植できないとかになるから、ダメ。言語の標準化では性能を縛るべきではない
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap
(ただしNoteで目標値を書いておくのは大事だよな。あと、実装がバブルソートになってるqsort()てめーはダメだ
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
これは、ランタイムの問題ではなく、単に標準ライブラリヘッダのコーディング上の問題です。C++03のコンパイラですら、Ο(logN) で実装できる。 RT @beepcap: @bolero_MURAKAMI それやると、組み込み環境にlibcが移植できないとかになるから、ダメ。
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
sprout::index_range を見ればよい。単にこれだけで実装できる。 https://t.co/zDs7F0JS
Ryou Ezoe @EzoeRyou
@bolero_MURAKAMI だれがTupleに数百もの要素を・・・あ、これはこれは、陶芸家の方でしたか。
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap
@bolero_MURAKAMI メモリ量的な問題や8bitCPUなどで常に実現可能なアルゴリズムがあるかを吟味しないと、やはり演算性能で縛るのは良いやり方だとは思えないなぁ・・・
Ryou Ezoe @EzoeRyou
陶芸家はC++標準化委員会のMLで議論してくるべきなんじゃないだろうか・・・しかしなぁ、テンプレートの再帰深度のOrderの規定なんて。
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
. @beepcap 完全にコンパイル時のみで解決される処理なので、ランタイムの環境は関係ないです。同一環境でコンパイルされるとしても、少なくともスタックの消費は Ο(N) の実装より遙かに効率的です。メモリはコンパイラの実装次第だが、大きく変わる要素はない。
Ryou Ezoe @EzoeRyou
というか、通常は、普通の実行時関数に何百個も実引数を渡さない以上、Variadic Templatesでtupleを使って再帰深度なんて考える必要はないしなぁ。
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
だいたい、<algorithm> からして、想定される実用上の実装から、性能の要件を定義しているので(検証は必要だが)要件を加えるのは問題ないはずだ。問題は、再帰深度のオーダーが、定義するに値するかどうかだけだ。
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap
@bolero_MURAKAMI ふうむ・・・例えばの話、線形探索が許されるのならTupleを単に要素のみの構造体の配列としても良いわけだ。このばあいスタックの消費はほぼゼロとなる。このような実装が許されなくなりそうじゃない?
Ryou Ezoe @EzoeRyou
まー、なんだかんだいっても、実行時関数に何百個も実引数を渡したりしないからなぁ。プリプロセッサ実装のboost::functionがデフォルトで10個ぐらいしか生成してなくても、それほど問題にはならない。
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap
(まあ、そもそもstackとqueue以外のデータ構造なんて冗長だよ派なんだけどな)
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
. @beepcap タプルの実装とは直交した問題です。integer_seq<N...> クラスが、make_integer_seq によってどう導出されるかというだけの問題です。これは、テンプレート操作のみで解決され、タプルの実装が何であれ変わりません。
Ryou Ezoe @EzoeRyou
make_integer_seqの私の記事の実装は、テンプレート再帰深度の増加が某陶芸家が発狂するO(N)な実装となっている。http://t.co/vPdbyUrO
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap
@bolero_MURAKAMI なるほど。データ構造のレイヤに依存しない探索アルゴリズムだと言いたいのか。・・・それが真なら一理あるなぁ。ただ、それは『ランダムアクセスが可能なデータ構造』が前提なのではないだろうかと思うのだけど、あってる?
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
. @beepcap そもそも、make_integer_seq (いわゆる IndexTuple idiom) はランダムアクセス可能な構造に対するイディオムです。
Ryou Ezoe @EzoeRyou
C++11規格で推奨されている再帰的にネストされたテンプレートのインスタンス化の回数は1024か。
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
make_integer_seq の Ο(logN) な実装の、Ο(N) な実装に対する想定されるデメリットは、コンパイル時間が僅少増える(かもしれない)程度。もちろんレイトレーシングで2secの処理が72minに増えると言った類でなく、本当に僅少なものだ。
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
僕が言うと「僅少」の信憑性が無くなるので、もし必要になればベンチ出すしかないが。
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap
@bolero_MURAKAMI それはそうだwwwそもそも、資源が厳しい環境でTupleを使うなんて言い出したら、その時点で止める。しかしながら言語の仕様でそれが『出来ない』ように縛る事とは別問題ではないだろうか。
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI
. @beepcap どうもよく伝わっていないようですが、テンプレート再帰深度の実装が Ο(logN) か Ο(N) かで、ライブラリユーザに対するインタフェースやその他の要件が変わったり劣化することは、まったくない。本当にまったくない。
残りを読む(7)

コメント

ログインして広告を非表示にする
ログインして広告を非表示にする