Java は Collections.sort があるのに .NET は List 自身が Sort メソッドを持っているのはなぜ？

だそうです。あまり疑問でもないです。だってIListはSortないし。比較するならIList - ListでありList - ArrayListでしょう。とはいっても、JavaのArrayListはほとんどList(Javaのほうの)と同じようなものですが、そうなってくるとむしろメソッドがなくて不便！って思ってしまうのはC#脳。

そして何故かスレッドの話は迷走していて不思議。パフォーマンス？ んー……。勝手な印象論ですみませんが、1さん(名前を出すのもアレなので1さん、ということにさせてください)はJavaのCollections.sortの性能を勘違いしているんじゃないかな？ 配列のコピーを問題にしてるようだけど、Javaの方式はコピー、してますよ。もっとも最初の方の発言(効率は重要じゃない)と後ろの発言(コピーが嫌)が矛盾していますが。ともかく、実際のSunの実装を見てみましょう。

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

toArrayしてコピー。それをsortして、forで詰め替え。C#で同じような外部Sort関数を書くのならば以下のようになります。厳密には違いますが、それは最後に述べます。

static void Sort<T>(IList<T> list)
{
    T[] array = new T[list.Count];
    list.CopyTo(array, 0);
    Array.Sort(array); // List<T>のSortもArray.Sortを利用しています
 
    for (int i = 0; i < array.Length; i++)
    {
        list[i] = array[i];
    }
}

forで詰め替えている様は、マジマジと見ると微妙。実際、このコードには問題があります。クイズだと思って、どこが問題なのか考えてみてください、答えは最後に述べます。

List<T>のSortは、内部に配列を持っているため、CopyToとforでの詰め替えが不要です。パフォーマンスで言えば理想的な形になっているわけです。 ゲッタとセッタ経由でソートの入れ替えすればいいぢゃん、というのはそうですね、違います。配列のほうが速いし！というのもそうでしょうが、それ以前にListインターフェイスの実装は自由です。例えばLinkedListのゲッタを考えてみたらどうでしょう。getの度に前(もしくは後ろ)から走査があるため、パフォーマンスが悲惨な事になるのは容易に想像出来ます。ListはArrayListだけじゃないので、ゲッタ/セッタに頼るのは無理がある。汎用的に、Listインターフェイスならば何でも受け入れるという設計にする以上、コピーを作るのは不可避です。

というわけで、パフォーマンス云々を言うならば、内部を知っているListクラスがSortを持つのはベストな選択でしょう。そして利便性を考えてもベストな選択。ならばいったい何処に不満があるのでしょうか？

Javaのほうが優れているのは、「自前でIListを実装したクラス」を破壊的ソートするのに、クラスにSortメソッドを用意したくない。といったところでしょうか。Sortの実装自体は通常はArray.Sortを呼ぶだけなので簡単なので別に手間でもないのですけどね……。というか、この手の基本アルゴリズムを自前実装したのを使うのは悪です(勉強用に、なら当然すべきで悪なのは自前実装の妄信です)。

ようするところ、Sortメソッドを自前で用意したくないけど破壊的ソートが欲しい、ということになる。ふーむ、個人的にはなくてもいいかな。非破壊的なソートがLinqのOrderByを使うことで可能なので、破壊的のほうを欲しいとはあまり思わない。

ListIterator

では本題。何でC#には破壊的ソートをしてくれる外部関数がないの？というと、インターフェイスの都合上、不可能だから。が理由だと私は考えています(そもそも必要性薄いから、が最大の理由だと思いますがそれはそれとして)。Javaのsortと私の書いたC#のSortを見比べてください。大きな違いがあります。それは、forでソートした配列をリストに詰め直している部分。

i.set((T)a[j]); // Java
list[i] = array[i]; // C#

C#の場合、listがLinkedListのようなものだった場合は悲惨なことになります。それに比べて、JavaではListIteratorを用いているため、配列と同じ処理効率で値をセット出来ます。C#には、このJavaのListIteratorに相当するものがないので、全てのIListに対して問題なく性能を発揮する破壊的ソート関数を作成することは不可能です。

「LinkedListのようなもの」という歯切れの悪い言い方をしたのは、.NETのLinkedListはIListを実装していないからです。インデクサで気楽にアクセスすることは出来ません。これは、大変素晴らしい決断だと思います。軽い操作だと勘違いさせるような重たい処理は最初から用意しない。(なお、どうしてもindexで取得したい場合はLinqのElementAtが使えます)。JavaのLinkedListと比較してC#のは貧弱すぎて困るぜ！とか思っていたならば、それは大間違いで、むしろJavaのLinkedListが危険すぎて困る。

ただ、IListのインデクサは取得にコストがかからないことを期待、してもいいとは思います。そんなのを一々気にしてたら何も作れない。それにちゃんと、.NETのLinkedListはIListじゃないしね。ね。というわけで上のほうで出したクイズは、問題があるかないかは何とも言えない微妙ラインです。んーと、つまりはfor(int i;i < hoge.length(); i++)の問題点はどこだー！みたいな話で、基本的にはhoge.length()なんてコストがかからないのを期待して問題ないし、コストがかかるんならそのクソクラスが悪い、みたいな。

ついでに個人的な意見ですがListインターフェイスにListIteratorはそこまで必要ではない。普通のIteratorと機能がかなり被る割には、使う機会はとても少ない。おまけに、ListIteratorのsetってoptionalで、実装されていることが保証されてない。この手の、実装しなくてもいいインターフェイスって撲滅した方がいいと思うんですけどねー。私は怖くて呼べません。

とはいえ、保証されないインターフェイスを完全に撲滅など出来はしません。例えばList(Java)/IList(C#)のAddは実行出来ることが保証されていない。JavaならArrays.asList(1, 2, 3).add(4)を、C#なら(array as IList).Add で簡単にNotSupportedを吐きます。他にもReadOnlyにしたコレクションにインデクサで値をセットしようとすれば、これまた同様に例外。コレクションフレームワークにおいてインターフェイスの完全保証を実現しようとするのは大変難しい。とは、私じゃなくて Java コレクション API の設計に関する FAQでSunが妥協した、と言うぐらいなので、無理なのでしょう。

まとまってませんが、結論としては疑問に思ったらソース読むのが手っ取り早い、とかそんなところで。Javaの良いところはC#に比べてフレームワークのコードへのアクセスが簡単なところですね。C#は部分的にはコードは公開されていて大変タメになるのですが、色々と面倒くさいし、公開されてない範囲も少なくないし……。.NET Reflectorのお世話になりまくってイリーガルな気分を味わうのはもう嫌ぽ。嘘。リフレクタ大好きですがそれはそれ。

Windows7杯では、無事グランプリを逃して部門賞に落ち着いたりした昨今ですがこんばんわ。長らくBlog放置、ついでにゲームも放置中という有様なので、改めてスケジュールを考えなおさないとな、というところに来てたりします。今年はまずはlinq.jsのWSH対応をやるぞ！とか言ってた気がしますがちっともやってませんし。で、代わりに何をやっているかというと、何故かここ一ヶ月は延々とLinqのJava移植をやっていたりします。どうしてこうなった……。予定なんて立てるだけ無駄ってことですな。

そんなわけで、今週中、無理でも来週中にはリリースするつもり、です。もう実装は出来上がっているのですがテストを一切書いてないので、テスト書きとJavaDoc書きと、あと事前条件の例外送出(これも一切書いてない)が残っているので、やらないといけない。実装はやる気満々にノリノリで書けたんですが、残ったこれらをやるのはモチベーションが全然上がらない。ダルぃ。シュタゲやりたい(やれよ)

進捗は例によってneuecc on Twitterでgyazoで画像張りながら、Javaに文句つけながらやってます。スタンダードにwhere-selectとか(NetBeansの赤線は解決しました)、正規表現がスッキリ！とかは、まぁまぁ悪くないと思うのですが、左外部結合で記述がカオスなどは何とも言えないネタ感が。作者の私がメソッドのシグネチャを合わせられなくて苦労したぐらいなので、一体誰が使えるんだよ、という。Join系は鬼門です。あと、匿名型の代わりにTupleを使うのですが、型定義が地獄になるのもねえ。 定番の無限フィボナッチなんかも書いたけど、Tupleの型定義のクドささえなければ見れるのだけど、現状だと少し厳しい。

// static importと合わせるとLLっぽく見えて素敵、的な何か
for (int i : range(5, 10)) {
    System.out.println(i);
}
 
// 10以上のもののうち重複なしで二倍にしてリストに格納する的な何か
int[] array = {3, 13, 51, 2, 1, 51, 67, 32, 13, 9};
ArrayList<Integer> list = Enumerable.from(array)
        .where(Predicates.greaterEqual(10))
        .distinct()
        .select(Functions.multiply(2))
        .toList(); // [26,102,134,64]

Java7のクロージャと型推論に期待しつつ、今のうちに出来ることはやっておく、的な何か。期待しないで期待して待っててください。多分、思われているよりかはマトモに使える代物だと思います。移植なんて誰もが考えるし、LinqのJava実装なんて当然幾つかあるんですが、どれも全然徹底してない(中途半端にSQLには対応してる)ので、今一つなんですね(JavaScriptの時も同じこと思ったわけだけど……)。ひたすら愚直にLinq to Objectsだけを忠実移植したものは初になると思います。いやまあ、何で誰もやらないかっていうと誰得としか言いようがないから、ってのもありますが。私は、割と普通なLinq好きーなのでそんなのちっとも気にしない！

標準Linq以外のメソッド類はlinq.jsにあるのは大体入れた。linq.jsのRangeDownToはアホだったので削った。RangeTo(0,-10)でいいわけですよね、Toなのだから。DownToとかアホすぎた、といったような反省も若干活かしてます。それとRxのCatchとかFinallyも入れた。良さそうなのは何でもいれますよー。というわけでもないのですけどね、ちょっと便利、程度だと躊躇います。入力補完に大量にメソッドが出るってのはあんまり嬉しいものでもないですから、なるべく厳選して。