何故C#には(Javaの)Collections.sortに相当するものがないのか

2010-02-25

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のお世話になりまくってイリーガルな気分を味わうのはもう嫌ぽ。嘘。リフレクタ大好きですがそれはそれ。

何故C#には(Javaの)Collections.sortに相当するものがないのか

ListIterator

Profile

Archive