hnwの日記

sort関数と全順序集合

PHP

大仰なタイトルですが、約1年前の記事「PHPのsort関数は相当おかしい」の補足記事です。僕が何を根拠にPHPのsort関数（の第二引数のデフォルト値）がおかしいと思ったかを説明します。一言でいうと、PHPの全ての値とSORT_REGULAR（言い換えるとPHPの<、==、>）の組み合わせが全順序集合になっていないからです。

前回の記事の概要

PHPのsort関数は第二引数で比較演算子を変更できますが、省略するとSORT_REGULARを用います。これはPHPの通常の比較演算子と同じ挙動で、両辺の値が数字っぽい場合は数値として、そうでなければ文字列として比較するものです。このような比較を用いると、ソートが不可解な挙動を示すことがあります。

$ php -r '$a=array("0xa","011","01a","2.0");sort($a);print_r($a);sort($a);print_r($a);'
Array
(
    [0] => 2.0
    [1] => 0xa
    [2] => 011
    [3] => 01a
)
Array
(
    [0] => 01a
    [1] => 2.0
    [2] => 0xa
    [3] => 011
)


4つの文字列をソートして、その結果を更にソートする、という例を作ってみました。1回目のソート結果では最大だった値"01a"が再度ソートすると最小になっています。これは大抵の人には予測不可能な挙動であり、挙動が予測可能なSORT_NUMERICまたはSORT_STRINGを明示的に指定すべきだ、というのが前回記事の趣旨でした。


では、なぜSORT_REGULARは不思議な動きをするのでしょうか。また、SORT_NUMERICやSORT_STRINGにすると何が変わるのでしょうか。これを説明する上で重要なのが、最初に挙げた「全順序集合」です。

全順序集合とは

全順序集合の定義はWikipediaによれば次のようなものです。

集合 A に、次のような条件（順序の公理と呼ばれる）を満たす二項関係 ≤ が定まっている時、対 (A, ≤) のことを順序集合 (ordered set) という。

  1. 反射律 (reflexivity): 任意の元 a について a ≤ a が成立。
  2. 推移律 (transitivity): a ≤ b かつ b ≤ c ならば a ≤ c が成立。
  3. 反対称律 (antisymmetry): a ≤ b かつ b ≤ a ならば a = b が成立。


順序集合 (A, ≤) が更に次の条件を満たすとき、(A, ≤) のことを全順序集合 (totally ordered set) という。

  1. 完全律 (totalness): A の任意の元 a, b について a ≤ b か b ≤ a のどちらかが成り立つ。


順序集合 - Wikipediaより抜粋


要は「順序」の数学的な定義とは何か？ということです。ざっくり言うと、全ての値を小さい方から一列に並べることができるものを全順序集合と呼びます。これは順序関係の中でも性質の良いものです。


SORT_REGULARの例で言えば、「全順序集合でない」とは「PHPの全ての値を一列に整列させることが出来ない」ということです。なぜ全順序集合ではないかと言うと、推移律が成立しないからです。（「"1e1"<"1f1"」かつ「"1f1"<"9"」なのに、「"1e1">"9"」が反例）


我々が普段考える「順序」は全順序集合なことが多いので、これを仮定して議論することが多い気がします。逆に、全順序集合でないものを扱うときは直感が外れる恐れがあるので、注意が必要です。

ソートは全順序集合を仮定している

ところで、ソートの定義って何でしょうか。Wikipediaには下記のようにあります。

主にコンピュータソフトにおけるリストに表示するデータに対し、全順序関係によって一列に並べることを指す。


ソート - Wikipedia


全順序関係が成り立つということは推移律が成り立つということですから、a,b,c,dがソート済みだとしたら、a≤b≤c≤dは当然として、a≤c、a≤d、b≤dなども成立しているのがソートということになります。


一方、SORT_REGULARは全順序集合ではないわけですから、そもそも上の定義でのソートは不可能です。また、ソートアルゴリズムの前提条件が成立しなくなるため、ソートアルゴリズム自体の挙動が予測不可能です。SORT_REGULARでの比較を考えると、隣接する要素同士の大小関係（a<=b<=c<=d）さえ、ソートアルゴリズムによっては保証できません（考えてみた範囲ではヒープソートがダメです）。PHPのsort関数はクイックソートで実装されているのでa<=b<=c<=dは保証できると思いますが、ソート結果として意味があるかは疑問です。

sort関数との付き合い方について補足

「PHPのsort関数は相当おかしい」に、第二引数がSORT_NUMERICやSORT_STRINGの場合は安心だと書きました。この両者であれば、PHPのあらゆる値に対して全順序集合となると考えたためです。


ただ、これは少し不正確でした。SORT_NUMERICについて言うと、NaN(Not a Number)を除外しないと全順序集合になりません。NaNは数字では無いことを意味する浮動小数点数で、無限大を無限大で割ったりすることで得られます。このNaNは他の数との比較が成り立たちません。

$ php -r '$nan=1e1000/1e1000;var_dump(0<=$nan, $nan<=0, $nan==0);'
bool(true)
bool(true)
bool(false)


0より大きく、0より小さいが、0とは違う、という意味不明な比較結果です。このように順序関係が定義できないので、ソート対象にすると不思議なことが起こります。

$ php -r '$a=array(2,1e1000/1e1000,3,1);sort($a,SORT_NUMERIC);print_r($a);'
Array
(
    [0] => 1
    [1] => 3
    [2] => NAN
    [3] => 2
)


NaNをソート対象に混ぜると挙動が怪しくなるのはPHPのせいではありません。例えばPerlで数値としてソートしても次のように不思議な結果になります。

$ perl -MData::Dumper -e 'my @a=(3,1,1e1000/1e1000,2);print Dumper sort {$a <=> $b} @a;'
$VAR1 = 1;
$VAR2 = 3;
$VAR3 = 'nan';
$VAR4 = 2;


結局、ソートして問題ないかどうかは「全順序集合かどうか」が基準になるということです。こんな単語を持ち出さなくてもNaNが入ってたらそりゃダメだろと思う人が多いでしょうし、その直感は非常に大切だと思います。ただ、前回の記事では直感を共有できない人には伝わらない気がしたので、説明を付ける意味で記事にまとめてみました。

まとめ

  • ソートは全順序集合を対象にする前提
    • 全順序集合ではないものをソートしても無意味
  • 数学すごい


数学って苦手意識が強い人が多いですが、今回の例で言えば「順序って何？」という答えにくい質問に理屈付きで答えてくれるわけですから、改めてすごい武器だと思うんですよね。小難しく書いてあっても実際は平易な内容のことも多いので、たまに向き合うと楽しいんじゃないかと思います。