Hatena::ブログ(Diary)

当面C#と.NETな記録 このページをアンテナに追加 RSSフィード

2007/3/30 (金)

[] パイプラインパターンとリソース管理  パイプラインパターンとリソース管理を含むブックマーク  パイプラインパターンとリソース管理のブックマークコメント

このごろ傾倒してるパイプラインパターン。C#3.0のメソッド拡張構文やLINQや関数言語型のような宣言型のプログラミングを見据えていろいろ模索しています。

部品を細かく分けて変更に強い構造にできる利点は非常に大きいと思っています。例えば、たびたび例に出しているファイルから1行づつ読み取るパターンですが、データのソースがファイルからコレクションやほかの何かに変更になっても影響が小さいですね。

また、汎用的な部品、例えば IEnumerable<T> Where<T>( Predicate<T> predicate, IEnumerable<T> input ) みたいなのを使って、述語部分(predicate)のみを各プログラムで記述するってのは魅力的です。煩雑な手続き部分が隠蔽されて、宣言的でわかりやすくなります。そのプログラムがフォーカスしてる具体的な部分がはっきりくっきりと浮かび上がってきます。ラムダ式が活躍する場所はこの述語です。ラムダ式はC#2.0の匿名メソッドから冗長性を省いたものです(実はそれだけじゃないけど)。

もっともこのあたりは、RubyPythonのような言語を使いこなしている人にとっては今更な話題かもしれません。

今日のレシピはリソース管理。Disposeがきちんと呼ばれるか実験です。Ouchメソッドでわざと例外を出して、TextFileReaderのDisposeが呼ばれるよね?という確認です。

リソース管理構文のusingが外側のループの例外発生に対して有効なのかどうか、です。また、OuchをOuch2に置き換えるとどうなるか?もお試しです。

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

public class Program
{
	public static void Main()
	{
		const string fileName = "text.txt";

		try
		{
			foreach ( string str in Ouch( TextFileReader( fileName ) ) )
			{
				Console.WriteLine( str );
			}
		}
		catch ( Exception e )
		{
			Console.WriteLine( e.Message );
		}
		Console.ReadLine();
	}

	private static IEnumerable<string> Ouch( IEnumerable<string> input )
	{
		int count = 0;
		foreach ( string s in input )
		{
			count++;
			if ( count > 2 )
				throw new Exception();
			yield return s;
		}
	}

	private static System.Collections.IEnumerable Ouch2( System.Collections.IEnumerable input )
	{
		System.Collections.IEnumerator it = input.GetEnumerator();
		it.MoveNext();
		yield return it.Current;

		throw new Exception();
	}

	public static IEnumerable<string> TextFileReader( string fileName )
	{
		using ( StreamReader2 sr = new StreamReader2( fileName ) )
		{
			string line;
			while ( ( line = sr.ReadLine() ) != null )
				yield return line;
		}
	}
}

public class StreamReader2 : StreamReader
{
	public StreamReader2( string fileName ) : base( fileName ) { }

	protected override void Dispose( bool disposing )
	{
		Console.WriteLine( "StreamReader2:Dispose" );
		base.Dispose( disposing );
	}
}

OuchではDisposeが呼ばれますね。対してOuch2では呼ばれません。解決策としてはOuch2内でもOuch同様foreachを使うのが一番簡単ですね。

ぜひ、ReflectorでOuchとOuch2を覗いて比べてみてください。いろいろと発見があると思います。

パイプラインパターンはC#3.0を待たなくても、今すぐ使えるパターンですね。ループを超えた最適化をしてくれればもっといいのになぁ。

(PLINQなんてのも見据えているけど、あまり期待はしていない(^^; GoogleのMapReduce的な発想ですね)

2007/3/29 (木)

[] WPFデモいろいろ  WPFデモいろいろを含むブックマーク  WPFデモいろいろのブックマークコメント

http://blogs.msdn.com/somasegar/archive/2007/02/10/wpf-real-world-apps-for-windows-vista-part-2.aspx

ここにWPFのデモがいろいろ紹介されていた。

でもなんだろう、この数年前のFlashうぜーって言われてたころの使いづらいFlashみたいなおもちゃの数々は…。全部見たわけじゃないけど、もういいやって思ってしまった(^^; どれもこれも操作方法がわからないし、無意味にアニメしてたり…。最初だからWPFの力を試すためのデモと考えれば、まぁこういうのになるんだろうなとは思うけど。でもって、どれもこれも重かったです、はい。

不思議なことにここで紹介されてるWPFデモ、ほとんどが日本製ですね。日本はWPF先進国?

昨日紹介したXamlerだけはすごくよかった。青空文庫ビュワーっていくつかあるようだけど、使ったことがないのでほかと比べてどうかは知らないけど、Xamlerはとても読みやすかった。使い勝手はまだこれからだけど、続けて開発していくそうです。XAMLとコードがそれぞれどのくらいの規模か知りたいな。

ところで、Somasegarさんのblogによると、今年はVisual Studio、10周年記念だそうで!おめでと〜。

さらにところで、OrcasXSLT Debuggerが載ってるようですね。ぷちうれしい。

[] Exit Status  Exit Statusを含むブックマーク  Exit Statusのブックマークコメント

http://golf.shinh.org/p.rb?exit+status

id:nattowさんに2byte抜かれた!これはもう縮まないと思ってたのに…。

92byteだったコードはこちら。

続きを読む

トラックバック - http://d.hatena.ne.jp/siokoshou/20070329

2007/3/28 (水)

[] Xamler  Xamlerを含むブックマーク  Xamlerのブックマークコメント

http://est.jp/

軽いWPFソフト。青空文庫をきれいに表示してくれる。こちらは非常に軽くてさくさく動く。XPでWPFを動かすと重いってことではないことがわかった。

このサイト、おもしろいものをいろいろ作っていますね。こういう会社は楽しそうだ。

次はもう少し重いWPFデモを動かしてみたいけど、あいにくと知りません。どこかにWPFのデモはありませんか?

トラックバック - http://d.hatena.ne.jp/siokoshou/20070328

2007/3/27 (火)

[] Healthcare Prototype  Healthcare Prototypeを含むブックマーク  Healthcare Prototypeのブックマークコメント

http://wpf.netfx3.com/files/folders/applications/entry6608.aspx

WPFの有名なデモ Healthcare Prototype をうちのXPで動かしてみたら、かなりきつかった。

CPU使用率がずっと100%付近になってファンがうるさすぎ。画面切り替わりのアニメはきちんと見えてないっぽい。一部の動きはWinFormより軽快だけど、それ以外はのっそり重い。Vistaではどうなのか?とか、グラフィックドライバ変えればどうなのか?とか気になるけど、今すぐどんなマシンでも使えるわけじゃないな。

ここまで凝ってないWPFのデモも探して試してみたいところ。

それにしても、このデモ、操作方法が全然わからなくてまいった。映画の中のハリボテコンピュータが体験できる貴重な一品w

トラックバック - http://d.hatena.ne.jp/siokoshou/20070327

2007/3/25 (日)

[] invert case  invert caseを含むブックマーク  invert caseのブックマークコメント

http://golf.shinh.org/p.rb?invert+case

id:nattowさんに抜かれたので再チャレンジ。

よく考えてみると問題の本質に気づいていなかった。Aha体験した。タイトル通り素直に書いたら100byteに縮んだ。

ショートコードって問題をいろんな面から考える力がつきますね。これまでは無理に曲解してばかりだったけど、素直に捕らえたほうが縮んだのはおもしろい。

[] tennis  tennisを含むブックマーク  tennisのブックマークコメント

id:matarilloさんにまた1byte抜かれたけど、もう無理と思ってmatarilloさんのとこに貼ってあったのを見てしまった。ら、また2byte縮んだ。あきらめるのはまだ早かった…

223byteのコードはこれでした。

続きを読む

[] permutater  permutaterを含むブックマーク  permutaterのブックマークコメント

順列の問題。いろいろな解法がありそう。

数日前は順列の生成がわからなくて断念。次に生成方法を調べて、まねたら回答と同じ順に出なかったのでまた断念。今日は丹念にサンプルを見てやっと解けた。いきなりトップ。やったね!

これをスラスラと解ける人はすごいなぁ。尊敬する。

トラックバック - http://d.hatena.ne.jp/siokoshou/20070325

2007/3/24 (土)

[] Implicitly typed local variables  Implicitly typed local variablesを含むブックマーク  Implicitly typed local variablesのブックマークコメント

次のC#3.0で追加される機能の var。Font font = this.Font; みたいな朗読したくない文が var font = this.Font; と書けて、ちょっといい感じ。Fontくらいだとバカっぽくなくなるだけだけど、Dictionary<int, Order> orders = new Dictionary<int, Order>(); が var orders = new Dictionary<int, Order>(); となるとかなりスッキリですね。

で、ふと思ったのが、foreachスニペット。デフォルトでは要素の変数名が var です。これって大丈夫なの?と思って調べてみました。普通に考えて var は新しい予約語だろうし、intって名前は変数名に使えないし。

May 2006の仕様書(注意:ワード文書)を見ると26.1にvarの記述があります。

varって型名は互換性のために警告つきながら使えるけど、型の名前は大文字で始める仕様に違反するので、この状態は起こりそうもないって記述はありました。

ん〜、でも、変数名については触れてなさそう。使えるんでしょうか…?使えないんでしょうか・・・?どっちなんだろう。使えないとなると標準のスニペットだけに影響は大きそう。

[] tennis  tennisを含むブックマーク  tennisのブックマークコメント

http://golf.shinh.org/p.rb?tennis

id:matarilloさんとのテニス対戦が熱い。

あまりおもしろくない問題でも、対戦相手がいるとものすごいやる気が沸いてくるw

すらどにプログラマのやる気ネタが出てるけど、競争を取り入れるのがよさげ。どうやって何を基準に競わせるかとか、一つのものを複数人で別々に作るのは無駄だとか、負けた人へのフォローとか、難しそうですが。

でも、対戦相手なし発表の場なしでこの問題を見かけたとしても、絶対手をつけなかったな。抜きつ抜かれつだからここまで短くなった。毎回これ以上短くならないと思ってコミットしてるのに、抜かれるとまた真剣に考えて新しい発見があるってことの繰り返し。競争はすごい楽しい(^^)

FizzBuzz

http://golf.shinh.org/p.rb?FizzBuzz

これが超人気なことに気づいた。もしかして一番人気?やってみると簡単な問題のわりに奥が深い。

125byteのコードを二つ見つけたけど、あと2byte縮まりません…。何がどうなってるんだか(^^;

トラックバック - http://d.hatena.ne.jp/siokoshou/20070324

2007/3/22 (木)

[] anarchy golf  anarchy golfを含むブックマーク  anarchy golfのブックマークコメント

http://golf.shinh.org/

ショートコードにどっぷりはまってしまってます。登録不要でお手軽なのがいい感じ。

文字列を手で辞書圧縮するような問題はあまり好みじゃないっぽい。でも抜かれるとまたチャレンジしてしまうわけですが(^^; Echoの72byteがわかったけど、わかってゲンナリ...

せっかくなのでおすすめ問題の紹介でも。

難易度、易。入力に応じて値を表示する問題。exit statusといいつつ、returnで返すわけじゃないです。

簡単な割りにショートコードの楽しさが味わえました。早い人なら5分くらい?


難易度、中〜難。パズルみたいにおもしろかった。ショートコード初体験ってことを割り引いてもとてもおもしろい。時間はかなりかかりました。

Javaトップのnattowさんのコード、実行時間が私のコードとずいぶん違うので、別の解法で同じ長さなのかぁ。興味あります。


究極の答え「42」を表示する問題。問題はおもしろくないけどPHPの結果がおもしろい。PHPなら普通2byteだろってところに、きっかり42byteのコードのkt3kさん!カッコイイ!

表示するだけならPHPが最短って特徴に改めて気づきました。プログラム本文と表示する文字列が普通の言語と逆転してますからね。寄生する言語・・・っていうとなんか嫌な感じだな(^^;

それにしても、shinhさん、9230byteってwww

ん〜、Smileys Triangleが縮まらないぞ、と。

トラックバック - http://d.hatena.ne.jp/siokoshou/20070322

2007/3/21 (水)

[] Echo  Echoを含むブックマーク  Echoのブックマークコメント

http://golf.shinh.org/p.rb?echo

68byte。チートしました、ごめんなさいごめんなさいごめんなさい…

チートなしはmeiさんが書いたのと同じ78byteしか思いつきませんでした。72byteって…

続きを読む

[] delete last line  delete last lineを含むブックマーク  delete last lineのブックマークコメント

http://golf.shinh.org/p.rb?delete+last+line

C#が1.1なのか、string.Remove()の1変数版が使えない…。sedawkが超有利なのは仕方ないけど、C#が137byteで最下位なのはくやしいので、晒します。応援求むw

using C=System.Console;class P{static void Main(){string[]s=C.In.ReadToEnd().Split('\n');for(int i=0;i<s.Length-2;)C.WriteLine(s[i++]);}}

しかもちょっと姑息だw

トラックバック - http://d.hatena.ne.jp/siokoshou/20070321

2007/3/20 (火)

[] ショートコード  ショートコードを含むブックマーク  ショートコードのブックマークコメント

http://golf.shinh.org/p.rb?Fibonacci+Numbers

楽しそうなんでやってみました。フィボナッチ数列。

95byteまでいけたけど、トップのお二人は87byte…。えええ、どうやるんだろ〜?

(追記)

3/21お昼についに87byte到達!

楽しすぎるwww 隙間時間にこればっかり考えてしまう(^^;

siokoshousiokoshou 2007/03/20 20:01 91byteまで来た!あとどうやるんだろ。む〜。

トラックバック - http://d.hatena.ne.jp/siokoshou/20070320

2007/3/19 (月)

[] ストリーム  ストリームを含むブックマーク  ストリームのブックマークコメント

id:siokoshou:20061202あたりの続きっぽいエントリー。

こないだWikipediaでコルーチンを見つけたときに、もしかしてと思ってSICPこと「計算機プログラムの構造と解釈」を見てみると、パイプラインパターンって呼んでたやつが「3.5ストリーム」としてしっかり載ってました。この本、ひげぽんさんに影響されて買ったはいいけど、やっぱり積読になってたのでしたw

各ストリームごとにきっちり分離して部品化できるから、状態管理が楽だよってことみたい。様々な場面で検討に値するアーキテクチャかもしれない。著名な教科書に載ってるような由緒正しいものだったとは。

数学っぽいことやってもおもしろくないんで、またテキスト処理。普段、テキスト処理はLLでやるけどねw

あるログファイルから特定の文字列を含まない行を取り出してます。LINQ風です。Selectの実装は載せてないけどLINQのSequence.csのWhere<T>()と一緒です。数行で書けるんで、頭の体操にどうぞ。

public static void Main( string[] args )
{
	try
	{
		foreach ( string str in
			Functional.Select( delegate( string s ) { return !s.Contains( "Opera" ); },
			Functional.Select( delegate( string s ) { return !s.Contains( "Mozilla" ); },
			Functional.TextFileReader( args ) ) ) )
		{
			Console.WriteLine( str );
		}
	}
	catch ( Exception e )
	{
		Console.WriteLine( e.Message );
	}
	Console.ReadLine();
}

この例ではテキストファイルから読んでるけど、これをコレクションクラスに変えたり、どっかと通信してその中身なんてことになっても、この大枠のアーキテクチャには影響がないかもしれないですね。本当にないかな?w もうちょっと考えてみます。

siokoshousiokoshou 2007/03/20 11:15 LINQはSQLを強く意識してることを考えるとSelectじゃなくてWhereのままのほうがよかったな…。反省。

トラックバック - http://d.hatena.ne.jp/siokoshou/20070319

2007/3/18 (日)

[][] Orcas.NET Framework  Orcasと.NET Frameworkを含むブックマーク  Orcasと.NET Frameworkのブックマークコメント

Orcasの情報、ぜんぜん追いかけてなかったんだけど、この記事読んでびっくり。

http://msdn.microsoft.com/msdnmag/issues/07/04/CLRInsideOut/default.aspx?loc=jp

.NET Frameworkを置き換えたり追加クラスがあったりするんですね。しかもバージョン据え置き???いや、それはないか…?レッドビット、グリーンビットだそうで。なんか、バージョンがややこしいことになりそう。

あ、でもBigIntegerいいですね。無限型ですか。なんだかC#Rubyを目指しているような気がするw

トラックバック - http://d.hatena.ne.jp/siokoshou/20070318

2007/3/16 (金)

[] コルーチン  コルーチンを含むブックマーク  コルーチンのブックマークコメント

http://en.wikipedia.org/wiki/Coroutine

コルーチン

yield っていろんな言語にあるけど、ずいぶん昔からある機能だったんですね。1963年って…。

「協調的処理、イテレータ、無限リスト、パイプなど、継続状況を持つプログラムが容易に記述できる」だそうで、こないだ遊んだパイプはこれだったのか。

cooperative tasks って例えばどんなのさ?ってリンクたどったらマルチタスクにリダイレクトされた。ふむ。

昨日のdiffネタのスクリーンショットにある、(小さくて見えないけど)Testってボタンを押すと押すたびに違うテストをするんだけど、これにyield使ってます。

簡単に使えるし、記憶力いいし、もっかい呼ぶまでじっと待っててくれるし、yield好き。

トラックバック - http://d.hatena.ne.jp/siokoshou/20070316

2007/3/15 (木)

siokoshou2007-03-15

[][][] .NET diff class  .NET diff classを含むブックマーク  .NET diff classのブックマークコメント

.NET 高速 diff classを公開します。2つの文字列のdiffを取ります。行単位のdiff(UNIXのdiffコマンドのような)と、文字単位のdiffを取れます。

"An O(NP) Sequence Comparison Algorithm"(PDF), Sun Wu, Udi Manber, Gene Myers, (1989) のアルゴリズムを使用したC#によるdiffクラスです。非常に賢い処理を作り上げた著者らに感謝いたします。

自由に使用してください。ただし、内容のいかなる保障もしません。バグを見つけたらコメントで教えてください。

テストはしていますが、仕事に使うのであれば再テストをしてから使用してください。

API

  • 行単位diff
    • public static DiffResult[] Diff( string textA, string textB )
    • public static DiffResult[] Diff( string textA, string textB, DiffOption option )
  • 文字単位diff
    • public static DiffResult[] DiffChar( string textA, string textB )
    • public static DiffResult[] DiffChar( string textA, string textB, DiffOption option )

DiffOption は TrimSpace, IgnoreSpace, IgnoreCase があります。詳しくはソースコードを参照してください。

結果は DiffResult 型の配列です。1つ目の文字列をオリジナル、2つ目の文字列を変更後の文字列とすると、両者の共通部分と異なる部分のレポートが結果として返ってきます。こちらも詳しくはソースコードを参照してください。

(2009/8/24 追記 行単位 diff のバグを修正。id:SiroKuro さん、ご指摘ありがとうございます。

参考 http://d.hatena.ne.jp/SiroKuro/20090823/1251043905)

以下、ソースコード。

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Diagnostics;

namespace FastDiff
{
  [Serializable]
  public struct DiffOption { public bool TrimSpace, IgnoreSpace, IgnoreCase; }

  [Serializable]
  public class DiffResult
  {
    public bool Modified; // 変更あり?
    public int OriginalStart;
    public int OriginalLength;
    public int ModifiedStart;
    public int ModifiedLength;

    public DiffResult( bool modified, int orgStart, int orgLength, int modStart, int modLength )
    {
      this.Modified = modified;
      this.OriginalStart = orgStart;
      this.OriginalLength = orgLength;
      this.ModifiedStart = modStart;
      this.ModifiedLength = modLength;
    }

    public override string ToString()
    {
      return ( ( this.Modified ) ? "Modified" : "Common" )
        + ", OrgStart:" + this.OriginalStart + ", OrgLen:" + this.OriginalLength
        + ", ModStart:" + this.ModifiedStart + ", ModLen:" + this.ModifiedLength;
    }
  }

  public class FastDiff
  {
    private int[] dataA, dataB;
    private string[] linesA, linesB;
    private bool isSwap;
    private Snake[] fp;

    private delegate bool IsSame( int posA, int posB );
    private IsSame isSame;


    private FastDiff() { }

    /// <summary>複数行の文字列を行単位で比較します</summary>
    /// <param name="textA">元テキスト</param>
    /// <param name="textB">変更テキスト</param>
    /// <returns>比較結果</returns>
    public static DiffResult[] Diff( string textA, string textB )
    {
      DiffOption option = new DiffOption();
      return Diff( textA, textB, option );
    }

    /// <summary>複数行の文字列を行単位で比較します</summary>
    /// <param name="textA">元テキスト</param>
    /// <param name="textB">変更テキスト</param>
    /// <param name="option">オプション指定</param>
    /// <returns>比較結果</returns>
    public static DiffResult[] Diff( string textA, string textB, DiffOption option )
    {
      if ( string.IsNullOrEmpty( textA ) || string.IsNullOrEmpty( textB ) )
        return StringNullOrEmpty( textA, textB );

      FastDiff diff = new FastDiff();
      return diff.DiffCore( textA, textB, option );
    }

    private DiffResult[] DiffCore( string textA, string textB, DiffOption option )
    {
      this.linesA = SplitLine( textA, option );
      this.linesB = SplitLine( textB, option );

      if ( this.linesB.Length < this.linesA.Length )
      {
        this.isSwap = true;

        string[] tmps = this.linesA;
        this.linesA = this.linesB;
        this.linesB = tmps;
      }
      this.dataA = MakeHash( this.linesA );
      this.dataB = MakeHash( this.linesB );

      this.isSame = delegate( int posA, int posB )
      {
        return ( this.dataA[ posA ] == this.dataB[ posB ] ) && ( this.linesA[ posA ] == this.linesB[ posB ] );
      };

      return DetectDiff();
    }

    /// <summary>単一行の各文字を比較します</summary>
    /// <param name="textA">元テキスト</param>
    /// <param name="textB">変更テキスト</param>
    /// <returns>比較結果</returns>
    public static DiffResult[] DiffChar( string textA, string textB )
    {
      DiffOption option = new DiffOption();
      return DiffChar( textA, textB, option );
    }

    /// <summary>単一行の各文字を比較します</summary>
    /// <param name="textA">元テキスト</param>
    /// <param name="textB">変更テキスト</param>
    /// <param name="option">オプション指定</param>
    /// <returns>比較結果</returns>
    public static DiffResult[] DiffChar( string textA, string textB, DiffOption option )
    {
      if ( string.IsNullOrEmpty( textA ) || string.IsNullOrEmpty( textB ) )
        return StringNullOrEmpty( textA, textB );

      FastDiff diff = new FastDiff();
      if ( textA.Length <= textB.Length )
      {
        diff.SplitChar( textA, textB, option );
      }
      else
      {
        diff.isSwap = true;
        diff.SplitChar( textB, textA, option );
      }

      diff.isSame = delegate( int posA, int posB )
      {
        return diff.dataA[ posA ] == diff.dataB[ posB ];
      };

      return diff.DetectDiff();
    }


    private static DiffResult[] StringNullOrEmpty( string textA, string textB )
    {
      int lengthA = ( string.IsNullOrEmpty( textA ) ) ? 0 : textA.Length;
      int lengthB = ( string.IsNullOrEmpty( textB ) ) ? 0 : textB.Length;
      return PresentDiff( new CommonSubsequence( lengthA, lengthB, 0, null ), true );
    }

    private void SplitChar( string textA, string textB, DiffOption option )
    {
      this.dataA = SplitChar( textA, option );
      this.dataB = SplitChar( textB, option );
    }

    private static int[] SplitChar( string text, DiffOption option )
    {
      if ( option.IgnoreCase )
        text = text.ToUpperInvariant();

      // TODO: FIXME! Optimize this
      if ( option.IgnoreSpace )
        text = Regex.Replace( text, @"\s+", " " );

      if ( option.TrimSpace )
        text = text.Trim();

      int[] result = new int[ text.Length ];
      for ( int i = 0; i < text.Length; i++ )
        result[ i ] = text[ i ];
      return result;
    }

    private static string[] SplitLine( string text, DiffOption option )
    {
      if ( option.IgnoreCase )
        text = text.ToUpperInvariant();

      string[] lines = text.Split( new string[] { "\r\n", "\n", "\r" }, StringSplitOptions.None );

      // TODO: FIXME! Optimize this
      if ( option.IgnoreSpace )
        for ( int i = 0; i < lines.Length; ++i )
          lines[ i ] = Regex.Replace( lines[ i ], @"\s+", " " );

      if ( option.TrimSpace )
        for ( int i = 0; i < lines.Length; ++i )
          lines[ i ] = lines[ i ].Trim();

      return lines;
    }

    private static int[] MakeHash( string[] texts )
    {
      int[] hashs = new int[ texts.Length ];

      for ( int i = 0; i < texts.Length; ++i )
        hashs[ i ] = texts[ i ].GetHashCode();

      return hashs;
    }

    private DiffResult[] DetectDiff()
    {
      Debug.Assert( this.dataA.Length <= this.dataB.Length );

      this.fp = new Snake[ this.dataA.Length + this.dataB.Length + 3 ];
      int d = this.dataB.Length - this.dataA.Length;
      int p = 0;
      do
      {
        //Debug.Unindent();
        //Debug.WriteLine( "p:" + p );
        //Debug.Indent();

        for ( int k = -p; k < d; k++ )
          SearchSnake( k );

        for ( int k = d + p; k >= d; k-- )
          SearchSnake( k );

        p++;
      }
      while ( this.fp[ this.dataB.Length + 1 ].posB != ( this.dataB.Length + 1 ) );

      // 末尾検出用のCommonSubsequence
      CommonSubsequence endCS = new CommonSubsequence( this.dataA.Length, this.dataB.Length, 0, this.fp[ this.dataB.Length + 1 ].CS );
      CommonSubsequence result = CommonSubsequence.Reverse( endCS );

      if ( this.isSwap )
        return PresentDiffSwap( result, true );
      else
        return PresentDiff( result, true );
    }

    private void SearchSnake( int k )
    {
      int kk = this.dataA.Length + 1 + k;
      CommonSubsequence previousCS = null;
      int posA = 0, posB = 0;

      int lk = kk - 1;
      int rk = kk + 1;

      // 論文のfp[n]は-1始まりだが、0始まりのほうが初期化の都合がよいため、
      // +1のゲタを履かせる。fpから読む際は-1し、書く際は+1する。
      int lb = this.fp[ lk ].posB;
      int rb = this.fp[ rk ].posB - 1;

      //Debug.Write( "fp[" + string.Format( "{0,2}", k ) + "]=Snake( " + string.Format( "{0,2}", k )
      //    + ", max( fp[" + string.Format( "{0,2}", ( k - 1 ) ) + "]+1= " + string.Format( "{0,2}", lb )
      //    + ", fp[" + string.Format( "{0,2}", ( k + 1 ) ) + "]= " + string.Format( "{0,2}", rb ) + " ))," );

      if ( lb > rb )
      {
        posB = lb;
        previousCS = this.fp[ lk ].CS;
      }
      else
      {
        posB = rb;
        previousCS = this.fp[ rk ].CS;
      }
      posA = posB - k;

      int startA = posA;
      int startB = posB;

      //Debug.Write( "(x: " + string.Format( "{0,2}", startA ) + ", y: " + string.Format( "{0,2}", startB ) + " )" );

      while ( ( posA < this.dataA.Length )
        &&  ( posB < this.dataB.Length )
        &&  this.isSame( posA, posB ) )
      {
        posA++;
        posB++;
      }

      if ( startA != posA )
      {
        this.fp[ kk ].CS = new CommonSubsequence( startA, startB, posA - startA, previousCS );
      }
      else
      {
        this.fp[ kk ].CS = previousCS;
      }
      this.fp[ kk ].posB = posB + 1; // fpへ+1して書く。論文のfpに+1のゲタを履かせる。

      //Debug.WriteLine( "= " + string.Format( "{0,2}", posB ) );
    }

    /// <summary>結果出力</summary>
    private static DiffResult[] PresentDiff( CommonSubsequence cs, bool wantCommon )
    {
      List<DiffResult> list = new List<DiffResult>();
      int originalStart = 0, modifiedStart = 0;

      while ( true )
      {
        if (   originalStart < cs.StartA
          || modifiedStart < cs.StartB )
        {
          DiffResult d = new DiffResult(
            true,
            originalStart, cs.StartA - originalStart,
            modifiedStart, cs.StartB - modifiedStart );
          list.Add( d );
        }

        // 末尾検出
        if ( cs.Length == 0 ) break;

        originalStart = cs.StartA;
        modifiedStart = cs.StartB;

        if ( wantCommon )
        {
          DiffResult d = new DiffResult(
            false,
            originalStart, cs.Length,
            modifiedStart, cs.Length );
          list.Add( d );
        }
        originalStart += cs.Length;
        modifiedStart += cs.Length;

        cs = cs.Next;
      }
      return list.ToArray();
    }

    /// <summary>結果出力</summary>
    private static DiffResult[] PresentDiffSwap( CommonSubsequence cs, bool wantCommon )
    {
      List<DiffResult> list = new List<DiffResult>();
      int originalStart = 0, modifiedStart = 0;

      while ( true )
      {
        if (   originalStart < cs.StartB
          || modifiedStart < cs.StartA )
        {
          DiffResult d = new DiffResult(
            true,
            originalStart, cs.StartB - originalStart,
            modifiedStart, cs.StartA - modifiedStart );
          list.Add( d );
        }

        // 末尾検出
        if ( cs.Length == 0 ) break;

        originalStart = cs.StartB;
        modifiedStart = cs.StartA;

        if ( wantCommon )
        {
          DiffResult d = new DiffResult(
            false,
            originalStart, cs.Length,
            modifiedStart, cs.Length );
          list.Add( d );
        }
        originalStart += cs.Length;
        modifiedStart += cs.Length;

        cs = cs.Next;
      }
      return list.ToArray();
    }

    private struct Snake
    {
      public int posB;
      public CommonSubsequence CS;

      public override string ToString()
      {
        return "posB:" + this.posB + ", CS:" + ( ( this.CS == null ) ? "null" : "exist" );
      }
    }

    private class CommonSubsequence
    {
      private int startA_, startB_;
      private int length_;
      public CommonSubsequence Next;

      public int StartA { get { return this.startA_; } }
      public int StartB { get { return this.startB_; } }
      public int Length { get { return this.length_; } }

      public CommonSubsequence() { }

      public CommonSubsequence( int startA, int startB, int length, CommonSubsequence next )
      {
        this.startA_ = startA;
        this.startB_ = startB;
        this.length_ = length;
        this.Next = next;
      }

      /// <summary>リンクリスト反転</summary>
      public static CommonSubsequence Reverse( CommonSubsequence old )
      {
        CommonSubsequence newTop = null;
        while ( old != null )
        {
          CommonSubsequence next = old.Next;
          old.Next = newTop;
          newTop = old;
          old = next;
        }
        return newTop;
      }

      public override string ToString()
      {
        return "Length:" + this.Length + ", A:" + this.StartA.ToString()
          + ", B:" + this.StartB.ToString() + ", Next:" + ( ( this.Next == null ) ? "null" : "exist" );
      }
    }

  }
}

"An O(ND) Difference Algorithm and Its Variations"(PDF), EUGENE W. MYERS, (1986)、APIやオプションはAn O(ND) Difference Algorithm for C#を、読み取り結果の保存についてはSubversionを参考にしました。感謝します。

subversionにあった番兵は使いませんでした。ハッシュ値と番兵の値が衝突した場合に配列の範囲外にアクセスする可能性がありうるので。subversionがリングリストにしてるのはこの対策かも。衝突するとどうなるのかよくわかりませんが、おそらくセキュリティホールではないと思います。ただ、正常なdiffは出せないような気がする…。

コード中のコメントアウトしてあるDebug.Write等を動かしながら、論文を読むと動きがわかると思います。すんごいよくできた賢いアルゴリズムでした。アルゴリズムの説明はそのうちちょっとだけ書くかもしれないし、面倒だから書かないかもしれないしw

読み取り方は希望があればコードをアップします。

NNNN 2007/03/26 17:14 ども。Diffの話題を漁っていてたどり着きました。
数年前にDiffのロジックに興味を持って、vivi作者の津田氏の「技術文書」で紹介されていた論文を読み、辛うじてO(ND)が理解できたのですが、O(NP)アルゴリズムに関しては解説しているサイトが見あたらず、『O(ND)は読んだしもう良いかなー』という感じで、暫く手を触れていませんでした。

宜しければザックリとでもO(NP)の解説を書いていただけるとありがたいです。

siokoshousiokoshou 2007/03/27 01:46 あまりわかってないけど(^^; さらっと書いてみます。O(ND)との違いは探索を狭い範囲からはじめて徐々に広げていく点です。k=0〜の範囲(中央部分)から探索をはじめ、一致がなくなったところで次のループで両隣のkについて探索し、再び0〜の範囲を見るってことの繰り返しです。これに対してO(ND)はすぐに広い範囲を探し始めるので、O(NP)より無駄が多いです。文章でたくさん説明するより、動きを見ると巧みさがすぐわかりますよ。
C#を動かせる環境があれば、このコードのDebug.Writeをはずして動かすと、探索の軌跡がきれいに表示されます。これと、EditGraphをつき合わせてたどってみると、動きが見えると思います。お試しあれ〜。

JakenJaken 2010/11/21 13:16 こんにちは、はじめまして。古い記事にコメント失礼します(^^;
バイナリDIFF差分がやりたくて調べてたら、ここにたどり着きました。大変参考になります。

早速、プログラムについて質問と改善(改悪?)案です。
PresentDiffとPresentDiffSwapがAとBを反転させるだけの同じ処理をしているように見えます。
「while(true)」のループ内でisSwapを判定してしまえば、一本化できると思うのですが、これを分けた理由は、やっぱりif判定の回数を減らして速度UPしたいからでしょうか。
速度を量っていないので、どれぐらい遅くなるかわかりませんが、こんな方法を思いつきましたので、ご報告です。
PresentDiffにisSwapを引数で渡して、内部の処理をこんな感じにします。
int startA, startB;
Func<CommonSubsequence, int> csStartA = null;
Func<CommonSubsequence, int> csStartB = null;
if (isSwap)
{
csStartA = (CommonSubsequence csf) => { return csf.StartB; };
csStartB = (CommonSubsequence csf) => { return csf.StartA; };
}
else
{
csStartA = (CommonSubsequence csf) => { return csf.StartA; };
csStartB = (CommonSubsequence csf) => { return csf.StartB; };
}

while (true)
{
startA = csStartA(cs);
startB = csStartB(cs);
省略。以後ループ内でstartAとstartBを参照する。
}
毎回ifするよりは速いのではないかと想像してるのですが、実測はしてませんw
メソッドコールが入るので、現状より遅くなるとは思うのですが、許容範囲にならないですかねぇ・・・。
とりあえず、これでメソッドが一本化でき、コードが短くならないでしょうか。

あと、ご存知かもしれませんが、同じO(ND)の実装でgoogleがdiffを公開してました。C#のコードもあるので、ご興味があれば是非比較記事を(笑)
http://code.google.com/p/google-diff-match-patch/

JakenJaken 2010/11/21 13:23 あ。見間違えてました。このロジックはO(NP)だった・・・
googleとは違いましたね;
忘れてくださいorz

KSKKSK 2011/05/12 09:46 はじめまして。
C#のDiffについて参考にさせていただいています。

1点質問なのですが、
コード中にDebug.Assertとありますが、ここでAssertとなった場合(行数は少ないが、文字数が多い文字列と比較した場合?)、その後の処理でどのようなことが起こるのでしょうか?
(処理速度が遅くなる?正常に比較できない?)

古い記事へのコメントですが、宜しければ教えてください。

siokoshousiokoshou 2011/05/16 15:21 KSKさん、こんにちは。
Assertにはなりません。あくまでもデバッグ用です。
AとBの長さには制約があり、逆にすると正常に比較できません。
詳しくは論文を参照願います。

kasuyakasuya 2016/05/18 14:36 いつもお世話になります。
使用してみまして、

string original = "静岡大学大学院";
string dest = "大学院理工学研究科情報専攻";
var DiffResult = FastDiff.DiffChar(original, dest);
を計算すると、
下記のような出力になりますが、
[0] = {Modified, OrgStart:0, OrgLen:2, ModStart:0, ModLen:0}
[1] = {Common, OrgStart:2, OrgLen:2, ModStart:0, ModLen:2}
[2] = {Modified, OrgStart:4, OrgLen:1, ModStart:2, ModLen:3}
[3] = {Common, OrgStart:5, OrgLen:1, ModStart:5, ModLen:1}
[4] = {Modified, OrgStart:6, OrgLen:1, ModStart:6, ModLen:7}

できれば下記のように出たらいいのにと思います。
[0] = {Modified, OrgStart:0, OrgLen:4, ModStart:0, ModLen:0}
[1] = {Common, OrgStart:4, OrgLen:3, ModStart:0, ModLen:3}
[2] = {Modified, OrgStart:7, OrgLen:0, ModStart:3, ModLen:10}

とはいえ、

静岡大学 大学院
大学院理工 学 研究科情報専攻

という対応付けでも

静岡大学大学院
大学院理工学研究科情報専攻

という対応付けでも同じ3文字対応付けられてるし仕方ないなと思ってもやもやしています。

siokoshousiokoshou 2016/05/20 23:13 kasuyaさん、こんにちは。
それがいいですね。最長一致とか呼ぶのでしょうか?
ぜひそのようなアルゴリズムを探すか作るかしてみてください。

2007/3/12 (月)

[][][] diff その3  diff その3を含むブックマーク  diff その3のブックマークコメント

前回は http://www.mathertel.de/Diff/ のコードの Hashtable を削除したら2倍速くなったところまで。今日はその続き。

このコードでは文字列を行ごとにばらしてハッシュ値にする前処理があって、その後にハッシュ値配列のdiffを調べる。この前処理とdiff処理の各時間を計ると、2桁差で圧倒的に前処理に時間が掛かってました。

じゃあってことで、ハッシュ化止めて文字列をそのまま比較してみると、前回のHashtableなし版と同程度の速度でした。これって、オリジナルはハッシュ化で余計遅くなってるってことじゃ…。高速化はまず計測ありきですな。

文字列のインターン化も試してみたけど、Hashtableあり版と同程度の時間でした。内部でHashtable使ってるってリッチャーが書いてるけど、それと一致する速度ですね。

しょうがないんで(なにが?w)、どう見ても手抜きな DiffCodes() を直してみました。Splitしてオプションに従って文字列いじってハッシュ値を求めた後は文字列を捨てるんで、どう見ても無駄です。経験的にSplitは遅い気がするし。LLっぽくてかなり重宝してるけど。

private static int[] DiffCodes( string text, Option option )
{
	if ( option.IgnoreCase )
		text = text.ToUpperInvariant();

	List<int> list = new List<int>();
	const int seed = 5381;
	int h = seed;
	for ( int i = 0; i < text.Length; i++ )
	{
		if ( text[ i ] == '\n' )
		{
			list.Add( h );
			h = seed;
			continue;
		}
		h = ( ( h << 5 ) ^ ( h >> 27 ) ) ^ text[ i ];
	}
	if ( ( h != seed ) || ( text[ text.Length - 1 ] == '\n' ) )
		list.Add( h );

	return list.ToArray();
}

まじめに行末を探しながらハッシュ化してみました。\r削除はいらないような気がしたんで削除。ignoreSpace と trimSpace は面倒なので元のコードを使ってください。ところで ignoreSpace は空白文字の連続を空白1文字にしてるけど、ignoreSpace って響きからすると空白全削除がいいような気がするんだけど、どうなんでしょう。

これで、オリジナルに比べて約6倍も速くなった!シャアより速いw

O(ND)とかO(NP)とか調べて楽しんでるのに、こんなところで高速化してしまうんじゃつまらないw ってわけで、O(NP)にも取り組んで、subversionの移植を捨ててペーパーのコードを持ってきました。subversionの一致部分の保存/読み取りのとこは参考にしつつ。今度こそO(ND)のコードより速くなりました。http://www.mathertel.de/Diff/ のコードと比べると当社比(?)14倍も高速。そのうち公開します。ペーパーではfpが-1ベースなのに対して0ベースに改善した(つもり)。たいていの言語でさらに速くなるハズ。

ところでsubversionのコードでシーケンスをリング状のリンクリストにしてる理由がよくわかんなかった。番兵を追加するときに、巧みに文字列の入れ替えをしてる(O(NP)では文字列長の制約がある。文字列A,BのうちBが長くないといけない)んだけど、そのためだけのような気がした。CとC#の違いも山程あるけど、もしかしたらsubversionも単純なコードにすればもう少し速くなるのかもしれない。あと、Cでは引数の[IN][OUT]くらいはコメントに書けw!

しっかし、アルゴリズムはまだしっかり理解できないな〜。速いアルゴリズムのほうが短くて単純なコードになってるのがおもしろい。以前見たQuickSearchもそうだったけど。比較回数はペーパーでは1/2とあるけど、それどころじゃなく減る場合も普通にあります。なんてかしこいんだろ。

トラックバック - http://d.hatena.ne.jp/siokoshou/20070312

2007/3/9 (金)

[][][] diff その2  diff その2を含むブックマーク  diff その2のブックマークコメント

http://www.mathertel.de/Diff/

ここのO(ND)なコード、「非常に早いコードです。diffのアルゴリズムに詳しくなければこれより早いコードは書けません。」と書いたばかりでなんだけど、ちょっといじったら2倍早くなった。前言撤回(^^;

Hashtableいらなくね?と気づいて、直接stringのGetHashCode()を取るようにしたら、手元のデータでは2倍も早くなってしまった。

ほかのいじったところと一緒に貼っときます。

public struct Option
{
	public bool TrimSpace, IgnoreSpace, IgnoreCase;
}

public static Item[] DiffText( string textA, string textB )
{
	Option option = new Option();
	return DiffText( textA, textB, option );
}

public static Item[] DiffText( string textA, string textB, Option option )
{
	DiffData dataA = new DiffData( DiffCodes( textA, option ) );
	DiffData dataB = new DiffData( DiffCodes( textB, option ) );

	LCS( dataA, 0, dataA.Length, dataB, 0, dataB.Length );
	return CreateDiffs( dataA, dataB );
}

private static int[] DiffCodes( string text, Option option )
{
	// strip off all cr, only use lf as textline separator.
	text = text.Replace( "\r", "" );

	if ( option.IgnoreCase )
		text = text.ToLower();

	string[] lines = text.Split( '\n' );

	if ( option.TrimSpace )
		for ( int i = 0; i < lines.Length; ++i )
			lines[ i ] = lines[ i ].Trim();

	// TODO: optimization: faster blank removal.
	if ( option.IgnoreSpace )
		for ( int i = 0; i < lines.Length; ++i )
			lines[ i ] = Regex.Replace( lines[ i ], "\\s+", " " );

	int[] hashs = new int[ lines.Length ];

	for ( int i = 0; i < lines.Length; ++i )
		hashs[ i ] = lines[ i ].GetHashCode();

	return hashs;
}

ちなみに、この高速化をしたら移植したO(NP)diffより速くなってしまった…。

2007/3/8 (木)

[][][] diff  diffを含むブックマーク  diffのブックマークコメント

(追記)この日の日記で紹介したO(ND)のdiffクラスより高速なO(NP)のdiffを書きました。id:siokoshou:20070315を参照。(追記終わり)


コード中でdiffを取りたかったので.NETなdiffクラスがないかと探してみたら、とてもよいものを見つけました。

http://www.mathertel.de/Diff/

deってことでドイツの方らしく、コードが大変几帳面でおもしろい(ステレオタイプな見方だけど)。Danke.

スピードはGood。作者によるとまだ最適化の余地はあるようですが、それでも非常に早いコードです。diffのアルゴリズムに詳しくなければこれより早いコードは書けません。.NET1.1らしく、Hashtableを使ってます。(追記)id:siokoshou:20070309 でさらに速くした。(追記終わり)

v5で public Item [] DiffText(string TextA, string TextB) を static に変更し忘れてますね。

サイト上で過去のバージョンとのdiffを見ることができて、これは自身のdiffを使ってるっぽい。ちょっとC風なコードですね。

2つのテキストの行の合計がintの範囲を超えるとマズイ作りだけど、2007年現在のメモリ量から言うと問題ないですね。

出力形式が扱いづらいんですが、共通項も出力するように改造するか、あるいは内部形式のDiff.DiffDataを直接扱えばきっと楽です。

CodeProjectでもC#のdiffの記事を2つ見つけたけど、こちらは総当りで比較するのか遅いのでお勧めできません。コードがイマイチだったんで、あまり読んでないけど。


diffのアルゴリズムについてぐぐるviviの作者さんのとこがよく参照されてるようです。vivi昔使っていました。vi派です。

上記のdiffはここにあるO(ND)アルゴリズムです。Unixのdiffを書いたときの論文っぽい。上記のサイトから論文のPDFへのリンクがあります。GNUのdiffもちらっと見たら、同じアルゴリズムのようです。

WikipediadiffLCS最長一致シーケンス列も良い資料です。普段からdiffを多用していながら、diffのアルゴリズムって気にしたこともなかったんですが、実に奥深い世界に繋がってておもしろいですねぇ。

ところで、気になるのは2倍早いというO(NP)なアルゴリズムのほう。インターネットアーカイブから論文を見つけました。ほとんど読んでませんが…。

実装を探してみるとRubyによる実装がありました。Rubyよくわかってないので、Rubyらしいところがわかりません…。

もう少し調べるてみるとSubversionがO(NP)とのこと。バージョン管理システムはdiffの上に成り立っているんで、diffの質は重要です。Cなのでコードを読んでみると…。これは本当に凄い凄いコードです!輝いて見えますw Guruが書くとCはこうなるのかって思い知らされました!Cなのにかなりきれいでテクニック満載。すげ〜すげ〜よ、これは、マジで…。プログラマを使い捨てていたらこんなコードを書ける人は生まれませんよ、なんて。

libsvn_diffの下あたりがdiff。論文のコードのpのループの最後のsnakeがないのはどうしてなんだろう?Rubyのコードにもない。(追記)わかった。擬似コードの2つ目のループに含めただけだった。(追記終わり)文字列をRing状のリンクリストにし、最後に番兵をつけて論文のコードにさらに磨きをかけてます。

ぼーっと読んでいてもよく分からないんでC#に移植してみました。ちまちまと移植してなんとか動いてますが、やっぱりまだ分からないところが多かったり(^^;

公開してもいいんでしょうか、これ。ライセンス読んでもよくわかりません。移植はどういう扱いになるんだろ?公開しても良いなら、ここにぺたんと貼り付けるんですが。どなたか詳しい方がいらっしゃいましたら教えてください。

気になるスピードですが、不満です。上記O(ND)のdiffより1割程度早いだけでした。早くはなっているものの、期待したほどじゃないのが、ね。元のSubversionのコードはファイルから読み込むようになっているところを、O(ND)のdiffを真似てstringを受けてハッシュ化して比較するように変更したんだけど、このあたりの速度が気になるところ。まあ、なにはともあれ速度は計測しないとね。そのうちまたちびちびと調べてみます。

今日のびっくりは、2chでよく見る「一方ロシアは鉛筆を使った」のネタ元が珠玉のプログラミングだったこと。コラム1の最後の問題でした。文言は違いますが。

2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 09 | 11 | 12 |
2007 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 08 | 09 | 10 | 12 |
2009 | 01 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 07 |
2011 | 04 | 07 | 10 |
2012 | 04 | 12 |
2013 | 08 |
2014 | 03 | 08 |
2017 | 09 |