トップ > .NET

pull or push / LINQ or Rx

.NET

partitionedはstd::partitionのlazy版です。

一瞬「すげー」と思ったんですが，よく読んでみたら，単に source sequence を二回列挙してるだけっぽくて残念*1．というかまあ二回列挙していいなら全然難しくありませんよね．C# で書いたとしたらこんな感じでしょーか．

static class Make
{
    public static Tuple<IEnumerable<T>, IEnumerable<T>> Partition<T>(
        this IEnumerable<T> source, Func<T, bool> pred)
    {
        return new Tuple<IEnumerable<T>, IEnumerable<T>>(
            source.Where(pred), source.Where(x => !pred(x)));
    }
}

『2007/4/2 - 当面C#と.NETな記録』のころからこの話をしているような気がしますが，source sequence を複数回列挙するような LINQ 演算子は邪道というのが私の持論です．
しかしながら source sequence の列挙回数は最大 1 回という条件を満たそうとすると，partition 系の分岐操作で面倒なことになります．このあたりは pull 型の連鎖である LINQ の宿命でしょうか．
以前『パイプライン色々: top down vs. bottom up (2) - NyaRuRuの日記』でまとめましたが，分岐操作は push スタイルの方が向いています．ちょうどタイミング良く .NET Reactive Framework (Rx) が最近ホットなので，興味がある人はチェックしてみると良いでしょう．Rx は push スタイルでイベントの連鎖を記述するため，partition 操作には向いているはずです．

参考

*1:おそらく，oven の range に相当するのは .NET では IEnumerator<T> であって，IEnumerable<T> ではないということなのでしょう．

文字列に頼らないリフレクション

.NET

なんかまた最近流行っぽいので．
拙作 Achiral では，ConstructorInfo や PropertyInfo を以下のように文字列に頼らずに取得可能です．

using System;
using System.Linq;
using System.Reflection;

using Achiral;
using Achiral.Extension;

static class Program
{
    static void Main(string[] args)
    {
        var member_info_list = new MemberInfo[]
        {
            Make.ConstructorInfo(() => new Version()),
            Make.PropertyInfo(() => Environment.CommandLine.Length),
            Make.MethodInfo(() => Console.WriteLine(default(int))),
        };

        member_info_list.ConsoleWriteLine();
    }
}

うちの日記での初出は『日本語識別子，Member Renaming，strong-typed reflection - NyaRuRuの日記』あたりですかね．私も当時この手法を知って結構感動した記憶があります．

C# でローカル変数の再代入を禁止したいとき

.NET

とりあえずみんな一回 let 句使ってコード書いてみるべき．

var seq =
    from _ in Enumerable.Repeat(1, 1)
    let x = 1000
    let xs = new List<int>{x}
    let y = Math.PI / 2.0
    let z = "hauhau"
    select _;

var pixelsQuery =
    from y in Enumerable.Range(0, screenHeight)
    let recenterY = -(y - (screenHeight / 2.0)) / (2.0 * screenHeight)
    select from x in Enumerable.Range(0, screenWidth)
           let recenterX = (x - (screenWidth / 2.0)) / (2.0 * screenWidth)
           let point = Vector.Norm(Vector.Plus(scene.Camera.Forward, 
                                               Vector.Plus(Vector.Times(recenterX, scene.Camera.Right),
                                                           Vector.Times(recenterY, scene.Camera.Up))))
           let ray = new Ray { Start = scene.Camera.Pos, Dir = point }
           let computeTraceRay = (Func<Func<TraceRayArgs, Color>, Func<TraceRayArgs, Color>>)
            (f => traceRayArgs =>
             (from isect in
                  from thing in traceRayArgs.Scene.Things
                  select thing.Intersect(traceRayArgs.Ray)
              where isect != null
              orderby isect.Dist
              let d = isect.Ray.Dir
              let pos = Vector.Plus(Vector.Times(isect.Dist, isect.Ray.Dir), isect.Ray.Start)
              let normal = isect.Thing.Normal(pos)
              let reflectDir = Vector.Minus(d, Vector.Times(2 * Vector.Dot(normal, d), normal))
              let naturalColors = 
                  from light in traceRayArgs.Scene.Lights
                  let ldis = Vector.Minus(light.Pos, pos)
                  let livec = Vector.Norm(ldis)
                  let testRay = new Ray { Start = pos, Dir = livec }
                  let testIsects = from inter in
                                       from thing in traceRayArgs.Scene.Things
                                       select thing.Intersect(testRay)
                                   where inter != null
                                   orderby inter.Dist
                                   select inter
                  let testIsect = testIsects.FirstOrDefault()
                  let neatIsect = testIsect == null ? 0 : testIsect.Dist
                  let isInShadow = !((neatIsect > Vector.Mag(ldis)) || (neatIsect == 0))
                  where !isInShadow
                  let illum = Vector.Dot(livec, normal)
                  let lcolor = illum > 0 ? Color.Times(illum, light.Color) : Color.Make(0, 0, 0)
                  let specular = Vector.Dot(livec, Vector.Norm(reflectDir))
                  let scolor = specular > 0 
                               ? Color.Times(Math.Pow(specular, isect.Thing.Surface.Roughness), light.Color) 
                               : Color.Make(0, 0, 0)
                  select Color.Plus(Color.Times(isect.Thing.Surface.Diffuse(pos), lcolor),
                                    Color.Times(isect.Thing.Surface.Specular(pos), scolor))
              let reflectPos = Vector.Plus(pos, Vector.Times(.001, reflectDir))
              let reflectColor = 
                  traceRayArgs.Depth >= MaxDepth
                  ? Color.Make(.5, .5, .5)
                  : Color.Times(isect.Thing.Surface.Reflect(reflectPos), 
                                f(new TraceRayArgs(new Ray { Start = reflectPos, Dir = reflectDir }, 
                                                   traceRayArgs.Scene, 
                                                   traceRayArgs.Depth + 1)))
              select naturalColors.Aggregate(reflectColor, (color, natColor) => Color.Plus(color, natColor)))
                                  .DefaultIfEmpty(Color.Background).First())
           let traceRay = Y(computeTraceRay)
           select new { X = x, Y = y, Color = traceRay(new TraceRayArgs(ray, scene, 0)) };

foreach (var row in pixelsQuery)
    foreach (var pixel in row)
        setPixel(pixel.X, pixel.Y, pixel.Color.ToDrawingColor());

(追記)
そういえば『C# 3.0 と let キーワード - NyaRuRuの日記』でも色々サンプル書いていた．

FizzBuzz

var f2 = from x in Enumerable.Range(1, 100)
         let a = x % 3 == 0 ? "Fizz" : ""
         let b = x % 5 == 0 ? "Buzz" : ""
         let c = (x % 3 != 0 && x % 5 != 0) ? x.ToString() : ""
         select a + b + c;

今年の1月1日から12月31日までを列挙

var cal = from month in Enumerable.Range(1, 12)
          let year = DateTime.Today.Year
          let numDays = DateTime.DaysInMonth(year, month)
          from day in Enumerable.Range(1, numDays)
          select new DateTime(year, month, day);

2000年から2009年までの13日の金曜日は？

var ft13 = from year in Enumerable.Range(2000, 10)
           let daysInThisYear =
               from month in Enumerable.Range(1, 12)
               let numDays = DateTime.DaysInMonth(year, month)
               from day in Enumerable.Range(1, numDays)
               select new DateTime(year, month, day)
           from date in daysInThisYear
           where date.Day == 13 && date.DayOfWeek == DayOfWeek.Friday
           select date;

2000年から2009年までの各年の日曜日の数

var mysundays =
    from year in Enumerable.Range(2000, 10)
    let daysInThisYear =
        from month in Enumerable.Range(1, 12)
        let numDays = DateTime.DaysInMonth(year, month)
        from day in Enumerable.Range(1, numDays)
        select new DateTime(year, month, day)
    let sundaysInThisYear =
        from date in daysInThisYear
        where date.DayOfWeek == DayOfWeek.Sunday
        select date
    select new { Year = year, SundayCount = sundaysInThisYear.Count() };

ユーザー定義のデフォルトコンストラクタと配列の初期化

.NET

(多くの) .NET 言語で，構造体にユーザー定義のデフォルトコンストラクタを作れないのはなんでよ？ という話．
http://pc12.2ch.net/test/read.cgi/tech/1245836827/949-
自分の理解としては >>964 の人と同じ．
.NET アセンブリの仕様としては，構造体にユーザー定義のデフォルトコンストラクタを定義することは可能．ただ，仮に定義したとしても配列の初期化では呼び出されないという点だけで十分に罠過ぎる．メジャーどころの .NET 言語は，言語レベルで禁止ということで個人的には納得済み．
ちなみに値型配列について，ユーザー定義のデフォルトコンストラクタを適用したい場合は，Array.Initialize という専用メソッドを呼び出してやるか，勝手に Array.Initialize を挿入してくれる言語とコンパイラが必要．
ついでに 0 初期化についても少し．
0 初期化された巨大なデータ構造が必要なとき，もし OS にゼロページを要求できるなら，データ構造にゼロページを割り当てて，かつ必要になるまでメモリアクセスをしないのが御利益が多め．
以下のふたつのコードは，buf と buf2 の中身は同じでも，割り当てられたページの状態には大きな違いがある．

const int bufSize = 1024*1024*512;
char* buf = (char*)VirtualAlloc(NULL, bufSize, MEM_COMMIT, PAGE_READWRITE);

char* buf2 = new char[bufSize];
SecureZeroMemory(buf2, bufSize);

buf については，VirtualAlloc 直後の段階ではまだワーキングセットは増えていない．512 MB 分のゼロページが割り当てられただけ．一方 buf2 については SecureZeroMemory がメモリ書き込みを行うので，確実に 512 MB のダーティー領域を作り出してしまう．仮にこの SecureZeroMemory の直後にページライタが動き出すだすと，buf2 の中身である大量のゼロは律儀にページファイルへ書き出されることに*1
CLR はこの辺がしっかりしていて，Large Object Heap に取られるような大きな構造体配列を作成すると，初期状態でゼロページになっている模様．C++/CLI で実験してみる．

#using <System.dll>
#using <System.Drawing.dll>
#include <atlbase.h>
#include <atltypes.h>

using namespace System;
using namespace System::Drawing;
using namespace System::Diagnostics;

int main() {
  const int elements = 1024*1024*16;

  Process^ process = Process::GetCurrentProcess();

  process->Refresh();
  Console::WriteLine(L"WS: {0}", process->WorkingSet64);
  Console::WriteLine(L"new CPoint[elements]");

  CPoint* ps = new CPoint[elements];
  process->Refresh();
  Console::WriteLine(L"WS: {0}", process->WorkingSet64);

  Console::WriteLine(L"gcnew array<Point>(elements)");
  array<Point>^ ps2 = gcnew array<Point>(elements);
  process->Refresh();
  Console::WriteLine(L"WS: {0}", process->WorkingSet64);

  for (int i = 0; i < elements; ++i) {
    ps2[i].X = 0;
    ps2[i].Y = 0;
    if (i % (1024*1024*1) == 0) {
      process->Refresh();
      Console::WriteLine(L"WS: {0} (index = {1})", process->WorkingSet64, i);
    }
  }

  // call IDisposable.Dispose
  delete process;

  delete[] ps;

  String^ s = Console::ReadLine();
  return 0;
}

結果．

WS: 9404416
new CPoint[elements]
WS: 144723968
gcnew array<Point>(elements)
WS: 145436672
WS: 145477632 (index = 0)
WS: 153870336 (index = 1048576)
WS: 162471936 (index = 2097152)
WS: 171114496 (index = 3145728)
WS: 179765248 (index = 4194304)
WS: 188407808 (index = 5242880)
WS: 197050368 (index = 6291456)
WS: 205701120 (index = 7340032)
WS: 214343680 (index = 8388608)
WS: 222998528 (index = 9437184)
WS: 231641088 (index = 10485760)
WS: 240291840 (index = 11534336)
WS: 248938496 (index = 12582912)
WS: 257589248 (index = 13631488)
WS: 266231808 (index = 14680064)
WS: 274882560 (index = 15728640)

ATL の CPoint を使うと，配列作成直後にいきなりワーキングセットが増加しているのに対し，System::Drawing::Point は配列要素へのアクセスによって順次ワーキングセットが増えていく．

*1:ただし Windows Vista 以降のページライタは，全てゼロであるページをゼロページに差し替えるようになった．[http://d.hatena.ne.jp/NyaRuRu/20071025/p1:title=ホワイトペーパー: Windows のメモリ管理の進歩 - NyaRuRu の日記] 参照のこと

if が文とは限らない話と，条件分岐で参照を返す話

.NET

(略)

でも、「式」しか書けない所ではそうはいかない。

例えば、(C++ で) 初期化リストの中や TMP では if 文なんて使えないので条件演算子を使わなければならない。

// ちと作為的な例だけど
class hoge
{
    const piyo& ref_p;
public:
    hoge(int a, int b, const piyo& p1, const piyo& p2)
        : ref_p(a < b ? p1 : p2)
    {}
};

これは if 文では絶対に書けない。

おまけ：

C++ では、条件演算子を含む式を左辺に持ってくることも可能なのは覚えておいても損はない。

でも使うなよ？絶対使うなよ？

(a < b ? a : b) = c;

なんか話が混ざってる感があるので，もう少し成分分解してみる試み．

  • if が常に文になってしまう言語の話
  • 条件分岐の結果として，参照を返しうるかという話

if が常に文になってしまう言語の話

if というキーワードを使うとかならず文になってしまう言語があって，しかもそいつらは目立つという現実が．具体的には C/C++ とか Java とか C# とか Visual Basic 8 までとか．
が，シンタックスの議論は怖いので深入りしないことにして，この話はパス．

// F#
let f c = if 'A' <= c && c <= 'Z' then (int)c - (int)'A'
          elif 'a' <= c && c <= 'z' then (int)c - (int)'a' + 26
          elif '0' <= c && c <= '9' then (int)c - (int)'0' + 52
          elif c = '+' then 62
          elif c = '/' then 63
          else -1

let g c = match c with
          | c_ when 'A' <= c_ && c_ <= 'Z' -> (int)c_ - (int)'A'
          | c_ when 'a' <= c_ && c_ <= 'z' -> (int)c_ - (int)'a' + 26
          | c_ when '0' <= c_ && c_ <= '9' -> (int)c_ - (int)'0' + 52
          | '+' -> 62
          | '/' -> 63
          | _ -> -1

条件分岐の結果として，参照を返しうるかという話

C よりも C++ を先に始めた自分のような人間には，

// C++
int a, b, c;
...
(a < b ? a : b) = c;  // (0)

int& x = (a < b ? a : b);  // (1)
x = c;  // (1')

の (0) は，単に (1) と (1') を組み合わせただけの話に見えます．(1) が可能なら (0) というシンタックスが成り立ってもまあいいじゃんという感じ．
んで，.NET 系の言語では，(1) が出来る言語が結構少なかったりします．Visual Studio 2010 に入っている言語だと，C++/CLI 以外では無理なんじゃないでしょうか．

// C++/CLI
int a = 0, b = 1, c = 2;
int% x = (a < b ? a : b);
x = c;

C++/CLI と C# のこの違いは，値型インスタンスに対するメソッド呼び出しとして表面化させることができます．

// C#
using System;

struct Data
{
    public int Id;
    public void SetId(int id) { Id = id; }
}

static class Program
{
    static void Main(string[] args)
    {
        var cond = DateTime.Now.Ticks % 2 == 0;
        var data1 = new Data();
        var data2 = new Data();
        (cond ? data1 : data2).SetId(1);

        Console.WriteLine("{0} {1}", data1.Id, data2.Id);
    }
}

// 結果: 常に "0 0"

C++ や C++/CLI のシンタックスになじんだ人にとって，シンタックスが似ているのに結果が違うこの C# のコードはなんとも気持ち悪いはず．手元の環境で実験してみたところ，Visual Basic 9 で導入された if 演算子 も同じくコピーを返してました．
一方 Visual Studio 2010 beta1 に付属の F# は結構惜しい感じでした．F# は，byref 型をある程度扱えるみたいで，例えば以下のようなコードは OK です．

// F#
let mymain =
    let mutable a = 0
    let c = 2
    let x = &a
    x <- c
    printfn "%d" a
    ()

ただ残念なことに，if 式の返値に byref 型を突っ込めないようです．次のコードは，コメントに書いた箇所でエラーになります．

// F#
let mymain =
    let mutable a = 0
    let mutable b = 1
    let c = 2

    // error FS0191:
    // A type instantiation involves a byref type. This is not permitted by the .NET runtime
    let x = if a < b then &a else &b

    x <- c
    printfn "%d %d" a b
    ()

気になるのでちょっくらフォーラムあたりで質問してみますかねぇ．

流れるようなインターフェイス，名前付き引数，クエリ式

.NET

C# 4.0 では名前付き引数・省略可能引数が使えるようになるので，シンタックス弄りがもう一段階フリーダムに．シンタックス関連は，深入りすべきなのか適当に引き返すべきなのか，正直よく分からんです．
個人的関心事をざっと列挙してみましたが，網羅的にまとめてくれる人激しく募集．

  • 関数/操作のチェインで要求を記述する方法
    • 実装技術
      • non-intrusive / intrusive という軸
      • メソッドチェイン / 演算子オーバーロード という軸 (id:NyaRuRu:20080316:p2)
      • Implicit Conversion (Scala)
      • 拡張メソッド (C#/Visual Basic)
  • データとして要求を記述する方法
    • 実装技術
      • 名前付き引数・省略可能引数 (Python / Visual Basic / C# 4.0 / ...)
      • ディクショナリ (ハッシュテーブル) の簡易記法 (id:NyaRuRu:20071211:p3)
      • JSON
      • Anonymous Type (C#) (id:NyaRuRu:20080706:p1)
      • Query by Example (id:NyaRuRu:20080617:p1)
    • 類似事例から学ぶべきことはないか？
      • コマンドラインオプション (gcc --help / ./configure --help)
        • gcc --help ぐらい多くなったときにスケールするか
        • zsh で ./configure のあとに TAB 補完やってくれるのかっこいい
      • いわゆる設定ダイアログボックス
      • CreateFont vs CreateFontIndirect
  • 文法レベルで手を加えた言語内 DSL
    • 実装技術
      • 流れるようなインターフェイスで文法を定義する / 最初から専用文法を定義する の軸
      • クエリ式 (C# / Visual Basic)
  • その他
    • 問題領域の分類
      • ID3DXMatrixStack (行列から行列への変換の連鎖)とか，LINQ (IEnumerable<T> から IEnumerable<U> への変換の連鎖)とか，数学的に見てもそりゃ相性良いでしょうな分野がある (id:NyaRuRu:20080313:p1)
    • バージョニング
    • テスト


話は変わりますが，PLINQ もだいぶシンタックスの微調整をやっている感じがありますね．AsSequential とか AsOrdered とか WithDegreeOfParallelism とか．シンタックス好きーは以下お勧め．

前後の値も利用したシーケンス処理 (その 2)

.NET

『前後の値も利用したシーケンス処理 - NyaRuRuの日記』の続き．

// 連続して同じ値が来る箇所だけを省いて取得する
// この場合だと1,2,4,3,4,0が取れることを目指す
int[] array = { 1, 2, 4, 4, 3, 3, 4, 0, 0 };

前回はこの問題を肴に Scan とか Pairwise を持ち出しましたが，この問題に特化して考えるとして，もうちょっと使いやすい関数はないでしょうか．
例えば，UNIX の uniq コマンド は要求されている仕様そのものスバリのように見えます．uniq コマンドに相当する PowerShell の Get-Unique を使ってみます．

PS Z:\> 1,2,4,4,3,3,4,0,0 | Get-Unique
1
2
4
3
4
0

同様の関数に，Haskell の group/groupBy，Python itertools の groupby などがあるようです．
Haskell.

Prelude> :m Data.List
Prelude Data.List> group [1,2,4,4,3,3,4,0,0]
[[1],[2],[4,4],[3,3],[4],[0,0]]
Prelude Data.List> map head $ group [1,2,4,4,3,3,4,0,0] 
[1,2,4,3,4,0]
Prelude Data.List> map head $ groupBy (==) [1,2,4,4,3,3,4,0,0]
[1,2,4,3,4,0]

IronPython 2.0.1

>>> from itertools import groupby
>>> [k for k, g in groupby([1,2,4,4,3,3,4,0,0])]
[1, 2, 4, 3, 4, 0]

一方で LINQ の GroupBy および F# の Seq.groupby は，SQL の GROUP BY 句に似た動作をするため，上記のような使い方はできません．そこでちょっと発想を変えて，run-length エンコーディングを行う関数を作ってみました．

public static IEnumerable<TResult> RunLength<T, TResult>(
    this IEnumerable<T> source, Func<T, int, TResult> resultSelector)
{
    //AssertNonNullArgument(source, "source");
    //AssertNonNullArgument(resultSelector, "resultSelector");

    using (var enumerator = source.GetEnumerator())
    {
        if (!enumerator.MoveNext())
        {
            yield break;
        }
        var count = 1;
        var first = enumerator.Current;
        var eq = EqualityComparer<T>.Default;
        while (enumerator.MoveNext())
        {
            var cur = enumerator.Current;
            if (eq.Equals(first, cur))
            {
                checked { ++count; }
            }
            else
            {
                yield return resultSelector(first, count);
                first = cur;
                count = 1;
            }
        }
        yield return resultSelector(first, count);
    }
}

これで，個数の方を捨てれば題意を満たせます．

// test
var source = new []{1,2,4,4,3,3,4,0,0};
var seq = source.RunLength((i,_) => i);
var ans = new []{1,2,4,3,4,0};
Assert.IsTrue(seq.SequenceEqual(ans));