ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

C#の独自ソートで順序関係を壊す

今回C#の記事ではあるんですが、実質的には特定のプログラミング言語に依存しない話です。
そして数学の順序関係からヒントを得ています。


さて、C#ではIComparer<T>インターフェースを実装するクラスを定義し、Compareメソッドを実装してやることにより、
リストのソートなどで要素同士を比較するときに使うメソッドをカスタマイズできます。

しかしながら、ふと思ったのですが、どのようにこのCompareメソッドを実装してもいいわけではなくて、書き方次第では正常にソートできなくなってしまうのではないかということが、

まあ考えてみれば当たり前のことではあるのですが、ピンときたわけであります。


たとえば、以下のようなコードを書いてみます。


class WrongComparer : IComparer<string> {
  public int Compare(string x, string y) {
    return 1;
  }  }

これは常にxがyより大きいことを意味しています。

ここでstringのリストlistで、list.Sort(new WrongComparer())を実行してみました。


すると例えばlistが { "Red", "Green", "Blue" } だったとき結果は { "Blue", "Green", "Red" } と逆順になりました。

MSDNによるとSortメソッドは要素数が16個より小さい場合は挿入ソートを使用するそうですので、もし一番後ろの"Blue"から入れ替えを始めていたとしたら、

最初は"Blue"が配置されて、次にCompare("Green", "Blue") == 1より"Blue"の後ろに"Green"、次にCompare("Red", "Green") == 1より"Green"の後ろに"Red"という感じで、順番がひっくり返るのもうなづけますね。



次に並び替えたあとのlistにもう一度ソートを実行してみます。

このときすでにソートは完了しているので2回目のソートが終わったlistには1回目との変化がないことが期待されるわけですが、
実際にやってみると、再び逆順の { "Red", "Green", "Blue" }にソートされてしまいます。

なのでそれはおかしいと。

もし順番が等しいと定義されている要素の組があれば、そこが入れ替わったんだと解釈すれば、おかしくないですけど、まあ今回はCompareメソッドの戻り値から見るに順番が等しい組は存在しないですからね。


しかし以下の点で、私の中でもまだちょっと理解の辻褄が合ってない部分があるのですが、もしCompareメソッドの戻り値がbool型で、「xがy以上」もしくは「xがyより小さい」の2つの判別しかできなかったとしたら、
今回のCompareメソッドはすべて「xがy以上」を返すメソッドというものに置き換わりますので、別にすべての要素が順番的に等しいんだと解釈しても問題ないですよね。


そのようなCompareメソッドにおいても要素a,b,cで
a>=b == true, c>=b == false(つまりc<b == true), a>=c == false(つまりa<c == true)
を返すみたいに、おかしなことになるケースはありますけど。

この場合、順番の概念がおかしなことになってしまっているわけですね。

順番の概念がおかしなことになるということは、ようするに数学の(全)順序関係を満たしていないようなCompareメソッドであることではないかと思いました。

この例ではc<bですからb>cであってb>=cでありますから、a>=bかつb>=cなので推移律からa>=cでないといけないところが、a>=cはfalseであるため推移律と矛盾しているということです。


そのひとつ上の"Red"等の例では、たとえば"Red"と"Green"で言えば、
一回目の並び替え結果から"Red">="Green"ですが、二回目の並び替え結果から"Green">="Red"だということで、
反対称律より"Red"="Green"だと思われるわけですが、実際にCompareメソッドを見てみると1を返すので"Red"と"Green"は別物、よって矛盾するわけですね。


そしてCompareメソッドが全順序関係の性質を満たしていないと、ソートした結果のリストもおかしなことになる、
具体的に言えば2回ソートしたときに2回目も順番が入れ替わってしまうなど…

あれ、2回目に順番が変わってしまうことをCompareメソッドが全順序関係の性質を満たしていないことの根拠に使っていたんじゃないかな、因果関係を逆にしていいんだろうか。


うーん、見返してみると相当穴のある理論な気がしないでもないですが…。
以前書いたように自分で理論を積み上げていくの苦手なんですよ。

あと、これはそもそも論じる対象がナンセンスなのかもしれないですね。


まあようするに、独自に実装したIComparer.Compareメソッドが構成する関係が全順序関係の性質を満たしていないと、それを使ってソートしたら色々と不都合が発生してしまうんじゃないかと言いたいのです。


まあそれでソートしたら並び替え結果は全順序集合じゃなくなるので、順番もクソもなくなるという、ただそれだけのことと言ってもいいのですけどね。

まあ、私の理論はこのザマで、結局よくわからないのですが…。
なお、調べてみたら参考になりそうな記事が一件。


 推移律はいらない? ─比較ソートの正当性に必要な比較関数の性質─ - λx.x K S K @ はてな
http://d.hatena.ne.jp/KeisukeNakano/20131225/1387930086

こちらの記事はCoqとかいう証明に使う言語でゴニョゴニョするという内容で、日本語でおkという感じなのですが、推移律いらないんですか???

推移律いるんじゃないですかねえ。
そもそも正当性とはなんぞや。


というわけで途中から回答を放棄するという歴史に残るクソ記事を生み出してしまいましたが、お許し下さいませ。

しかし、こうやって記事に書いてみると、わかったつもりになっていることでも、自分の理解がすごく曖昧だということに気づくのでいいですよね。



ところで、話は変わりますが、MSDNにおいて

List(T).Sort メソッド (IComparer(T)) (System.Collections.Generic)
https://msdn.microsoft.com/ja-jp/library/234b841s(v=vs.110).aspx

を見ればリストの要素数によってはクイックソートを用いることもあると読めますが、

数値でない要素に対して自分でCompareメソッドを定義してソートするってときに、数値ならピボットを選ぶとき平均値を使えばまともに分割してくれますが、

数値でなくて平均値を算出できない場合はどうなんでしょうかね。


適当な要素を取ってきてピボットにするしかないと思いますが、最小値(実装によっては最大値)を運悪く取ってしまうとこれは無限ループに陥ってしまうのではないでしょうか。

なお、参考になりそうなWebページを探していたら私の姉妹ブログが出てきたので張っておきます。

クイックソートのピボットの選び方にて
http://blogs.yahoo.co.jp/blog_of_cyberboy/40477146.html


まあとりあえず一回やってみて分割されなかったら、さっき選ばなかったピボットを選ぶみたいな感じで上手いことやってるんでしょうか。

tag: C# リスト ソート 数学 順序 関係 クソ記事 クイックソート

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/477-c48b4e8f
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。