ToLookup<TKey,TElement> の基本と応用
ネタもと『どうでもいいコードの断片 - プログラマブルな趣味、もっぱらスクリプティング』．
ツボにはまればとっても便利な ToLookup．でもちょっと知名度低いかもしれない．
例えばこんなコード．
using System; using System.Linq; using System.IO; static class Program { static void Main(string[] args) { // ファイルリスト var fileNames = new[] { "200.xls", "100.doc", "300.ppt", "500.xls", "400.ppt", "600.ppt" }; // 拡張子からファイルリストへのルックアップテーブルを作成 var extToFiles = fileNames.ToLookup(f => Path.GetExtension(f)); // 拡張子 ".xls" を持つファイル名を表示 extToFiles[".xls"].ToList().ForEach(Console.WriteLine); // 拡張子 ".js" を持つファイル名を表示 extToFiles[".js"].ToList().ForEach(Console.WriteLine); } }
ILookup<TKey,TElement> って何？
ToList や ToArray，ToDictionary は今までも対応するコンテナがあったからまあ分かる．でも ToLookup が返す Lookup<TKey, TElement> ってコンテナは何？ という人は IDictionary<TKey, IEnumerable<TElement>> の便利版と考えればとりあえず OK．
ILookup<string, int> lookup = ... // インデクサにキーを与えると対応する IEnumerable<T> が返る IEnumerable<int> q1 = lookup["Key1"]; IEnumerable<int> q2 = lookup["Key2"];
IDictionary<TKey, IEnumerable<TElement>> と比べてどこが便利かというと，存在しないキーについて空のシーケンスを返してくれるところ．
// 存在しないキーについては空シーケンスが返り，例外は起きない IEnumerable<int> q2 = lookup["not existing key"]; Assert.AreEqual(0, q2.Count());
存在しないキーに空シーケンスを返すと何がうれしいの？
この挙動はパイプラインを連結していったときに真価を発揮する．
// 以下のようなコードで key の存在チェックが不要になる List<string> list = ... list.Select(key => lookup[key]) .Select(q => q.Count()); list.SelectMany(key => lookup[key]) .ForEach(Console.WriteLine);
どんなときに使うの？
データベースによる階層構造表現．ありがちな隣接リストモデルでたとえばこんなのを考えてみる．
| Element | Parent |
|---|---|
| "Object" | null |
| "MarshalByRefObject" | "Object" |
| "Stream" | "MarshalByRefObject" |
| "BufferedStream" | "Stream" |
| "FileStream" | "Stream" |
| "IsolatedStorageFileStream" | "FileStream" |
| "MemoryStream" | "Stream" |
| "UnmanagedMemoryStream" | "Stream" |
| "CryptoStream" | "Stream" |
| "PipeStream" | "Stream" |
| "AnonymousPipeServerStream" | "PipeStream" |
| "AnonymousPipeClientStream" | "PipeStream" |
| "NamedPipeServerStream" | "PipeStream" |
| "NamedPipeClientStream" | "PipeStream" |
階層ツリーを親の方向にたどるのは簡単．要素名は Unique ということにして，ある要素の階層の親をたどるには再帰的に Parent 列の項目をたどっていけば OK．でも Root から子方向に全部たどるのはこのままだと分かりにくいね，と．
そこで Parent をキーにして "ToLookup" してみる．
- Object
- MarshalByRefObject
- MarshalByRefObject
- Stream
- Stream
- BufferedStream
- FileStream
- MemoryStream
- UnmanagedMemoryStream
- CryptoStream
- PipeStream
- FileStream
- IsolatedStorageFileStream
- PipeStream
- AnonymousPipeServerStream
- AnonymousPipeClientStream
- NamedPipeServerStream
- NamedPipeClientStream
これは親が同じ要素同士でテーブルを分割したのに相当する．最近の Explorer や Outlook の表示形態で「グループ化」ってのがあるけど，あれと同じ．
まず子要素を列挙して，列挙された子要素をキーとすれば今度は孫要素が列挙できる．こうして，ある要素にぶら下がった要素を全て列挙できる．
隣接リストモデルから ToLookup
まず C# 3.0 でテーブル定義．
var table = new [] { new {Element="Object", Parent=default(string)}, new {Element="MarshalByRefObject", Parent="Object"}, new {Element="Stream", Parent="MarshalByRefObject"}, new {Element="BufferedStream", Parent="Stream"}, new {Element="FileStream", Parent="Stream"}, new {Element="IsolatedStorageFileStream", Parent="FileStream"}, new {Element="MemoryStream", Parent="Stream"}, new {Element="UnmanagedMemoryStream", Parent="Stream"}, new {Element="CryptoStream", Parent="Stream"}, new {Element="PipeStream", Parent="Stream"}, new {Element="AnonymousPipeServerStream", Parent="PipeStream"}, new {Element="AnonymousPipeClientStream", Parent="PipeStream"}, new {Element="NamedPipeServerStream", Parent="PipeStream"}, new {Element="NamedPipeClientStream", Parent="PipeStream"}, };
ToLookup を使ってルックアップテーブルに変換．
var lookup = table.Where(item => item.Parent != null)
.ToLookup(item => item.Parent, item => item.Element);
Parent が null のものを抜いておくのがこつ．ToLookup のオーバーロードもいくつかある．
いったんルックアップテーブルができればあとは簡単．
// "Object" の子要素を列挙 lookup["Object"].ForEach(s => Console.WriteLine(s)); // "Object" の孫要素を列挙 lookup["Object"].SelectMany(item => lookup[item]) .ForEach(s => Console.WriteLine(s)); // "Object" のひ孫素を列挙 lookup["Object"].SelectMany(item => lookup[item]) .SelectMany(item => lookup[item]) .ForEach(s => Console.WriteLine(s));
Lookup を利用した再帰を一発で書く
先日公開した Achiral では CascadeDepthFirst / CascadeBreadthFirst という Extension Method が用意してあって，先ほどの SelectMany の繰り返しを再帰的に行ってくれる．色々な型を "Extension" しているので，書き方も色々．
// Func<T, IEnumerable<T>>.CascadeDepthFirst(T initial) var q1 = Make.Func((string item) => lookup[item]) .CascadeDepthFirst("Object"); // ILookup<T, T>.CascadeDepthFirst(T initial) var q2 = lookup.CascadeDepthFirst("Object"); // IEnumerable<T>.CascadeDepthFirst(ILookup<T, T> lookup) var q3 = Make.Sequence("Object") .CascadeDepthFirst(lookup); // IEnumerable<T>.CascadeDepthFirst(Func<T, IEnumerable<T>> func) var q4 = Make.Sequence("Object") .CascadeDepthFirst(item => lookup[item]); // IEnumerable<T>.CascadeDepthFirst(Func<T, IEnumerable<T>> func, // Func<T, int, TResult> selector) var q5 = Make.Sequence("Object") .CascadeDepthFirst(item => lookup[item], (item, nestLevel) => item);
実際に Reflection で mscorlib.dll と System.Core.dll に含まれる type-tree を書いてみる．ルートを System.IO.Stream として，それ以下のものを列挙．
using System; using System.Linq; using System.IO; using Achiral; using Achiral.Extension; static class Program { static void Main(string[] args) { // mscorlib.dll と System.Core.dll に含まれる全ての型 var types = Enumerable.Concat( typeof(int).Assembly.GetTypes(), typeof(Enumerable).Assembly.GetTypes()); var childrenLookup = types.Where(type => type.BaseType != null) .ToLookup(type => type.BaseType, type => type); childrenLookup.CascadeDepthFirst(typeof(Stream), (Type, NestLevel) => new { Type, NestLevel } ) .ConsoleWriteLine(item => new string(' ', 3 * item.NestLevel) + item.Type.FullName); } }
実装についてはソースコードをどうぞ．
便利な ToLookup を追加する
Achiral では他にも ILookup を作るための拡張メソッドをサポートしている．
一番使い勝手が良いのが，IDictionary<TKey, IEnumerable<TResult>> から ILookup<TKey, TResult> を作る拡張メソッド．
using Achiral; using Achiral.Extension; var lookup = new Dictionary<string, IEnumerable<string>> { { "Object", new []{"MarshalByRefObject"} }, { "MarshalByRefObject", new []{"Stream"} }, { "Stream", new []{"BufferedStream", "FileStream"} }, { "FileStream", new []{"IsolatedStorageFileStream"} }, }.ToLookup();
このほか，IDictionary<TKey, Func<IEnumerable<TResult>>> から ILookup<TKey, TResult> への ToLookup も追加してある．
using Achiral; using Achiral.Extension; var lookup = new Dictionary<string, Func<IEnumerable<object>>> { { "Once", () => Enumerable.Repeat(new object(), 1) }, { "Twice", () => Enumerable.Repeat(new object(), 2) }, { "Infinite", () => Make.Repeat(new object()) }, }.ToLookup();
これで階層的な構造のデータソースも比較的楽に取り扱えるようになる，かもしれない．
