[Java]シャッフルの話

面白い例外を出したので、話のタネに。

配列をシャッフルする必要がありました。
Arrays.shuffle()という関数があればそれを使って終わりだったのですが、残念ながらはCollectionsshuffle()はあってもArrays.shuffle()はありません。シャッフルのためだけにわざわざコレクションにデータを移しかえるのは無駄なので（この認識は間違いです。正解はページの最後でｗ）別の方法を模索しました。
別の理由でこの配列をsortする必要がありましたので、おなじくsort()を使ってシャッフルができないかと思い付き、以下のようなComparatorを作ってみました。

class Comparison implements Comparator<Player> {
 @Override
 public int compare(Player lhs, Player rhs) {
  return rand.int(3)-1;
 }
}

compare()は2つのオブジェクトを比較して、大小の判定をします。
通常はデータを解析して適切な判断をするのですが、このComparatorは結果を乱数で返します。
比較結果がめちゃくちゃなのですから、まっとうに並ぶわけがないですが、シャッフルしたいのですから狙い通りです。
これは一見上手くいきました。
一見上品にもみえました。

しかし、このロジックは稀に例外を起こします。

java.lang.IllegalArgumentException: Comparison method violates its general contract!

general contract、一般契約に違反しています、というもの。
この場合の一般契約とは、Java.lang.Objectのメソッド、equalsが同じものは常に同じであることを保証するというものを指すのだと思います。
equalsとhashCoedeはObjectのメソッド、Java世界のすべてのオブジェクトが備えていなければならないものです。
例えばこれらはHashMap等にオブジェクトに格納する際に使用されます。
一般契約が守られなければ、これらJavaの根幹に当たる仕組みの動作が保証されなくなります。
とても大事なルールなのです。

さて、今回私はObjectをいじっているわけではありませんが、Objectが一般規約を守っているという前提で使用されているsortという仕組みを使っています。
どのようにして私のハッキングに気がついたのか定かではありませんが、恐らくはsortのロジックがあり得ない状態に陥ったのは想像に難くありません。
この仕掛けはやってはいけないものでした。

この話の怖いところは、上記の例外が以外と低確率でしかでないということです。
件のアプリでは、データ8つの抽選で遭遇することはまずなくて、80個程度の抽選で時々出るというくらいでした。
この致命的なバグは、試験が甘ければ気付かれることなく製品に入り込む可能性が十分にあります。

では、当初の命題、配列をシャッフルするにはどうするのが正しいのでしょうか。
今、私は以下のロジックを使っています。

Collections.shuffle(Arrays.asList(players));

別の記事で書きましたが、asListはplayersをラップする固定長のリストを返します。asListで返されたリストの内容を操作するとplayersの内容も操作されることが仕様上保証されています。シャッフルの場合ももちろんplayersのインスタンス内容が直接シャッフルされます。
リスト化する際にコピーが発生しませんから、配列をシャッフルするのとほぼ等価なパフォーマンスが期待できます。

ところで、こんな仕掛けを思いついてしまいました。

class Comparison implements Comparator<Player> {
 @Override
 public int compare(Player lhs, Player rhs) {
  if(lhs==rhs){
   return 0;
  }else{
   return rand.int(2)==0?1:-1;
  }
 }
}

同じインスタンスなら0（同じ）を返し、それ以外は0以外をランダムで返します。
比較は乱数ですが、equalsについての動作は保証されています。
まぁ、単なる興味で、使う気はありませんが。