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

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

シーケンス中で連続して同じ値が入っている各箇所について,2 個目以降は削除したシーケンスが欲しい,という問題.
割とこういう単純な問題でも,入社試験とかで「んじゃホワイトボードに書いてみて」なると案外焦ってミスったりするんですよね.って面接でプログラムを書いたことが数回しかない自分のような人間が適当に言ってるだけですが.
まあそれはさておき,現実のプログラミングで見かける以下のような問題,「シーケンス処理で前後の値も使ってほげふが」という点では同系統と見なすことができるんじゃないかと思います.

  • MIDI 規格のランニングステータスで省略されているステータスバイトを復元する
  • 毎月の売り上げデータから,先月比で売り上げが下がっている月を探す
  • 2 行続いた空行がデータの終わりを表すので,その 2 行の手前までを変数に格納する

この手の問題を解くのに for / while ループは見飽きてるでしょうから,別の方法を 2 つほど.

リスト処理関数を使う

LINQ でさまざまなリスト処理関数*1が追加されましたが,汎用的なリスト処理関数の組み合わせで「前後の値も利用したシーケンス処理」を行うことが出来ます.例えば TakeWhile や SkipWhile などは何かと便利ですね.
この他に前後の値を利用するのに便利な関数としては,F# で言うところの Seq.pairwise があります.このリスト処理関数は,N 個のシーケンスを,隣接するデータのペアのシーケンス tuple × (N - 1) 個に変換してくれます.C# で書くとこんな感じ.

public static IEnumerable<Tuple<T,T>> Pairwise<T>(this IEnumerable<T> source)
{
    //AssertNonNullArgument(source, "source");

    using (var enumerator = source.GetEnumerator())
    {
        if (!enumerator.MoveNext())
        {
            yield break;
        }
        var prev = enumerator.Current;
        while (enumerator.MoveNext())
        {
            yield return new Tuple<T,T>(prev, enumerator.Current);
            prev = enumerator.Current;
        }
    }
}

より汎用的な関数として,Scan (F# で言うところの Seq.scan) を事前に定義しておけば,Scan を使って Pairwise 相当のものを書くこともできます.
source を 2 回列挙する副作用がない,あるいはそれが無視できる場合には,source.Skip(1) と source を ZipWith で結合しても Pairwise の代わりになるでしょう.そういえば .NET Framework 4.0 では,Zip と Tuple が入るそうですね.
んで話を戻して,Pairwise を使うと「毎月の売り上げデータから,先月比で売り上げが下がっている月を探す」とか「連続で空行が来たら停止」みたいなのは割と簡単に書けることがあります.でも,データ数が 1 のときの扱いでやっぱり注意が必要だったり,最初の問題のように不確定な個数のデータが連続してやってくる場合には使えないこともあったり.そこまで万能でもない子かもしれません.端っこの情報が必要なときは,Scan のようなもう少し汎用的な関数に戻る必要がありそうです.

パターン言語 + 置換

最初の問題を文字列に置き換えてみましょう.つまり,文字列 "12433400" 中の連続する文字をひとつにまとめ,結果として文字列 "124340" を得る,とします.これは以下のように書けます.

var result = Regex.Replace(@"12433400", @"(.)\1+", @"$1");
// 結果: "124340"

この方法は一旦文字列化を行うため,例えば負数や 10 以上の数字に対してはそのままでは使えません.前方参照とか先読みとか戻り読みとか,折角強力なパターン記述能力を持ちながら,文字列にしか使えない世の多くの正規表現ライブラリはやっぱり勿体ないんじゃないかと思います.
C++ なら,『boost xpressive で数列に対する文法を作る - NyaRuRuの日記』のように,boost xpressive を使うことで,任意の int 型のシーケンスに対して同じような置換動作を定義できそうです.さらに 文字の切り替わりをトークンの区切りとみたてることで,Lazy に列挙することもできそうな感じですね (regex_token_iterator).
ついでにここ数ヶ月の心の友,Mathematica でも解いてみます.ここでは ReplaceRepeated を使ってみました.

{1, 2, 4, 4, 3, 3, 4, 0, 0} //. {a___, x_, x_, b___} -> {a, x, b}
(* 結果: {1, 2, 4, 3, 4, 0} *)

{1, 1, 1, 1, 1} //. {a___, x_, x_, b___} -> {a, x, b}
(* 結果: {1} *)

2 個連続した数値を 1 個にまとめるという処理を,結果が変わらなくなるまで何度も適用しています.N 個 (N > 1) の連続した数値を一気にキャプチャしたければ,以下の方法でも OK です (結果は同じ).

{1, 2, 4, 4, 3, 3, 4, 0, 0} //. {a___, Longest[Repeated[x_, {2, Infinity}]], b___} -> {a, x, b}
(* 結果: {1, 2, 4, 3, 4, 0} *)

{1, 1, 1, 1, 1} //. {a___, Longest[Repeated[x_, {2, Infinity}]], b___} -> {a, x, b}
(* 結果: {1} *)

とまあこんな感じで,「次のデータをチラ見して」/「さっきのデータを憶えておいて」という頻出問題も,見方を変えればリスト処理関数として汎用化したり,かなりコンパクトなパターン言語に落とし込めたりするケースもありやなしやというお話でした.
もっとも,言語指定がありがちなお仕事プログラミングや入社試験でこんな手が使えるかどうかは微妙です.Loop が平常心と共にあらんことを.

おまけ: Mathematica のサイトライセンス

大学生/大学院生で Mathematica に興味があるけど持ってないという人は,いちど大学の IP アドレスから以下のページを見てみると良いかも.

更新履歴

  • 2009年3月12日
    • サブセクションを「Pairwise を使う」から「リスト処理関数を使う」に変更
      • これに伴い本文修正

*1:ここではシーケンスの意味でリストと呼んでいます

Expression trees と .NET 風メタプログラミング

そういえば昔似たようなことをやっていた.



元々 C++ を使っていた人が,C++ 的な template メタプログラミングを C# で再現したくなるのも分からなくはない.しかし,いつまでも template 的な実装にこだわり続けるわけにもいくまい.
個人的な印象では,.NET 全体の潮流は Expression Trees を基盤とした実行時メタプログラミングに向かっている.Dynamic Language Runtime - Docs and specs の expr-tree-spec.doc を読んで,この印象は確信にかなり近づいた.どれぐらいの人数になるかは分からないが,C++ template に対する boost のようなライブラリが,.NET の Expression Trees に対しても欲しいという人間は今後一定数現れるだろう.
たとえば Expression Trees のグラフ簡約評価器.あれば今すぐにでも使いたいぐらいだがこういうのが全然転がっていない*1.まだまだやること,やれることはいくらでもある.
Expression Trees で何ができるのか / どんな追加のライブラリがあると便利なのかについて真剣に考えている人はまだまだ少ない.必要な視点のひとつは,C++ template 的な実装方法や「C++ にはこれがあった」についてとりあえずいったん忘れることではないかと思っている.出発点のリセットが,プログラミングの視野を広げる良いチャンスになることもあるだろう.

おまけ

305 名前: デフォルトの名無しさん [sage] 投稿日: 2008/09/15(月) 02:45:42 
>>304 
ttp://d.hatena.ne.jp/NyaRuRu/20060802 

理論的には簡単に出来るはずだから誰かやってねーかなぁと思って 
ぐぐったら、やっぱり NyaRuRu 氏が取り上げてた 
2.0 考えた LCG 版でも書いてみようかなぁ 

310 名前: デフォルトの名無しさん [sage] 投稿日: 2008/09/15(月) 05:42:11 
>>305 
その記事微妙に勘違いしてる部分がある 
そのままでも動くんだが組み込み演算/ユーザ定義演算で場合分けは不要 
IL見れば分かるけど、内部にGetUserDefinedBinaryOperatorOrThrowというようなメソッドがある 

ほぼすべての演算を定義した構造体をなんとなく作ったけど、あまり使ってないな 

確かにこれはおっしゃる通り.なんでわざわざ場合分けしていたのか気になって(さすがに忘れている),当時のアセンブリを調べてみたところ理由がわかった.LINQ CTP May 2006 に付属する Expression.Add 等は,現在のバージョンと仕様が異なりユーザ定義演算を一切考慮しないので,当時は場合分けが必須だったようだ.その後仕様変更があって今は確かに場合分け不要である.この変更は個人的にもありがたい.

*1:といいつつ探せば絶対誰かが作ってそうな根拠のない印象もある.単純な Call-by-Name と Call-by-Need は『[http://community.bartdesmet.net/blogs/bart/archive/2008/08/22/curry-for-dummies-cont-d-a-happy-ending.aspx:title=CURRY FOR DUMMIES (CONT’D) – A HAPPY ENDIN]』で既にやられている

Visual Studio 2010 CTP を BITS でダウンロードするための PowerShell Script

相変わらず RAR で 11 分割とか面倒なことをしてくれるので『Visual Studio 2008 beta 2 を BITS でダウンロードするための PowerShell Script - NyaRuRuの日記』再び的な.
カレントディレクトリにダウンロードするので,実行場所にご注意を.

bitsadmin /create VS2010CTP

(1..11) | % {
  if($_ -eq 1) {
     @{'num'=$_; 'ext'=".exe"}
  } else {
     @{'num'=$_; 'ext'=".rar"}
  }
} | % {
 @{ 'filename'=[String]::Format("VisualStudio2010CTP_11PartsTotal.part{0:0#}{1}", $_.num, $_.ext) }
} | % {
 @{ 'url'="http://download.microsoft.com/download/9/7/4/97467b12-d04b-463f-b703-0e334c177799/"+$_.filename;
    'path'=(pwd).Path + "\" + $_.filename } 
} | % {
  bitsadmin /addfile VS2010CTP $_.url $_.path
}

bitsadmin /resume VS2010CTP

最後の /resume のところでダウンロードが始まります.ダウンロード状況を知るには /monitor を使います.

bitsadmin /monitor

ダウンロードが終わったら以下のコマンドでジョブを終了させてください.

bitsadmin /complete VS2010CTP

C# マニアが JIS X 3015:2008 を読むべき理由

JIS X 3015:2008 とか互換性とか - NyaRuRuの日記』に「JIS X 3015:2008 のセールスポイント」として追記した.
ジェネリクス周りの「注記」がとてもおもしろい.さすがに「注記」目的に買うには高いけど,こういう資料は貴重なので個人的には OK だったり.

JIS X 3015:2008 とか互換性とか

JIS X 3015:2008 の PDF 版を購入した

JIS X 3015:2005 が改訂されて JIS X 3015:2008 になりました.

ウェブストアでも販売が開始されてます.

いずれ記事執筆等で必要になるので,私はさっさと PDF 版の規格票を購入しました.以前の JIS X 3015:2005 *1 と比べて若干値上がりしている模様(15,120円→17,430円).

JIS X 3015:2008 のセールスポイント

JIS X 3015:2008 は ISO/IEC 23270:2006 と 技術的内容において一致している とのことですが,実際には多数の「注記」が追加されています.
この「注記」は,ISO/IEC 23270:2006 で分かりにくかったり曖昧だったりした部分や,ISO/IEC 23270:2006 の後に判明した仕様上の問題点等を補足するもので,技術的にも大変興味深い資料となっています.「注記」そのものは「規定」ではありませんが,「注記」部分を選択的に読むことで,C# への理解がより深まることでしょう.
また,いくつかの errata については JIS X 3015:2008 で修正を取り込んでいるようです*2
実際の作業にあたられた「プログラム言語 C# JIS 原案作成委員会」の方々に感謝を.

無償公開されている ISO/IEC 23270:2006

ISO/IEC 23270:2006 は一般向けに無償公開されています.Common Language Infrastructure (CLI) 規格も同様.

ちなみに以前某氏から聞いた話では,.NET 関係のとある規格 (CLI かな) の JIS 版を, Microsoft としては無償公開ということにしたかったものの,JIS 側の都合で結局有償頒布になってしまったことがあるとかなんとか……あー,あくまでうわさですようわさ.

C# は○○○○(←好きな言語名を入れる)と違って国際的な標準規格なので云々」といううたい文句について

この手のうたい文句を見ると,国際的な標準規格が存在することにより期待される理想の状態をつい思い浮かべてしまい,それが既に実現されているような印象を受けますが,実際にはそうでもないです.というのがエンジニア向けの実情.
もちろん,規格化はエンジニアにとっても役立っています.多くの方々の多大なる努力により,規格制定プロセスの間に,仕様のミスや曖昧な文章が多数発見・修正されています.これらの作業は C# コンパイラ間の互換性を高める方向に作用するでしょうし,ひいては Microsoft の C# コンパイラの品質改善にもつながるでしょう.

Visual C# 2008 のコンパイラオプション langversion は割と手抜き

Visual C# 2008 には langversion というコンパイラオプションがあって,ISO-1/ISO-2/default のうちからひとつを指定できます.ISO-1/ISO-2 という名前がついていると,過去の規格でコンパイルできそうな気がしてきます.

引数

  • option
    • option が ISO-1 の場合、コンパイラは ISO/IEC 23270:2003 C# の言語仕様に含まれていない構文に対してエラーを生成します。
    • option が ISO-2 の場合、コンパイラは ISO/IEC 23270:2006 C# の言語仕様に含まれていない構文に対してエラーを生成します。
    • option が default の場合、コンパイラは有効なすべての構文を受け入れます。既定値は /langversion:default です。

が,実はこの ISO-1/ISO-2,そんなに厳密なものではありません.

Language versionはコンパイラの解析ツリーレベルで動作し、言語構文の中に表現された言語機能をコントロールします。これは意味的な違いといったような、言語に対する他の変更に関連するISO仕様への適合までも含むわけではありません。デフォルトのオプションでは常にその言語の最新バージョンが指定されるようになっています。

型システムが絡むあいまいさ/非互換性

型システムが絡むあいまいさ/非互換性はまだまだ散発的に見つかっています.なかなか枯れません.
たとえば,以前お伝えした以下のケース,最終的に言語仕様のアップデートで解決するそうです.

C#言語仕様」には、この状況に関する適切な説明が欠けています。このコンパイルエラーは仕様(by design)ですので、それに合わせて「C#言語仕様」をアップデートする予定です。

私どもではジェネリックを通して変換の制限の回避を可能にすることは望んでおりません。

型推論と互換性

型システムが絡むあいまいさ/非互換性の中でも特に最近特に問題が頻発しているのが,型推論に関してです.

さて,C# Generics で,同様の推論が可能かどうかについてですが,まず Visual C# 2008 に付属する C# コンパイラでは不可能です.じゃあ仕様的に不可能かというと,実はこのあたり結構ごたごたしていてよく分からないんですよね.

上に挙げたリンクで問題にされているのは,主に,(左辺の) デリゲートの戻り値型から (右辺の) ジェネリックメソッドの戻り値の型を推論するというケースです.このケースの中で,言語仕様では出来ると書かれているものが,Visual C# 2008 の C# コンパイラでは出来ないことがあるけどなんで?というお話です.ちなみに結論は,仕様も実装も Errata があったとのこと.

いずれ出版済みの言語仕様も修正するそうです.結局この辺の事情がどなっているのか・今後どうなるかは私にもよく分かりません.新しい実装は C# 4.0 で入りそうなので,もしかしたら上記 Java のような型推論が可能になっているんじゃないかと密かに期待しています.

複雑な式をひとつ与えられたときの,「C# の仕様上,この式は (推論が成功して) コンパイルできますか?」という質問,結構厄介です.仕様から実装まで含めて完全に落ち着くにはあと数年を要するんじゃないでしょうか.そして,その頃にはまた新しい推論ルールが追加されようとしているやもしれません.

C# 3.0 以降の標準化はどうなっているの?

先日行われたインタビューで,Anders Hejlsberg が C# 3.0 以降の標準化について述べています.

Do you expect C#3.0 to become an ECMA and ISO standard, as previous versions have?

We’re certainly open to that. There’s no ongoing work in the standards committee at the moment, but it’s really more a question of whether the community of industry partners out there would like to continue with that process. I should also say that the standards for C# explicitly do permit implementers to have extensions to the language, so though C# 3.0 is not standardized, it is certainly a complete implementation of the C# 2.0 standard. It is 100% backwards compatible, as all versions are.

今のところ C# 3.0 を ECMA や ISO に提出する動きはないんだとか.

*1:JIS X 3015:2005 規格書ダウンロード販売 - NyaRuRuの日記

*2:例えば §25.7.1「制約の充足」の,『制約が値型制約の場合~』に書かれている 3 つ目の条件.公開されている ISO/IEC 23270:2006 には書かれていない条件「A が,構築子制約new()をもつ型仮引数になっている。」が追加されている

変数スコープの最後までオブジェクトは生きているという誤解

先日に引き続き,@IT 会議室突っ込みシリーズ.

未記入さんの書き込み (2008-10-01 21:41) より:

バグではない理由:
参照していると、回収されません。Dispose は、メモリの破棄ではありません。

参照しているというのは fm2 のことでしょうか。fm2 はループ内で宣言されているので、ループ 1周ごとにスコープを抜ける、つまり new Form2() は参照されていない状態になるのではないでしょうか?

GC.Collect() で直前の fm2 が解放されるとは思っていませんが、ループ 1周遅れで、ひとつまえの new Form2() インスタンスは GC で回収されても良さそうに思います。直近の 1インスタンスは GC.Collect() で回収されないと思いますが、それだけでメモリ使用量が増加傾向になるものでしょうか?

よねKENさんのフォローと同じだと思いますが。

オリジナルのコード

while (true) 
{ 
    Form2 fm2 = new Form2(); 
    fm2.ShowDialog(); 
    fm2.Dispose(); 
    GC.Collect(); 
}

GC.Collect が実行されるときには fm2 は参照されています。従って、1つは残ります。

1 つ必ず残るとは限りません.Compact CLR の特定バージョンがそういう実装になっているといった話なら分かりますが,CLI 仕様からは「1 つ必ず残る」と断定はできないはずです.
(C# では) 変数スコープの最後までオブジェクトは生きているというこの誤解,あちこちで目にしますが,実際にはそんなことは保証されていません.C# コンパイラは,スコープ終了点までオブジェクトを延命するようなコードを必要もなく埋め込みません.その結果,デスクトップ CLR では比較的簡単に「スコープ終了前の回収」を見ることができます.特徴的なケースでは,生成したオブジェクトのコンストラクタが完了する前に,そのオブジェクトが回収されることすらあります*1
詳しくは『 プログラミングMicrosoft .NET Framework 第2版』の第 20 章あたりをどうぞ.

プログラミングMicrosoft .NET Framework 第2版 (マイクロソフト公式解説書)

プログラミングMicrosoft .NET Framework 第2版 (マイクロソフト公式解説書)

構造体とクラスの使い分け

@IT 会議室ネタ.内容は GC 絡み.

回答に妙に気になる内容がたくさんあったので少しだけ書いてみます.アカウント無いので.
あと,同じサイトで以前こんな記事を書いているので,よろしければどうぞ的な.



ひとくちに GC 対策といっても色々あって,たとえば以下の 2 つは別物です.

  • GC の発生頻度そのものを抑えるために, GC ヒープからのアロケーションを避けること
  • GC 発生時の停止時間を短くするために,「生きているオブジェクト」の個数を少なく保つこと

ボクシングを減らすのは前者,値型だけで構成された構造体の配列を活用するのは後者に有用です.
んで各論.

ひろしさんの書き込み (2008-09-23 15:02) より:

Q1.配列の場合、(b)(c)に関係なくクラスより構造体のほうが常に有利ですか?

Q2.CLR標準のジェネリックコレクション(例 List<T> Queue<T> Dictionary<T>等)についてガイドライン等、有用な情報源はありますか?

Q1

次のようなサンプルを実行してみればわかります。

public struct A
{
    public string name;
}

public class AList : List<A>
{
}

main()
{
    AList l = new AList();
    for (int i = 0; i < 10; i++) {
        l.Add(new A());
        // 「l[i].name = i.ToString();」ではない理由は?
        A r = l[i];
        r.name = i.ToString();
    }
    foreach (A a in l) {
        // この出力が、どうなるかに注目
        System.Diagnostics.Debug.WriteLine(a.name);
    }
    // これとの違いを考えよう
    A[] arr = new A[10];
    for (int i = 0; i < arr.Length; i++) {
        arr[i] = new A();
        arr[i].name = i.ToString();
    }
    foreach (A a in arr) {
        System.Diagnostics.Debug.WriteLine(a.name);
    }
}

これの謎は、ボックス化とボックス化解除 (C# プログラミング ガイド)<microsoft.com>あたりで。

ここに示されたコードで,本当にボクシングは発生するのでしょうか? (ToString や文字列出力の内部実装をのぞく)
おそらく List<T> のインデクサが byref-return*1 を使わずに値のコピーを返していることに気をつけろと言いたいのだと思うのですが,そこでなぜボクシングの話になるのかが分かりません.配列の場合もやはりボクシングは関係なくて,単にマネージポインタが使われているだけですし.
まあそれはさておき,質問者の Q1 に対する私なりの回答ですが,確かに値型だけで構成された構造体の配列は,「生きているオブジェクト」の個数を減らすのに有効です.ただし,その他の条件下では構造体が不利なケースもあるかもしれません.一般論として有利不利を言い切るのは難しい問題に,万能の判断基準を求めているように見えます.難しく考えずに,「困らない方」を選べば良いんじゃないでしょうかね.
次.

ひろしさんの書き込み (2008-09-24 20:46) より:

例えば配列の場合は、構造体で要素を構成すればメモリ上ではひと固まりになります。一方、クラスで要素を構成すればはメモリ上で要素の数だけ分散してしまいます。後者のほうが、GCに大きな負荷をかけてしまうような気がします。

関係ありません。

自分でメモリ管理をしてみれば、わかります。C言語の教科書的参考書なら、基本的なメモリ管理の方法が書いてあると思います。

ここも質問者の方が正しくて,「生きているオブジェクト」の個数を少なくすることは GC のマークフェイズの負荷を減らす上で有効です.まあこの辺は @IT に書いた記事読んでくださいということで.

さらに記事には、10万個のオブジェクトがまだ参照されていることをXbox 360 CLRが調べて回るだけで、14ミリ秒の時間が必要だったという記述が続く(コンパクト化の作業時間を含まないでこの値だそうだ)。この停止時間を短くするには、結局のところオブジェクト数を減らすしかほかにない。純粋な値型の配列は要素数によらず1オブジェクト扱いなので有利というわけだ。

さらに次.

あるいは各ジェネリックコレクション特有の実装を反映した個別のルールが必要になるのでしょうか?

構造体かクラスか/値型か参照型か を格納するコレクションで決めるなんてナンセンスだと思いますけど!? .NETクラスライブラリのコレクションの実装は、いたってフツーな実装ですよ。

コレクションの特徴(追加挿入の得意不得意、ランダムアクセスの得意不得意・・・)を知らずに使うほうが よっぽど問題だと思います。

私は回答者のようには思わなくて,GC を気にせざるをえない状況下では当然コレクションの内部実装も気にします.もちろんコレクションの特徴自体も重要なのですが,そういった特徴が同じでも,GC への影響がまるで異なる複数の実装がありうるわけです.質問者の方が気にしているのは,そういった別の評価軸のことでしょう.
次.

Tdnr_Symさんの書き込み (2008-09-28 03:21) より:

ジェネリックを使っていればボックス化が発生するような場面はそうないですよね!?

ジェネリック コレクション クラスが参照型なので、発生していると思います→2008-09-24 22:02

先ほども書いたように,あのコードでボクシングが発生しているとは思えません.