Version 13.01
アルゴリズム？

「今回からは【アルゴリズム】について説明していきます」
『アルゴリズムってよく聞くけど、具体的にはなんのこと？』
「うーん」
『うーん、って……』
「英語で algorithm 、簡単に言うと【計算方法】とか【処理方法】とかっ
て意味」
『？？？』
「たとえば〈文字コードを調べるアルゴリズム〉だったら」
『〈文字コードを調べる処理方法〉ってこと？』
「そういうこと」
『でもさ……じゃあプログラム＝アルゴリズム、ってならない？』
「そこが微妙なところかもね。プログラムとアルゴリズムを区別するとした
ら、アルゴリズムは〈多くのデータを処理する、汎用的な処理〉、ってとこ
ろかな」
『んー』
「たとえば、ボタンが押されたときの処理、とかは押されるたびに呼ばれて
実行されるだけだからアルゴリズムじゃないけど、リストボックスの中の
データをソートする、とかはアルゴリズム」
『そしたら、さっきの文字コードを調べるっていうのは？』
「文字列は文字の集まりでしょ」
『あ……』
「文字ひとつひとつをチェックしてコードを調べて、ってするから」
『そういうのがアルゴリズム……』
「でも曖昧な単語ってことにはかわりないから、あまりこだわらないで」
『ってゆーか自分でもよくわかってないだけじゃん』
「う”」
『で、具体的にアルゴリズムってどんなのなの？』
「そうだね、大まかに分けると次のような感じかな」

・計算
・チェック
・変換
・検索
・ソート

『具体的にゆーと？』
「計算は和とかを求めたり、難しいのだと方程式を解いたり」
『それはなんか科学っぽいね……』
「そういうのは実際の科学の話になるから今回はパス」
『チェック、ってチェックだよね』
「そう、さっきの文字コードもチェックのひとつ。データが正しいか間違っ
てるかを調べること」
『変換は、 atoi() とかのこと？』
「そう、あるデータを他のデータに変えること」
『検索は検索ね。ソートって並び替えのことだね』
「検索とソートはアルゴリズムの中でも一番大きな分野かな」
『そなの？』
「理由は〈よく使われるけど汎用的にできない〉からかな。たとえば 
Version 12.12 ( No.235 ) の次の構造体」

struct TEST_STRUCT_DOUBLE_2
{
    char m_ch;
    double m_d;
    char m_ch2;
};

「この構造体の配列があるとします」

    TEST_STRUCT_DOUBLE_2 stTEST_STRUCT_DOUBLE_2[3];

「これをソートするためには、 TEST_STRUCT_DOUBLE_2 用のソート関数を作
らなきゃいけないでしょ」
『そか、引数とかの型が違ったら、それごとに関数作らなきゃいけないん
だ』
「しかも、この構造体って m_ch 、 m_d 、 m_ch2 の３つの変数があるけ
ど、どの変数でソートするのか、っていう問題もあります」
『どの変数でソート、って？』
「たとえば……」

    stTEST_STRUCT_DOUBLE_2[0].m_ch = 1;
    stTEST_STRUCT_DOUBLE_2[0].m_d = 2.0;
    stTEST_STRUCT_DOUBLE_2[0].m_ch2 3;

    stTEST_STRUCT_DOUBLE_2[1].m_ch = 2;
    stTEST_STRUCT_DOUBLE_2[1].m_d = 1.0;
    stTEST_STRUCT_DOUBLE_2[1].m_ch2 3;

    stTEST_STRUCT_DOUBLE_2[2].m_ch = 3;
    stTEST_STRUCT_DOUBLE_2[2].m_d = 3.0;
    stTEST_STRUCT_DOUBLE_2[2].m_ch2 1;

「というデータの場合を考えてみます。さて」

stTEST_STRUCT_DOUBLE_2[0]
stTEST_STRUCT_DOUBLE_2[1]

「このふたつ、どっちが大きい？」
『え、大きい方？』
「そう。大きいか小さいかが決められないと、ソートできないから」
『そういえばそうだね、順番決められないもんね……え、でも、それって決
まんなくない？ m_ch で比較するのか……あ、そういうこと』
「そういうこと。変数が複数ある場合、どの変数で大小を決めるのか、って
いうのを考えなきゃいけないし、さらに、場合によっては〈全部足した数で
比較する〉、っていうこともあり得るでしょ」
『そか、そういえば……ってことは、比較方法って無数にあるじゃん』
「だから必要な比較方法ごとに関数が必要になるわけ」
『う”、面倒そう』
「ソートとかはプログラムごとに一から起こすことが多くて、そのために
色々な方法が多かったりする、ってところかな」
『なるほど』
「ただ、最近はこの問題は解決しつつあります」
『え？』
「まず、型の問題だけど、今は【テンプレート】っていうものがあって、こ
れを使うと色々な型をひとつの関数で処理できるようになります」
『へー、便利ねー』
「加えて〈比較する関数を取り替える〉方法が確立してきたから、比較方法
ごとに関数を作る必要がなくなったっていうのもあります」
『比較する関数を取り替える……？　そんなことできるの？　プログラムの
中で呼び出してる関数取り替えるようなもんでしょ』
「方法自体は実はいっぱいあるけど、今まで説明してきた範囲で例を挙げる
と Version 8.07 ( No.149 ) のウィンドウプロシージャやダイアログ
プロシージャみたいな感じ」
『あれってウィンドウのメッセージが送られてくるってゆーのでしょ？』
「それは置いておいて、ウィンドウプロシージャって、まず関数を登録し
て、イベントが発生するとその関数が呼ばれる、って仕組みでしょ」
『うん』
「同じように、ソートする関数に〈比較関数〉を登録して、比較するときに
その関数を呼んでもらって、その中で比較する、っていう形にすれば」
『比較方法を変えたいときには、別の比較関数を登録する！』
「そういうこと。ただ、これは一般的には使われてません」
『え？　そうなの？』
「理由はいくつかあって、ウィンドウプロシージャの時もそうだけど、型が
すごく危険なんだよね」
『そういえば WPARAM と LPARAM のキャストは怖いよね……』
「それに、関数ポインタもあまり使われていないし」
『関数ポインタ？』
「ウィンドウプロシージャを登録するとき」

    int iRet
        = DialogBox
            ( p_hInstance
            , MAKEINTRESOURCE( IDD_MAIN )
            , NULL
            , DialogProc
            );

「っていうように、関数の () を取ったものを渡したでしょ。こう、 () を
取った関数は〈関数のアドレス〉になるんです」
『あ、それが関数のポインタってわけね』
「そういうこと。この方法自体があまり広まってないかな」
『ってことは、今は違う方法？』
「が使われてます。でもその方法はちょっと難しいのと、今回のアルゴリズ
ムの話とは関係ないからしないことにします」
『あとでぐぐるからキーワードだけ教えて』
「そうだね〈関数オブジェクト〉とか〈プレディケート〉で検索してみて」
『……宣伝？』
「……最後に重要なこと。アルゴリズムでは早さが非常に重要になります」
『そりゃ、なんでもそうなんじゃないの？』
「もちろんそうなんだけど、アルゴリズムでは特に。たとえば」

    int iAry1[10000];
    int iAry2[10000];
    int iAry3[10000];

「という配列があって、この配列の中にランダムに数字が入っているとしま
す」
『すごい量になるね』
「さてここで」

・ iAry1 の中で、 iAry2 と iAry3 どちらにも含まれない数を表示する。

「という場合を考えてみて」
『んっと、 iAry1 の中からひとつ取りだして、それが iAry2 の中にあるか
調べて、また iAry1 から取り出して……』
「という形ですると、 10000 * 10000 * 10000 = 1000000000000 回チェッ
クする必要があります」
『かなり多い……のかな？』
「これを 1GHz の CPU で処理する場合。 1GHz をおおざっぱに計算すると 
1000 * 1000 * 1000 = 1000000000 、１回のチェックで 10 の処理が必要だ
とすれば、これを 10 で割って 100000000 、つまり１秒間に 100000000 回
チェックできます」
『ってことは 1000000000000 / 100000000 = 10000 ……げ、 2.8 時間？』
「そういうこと。普通のアプリじゃ〈動かない〉も同然でしょ」
『これじゃ意味ないね……』
「でも、今のは全部べたに検索した場合。もっと早くする方法があります」
『たとえば？』
「配列をソートしたりとか」
『ソート……あ、そうすれば全部見る必要ないよね、数が大きくなったらそ
れ以上のから探しても見つからないんだから』
「 iAry2 と iAry3 を先にくっつけておくとか」
『くっつける？』
「ひとつの配列にまとめて、同じ数はひとつだけ残すようにすれば、その分
検索量が減るでしょ」
『そういえば……』
「そして、そのひとつにまとめた配列をグループ化するとさらに早くなりま
す」
『グループ化……ってことは、それを何個かに分けるってこと？』
「そう、たとえばグループを 10000 ごとに分けて、チェックする数を、ま
ずどのグループに当てはまるのか調べて、それからそのグループの中だけで
チェックすれば」
『そうすれば他のグループは見なくて済む！』
「そういうこと。つまり、チェックする方法を変えることで、処理速度は大
きく変わるんです」
『だからアルゴリズムは処理速度が重要、ってわけね』

/*
    Preview Next Story!
*/
『なんか最近、先が見えない感じ』
「どうして？」
『具体例ってゆーか、ウィンドウをどうこうとかの方がわかりやすいかも』
「この１年は基礎的なことをずっとやってきたからね」
『で、来年もまた基礎的なのをする、と』
「というわけで次回」
＜ Version 13.02 アルゴリズム関数の基本 ＞
『につづく！』
「来年はさらに地味〜な方向に進むから」
『さらに！？』