読者です 読者をやめる 読者になる 読者になる

uehaj's blog

Grな日々 - GroovyとかGrailsとかElmとかRustとかHaskellとかFregeとかJavaとか -

Groovyのsortにまつわる衝撃の事実

groovy

今日までわたしは、リストを返すクロージャを、sortに渡せば、ソートの第一キー、ソートの第二キーみたいにソートするのに使えると私は思っていました。
例えば以下のようなコードです。

data1 = [aa:1, z:1, c:7, b:1, g:1]
println data1.sort{[it.value, it.key]}

このようなソート指定を私が最初に見たのは、角谷さんが翻訳されたGroovyドキュメントです。JGGUGの前身のGrails Code Reading勉強会の第一回ぐらいにこのテキストをもとにした読みあわせをやりましたが、そのときにもこのソート方法が話題になりました。上のドキュメントによれば、

Groovy Bean では複数のプロパティを使用したソートが簡単にできる。たとえば、Player という Bean に name、age、score というプロパティがあるとしよう。この Bean のリストが players に格納されていて、それを age と score の値を基に並び替えるには、次のように書く。

players.sort { [it.age, it.score] }

とのことです。

しかし、今日気づいたのは、1文字の長さの文字列ならこのやりかたで正しくソートできるのに、2文字の長さの文字列だとうまくソートされないということです。たとえば、最初の例は「[b:1, g:1, z:1, c:7, aa:1] が出力されます。

調べたところ、結論としてわかったのは、驚くべきことに、「(現バージョンの)Groovyにこんなソート機能は無い!」ということでした。ええ、無いのです。具体的には、このパターンのソートを実行すると呼ばれるのはsrc/main/groovy/util/OrderBy.javaで、別にリストについて特別扱いをしていないのです。そこでクロージャの戻り値のソートのための判定をしているのは次のコード:

            return value1.hashCode() - value2.hashCode();

です。今回比較用クロージャが返しているリストに関しては、hashCode()は次の動作をします。

  hashCode = 1;
  Iterator i = list.iterator();
  while (i.hasNext()) {
      Object obj = i.next();
      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
  }

要するにリストであれば頭から係数をかけて要素のhashCodeを合計していきます。また、S文字列が1文字であれば、String#hashCode()はその文字コードを返します。結果的にリストとしての辞書ソートみたいなものが実現されていて、「動くように見えていた」というのが真相です。しかしこれは偶然であり、例えば冒頭のコードのように比較対象文字列が2文字以上になると破綻します。Integerとかの数値のhashCodeはその数値自身でこれもうまくいくケースはあるかも。しかしこれを「正しく動いている機能」とみなすのはつらい。

GinA本にも書いてないので変だなと思って調べてみたらこの始末。えらい。すごい>GinA本。

この幻のテクニックの由来ですが、どっからきてるんでしょうね。もちろん原文"Groovy - Scripting for Java"にもあります。昔のバージョンのGroovyには存在していたのか、あるいは最初から無かったのか。Rubyにはあるのかな?少しだけ探したのですが見つけられませんでしたが。
アイデアとしてはとてもいいと思うんですよね。ブログの記事でほめているものをいくつか見たことがあります*1

実際に実装するように提案してみようかな。

*1:[http://d.hatena.ne.jp/uehaj/20081015:title=自分でも書いているし。すみません]

広告を非表示にする