メモメモメモメ

2010年12月31日金曜日

Feedのアドレス

ちょっとあまりにも配信に時差がでちゃうので、Feedのアドレス変えます。すません。

Blogpost：無聊を託つ

http://feeds.feedburner.com/blogspot/jNRCtw

Tumblr：等閑に付さないように

http://feeds.feedburner.com/tumblr/ijTN

旧FeedのアドレスはTumblrの方に向けます。ホントすません。

2010年12月30日木曜日

問題だと思っていることはホントに問題なの？

すっかり忘れてました。新しく開発者を採用するにあたり、会社の方針に合わせてコードを書いてもらいました。で、採用担当としてこんな問題を考えました。

問題内容

２つの文字列を与えられた時、それぞれの文字列の一致率を０～１の間で算出する関数を作成せよ。
※一致率の定義の仕様も含めて考えてください。

いろいろ考え方や思うところはあると思いますが、今回に関しては問題を解く過程をとても重視しました。どういうふうに仕様を決めるのかも含め、です。内容からして勝手に仕様を決めていいように思われるかもしれないですが、そこの解釈も重視です。与えられた情報の範囲内でどこまで飛べるのか、みたいな。

解答例

public static decimal Rate(string value1, string value2)
{
    if (string.IsNullOrEmpty(value1) || string.IsNullOrEmpty(value2))
        return 0m;

    if (string.IsNullOrEmpty(value1.Trim()) || string.IsNullOrEmpty(value2.Trim()))
        return 0m;

    if (string.Compare(value1, value2, StringComparison.CurrentCulture) == 0)
        return 1m;

    var longer2nd = value1.Length < value2.Length;
    var val1 = longer2nd ? value1 : value2; // 短い文字列
    var val2 = longer2nd ? value2 : value1; // 長い文字列
    int match = 0, p1 = 0, p2 = 0, p2Index = 0;

    while (p1 < val1.Length && p2 < val2.Length)
    {
        if (val1[p1] == val2[p2Index])
        {
            match += 2;
            p1++;
            p2 = p2Index++;
        }
        else
        {
            p2Index++;
            if (p2Index >= val2.Length)
            {
                p1++;
                p2Index = p2;
            }
        }
        
        if (val2.Length - 1 < p2Index)    // 進みすぎたときには引き戻す
            p2Index = p2;
    }

    return match / (decimal)(value1.Length + value2.Length);
}

最初のほうはエラーチェックだから、今回別に無くてもよかったです。

あれっすよ、こんなの10分やそこらでコード化するもんじゃないかもね。でも、考え方というか解き方というか、問題はどこでどういう回答をビジネスオーナーは望んでいるのか、ですよね。

問題を考えたものとしては、この問題で先頭一致の割合だけでとくのが一番簡単なのは分かってて、それだけじゃない解き方を答えて欲しいな～、と思ってました。

“どのくらい一致しているか”

の定義は様々だけど「全体文字数に占める一致文字数の割合」が手頃な回答ですよね。んじゃ、一致文字数というのはどういう意味だと解釈するのが面白いか。文字列を前半・中央・後半の3つの集合として考えて、それぞれの文字列の比較開始位置と一致文字数を数えていけば、それらしい数値を出すこと方法として面白いんじゃないかと思うんだけど、どうかな。

前半	中央	後半	文字列１	文字列２
○	○	○	AABBCC	AABBCC
○	○		AABBCC	AABBzz ※AABBも同じ
	○	○	zzBBCC	yyBBCC ※BBCCも同じ
○		○	AAzzCC	AAyyCC ※AACCも同じ
	○		zzAAyy	xxAAww

※前半だけ、後半だけは前半＋中央と中央＋後半と同じ。

こんな感じのパターン。ちなみにこのパターンを答えた人がひとりだけいましたよ。なんで同じ答えにたどり着いたのかというと、そういう定義をオーナーが望んでると聞き出したからです。そりゃ同じになるわね。

じゃー、このコードがホントにそれっぽく一致率がでるのか確認するテストコード。

[TestMethod]
public void 空文字渡し()
{
	var rate = MatchRate.Rate(null, null);
	Assert.AreEqual(0, rate);

	rate = MatchRate.Rate("", null);
	Assert.AreEqual(0, rate);

	rate = MatchRate.Rate(null, "");
	Assert.AreEqual(0, rate);

	rate = MatchRate.Rate("", "");
	Assert.AreEqual(0, rate);

	rate = MatchRate.Rate("", "AA");
	Assert.AreEqual(0, rate);

	rate = MatchRate.Rate("AA", "");
	Assert.AreEqual(0, rate);
}

[TestMethod]
public void 空白渡し()
{
	var rate = MatchRate.Rate(" ", "");
	Assert.AreEqual(0, rate);

	rate = MatchRate.Rate("", "  ");
	Assert.AreEqual(0, rate);

	rate = MatchRate.Rate("AA", " ");
	Assert.AreEqual(0, rate);
}

[TestMethod]
public void 完全一致()
{
	var rate = MatchRate.Rate("AA", "AA");
	Assert.AreEqual(1m, rate);

	rate = MatchRate.Rate("aa", "aa");
	Assert.AreEqual(1m, rate);
}

[TestMethod]
public void 前方一致で６６パーセント()
{
	var rate = MatchRate.Rate("AA", "AABB");
	Assert.AreEqual(2m / 3m, rate);
}

[TestMethod]
    public void 後方一致で６６パーセント()
{
	var rate = MatchRate.Rate("AA", "BBAA");
	Assert.AreEqual(2m / 3m, rate);
}

[TestMethod]
public void 中央一致で６６パーセント()
{
	var rate = MatchRate.Rate("AA", "BAAB");
	Assert.AreEqual(2m / 3m, rate);
}

[TestMethod]
public void 前後半一致で６６パーセント()
{
	var rate = MatchRate.Rate("AA", "ABBA");
	Assert.AreEqual(2m / 3m, rate);
}

[TestMethod]
public void 前後半一致で７５パーセント()
{
  var rate = MatchRate.Rate("ABCDE", "ADE");
  Assert.AreEqual(6m / 8m, rate);
}

だいたいいい感じなんじゃないっすかね。直感的にそんな感じ。セマンティックとか関係なく、ですから。問題はここまでで終了。

だたひとり答えにたどり着いたクマさんに拍手。

ここからさらに考え方を進めてみましょう。もし文字列が文章だとしたら。文章だと”の”とか”を”とかが入ってくるから、普通に一致させるだけだと、それっぽくならないですね。なので、このアルゴリズムを再帰に改造して、前半を無視したほうが一致率が上がるなら無視するというふうに改造してみます。何でかというと、このアルゴリズムだと一致率は上昇して頂点になったあと下降するっていう山型になるはずだからです。現在の位置と次の位置との比較で一致率が上昇してるなら、現在の位置は無視したほうがそれっぽい数値に近づくってことです。そうするとコピペ文章なんじゃん？っていうものに関しての判定が”それっぽく”できます。あくまで”それっぽく”ですよ。

public static decimal Rate(string value1, string value2)
{
    return Rate(value1, value2, null);
}

public static Func<string, int, string, int, bool> RecursiveCommand = (val1, idx1, val2, idx2) =>
{
    var p1Rate = Rate(val1.Substring(idx1), val2.Substring(idx2), null);
    var p1IncRate = Rate(val1.Substring(idx1 + 1), val2.Substring(idx2), null);
    return p1Rate < p1IncRate;
};

public static decimal Rate(string value1, string value2, Func<string, int, string, int, bool> command)
{
    if (string.IsNullOrEmpty(value1) || string.IsNullOrEmpty(value2))
        return 0m;

    if (string.IsNullOrEmpty(value1.Trim()) || string.IsNullOrEmpty(value2.Trim()))
        return 0m;

    if (string.Compare(value1, value2, StringComparison.CurrentCulture) == 0)
        return 1m;

    var longer2nd = value1.Length < value2.Length;
    var val1 = longer2nd ? value1 : value2; // 短い文字列
    var val2 = longer2nd ? value2 : value1; // 長い文字列
    int match = 0, p1 = 0, p2 = 0, p2Index = 0;

    while (p1 < val1.Length && p2 < val2.Length)
    {
        // p1とp1+1で比較してp1+1のほうがRateがよければp1はスキップする
        if (command != null)
        {
            p1 += command(val1, p1, val2, p2Index) ? 1 : 0;
        }

        if (val1[p1] == val2[p2Index])
        {
            match += 2;
            p1++;
            p2 = p2Index++;
        }
        else
        {
            p2Index++;
            if (p2Index >= val2.Length)
            {
                p1++;
                p2Index = p2;
            }
        }

        if (val2.Length - 1 < p2Index)    // 進みすぎたときには引き戻す
            p2Index = p2;
    }

    return match / (decimal)(value1.Length + value2.Length);
}

で、最初のテストがパスするのを確認したうえで、以下のテスト。

[TestMethod]
public void 再帰のほうがそれっぽくなる()
{
  var rate = MatchRate.Rate(
      "ABCDEF",
      "AECDEF"
  );
  var rateR = MatchRate.Rate(
      "ABCDEF",
      "AECDEF",
      MatchRate.RecursiveCommand
  );
  Console.WriteLine("Rate={0} < RateR={1}", rate, rateR);
  Assert.IsTrue(rate < rateR);
}

[TestMethod]
public void コピペしてちょっと手直しした文章()
{
  var rate = MatchRate.Rate(
		"衆院は３１日の夜、会議を開き、日本郵政３社への再編などを柱とする郵政改革法案を賛成多数で可決し、参院に送付した。与党は参院でも短時間で審議し、６月１６日までの会期内成立を目指す構え。自民、公明、みんな、たちあがれ日本の野党４党は１日、与党の意向を受け、本会議開催を強行した横路孝弘衆院議長に対する不信任決議案を提出する。",
		"衆院は３１日深夜、本会議を開き、日本郵政グループの３社への再編などを柱とする郵政改革法案を民主、国民新党などの賛成多数で可決し、参院に送付した。与党は参院でも短時間で審議を終え、６月１６日までの会期内成立を目指す構え。自民、公明、みんな、たちあがれ日本の野党４党は１日、与党の意向を受け、本会議開催を強行した横路孝弘衆院議長に対する不信任決議案を提出する。",
            MatchRate.RecursiveCommand
	);
	Console.WriteLine(rate);
}

ソースアップしておきまーす。何かの役に立つコードではないけどね！

2010年12月29日水曜日

Razor Templating Engine

CodePlexで新しいのが出てたよ～。面白いね～。テンプレートエンジンっていろいろ用途があるけど需要はどーなんだろね。まぁ、いいや。Razor記法でWeb以外にも使えるって楽しいっすよね。だっていろいろ覚えなくて済むし。ちなみにASP.NETの<%...%>とか<%$…%>とか<%#…%>なんかの記法も用途特化したテンプレートエンジンが解釈してクラスファイルを生成してますよね。

んでね、Razorは純粋にテンプレートエンジンって言ってるくらいだからWebのコンテキストや実行Hostに依存しないわけですね。つまりConsoleアプリでも使えるってことです。もちろんHtmlHelperとかWeb関連のアセンブリに依存するものはあるとしても、それ自体はRazorの機能じゃなくてHelperの機能。TemplateBaseクラスが生成されるクラスの親クラスになるって言う仕組みなので、親クラスにいろいろWeb関連の機能を保持するっていう、Razorとは直接関係なっしんぐ。

サンプル見てみるとこんな感じですね。

string template = "Hello @Model.Name! Welcome to Razor!";
string result = Razor.Parse(template, new { Name = "World" });

Console.WriteLine(result);
Console.ReadLine();

簡単ですね～。お気楽です。

同じくサンプルのHtmlHelperを使うパターン。

Razor.SetTemplateBaseType(typeof(HtmlTemplateBase<>));
string template =
@"<html>
    <head>
    <title>Hello @Model.Name</title>
    </head>
    <body>
    Email: @Html.TextBoxFor(m => m.Email)
    </body>
</html>";

var model = new PageModel { Name = "World", Email = "someone@somewhere.com" };
string result = Razor.Parse(template, model);

Console.WriteLine(result);
Console.ReadLine();

はい、これも簡単ですね。イメージ通りです。

PageModelは自分で作ってね。あと、RazorEngine.Coreだけじゃ足りなくて、RazorEngine.Templatesアセンブリも必要なので、ソースのダウンロードはここからどーぞ。

これらは全て実行時にクラスファイル(特に指定が無い限りc#)をオンメモリで生成してコンパイルします。そのタイミングでAppDomain内からはクラスのインスタンスを生成できるようになるって言う流れはASP.NETのパイプラインそのもの。

試しに最初のサンプル(Hello World!のほう)をステップ実行していくと、どういうクラス名で生成されるのかというのを追いかけていくと．．．。

雑ですね。Guid.NewGuid()から数字とハイフンを除外したのがクラス名。それにNamespaceをくっつけてます。で確認。

ちゃんといます。で、AppDomainの仕様を見てみるとこんなことがかかれてます。

既定のアプリケーションドメインにロードされたアセンブリは、プロセスの実行中にメモリからアンロードすることはできません。しかし、アプリケーションドメインをもう 1 つ開いてアセンブリをロードおよび実行すると、そのアプリケーションドメインがアンロードされたときに、アセンブリもアンロードされます。このテクニックを使用すると、大きな DLL を使用する場合のある、長時間実行されるプロセスのワーキングセットを最小限に抑えることができます。

AppDomain クラス (System)

ん～、どーだろ。どうなるんだろね。

めちゃめちゃ分かりにくいですね。2個目のサンプル(HtmlHelper使うほう)を使ってRazor.Parseを繰り返してる途中です。

Razor.SetTemplateBaseType(typeof(HtmlTemplateBase<>));
var model = new PageModel { Name = "World", Email = "someone@somewhere.com" };

for (var i = 0; i < (singleExec ? 1 : Repeat); i++)
{
    var sw = new Stopwatch();
    sw.Start();
    var result = Razor.Parse(Template, model);
    sw.Stop();

    Console.WriteLine(
        "{0} - {1} {2} ms {3:0,###} bytes",
        result.GetHashCode(),
        i,
        sw.ElapsedMilliseconds,
        Process.GetCurrentProcess().PrivateMemorySize64);
}

少しずつメモリ使用量と動作時間が長くなっていきます。最初は200msとかで処理。すごく単純で1種類だけの生成なのにね。ちなみに一度コンパイルしたものをその後何度も使用する場合は超早い。

10000回実行してもすぐ終了。

これってつまり、ASP.NETでも同じでaspxを何度も書き換えてると処理時間はどんどん増加。いつか破綻？でもリサイクルも走るし、そもそも運用環境でそんなことしないから問題にはならないか。

AppDomainをアンロードしない限りアセンブリもアンロードされないってことはつまり常時動いてるようなシステムで頻繁にコンパイルを繰り返すのはよろしくないね！ってなりましょう。それをひっくり返すのがAppDomainを別に作ってそっちで動かす方法。

リファレンスにもちゃんとかかれてますね。ボスもタイムリーに(MEFだけど)、そんなことをブログに書いてました。

MEFでディレクトリカタログを追いかける(C# Advent Calender jp:2010 12/02) « kazuk は null に触れてしまった

なのでAppDomainを作って実行するように試してみた。

けど無理！遅すぎ！

var sw = new Stopwatch();
sw.Start();

AppDomainSetup ads = new AppDomainSetup();
ads.ApplicationBase = Environment.CurrentDirectory;
ads.DisallowBindingRedirects = false;
ads.DisallowCodeDownload = true;
ads.ConfigurationFile = AppDomain.CurrentDomain.SetupInformation.ConfigurationFile;

AppDomain executeAppDomain = AppDomain.CreateDomain("AD#" + i, null, ads);
var razor = executeAppDomain.CreateInstanceAndUnwrap(
    Assembly.GetEntryAssembly().FullName,
    typeof(RazorTemplateTest).FullName
) as RazorTemplateTest;

razor.ExecuteParse(i);

AppDomain.Unload(executeAppDomain);

sw.Stop();

Console.WriteLine(" {0} : {1} ms",
    AppDomain.CurrentDomain.FriendlyName,
    sw.ElapsedMilliseconds);

でも、まぁ、思ったような結果が出なかった残念な調査でした。ホントはもっとメモリ開放されないことを想定してたんだけどな～。

オチがない．．．。

using System;
using System.Diagnostics;
using System.Reflection;
using RazorEngine;
using RazorEngine.Templating;

namespace ConsoleApplication1
{
    public class PageModel
    {
        public string Name { get; set; }
        public string Email { get; set; }
    }

    public class RazorTemplateTest : MarshalByRefObject
    {
        private static int Repeat = 10000;
        static string Template =
@"<html>
    <head>
        <title>Hello @Model.Name</title>
    </head>
    <body>
        Email: @Html.TextBoxFor(m => m.Email)
    </body>
</html>";

        public void ExecuteParse()
        {
            ExecuteParse(-1);
        }

        public void ExecuteParse(int counter)
        {
            Razor.SetTemplateBaseType(typeof(HtmlTemplateBase<>));
            var model = new PageModel { Name = "World", Email = "someone@somewhere.com" };

            for (var i = 0; i < (counter!=-1 ? 1 : Repeat); i++)
            {
                var sw = new Stopwatch();
                sw.Start();
                var result = Razor.Parse(Template, model);
                sw.Stop();

                Console.WriteLine(
                    "{0} - {1} {2} ms {3:0,###} bytes",
                    AppDomain.CurrentDomain.FriendlyName,
                    counter != -1 ? counter : i,
                    sw.ElapsedMilliseconds,
                    Process.GetCurrentProcess().PrivateMemorySize64);
            }
        }

        public void ExecuteCompile()
        {
            Razor.SetTemplateBaseType(typeof(HtmlTemplateBase<>));
            var model = new PageModel { Name = "World", Email = "someone@somewhere.com" };

            Razor.Compile(Template, typeof(PageModel), "test");

            for (var i = 0; i < Repeat; i++)
            {
                var sw = new Stopwatch();
                sw.Start();

                var result = Razor.Run(model, "test");

                sw.Stop();

                Console.WriteLine(
                    "{0} - {1} {2} ms {3:0,###} bytes",
                    result.GetHashCode(),
                    i,
                    sw.ElapsedMilliseconds,
                    Process.GetCurrentProcess().PrivateMemorySize64);
            }
        }

        public void ExecuteAnotherAppDomain()
        {
            for (var i = 0; i < Repeat; i++)
            {
                var sw = new Stopwatch();
                sw.Start();

                AppDomainSetup ads = new AppDomainSetup();
                ads.ApplicationBase = Environment.CurrentDirectory;
                ads.DisallowBindingRedirects = false;
                ads.DisallowCodeDownload = true;
                ads.ConfigurationFile = AppDomain.CurrentDomain.SetupInformation.ConfigurationFile;

                AppDomain executeAppDomain = AppDomain.CreateDomain("AD#" + i, null, ads);
                var razor = executeAppDomain.CreateInstanceAndUnwrap(
                    Assembly.GetEntryAssembly().FullName,
                    typeof(RazorTemplateTest).FullName
                ) as RazorTemplateTest;

                razor.ExecuteParse(i);
                
                AppDomain.Unload(executeAppDomain);

                sw.Stop();

                Console.WriteLine(" {0} : {1} ms",
                    AppDomain.CurrentDomain.FriendlyName,
                    sw.ElapsedMilliseconds);
            }
        }
    }

    class Program
    {

        static void Main(string[] args)
        {
            //new RazorTemplateTest().ExecuteParse();
            //new RazorTemplateTest().ExecuteCompile();
            new RazorTemplateTest().ExecuteAnotherAppDomain();

            Console.ReadLine();
        }
    }
}

こんなコードで～す。

登録: 投稿 (Atom)