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も入れた。良さそうなのは何でもいれますよー。というわけでもないのですけどね、ちょっと便利、程度だと躊躇います。入力補完に大量にメソッドが出るってのはあんまり嬉しいものでもないですから、なるべく厳選して。

以前に応募した、Windows 7杯 自作PCの祭典 2009ですが、部門賞「勝手にオレが一番！部門」で無事受賞することが出来ました。部門賞の5台の中から、一般投票でグランプリを決めるので、是非とも私に投票してやってくださいー。あと2/13に秋葉原のリナカフェで当日一般投票&結果発表があるそうなので、そちらも是非どうぞ。あ、私の応募記事ですが→neue cc - デスクトップシアター for Windows 7杯になります。発表会場ではパネルに写真を飾るそうなので、もう少し良い写真を撮っておけば良かったなあ。昔は壁紙を揃えたりカッコつけた照明にしたりしてたんですが、今回は応募締め切りギリギリで必死に写真撮って記事書いて、ってやってたので余裕がありませんでした。若干後悔。

私的には、定格パフォーマンス部門の人のLevel 10が自作PC本体の魅力としてはカッコイイ！ですね。写真の構図が憎い。 あと、バカPC部門の冷蔵庫PCはナイスですな。リザーブタンク=ペットボトルは最高のアイディアだと思います。それにしても、かなり大掛かりに加工してあって、凄いなあ。まさに自作PC、という凄さでは一番ですね。他は、んー、特別賞のマルチタッチ賞が該当なしなのはしょうがないかな。Windows7杯なので、Win7の追加機能であるマルチタッチを！というのは分からないでもないけれど、自作PCでマルチタッチを生かすっていうのは難しいよ。一体何をどうすればいいんだ、という。

写真で振り返る机上写真の歴史

写真が残ってなかったりするのがあるのが悔しいなあ。とか思いつつも、残ってるものを探してきました。ローカルHDDに見つからなくても、Web上に残ってたりして助かりました。やっててよかったWebサイト。といっても、やはり残ってないのも多いのね。残念。

2002年です。VAIOなので自作PCじゃないよ！ これは何と言うか、懐かしいね。非常に懐かしい。CRTモニタはともかく、MDデッキとかMIDI音源(YAMAHAのMU2000)とかポータブルCDプレイヤーとか、今じゃあすっかり廃れたものが映っていて泣ける。マウスはIntelliMouse Explorerの、たぶん初代かな。

飛んで2006年です。4年も飛んじゃうのが痛い、こうなるまでにも過程があったんですが……。2002年の写真を見て思いっきり懐かしめたので、もっと残ってると良かったのだけど。既にXbox360だものねえ(画面のものはPGR3)。時代飛びすぎ。この頃はCRT信者でモニタを22インチCRETにしてトランスコーダーで写していましたね。液晶なんて残像！残像！あんなもんクソだ使えねー。CRT解像度最強だし。とか言ってた気がしますが、なかったことにしましょう。ちなみに2chスピーカーはこの頃のほうが良いの使ってました。PIEGAのアルミニュウム筐体のスピーカーでして、音もデザインもとても気に入ってました。サラウンド環境は7.1ch。マウスはMX1000かな、これは。多ボタンマウス信者の始まりである。

2007年の8月。いつのまにやら全モニターが液晶になってる。やっぱ液晶だとスタイリッシュな感じになりますなー。大きさは全部WUXGA(1920x1200)。サラウンドは、センタースピーカーなしの6.1chという若干変則的な形を取っていました。デスクトップシアターだとセンタースピーカーの置き場に困るんですよねー。この問題を解決させられなくてずーっと悩んでいました。ま、この頃はセンタースピーカーは左右スピーカーの中央で聞けるのならなくても問題ない。一人で椅子に座って聞くデスクトップシアターではファントム再生(左右のスピーカーでセンタースピーカーの音を仮想的に作る)でも問題ない。むしろ、そのほうが音の統一感が出ていい。とか言っていましたが、なかったことにしましょう。マウスは恐らくMX-R。キーボードはHappyHackingKeyboardですなー。デザインは最高に好き。でも、今は日本語配列のRealForceになりました。

2007年の11月。これはデスクトップシアターの薦めという記事で書いた時のもの。スピーカーを小型スピーカーに変更したことで、9.1ch環境になりました。スペース的にも大型スピーカーを廃したことで余裕が出て正解だったと思っています。センタースピーカーも、(モニタ土台のほうの)デスク下に配置することで解決。PIEGAのスピーカーとの決別と、それによる2ch再生力の低下に悩んだんですが、それは今ではSTAXで聴くからいいもん、という方向で解決(？)しました。

2008年の11月。こりゃまたえらく簡素になったねー、というわけですが、これは引越しして一人暮らしを始めた時の写真です。モニタとかデュアルでいいっすよ、とか思って色々と整理したはずなんですが、やっぱりデュアルでは不満になったので結局、買い揃えていくことになったという。なんだかなー。ともかく、新生活のフレッシュさを感じたり感じなかったりして、ちょっと思い出深い。涙ちょちょぎれます。で、まあ、私は家にいる時は、このデスク左にちょっと映ってるベッドで寝てるか、椅子に座ってるかの二択しかありません。NEETになりたいなあ。職場なんて行きたくないでござる。

2009年の2月。これはneue cc - 解像度6000オーバーという記事で書いたもので、メインモニタがついに30インチになりました記念。メインモニタとあわせて左右のモニタも新調しました。ちなみに、せっかくの縦回転ですが、今の環境だと縦が塞がっているので出来ないんですよねえ……。トレードオフといえばそうなのですけど、この頃がちょっと懐かしい。

2010年の1月。これがneue cc - デスクトップシアター for Windows 7杯の写真で、今の環境です。9.1chなのですが、AVアンプを変えたので全方位を横一列に取り囲んでの9.1chじゃなくて、フロント上部に2台設置しての9.1chという環境に変わりました。このハイトスピーカーの置き方は最近出たドルビープロロジックIIzという規格によるもので、徐々に増えて行くんじゃないかと思っています。まあ、あとは再びクアドラプルモディスプレイ環境に戻ったり、ノートPCがあるから5画面だよ、といった感じであったり、今までの集大成的なものになっています。

といったわけで、駆け足で振り返ってみました。やっぱ2002-2006の間の写真がないのが痛い。絶対後悔するので、写真はちゃんと残しておきましょう、まる。ブログにアップしておけば、サルベージも容易でいいね！ていうか、実際2002年の写真以外はローカルに残ってなくて全部ウェブから引っ張ってきたのですが……。やっててよかったWebサイト。あと、写真がちっとも上達しないのが酷い。むむむ。

• AnonymousComparer - lambda compare selector for Linq

AnonymousComparerを再度バージョンアップしました。ダウンロードは上記リンク先、CodePlexからどうぞ。バグがなければ、これで最後だと思います。いやもう内容的には出尽くしたかな、と。更新内容はIComparer<T>を作成可能にしました。また、OrderByでIComparer<T>を利用するものへ、拡張メソッドを追加しました。

// こんなシーケンスがあるとして、IComparer<T>を使用してその場で自由に比較を指定したい
var seq = new[] { 1, 2, 3 };
// IComparer<T>を作る
var comparer = AnonymousComparer.Create<int>((x, y) => y - x);
seq.OrderBy(x => x, comparer);
// OrderBy/ThenByに拡張メソッドが追加されているので、型推論が効いたまま書けます
// List.Sort(Comparison)みたいなイメージですかね
seq.OrderBy(x => x, (x, y) => y - x); // 3, 2, 1
seq.OrderByDescending(x => x, (x, y) => y - x); // 1, 2, 3

LinqにはDescendingが用意されているので、あまり使い道はなさそうですね。私もOrderByのICompare<T>オーバーロードを使いたいと思ったシチュエーションが今までにありませんし……。第一引数がkeySelectorなので、それで十分用を足せちゃうのですよね。それにしても、DescendingでIComparerを指定した場合の結果は紛らわしくていかんですな。

さて、更新内容はもう一つあって、むしろこっちのほうが重要なのですが、compareKeySelectorを利用したオーバーロード(Linq演算子への拡張メソッドは全部それです)で、シーケンスにnullが含まれている場合にnullで落ちるのを修正しました。今回からはヌルぽで落ちません。どういうこっちゃ、というと説明しづらいのでコードで。

class MyClass
{
    public int MyProperty { get; set; }

    public override string ToString()
    {
        return "Prop = " + MyProperty;
    }
}

static void Main()
{
    var array = new[]
    {
        new MyClass{MyProperty=1},
        null,
        new MyClass{MyProperty=2},
        null,
        new MyClass{MyProperty=1}
    };
    var r1 = array.Count(); // 5
    var r2 = array.Distinct().Count(); // 4 (nullが重複として消える)
    foreach (var item in array.Distinct(mc => mc.MyProperty))
    {
        Console.WriteLine((item == null) ? "ヌルぽ" : item.ToString());
    }
    // 出力結果は
    // Prop = 1
    // ヌルぽ
    // Prop = 2
}

といった感じです。分かったような分からないような？