linq.js ver 2.1.0.0 - ToDictionary, Share, Let, MemoizeAll

CodePlex - linq.js - LINQ for JavaScript

linq.jsを2.0から2.1に更新しました。今回はただのメソッド追加というだけじゃなく、1.*の時から続いてる微妙コードを完全抹殺の一掃で書き換えた結果、内部的にはかなり大きな変更が入りました。その影響で挙動が変わってるところも割とあります。

まず、OrderByのロジックを変更しました。これで動作はC#完全準拠です(多分)。前のはかなりアレだったのでずっと書きなおしたいと思ってたのですが、やっと果たせました。従来と比べるとThenByを複数個繋げた時の挙動が変わってくる(今まではOrderByのみ安定ソートで、ThenBy以降は非安定ソートだったのが、今回からは幾つ繋げても安定ソートになります)ので、複雑なソートをやろうとしていた場合は違う結果が出る可能性はなきにしもあらず、ですが、基本的には変化なしと見て良いと思います。

ちなみにJavaScriptのArray.sortは破壊的だし、安定である保証もないので、linq.jsのOrderBy使うのは素敵な選択だと思いますよ!非破壊的で安定で並び替え項目を簡単に複数連結出来る(ThenBy)という、実に強力な機能を提供しています。代償は、ちょっと処理効率は重いかもですね、例によってそういうのは気にしたら負けだと思っている。

他に関係あるところで大きな変更はToLookup。戻り値を、今まではJSのオブジェクトだったのですが、今回からはlinq.jsの独自クラスのLookupになります。すみませんが、破壊的変更です、前と互換性ありません。変えた理由はJSのオブジェクトを使うとキーが文字列以外使えないため。そのことはわかっていて、でもまあいっかー、と思っていたのですがGroupByとか内部でToLookupを使ってるメソッドの挙動が怪しいことになってる(という報告を貰って気づいた)ので、ちゃんとした文字列以外でもキーに使えるLookupを作らないとダメだなー、と。

GroupByでのcompareSelector

そんなわけで、GroupByのキーが全部文字列に変換されてしまう、というアレゲなバグが修正されました。あと、オーバーロードを足して、compareKey指定も出来るようにしました。何のこっちゃ?というと、例えばDateもオブジェクトも参照の比較です。

alert(new Date(2000, 1, 1) == new Date(2000, 1, 1)); // false
alert({ a: 0} == { a: 0 }); // false

JavaScriptではどちらもfalse。別のオブジェクトだから。C#だとどちらもtrue、匿名型もDateTimeも、値が比較されます。そんなわけでJavaScriptで値で比較したい場合はJSONにでもシリアライズして文字列にして比較すればいいんじゃね?とか適当なことを言ってみたりはしますが、実際Linqだと参照比較のみだと困るシーン多いんですねえ。そんなわけで、GroupBy/ToLookup、その他多数のメソッドに比較キー選択関数を追加しました。例を一つ。

var objects = [
    { Date: new Date(2000, 1, 1), Id: 1 },
    { Date: new Date(2010, 5, 5), Id: 2 },
    { Date: new Date(2000, 1, 1), Id: 3 }
]
 
// [0] date:Feb 1 2000 ids:"1" 
// [1] date:Jun 5 2010 ids:"2"
// [2] date:Feb 1 2000 ids:"3" 
var test = Enumerable.From(objects)
    .GroupBy("$.Date", "$.Id",
        function (key, group) { return { date: key, ids: group.ToString(',')} })
    .ToArray();

キーにDateを指定し、日付でグルーピングしたいと思いました(この程度の指定で関数書くのは面倒くさいし視認性もアレなので、文字列指定は非常に便利です)。しかし、それだけだと、参照比較なので同じ日付でも別物として扱われてしまうのでグルーピングされません。$.Date.toString()として文字列化すれば同一日時でまとめられるけれど、Keyが文字列になってしまう。後で取り出す際にKeyはDateのまま保っていて欲しい、といった場合にどうすればいいか、というと、ここで今回新設した第四引数のcompareSelectorの出番です。

// [0] date:Feb 1 2000 ids:"1,3"
// [1] date:Jun 5 2010 ids:"2"
var test2 = Enumerable.From(objects)
    .GroupBy("$.Date", "$.Id",
        function (key, group) { return { date: key, ids: group.ToString(',')} },
        function (key) { return key.toString() })
    .ToArray();

比較はキー(この場合$.Date)をtoStringで値化したもので行う、と指定することで、思い通りにグループ化されました。なお、C#でもこういうシーン、割とありますよね。C#の場合はIEqualityComparerを指定するのですが、わざわざ外部にクラス作るのは大変どうかと思う。といった時はAnonymousComparerを使えばlinq.jsと同じようにラムダ式でちゃちゃっと同値比較出来ます。

なお、今回からGroupByの第三引数(resultSelector)が未指定の場合はGroupingクラスが列挙されるように変更されました。GroupingはEnumerableを継承しているので全てのLinqメソッドが使えます。その他に、.Key()でキーが取り出しできるというクラスです。

Lookup

LookupはGroupByの親戚です。むしろGroupByは実はToLookupしたあと即座に列挙してるだけなのだよ、ナンダッテー。で、何かというとMultiDictionaryとかMultiMapとか言われてるような、一つのキーに複数個の要素が入った辞書です。そして、immutableです。不変です。変更出来ません。

var list = [
    { Name: "temp", Ext: "xls" },
    { Name: "temp2", Ext: "xLS" },
    { Name: "temp", Ext: "pdf" },
    { Name: "temp", Ext: "jpg" },
    { Name: "temp2", Ext: "PdF" }
];
 
var lookup = Enumerable.From(list).ToLookup("$.Ext", "$.Name", "$.toLowerCase()");
 
var xls = lookup.Get("XlS"); // toLowerCaseが適用されるため大文字小文字無視で取得可
var concat = xls.ToString("-"); // temp-temp2 <- lookupのGetの戻り値はEnumerable
var zero = lookup.Get("ZZZ").Count(); // 0 <- Getで無いKeyを指定するとEnumerable.Emptyが返る
 
// ToEnumerableでEnumerableに変換、その場合はGroupingクラスが渡る
// Groupingは普通のLinqと同じメソッド群+.Key()でキー取得
lookup.ToEnumerable().ForEach(function (g)
{
    // xls:temp-temp2, pdf:temp-temp2, jpg:temp
    alert(g.Key() + ":" + g.ToString("-"));
});

ToLookup時に第三引数を指定すると、戻り値であるLookupにもその比較関数が有効になり続けます。今回はtoLowerCaseを指定したので、大文字小文字無視でグルーピングされたし、Getによる取得も大文字小文字無視になりました。なお、GroupByでもそうですが、キーは文字列以外でも何でもOKです(compareSelectorを利用する場合はその結果が数字か文字列か日付、そうでない場合はそれそのものが数字か文字列か日付を使う方が速度的に無難です、後で詳しく述べますが)。

Dictionary

Lookupは内部でDictionaryを使うためDictionaryも作成、で、せっかく作ったのだから公開しますか、といった感じにToDictionaryが追加されました。ToObjectと違い、文字列以外をキーに指定出来るのが特徴です。

// 従来は
var cls = function (a, b)
{
    this.a = a;
    this.b = b;
}
var instanceA = new cls("a", 100);
var instanceB = new cls("b", 2000);
 
// オブジェクトを辞書がわりに使うのは文字列しか入れられなかった
var hash = {};
hash[instanceA] = "zzz";
hash[instanceB] = "huga";
alert(hash[instanceA]); // "huga" ([Object object]がキーになって上書きされる)
 
// linq.jsのDictionaryを使う場合……
// new Dictionaryはできないので、新規空辞書作成はこれで代用(という裏技)
// 第三引数を指定するとハッシュ値算出+同値比較にその関数を使う
// 第三引数が不要の場合はToDictionary()でおk
var dict = Enumerable.Empty().ToDictionary("", "",
    function (x) { return x.a + x.b });
 
dict.Add(instanceA, "zzz");
dict.Add(instanceB, "huga");
alert(dict.Get(instanceA)); // zzz
alert(dict.Get(instanceB)); // huga
 
// ...といったように、オブジェクト(文字列含め、boolでも何でも)をキーに出来る。
// ToEnumerableで列挙も可能、From(obj)と同じく.Key .Valueで取り出し
dict.ToEnumerable().ForEach(function (kvp)
{
    alert(kvp.Key.a + ":" + kvp.Value);
});

空のDictionaryを作りたい場合は、空のEnumerableをToDictionaryして生成します。微妙に裏技的でアレですが、まあ、こういう風に空から使うのはオマケみたいなものなので。というかToDictionaryメソッド自体がオマケです。DictionaryはLookupに必要だから作っただけで、当初は外部には出さないつもりでした。

第三引数を指定しないとオブジェクトを格納する場合は線形探索になるので、格納量が多くなると重くなります(toStringした結果をハッシュ値に使うので、Dateの場合は値でバラつくので大丈夫です、普通のオブジェクトの場合のみ)。第三引数を指定するとハッシュ値の算出にそれを使うため、格納量が増えても比較的軽量になります(ハッシュ衝突時はベタにチェイン法で探索してます)。なお、第三引数はハッシュ関数、ではあるのですが、それだけじゃなくて同値比較にも利用します。GetHashCodeとEqualsが混ざったようなものなので、ようするにAnonymousComparerのデフォルト実装と同じです。

勿論、ハッシュ関数と同値比較関数は別々の方が柔軟性が高いんですが(特にJavaScriptはハッシュ関数がないから重要性は高いよね!)、別々に設定って面倒くさいしぃー、結局一緒にするシーンのほうが割と多くない?と思っているためこのようなことになっています。というだけじゃなくて、もしequalsとgetHashCodeを共に渡すようにするなら{getHashCode:function(), equals:function()} といった感じのオブジェクト渡しにすると思うんですが、私はIntelliSenseの効かない、こういうオブジェクト渡しが好きではないので……。

メソッドはIDictionaryを模しているためAdd, Remove, Contains, Clear、それにインデクサが使えないのでGet, Set、EnumerableではないかわりにToEnumerableでKeyValuePairの列挙に変換。Addは重複した場合は例外ではなく上書き、Getは存在しない要素を取得しようとした場合は例外ではなくundefinedを返します。この辺はC#流ではなく、JavaScript風に、ということで。

GroupingはEnumerableを継承しているのに、DictionaryとLookupは継承していないのでToEnumerableで変換が必要です。C#準拠にするなら、Groupingと同じく継承すべきなのですが、あえて対応を分けた理由は、Groupingはそのまま列挙するのが主用途ですが、LookupやDictionaryはそのまま使うのがほとんどなので、IntelliSenseに優しくしたいと思ったのからです。90近いメソッドが並ぶと、本来使いたいGetとかが見えなくなってしまうので。

なお、Dictionaryの列挙順は、キーが挿入された順番になります。不定ではありません。JavaのLinkedHashMapみたいな感じです(C#だとOrderedDictionary、Genericsじゃないけど)。順序保持の理由は、DictionaryはLookupで使う->LookupはGroupByで使う->GroupByの取り出し順は最初にキーが見つかった順番でなければならない(MSDNにそう記載がある)。といった理由からです。ちなみにですが、GroupByが順番通りに来るってのは経験則では知ってたのですがMSDNに記載があったのは見落としていて、むしろ不定だと考えるべきじゃないか、とかTwitterでデマ吹いてたんですが即座にツッコミを頂いて大変助かりました、毎回ありがとうございます。

Share, Let, MemoizeAll

そして3つの新メソッド。これらはReactive Extensionsに含まれるSystem.Interactive.dllのEnumerableに対する拡張メソッドから移植しています。

// Shareはenumeratorを共有する
// 一つの列挙終了後に再度呼び出すと、以前中断されたところから列挙される
var share = Enumerable.Range(1, 10).Share();
var array = share.Take(4).ToArray(); // [1,2,3,4]
var arrayRest = share.ToArray(); // [5,6,7,8,9,10]
 
// 例えば、これだと二度列挙してしまうことになる!
// 1,1,2,3とアラートが出る
var range = Enumerable.Range(1, 3).Do("alert($)")
var car = range.First(); // 1
var cdr = range.Skip(1).ToArray(); // [2,3]
 
// Shareを使えば無駄がなくなる(アラートは1,2,3)
var share = range.Share();
var car = share.First(); // 1
var cdr = share.ToArray(); // [2,3]

Shareは、列挙の「再開」が出来ると捉えると良いかもしれません。ちなみに、再開が出来るというのは列挙完了までDispose(終了処理)しないということに等しいのには、少しだけ注意が必要かもしれません。

// Letの関数の引数は自分自身
// [1,2], [2,3], [3,4], [4,5]
Enumerable.Range(1, 5).Let(function (e)
{
    return e.Zip(e.Skip(1), "x,y=>[x,y]");
});
 
// 上のLetはこれと等しい
var range = Enumerable.Range(1, 3);
range.Zip(range.Skip(1), "x,y=>[x,y]");
 
// 余談:Pairwiseは↑と同じ結果です、一つ先の自分との結合
Enumerable.Range(1, 5).Pairwise("x,y=>[x,y]");

Letは、Enumerableを受け取ってEnumerableを返す関数を渡します。何のこっちゃですが、外部変数に置かなくても、メソッドチェーンを切らさずに自分自身が使えるということになります。使い道は主に自分自身との結合を取りたい場合、とか。なお、何も対処せずそのまま結合すると二度列挙が回ることには注意が必要かもしれません。

// MemoizeAllは、そこを一度通過したものはキャッシュされる
var memo = Enumerable.Range(1, 3)
    .Do("alert($)")
    .MemoizeAll();
 
memo.ToArray(); // 一度目の列挙なのでDoでalertが出る
memo.ToArray(); // 二度目の列挙はキャッシュからなのでDoを通過しない
 
// Letと組み合わせて、自己結合の列挙を一度のみにする
Enumerable.Range(1, 5)
    .MemoizeAll()
    .Let(function (e) { return e.Zip(e.Skip(1), "x,y=>[x,y]") });

MemoizeAllはメモ化です。二度三度列挙するものは、一度.ToArray()とかして配列に置いたりすることが少なくなかったのですが、MemoizeAllはその辺を遅延評価のままやってくれます。使いかっては良さそう。ただし、これもShareと同じく列挙完了まで例外が起ころうが何だろうがDispose(終了処理)しないのは注意が必要かもしれません。素のJavaScriptではリソース管理は滅多にないので関係ないですが、例えばメモ化が威力を発揮しそうな(linq.jsではWSHで、C#だったら普通にやりますよね)ファイル読み込みに使おうとすると、ちょっと怖い。ていうか私はそういう場合は素直にToArrayします。

この3つは「注意が必要かもしれません」ばかりですね!ただ、MemoizeAll->Let->Zipで自分自身と結合するのは便利度鉄板かと思われます。便利すぎる。

まとめ

Dictionaryの導入は地味に影響範囲が大きいです。集合演算系メソッドもみんなDictionary利用に変えたので。なんでかというと、ええと、そう、今まではバグっておりました……。trueと”true”区別しないとか。Enumerable.From([”true”,true]).Distinct()の結果が[”true”]になってました。ほんとすみません。今回から、そういう怪しい挙動は潰れたと思います。いや、Dictionaryがバグッてたら元も子もないのですが多分大丈夫だと思います思いたい。

とにかく一年前の私はアホだな、と。来年も同じこと思ってそうですが。

Share, MemoizeAll, LetのRx移植三点セットは遊んでる分には面白いんですが、使いどころは難しいですね。ちなみに、MemoizeAllということで、RxにはAllじゃないMemoizeもあるのですが、かなり挙動が胡散臭いので私としては採用見送りだし、C#でも使う気はしません。内部の動きを相当意識してコントロールしないと暴走するってのが嫌。

VS2010のJavaScript用IntelliSenseは本当に強化されましたねー。ということで、VS2010ならDictionaryやLookupでIntelliSenseが動作するのですが、VS2008では動作しません。完全にVS2010用に調整してたら2008では動かないシーンも幾つか出てきてしまった……。まあでも、2010は素敵なのでみんな2010使えばいいと思うよ。私はまだExpressですががが。一般パッケージ販売まだー?(6月です)

そういえば、2.0は公開からひと月でDL数100到達。本当にありがとうございます。そろそろ実例サンプルも作っていきたいのですがネタがな。Google Waveって結局どうなんでしょうかね。ソーシャルアプリは何か肌に合わない雰囲気なのでスルーで、Waveに乗り込むぜ、とか思ってたんですが思ってただけで乗り込む以前に触ってもいないという有様。HTML5は、ええと、基本はC#っ子なのでSilverlight押しだから。うー、じゃあChrome拡張辺りで……。いやでもHTML5かな、よくわからないけれど。

今のところ最優先事項はlinq.javaなんですけどね、忘れてない忘れてない。というか、linq.js 2.0も今回のOrderByのロジック変更も、linq.javaで書いてあったのを持ってきただけだったりして。もうほんと、とっとと出したいです。出してスッキリして次に行きたい。

そんなわけで、この2.1でlinq.jsはようやくスタート地点に立てたぜ、という感じなので使ってやってください。

Comment (2)

Me : (10/18 21:02)

Hi there.
First of all congratulations for this amazing library.
I hope one day it replaces the JavaScript specs about built-in functions.
Why are you switching to lower camel case in the new version? You are switching, aren’t you?
I know the traditions on JavaScript code style, but I think C#’s tradition is better! :D

Me : (10/19 01:56)

Also, this benchmark suggests that the performance is not very good.
http://danieltao.com/lazy.js/comparisons.html
I don’t know what version of the library they have used or how they have used it, but have you got any idea of what the performance is compared to other libs?
Thanks! :)

Name
WebSite(option)
Comment

Trackback(0) | http://neue.cc/2010/05/18_258.html/trackback

Search/Archive

Category

Profile


Yoshifumi Kawai
Microsoft MVP for Visual Studio and Development Technologies(C#)

April 2011
|
July 2018

Twitter:@neuecc
GitHub:neuecc
ils@neue.cc