東方算程譚

Visual Studio 2010 Release Candidate

επιστημη — Tue, 09 Feb 2010 11:54:00 GMT

でましたよ、Release Candidate。 VS2010の。

そらもーリリース・キャンディデート っちゅーくらいなもんだから
砂糖菓子のように甘くそしてはかない夢の一日ちがーう!

おかげでアレだ、日英のβ版引っこ抜かんならんわ、
TechDaysの仕込みネタ再検証だわ、飛び込み仕事がどかどかと。

...て、によによしてる俺ガイル♪

よいどれコンパス

επιστημη — Wed, 03 Feb 2010 14:59:00 GMT

# 「数学Day」前座

べろべろに酔っ払ったコンパスがいる。
よたよたふらふらと歩き回るが歩幅は一定。
このよいどれコンパスを広場の真ん中に置き去りにする。
コンパスはどんな軌跡を描くだろうか。

雰囲気的に「中心が濃く、中心から遠ざかるほど薄い雲」になりそう。
ホントカナ?

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        bmp = New Bitmap(PictureBox1.Width, PictureBox1.Height)
        PictureBox1.Image = bmp
        x = PictureBox1.Width / 2
        y = PictureBox1.Height / 2
    End Sub

    Private bmp As Bitmap
    Private x As Integer
    Private y As Integer
    Private r As New Random()

    Private Sub start_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles start.Click
        Timer1.Enabled = True
    End Sub

    Private Sub Timer1_Tick(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Timer1.Tick
        Dim theta As Double = r.NextDouble() * 2.0 * 3.1416
        x = x + 5 * Math.Sin(theta)
        y = y + 5 * Math.Cos(theta)
        If (x > 0 AndAlso x < PictureBox1.Width) Then
            If (y >= 0 AndAlso y < PictureBox1.Height) Then
                bmp.SetPixel(x, y, Color.Red)
                PictureBox1.Image = bmp
            End If
        End If
    End Sub

乱数の精度に依存しそうですねー。

DbC/PbC と NVI

επιστημη — Tue, 02 Feb 2010 11:28:00 GMT

先週末のわんくま東京勉強会、ひさしぶりに懇親会に出たなり。

ま、それはそれとして、中さんのセッション: Spec# は面白かたあるよ。
DbC(Design by Contract:契約による設計) / PbC(Programming by Contract:契約プログラミング)
はEiffelやDあたりがサポートしてるんだけど、そいつをC#でもやっちまえって魂胆ね > Spec#

従来

class Base {
public virtual int func(int x) {
    Debug.Assert(x > 0 && x < 10); //事前条件: x = 0..9 でなければならない
    ....
    int result = ごーにょごにょ
    Debug.Assert(result >= 0); // 事後条件: 0以上を返すことをここに誓う
    return result;
}
}

なんてな Assert で利用者が守るべき契約(事前条件) 提供者が守る契約(事後条件) を
コード上に明記しよう。そうすることでより堅牢でバグの少ない(あっても直ちに判明する)
コードを書こうや、と。
# 不変表明(invariant)ゆーのんもありますがー

ここで問題となるのが、派生クラスで func をoverrideしちまったとき、
Base::funcに埋め込まれた契約条件がoverride側に適用されんです。
で、こいつの解決策のひとつがNVI(Non Virtual Interface)ってイディオム。

「利用者にvirutalなメソッドを晒すなﾎﾞｹｪ」てことっす。
んじゃどーするかっちゅーと:

class Base {
public sealed int func(int x) {
    Debug.Assert(x > 0 && x < 10); //事前条件: x = 0..9 でなければならない
    int result = do_func(x);
    Debug.Assert(result >= 0); // 事後条件: 0以上を返すことをここに誓う
    return result;
}
protected virtual int do_func(int x) {
    return ごーにょごにょ;
}
}

こーしておく。派生クラスはfuncから呼ばれてる do_func をoverrideするのね。

CodeZineに書きました。

επιστημη — Tue, 26 Jan 2010 21:47:00 GMT

C++/CLIでの
System::String^ と std::string と std::wstring と
const char* と const wchar_t* との間を行ったり来たりする方法。

どぞ、よろしく。
※ IBM ICU(International Components for Unicode）も紹介しちょります。

くだらんことやってますのん

επιστημη — Sat, 23 Jan 2010 06:46:00 GMT

ケッタイなこと頼まれましてね。
えとね、たとえばこんな数枚のWeb-pageがあったとするやないですか。

とかとか。

最初のページのURLあげるから、

「リンクを次々に辿りながらtable内の<td>～</td>を拾って一本の表を仕立ててくれ」

ってんですよ。

こんな感じで。

つまりこの、HTMLを解析しぃのページ上のリンクをつつきぃの、そゆこと自動でやってくれと。

んで僕が目を付けたのが selenium てゆー Web-アプリのTestTool.
seleniumはブラウザ上での人の操作を記録し、play-backしてくれます。

面白いことに、このseleniumを外から(.NETやらJavaやらPHPやらRubyやらで)

リモコン操作できるんす。

こいつを使ってページを渡り歩き、seleniumが読みだしたHTMLをパーサで解析してます。
.NET Frameworkには出来合いのHTMLパーサがなさげ(よね?)なので、
「すまんけどXHTMLなページ限定」と念を押してXML-domパーサ使いました。
”GET”ボタン押すと↓こんなのが動きます。　40行で書けちゃったですよ。

private void btnGET_Click(object sender, EventArgs e)
{
string serverURL = "localhost";
int serverPort = 4444;
string targetBrowser = "*firefox";
string targetURL = "http://www1.c3-net.ne.jp/episteme/";
selenium = new Selenium.DefaultSelenium(serverURL, serverPort, targetBrowser, targetURL);
selenium.Start();
selenium.Open("/episteme/CodeZine/trial.html");
while ( true ) {
StringBuilder builder = new StringBuilder("<?xml version='1.0' ?>");
// 得られたHTMLから<body>～</body>を抽出し、<html>～</html>ではさむ
builder.Append("<html>");
string html = selenium.GetHtmlSource();
int startpos = html.IndexOf("<body");
int endpos = html.IndexOf("/body>") + 6;
builder.Append(html, startpos, endpos - startpos);
builder.Append("</html>");
// XHTMLをXMLパーサで解析
XmlDocument document = new XmlDocument();
document.Load(new StringReader(builder.ToString()));
// <tr>～</tr> を抽出し、その中の<td>～</td>で行を構成する
foreach ( XmlNode row in document.DocumentElement.GetElementsByTagName("tr") ) {
ListViewItem item = null;
bool first = true;
foreach (XmlNode node in row.ChildNodes) {
if (node.Name != "td") break;
if (first) item = new ListViewItem(node.InnerText)
else item.SubItems.Add(node.InnerText);
first = false;
}
if ( item != null ) lstTable.Items.Add(item);
}
// HTML中に"これでおしまい"を見つけたら終了。
if (selenium.IsTextPresent("これでおしまい")) break;
// さもなくば "こちら"が示すリンクに飛ぶ
selenium.Click("link=こちら");
selenium.WaitForPageToLoad("30000");
}
selenium.Stop();
}

よくわかる解説ぅ── アムダールの法則

επιστημη — Wed, 06 Jan 2010 11:59:00 GMT

ネタ元 → 性能向上は難しい──アムダールの法則

アムダールの法則(Amdahl's Law):

　性能向上 P = 1/(F+(1-F)/N)
　　F : 並列化できない部分の割合
　　N : コア数

なぜにこんな式が導き出せるかっちゅーとですね。
処理全体が10個のブロックでできてるとしましょう。
どのブロックも処理時間は同じってことで、
全体の処理時間は↓こんだけ。
□□□□□□□□□□

このうちF(たとえば4割)が並列化できない黒ブロックとすると
■■■■□□□□□□
ですね。全体が1なら■の割合がF, □の割合が(1-F)です。

んでもって□の部分(1-F)をN個のコアで分担します。N=2 なら
■■■■□□□
　　□□□
短くなった分早く終わる、つまり性能向上と。

この長さは ■部の長さ + □部の長さ = F + (1-F)/N
性能は処理時間の逆数だから
P = 1/(F+(1-F)/N)
っちゅーわけっす。

性能向上は難しい──アムダールの法則

επιστημη — Wed, 06 Jan 2010 10:17:00 GMT

Core2Duo/Quadとかi7とかPhenomとか、マルチコアCPUがアッタリマエになっちゃいました。
CPUクロックが頭打ちになっちまっただから数で稼ごうってわけすね。
水圧上げるのがキツくなればパイプ太くして水量増やすってゆー、わかりやすぅい♪
マルチコアでどんだけ性能上がるんや? の目安に「アムダールの法則」ちうのがあります。

アムダールの法則(Amdahl's Law):

　性能向上 P = 1/(F+(1-F)/N)
　　F : 並列化できない部分の割合
　　N : コア数

式を変形すると: P = N/((N-1)F+1) となります。
・F=0つまりアタマからケツまで並列化できれば P = N となり、
　コアの数だけ速くなる。そらそーだ。
・F=1つまり並列化できる部分がまったくなければ P = 1となり、
　コアをいくら積もうが無駄無駄ムダァ! と。

さらに上式をFについて解くと: F = (N-P)/((N-1)P) となります。
・dual-core: N =2 とおくと F = (2-P)/P
　スピード5割増を狙うなら F = (2-1.5)/1.5 = 1/3
　全体の7割以上が並列化されないと5割増は期待できんてことになります。
・quad-core:N=4ならば F = (4-P)/3P
　同じく5割増なら F = (4-1.5)/4.5 = 5/9。
　半分くらいは並列化できにゃならんですな。

んなわけで、並列化できない部分が多いといっくらコア積んでも
効果薄いてゆーアッタリマエの結果が導かれるわけっす。

性能阻害要因は"並列化できない部分"だけでなく、
メモリアクセス、コア間通信、粒度(スレッドのオーバヘッド)、負荷のバラツキ
なんかがあって、実際のパフォーマンスはさらに悪くなりますです。

※ 4月わんくま東京勉強会「数学Day」の伏線か?

毎度ありがとうございます

επιστημη — Fri, 01 Jan 2010 23:29:00 GMT

Fukuda Fumiki 様

おめでとうございます! このたび、2010 Microsoft® MVP アワードを受賞されましたことを、謹んでお知らせ致します。MVPアワードは、実用的で質の高い専門知識を他のユーザーとの間で積極的に共有している、優れたテクニカルコミュニティリーダーに贈られます。過去１年において、Visual C++コミュニティに大いに貢献していただきまして誠にありがとうございます。

ってなメールが届いたよっと♪

2004年からなんだかんだと毎年頂いて今年で７年目となります。
　SQLわからんちんでも
　WPFなにそれおいしいの? でも
　LINQてコンパイル後にかけるアレ? でも
MVP(マじめにヴぁかやれるプろぐらま)になれるんだよー

そゆわけで今年も一年、エラソーな顔してあちこち顔出しますんで、どぞご贔屓に。

今年もよろしくおながいしまつー

επιστημη — Fri, 01 Jan 2010 01:51:00 GMT

さてさて、2010年も残る一年となりましたが皆様いかがお過ごしでしょうか。

ウチのカミさんね、元旦には洗濯機を回さないの。
「服（福）を流す」のはゲンが悪いとかなんとか。
それってただのダジャレじゃーんとか思いつつ、
「コトバには魂が宿る」というのもまんざら悪くない思想です。
まじないとか呪文とか、言霊(ことだま)てやつですな。

わしらプログラマてーのは言葉の羅列に魂を宿らせるのを生業としとるわけです。
今年もまた「お?」と思わせるコードを書いていきたいものです。
んなわけで、よろしゅうおたのもうします。どうぞご贔屓に。

暮れも押し詰まりましてぇ…

επιστημη — Wed, 30 Dec 2009 18:56:00 GMT

絶賛お引越しちうなう。 Vista → Windows7（64ｱﾙﾁﾒ）のね。
# おぉ、軽い♪

いやー、とにかくめんどっちーのですわ。
ｲﾝｽｺせんならんもんがオニのようにようけあるもんで。

とりあえずOffice2010β突っ込んで通信経路(ﾒｰﾙ)確保。
その後ﾁｮｰｼぶっこいてVisual Studio 2010β2 押し込んでｱﾚいれてｺﾚいれて。

んで、ちょっと失敗したポい。VS2008のｲﾝｽｺに失敗しました。
2010β2を先に押し込んだのがいかんかったのかしら...

Vista残してある(dual-bootっす)からいいっちゃいいんだけど、
行き来するのがめんどっちーので、一旦更地に戻して再ｲﾝｽｺしよっかなー、
引き返すならいまのうちなのよねー

ウチのネットワーク事情

επιστημη — Thu, 24 Dec 2009 09:12:00 GMT

ネタ元 → うちのゲーム機事情

えーと、えぴ家では...
僕の部屋、クローゼットから屋根裏に繋がる穴ポコがあるんでそっから光ケーブルを引き込み、CATV信号に変換して屋内のTV線へ。
同時にCATVの光に相乗りしたcable-modem。そっからずるずるーときしめんみたいな平たいEtherで机横ちょのルータへ。

ルータのポートから僕のメイン機とﾊｺｻﾌﾞﾛｰ(RRoDなう)、およびﾃﾞﾑﾊﾟLANトランシーバ。

隣のカミさんとこではポンコツノート(すっげー旧いがWebとmailがありゃぢゅーぶんとのこと)にPCMCIAﾃﾞﾑﾊﾟcard。

向かいのボーズんとこはXP機に無線のボード、DSwireless-adapter。そしてWii。

8MbpsのCATV相乗り回線に
Vista/Win7機1, XP機2、Wii1、XBox1、(XP機経由で)DS2の
計7つがぶらさがってますねぇ。

[追記] わんくま「事情」祭り開催中なう。みなさま奮って御参加を♪

今年もおせわになりました

επιστημη — Tue, 22 Dec 2009 23:19:00 GMT

暮れのご挨拶にはちょっと早いけども。

今年の決算(?)報告書。
いままでCodeZineに載った僕の記事、2009年1月からのPageViewでございます。

No.	TITLE	PAGEVIEW	DATE
3864	ヒープソートのアルゴリズム	16554	2009/05/13
4035	C++0xの新機能「ラムダ式」を次期Visual Studioでいち早く試す	15481	2009/09/10
2886	マージ・ソート : 巨大データのソート法	15415	2008/08/13
1382	C++/CLIによるCライブラリの.NET化	15022	2007/06/19
1075	CUnitによるテスト駆動開発	14163	2007/03/13
2414	SQLiteで“おこづかいちょう”	12591	2008/05/14
2290	C/C++に対応した、もうひとつのUnitTestFramework─WinUnit	8109	2008/03/18
885	Cで実現する「ぷちオブジェクト指向」	7690	2007/02/14
1540	C# 1.1からC# 3.0まで～言語仕様の進化	5350	2007/08/06
1252	SQLiteで組み込みDB体験（2007年版）	4992	2007/05/07
4650	.NETでマンデルブロ集合を描く	4951	2009/12/10
1937	BoostでC++0xのライブラリ「TR1」を先取りしよう (1)	3746	2007/12/11
2664	STL/CLRツアーガイド	3232	2008/07/07
1967	BoostでC++0xのライブラリ「TR1」を先取りしよう (2)	2673	2008/01/07
2171	BoostでC++0xのライブラリ「TR1」を先取りしよう (5)	2233	2008/02/22
2158	BoostでC++0xのライブラリ「TR1」を先取りしよう (4)	1203	2008/02/12
2134	BoostでC++0xのライブラリ「TR1」を先取りしよう (3)	1109	2008/02/04

…おもしろいもんですな。ヒープソートを解説したやつが一番人気となりました。
上位に並ぶアーティクルはどれも毎月そこそこのPVをコンスタントに稼いでいます。
検索でひっかかってくんのかも。「定番の解説記事」として参照していただいているなら幸甚でございます。
気になるのが５位:CUnitネタ。CUnitネタは少ないからか、どっこいまだまだCは健在てことか。

てか今年書いたの少なっ! 来年はもちーと書きたいす。できることなら毎月でも。
んなわけで、ネタになりそなおもろいお話、たくさん聞かせてくださいましね。

とうとう出ちゃいました…

επιστημη — Sun, 20 Dec 2009 23:04:00 GMT

あー…ﾊｺｻﾌﾞﾛｰに恐れていた事態が。
遂にお出ましになりました、例の RRoDっす orz

これが出た場合、保証期間が二年延長され、三年となります。
バックパネルの製造年月日みると 2006-11 切れちょるやないけ!

電源落としてしばらくほっとけば何事もなかったかの如く快癒なさることも
ありますが、安心して遊べませんです。保証切れの修理っておいくらかかるんだべ。

HDがそろそろ詰まってきたんで買い替えてもいいかなーとか。
クリアデータの移行とか、できるんかしら?

マルチスレッドに向かないバブルソートを無理くり…

επιστημη — Sat, 19 Dec 2009 04:15:00 GMT

ネタ元 → Multi-Core と Multi-Thread
# わんくま同盟東京勉強会 #39 の復讐復習ね。

Jittaさんのゆーとーり、複数の処理が互いに依存している場合マルチスレッド化はできない…
てゆーか、一方が他方の処理終了を待ってなきゃいかんのでシングルスレッドと大差ないわけで、
マルチスレッドによる効果が薄くなるす。

お互いの処理が依存せず、つまり待ち合わせ(同期/排他)がなく、勝手気ままにオノレの道を
突き進むことができるなら、マルチスレッド化すればコアの数だけ同時実行できるから
そりゃ速くなるわな、と。

ソート対象となる配列を前半と後半に分け、それぞれをソートする分には互いに干渉せず
ぶん回れますわね。ほんでもって、ソートされた前半と後半をマージすりゃソート完了。
C++ と PPL(Parallel Patterns Library) でやってみまひょ。


#include <iostream>  // cout
#include <algorithm> // randum_shuffle, inplace_merge, etc.
#include <vector>    // vector
#include <ppl.h>     // parallel_invoke
#include <cassert>   // assert
#include <windows.h> // GetTickCount

using namespace std;
using namespace Concurrency;

// バブるソート
template<typename Iterator>
void bubble_sort(Iterator first, Iterator last) {
  Iterator lastSwapped = last;
  --lastSwapped;
  do {
    Iterator limit = lastSwapped;
    lastSwapped = first;
    for ( Iterator i = first; i != limit; ++i ) {
      if ( i[0] > i[1] ) { 
        iter_swap(i, i+1);
        lastSwapped = i;
      }
    }
  } while ( lastSwapped != first );
}

int main() {

  const int N = 10000;

  // 元ネタの準備
  int* src = new int[N];
  for ( int i = 0; i < N; ++i ) src[i] = i;
  random_shuffle(src, src+N);

  vector<int> data;
  // 整列してればtrueを返す関数オブジェクト
  auto in_order = [&]() { 
    return adjacent_find(data.begin(), data.end(), 
             [](int x, int y) { return x > y;}) == data.end();
  };

  { // ふつーにバブる
  data.assign(src,src+N);
  DWORD t = GetTickCount();
  bubble_sort(data.begin(), data.end());
  cout << "single: " << GetTickCount() - t << " [ms]\n";
  assert( in_order() ); // ソートできたかな?
  }

  { // 前半と後半を同時にバブり、しかるのちマージ
  data.assign(src,src+N);
  DWORD t = GetTickCount();
  // PPL使ってふたついっぺんに実行!
  parallel_invoke(
    [&](){ bubble_sort(data.begin(), data.begin()+N/2); },
    [&](){ bubble_sort(data.begin()+N/2, data.end()); }
  );
  // マージして一本にする
  inplace_merge(data.begin(), data.begin()+N/2, data.end());
  cout << "multi : " << GetTickCount() - t << " [ms]\n";
  assert( in_order() ); // ソートできたかな?
  }

  delete[] src;
  return 0;
}

実行結果:
single: 219 [ms]
multi : 93 [ms]
…ね♪

ActionとFunc

επιστημη — Thu, 17 Dec 2009 18:48:00 GMT

C++のばやい、voidを返すことができます。たとえば:

#include <iostream>
#include <functional>

namespace std { using namespace std::tr1; }

void f() { std::cout << "f()\n"; }
void g() { std::cout << "g() calls:"; return f(); } // ココ!

int main() {
  std::function<void(void)> function = g;
  function();
}

かたやC#では:

using System;

class Program {
  public static void f() { Console.WriteLine("f()"); }
  public static void g() { Console.Write("g() calls:"); return f();} // ココ!
  
  public static void Main() {
    g();
  }
}

error CS0127: 'Program.g()' は void 型を返すため、キーワード
return の後にオブジェクト式を指定することはできません。

しょぼーん。

Action<T> と Func<T,TResult> を統一的に扱いたく
# つまり戻り値voidでもFuncで済ましたくて

using System;

class Program {
  public static void Main() {
    Action<string> a = (s)=>{ Console.WriteLine("{0}ワールド",s); };
    a("ヘロー"); // ↓ココ!
    Func<string,typeof(void)> f = (s)=>{ Console.WriteLine("{0}ワールド",s); };
    f("なるほど ザ・");
  }
}

error CS1525: 'string' は無効です。
error CS1525: ',' は無効です。
error CS1002: ; が必要です。

お、おまえは何を言っているのだ!?
# typeof() って静的に解決できるんじゃないのぅ?