2010-02-03

オーダーについて解説しる!

Order I Say! « C++Next

strict weak orderingって何よというお話。

アキラさんが興味を示していたので読んでみた。幸い、Not Foundではなかった。しかし、イケメンのアキラさんとは違い、私には数学が分からない。でも、英語はちょっとだけ分かる。そこで、ここでは、高校までの数学の概念と、英語力だけで、無理やり理解したふりをして解説する。

規格では、ソートや連想コンテナへの要求として、strict weak orderingというのがあるが、これは一体どういう意味だろうか。

調べていくと、"a strict weak ordering is a strict partial order in which incomparability is transitive."とある。なるほど、ちょっとルールが追加されたstrict partial orderなんだな。、しかしstrict partial orderとは、一体何だろう。

strict total orderというものがあるが、これは複雑すぎる(ルールが多すぎる)。strict partial orderは簡単だが(ルールが少ないが)、あまりにも貧弱すぎる。strict weak orderは、その中間に位置する。

と、ここまでが、orderの数学的定義へ言及することを避けての解説である。数学が理解出来ない者としては、orderの数学的な定義の解説は理解できない。しかし、なぜstrict weak orderingであることが、そんなに重要なのか。なぜわざわざ、規格のいたる所で、strict weak orderingであることを明記しなければならないのか。

それは、アルゴリズム的に、ある場面で、比較を省略することができるからだ。高校までの数学で考える。x, y, zという整数に対して、不等号、<、を適用した場合。x < y, y < z, ということを知っていれば、x < z, は比較しなくても分かるということは、高校までの数学を知るものならば、当然のことである。つまりこれは、もし、このルールが保証されているならば、x < y, y < zであることを知っておけば、x < z, という比較は、省略できるということを意味する。strict weak orderingは、これを数学的に保証するのである。

原文では、二つの問題が出されている。数学が得意であれば、挑戦してみるのも面白いかもしれない。

私は数学が壊滅的にできないので、細かい部分を知りたい数学オタクは、こんな解説より原文を読んで欲しい。結局、私の興味は、なぜ、規格でstrict weak orderingと明記することが重要なのかということにあるのだから。

5 comments:

tiger said...

数学の半順序の事かも

egtra said...

半順序はpartial orderです。weak orderingは訳すとしたら弱い順序とか弱順序となります。Cryoliteさんはstrict weak orderingを厳密で弱い順序と訳していますね: http://d.hatena.ne.jp/Cryolite/20040529

hito said...

おお。
やっぱりCryoliteさんは、この手の事に詳しいですね。

tiger said...

strict weak ordring が半順序という事が言いたかったのではなく、順序集合の関係の話なんじゃないの?と言いたかったんです。
http://en.wikipedia.org/wiki/Strict_weak_ordering
の解説によると、全順序集合のように思えるです。
1.全ての x に対して ( x < x ) == false
2.全ての x != y に対して x < y ならば !(y < x)
3.全ての x,y,z に対して ( x < y && y < z ) ならば ( x < z ) == true
4.全ての x,y,z に対して ( x == y && y == z ) ならば ( x == z ) == true
コンピュータの扱える数は、有限なので、weak という表現をしてるのかも?

tiger said...

もう一度、Coyoliteさんの記事を読み直しましたが、Coyolite さんの考察で合ってる気がしてきました。