09/09/04 22:36:49
>>734
その解釈には無理が無いか？
もしそのとおりであれば、 gcc のバグ報告に対して 23.1/2 をあげる必要が
無かったはず。
それに、 defect 139 を挙げてるのは、報告者が vector の push_back に
言及してたからでしょ。 deque の push_back については最新のドラフトでも
constant time が要求されてるよ。
736:デフォルトの名無しさん
09/09/04 22:59:02
>>735
無い。無理があるのは
You are talking about complexity in terms of the number of operations
performed on pointers to the contained objects.
の方だと思うぞ。そもそも、Standardでは
23.1.1
All of the complexity requirements in this Clause are stated solely in terms
of the number of operations on the contained objects. [ Example: the copy
constructor of type vector <vector<int> > has linear complexity, even though
the complexity of copying each contained vector<int> is itself linear. end
example ]
とわざわざ例を挙げて言っているように、ポインタ経由でアクセスしているか否かを
問題にしているわけではない。
最新のドラフトでは確かに"should have constant complexity"と書いてあるが、
そもそもDefect 139は "Status: TC Submitter: Andrew Koenig Date: 30 Mar 1999"
とあるように、確実に当時のStandardに反映されている。その後complexityに対する
委員会の見解が変わったか、エンバグしたかのどちらかだろう。
737:デフォルトの名無しさん
09/09/04 23:16:42
>>736
誰もポインタ経由でアクセスしているか否かなんて問題にしてないよ。
問題なのはコンテナ内の要素に対する操作か否か。
list の size で要素を数え上げる処理は明らかに違うでしょ。
あと、 deque の push_back の要件は defect 139 で修正された
Optional sequence operations じゃなくて、 23.2.1.3 [lib.deque.modifiers] に
別途記載されている。最新のドラフトだと 23.3.2.3 ね。
> Inserting a single element either at the beginning or end of a deque always
> takes constant time and causes a single call to a constructor of T.
やっぱりおかしいよ。
738:デフォルトの名無しさん
09/09/04 23:31:13
>>736
"should have constant complexity" って、どこ見てるの？
defect 139 で修正された Optional sequence operations についての記述では
2003 の時点でも最新のドラフトでも
"shall implement them so as to take amortized constant time" って書いてあるよ。
まぁ、もう元の話とは関係ないんだけどね。
739:デフォルトの名無しさん
09/09/05 00:38:32
>>737
そもそもGCCのバグ報告を持ち出したのは、ポインタ経由での要素へのアクセスは
オブジェクトへのアクセスでは無いからcomplexityに影響しないということだと
思うが。
> 問題なのはコンテナ内の要素に対する操作か否か。
> list の size で要素を数え上げる処理は明らかに違うでしょ。
その認識が合っているとは思えない。list::reverse()のcomplexityはlinear time
だとStandardにあるが、これはlist::size()同様にリンクポインタをいじることで
実現可能。もしリストのリンクを辿ることが"operations on the contained objects"
でないのなら、list::reverse()のcomplexityも当然constant timeと書くと思うが。
こんな矛盾を委員会が放置しているとは思えないし、そもそも>>728が言うような
誤解をしているとも思えない。
740:デフォルトの名無しさん
09/09/05 00:46:04
>>738
> "should have constant complexity" って、どこ見てるの？
これは間違いだった。General container requirementsのsize()について見ていた。
> defect 139 で修正された Optional sequence operations についての記述では
> 2003 の時点でも最新のドラフトでも
> "shall implement them so as to take amortized constant time" って書いてあるよ
見落としていたが、確認した。
741:デフォルトの名無しさん
09/09/05 00:57:07
>>739
gcc のバグ報告ちゃんと読んでる？
ポインタ経由での要素へのアクセスなんてどこにもでてきてないはずなんだけど。
問題になってるのは deque 内に持ってるポインタ配列の再確保とコピーね。
> こんな矛盾を委員会が放置しているとは思えないし、そもそも>>728が言うような
> 誤解をしているとも思えない。
みんなそう思ってるんだけど、事実は矛盾が発生しているようだという話ね。
list のリンク操作は "operations on the contained objects" であって
deque のポインタ配列操作はそうではない、というのはおかしい。
元々の意図はそうなんだろうとは思うけど、それが 23.1/2 の記述が甘いせいで
おかしくなっている、と。
742:デフォルトの名無しさん
09/09/05 01:09:31
>>741
正しくはポインタへのアクセスだったな。まあそのくらい補完してくれよ。
で、お前さんの立場は何なの？
list::size()やlist::reverse()はO(1)（面倒だからO表記を使う）とStandardに
書くべきだという意見？
自分は、こんな大事に気づかずに放置するわけが無くて、deque::push_back()の
complexityをamortized O(1)と書くべきという意見。
amortized complexityを良く理解していない人は結構多い上に、defect 139に
あるように実際同様のバグがあったこと、こちらの方が可能性が高いと考える。
743:デフォルトの名無しさん
09/09/05 01:09:40
調べてみると、こんなのが出てきた。
URLﾘﾝｸ(www.open-std.org)
ここの Issue Number 20-036 で問題の 23.1 p2 の追加が行われている。
これが "10 July 1996" とあるので、おそらく list の計算量要求なんかはそれ以前から
あったもので、操作全体の時間について言っていたのがそのままになってる可能性が高い。
N2923 も含めて、 list のリンク操作はあきらかに計算量に含まれる想定で書かれている
ので、 23.1 p2 の文面を現状に合うように修正するべきなんじゃないかと思う。
そうすると、 deque の push_back に対する要求は amortized constant に合わせて修正
しないといけなくなりそう。ただし、これは制限を緩めるものなので、現状の実装を変更する
必要は生じないはず。
744:デフォルトの名無しさん
09/09/05 01:29:39
>>742
> で、お前さんの立場は何なの？
> list::size()やlist::reverse()はO(1)（面倒だからO表記を使う）とStandardに
> 書くべきだという意見？
そうするか、 >>743 のとおり 23.1/2 のほうを直すか、とにかく矛盾を直すべき
だとは思う。
>>743 のほうが自然だし、楽だね。
745:デフォルトの名無しさん
09/09/05 01:32:24
>>743
なるほど。確かにそういう事になるだろうな。そうすれば>>728や>>735>>737
のようなおかしな解釈をする輩がいなくなる。
そもそもコンテナ内の要素数に依存するような操作をしているのにポインタへの
アクセスは関係ない、なんて言い出したらcomplexityを明示することが無意味に
なってしまう。
746:デフォルトの名無しさん
09/09/05 02:15:43
どちらかというと「標準委員会が矛盾に気づかないわけがない」なんて
思い込んでるほうがおかしいだろ。
747:デフォルトの名無しさん
09/09/05 02:48:46
>>746
見苦しいぞ
748:746
09/09/05 03:01:16
へ？なんで？意味がわからない。
749:デフォルトの名無しさん
09/09/05 09:28:43
>>746
おまいは>>728から100回読み直してこい
750:デフォルトの名無しさん
09/09/05 13:05:38
どっちがおかしいよかよくわかってない美少女中学生もお忘れなく
751:デフォルトの名無しさん
09/09/05 15:48:55
規格の文面をまじめに読むと、どっちの解釈が「おかしい」とも言い切れない状態に
なってるのが問題。
752:デフォルトの名無しさん
09/09/05 15:56:27
ここでいう「どっち」は >>728 と >>743 の２つね。（ >>745-746 は敢えてスルー）
728 は deque::push_back の（計算量）要求は正しくて list::size() の要求は無意味。
743 は list::size() の要求には意味があって deque::push_back の要求は間違ってる。
753:デフォルトの名無しさん
09/09/06 12:29:21
23.1.1 の記述を問題にしてる人は、具体的にどう直せば厳密になると思う？
俺はまともに書き下せる気がしないので、
「今の文面を、常識的に考えて意図したいであろう意味と解釈して読め」
が現実的だと思うんだけど。
754:デフォルトの名無しさん
09/09/06 13:04:37
計算量とか「実装の質」で切り捨てたらあかんの？
なんか言語の規格で決める事じゃないような気がする
755:デフォルトの名無しさん
09/09/06 13:13:12
>>754
それはさすがに認識のレベルが出発点にすら立ってない