Togetter/min.tを安心してお使い頂くためのガイドラインを公開しました。
編集可能

テンプレート再帰深度

6
Ryou Ezoe(江添 亮) @EzoeRyou

本の虫: C++ 2013-01 mailingの簡易レビュー http://t.co/vPdbyUrO

2013-01-24 03:36:56
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

どうやら IndexTuple idiom が標準でサポートされるようだ。 | 本の虫 C++ 2013-01 mailingの簡易レビュー http://t.co/bhZ8bHY0

2013-01-24 08:12:33
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

ところで、std::make_integer_seq の実装は、テンプレート再帰深度が高々 Ο(logN) であるという要件を加えるべきだと思う。でなければ、数百以上の要素のシーケンスに対しての実用ができなくなる。

2013-01-24 08:16:09
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap

@bolero_MURAKAMI それやると、組み込み環境にlibcが移植できないとかになるから、ダメ。言語の標準化では性能を縛るべきではない

2013-01-24 08:19:00
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap

(ただしNoteで目標値を書いておくのは大事だよな。あと、実装がバブルソートになってるqsort()てめーはダメだ

2013-01-24 08:20:58
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

これは、ランタイムの問題ではなく、単に標準ライブラリヘッダのコーディング上の問題です。C++03のコンパイラですら、Ο(logN) で実装できる。 RT @beepcap: @bolero_MURAKAMI それやると、組み込み環境にlibcが移植できないとかになるから、ダメ。

2013-01-24 08:23:08
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

sprout::index_range を見ればよい。単にこれだけで実装できる。 https://t.co/zDs7F0JS

2013-01-24 08:25:41
Ryou Ezoe(江添 亮) @EzoeRyou

@bolero_MURAKAMI だれがTupleに数百もの要素を・・・あ、これはこれは、陶芸家の方でしたか。

2013-01-24 08:26:28
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap

@bolero_MURAKAMI メモリ量的な問題や8bitCPUなどで常に実現可能なアルゴリズムがあるかを吟味しないと、やはり演算性能で縛るのは良いやり方だとは思えないなぁ・・・

2013-01-24 08:28:04
Ryou Ezoe(江添 亮) @EzoeRyou

陶芸家はC++標準化委員会のMLで議論してくるべきなんじゃないだろうか・・・しかしなぁ、テンプレートの再帰深度のOrderの規定なんて。

2013-01-24 08:28:27
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

. @beepcap 完全にコンパイル時のみで解決される処理なので、ランタイムの環境は関係ないです。同一環境でコンパイルされるとしても、少なくともスタックの消費は Ο(N) の実装より遙かに効率的です。メモリはコンパイラの実装次第だが、大きく変わる要素はない。

2013-01-24 08:32:39
Ryou Ezoe(江添 亮) @EzoeRyou

というか、通常は、普通の実行時関数に何百個も実引数を渡さない以上、Variadic Templatesでtupleを使って再帰深度なんて考える必要はないしなぁ。

2013-01-24 08:33:40
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

だいたい、<algorithm> からして、想定される実用上の実装から、性能の要件を定義しているので(検証は必要だが)要件を加えるのは問題ないはずだ。問題は、再帰深度のオーダーが、定義するに値するかどうかだけだ。

2013-01-24 08:36:39
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap

@bolero_MURAKAMI ふうむ・・・例えばの話、線形探索が許されるのならTupleを単に要素のみの構造体の配列としても良いわけだ。このばあいスタックの消費はほぼゼロとなる。このような実装が許されなくなりそうじゃない?

2013-01-24 08:37:20
Ryou Ezoe(江添 亮) @EzoeRyou

まー、なんだかんだいっても、実行時関数に何百個も実引数を渡したりしないからなぁ。プリプロセッサ実装のboost::functionがデフォルトで10個ぐらいしか生成してなくても、それほど問題にはならない。

2013-01-24 08:41:30
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap

(まあ、そもそもstackとqueue以外のデータ構造なんて冗長だよ派なんだけどな)

2013-01-24 08:41:38
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

. @beepcap タプルの実装とは直交した問題です。integer_seq<N...> クラスが、make_integer_seq によってどう導出されるかというだけの問題です。これは、テンプレート操作のみで解決され、タプルの実装が何であれ変わりません。

2013-01-24 08:42:12
Ryou Ezoe(江添 亮) @EzoeRyou

make_integer_seqの私の記事の実装は、テンプレート再帰深度の増加が某陶芸家が発狂するO(N)な実装となっている。http://t.co/vPdbyUrO

2013-01-24 08:46:06
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap

@bolero_MURAKAMI なるほど。データ構造のレイヤに依存しない探索アルゴリズムだと言いたいのか。・・・それが真なら一理あるなぁ。ただ、それは『ランダムアクセスが可能なデータ構造』が前提なのではないだろうかと思うのだけど、あってる?

2013-01-24 08:46:56
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

. @beepcap そもそも、make_integer_seq (いわゆる IndexTuple idiom) はランダムアクセス可能な構造に対するイディオムです。

2013-01-24 08:49:01
Ryou Ezoe(江添 亮) @EzoeRyou

C++11規格で推奨されている再帰的にネストされたテンプレートのインスタンス化の回数は1024か。

2013-01-24 08:50:21
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

make_integer_seq の Ο(logN) な実装の、Ο(N) な実装に対する想定されるデメリットは、コンパイル時間が僅少増える(かもしれない)程度。もちろんレイトレーシングで2secの処理が72minに増えると言った類でなく、本当に僅少なものだ。

2013-01-24 08:52:46
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

僕が言うと「僅少」の信憑性が無くなるので、もし必要になればベンチ出すしかないが。

2013-01-24 08:53:54
ITが分からないbeepcap@HTTPSの強制には反対 @beepcap

@bolero_MURAKAMI それはそうだwwwそもそも、資源が厳しい環境でTupleを使うなんて言い出したら、その時点で止める。しかしながら言語の仕様でそれが『出来ない』ように縛る事とは別問題ではないだろうか。

2013-01-24 09:06:44
狂える中3女子ボレロ村上/陶芸C++er @bolero_MURAKAMI

. @beepcap どうもよく伝わっていないようですが、テンプレート再帰深度の実装が Ο(logN) か Ο(N) かで、ライブラリユーザに対するインタフェースやその他の要件が変わったり劣化することは、まったくない。本当にまったくない。

2013-01-24 09:11:44
残りを読む(7)

コメント

コメントがまだありません。感想を最初に伝えてみませんか?