日曜日にBCB!



Do It Yourselfでひとつプログラムでも作ってみませんか。


第2話「アルゴリズムが肝心」

かなり抽象的な話になってしまいますが、プログラムってなんでしょう。パソコンで使うアプリケーションだけがプログラムではありません。この世はプログラムが氾濫しています。勝手な予想ですが、全世界の人口よりもプログラムの総数の方がきっと多いでしょう。今のデジタル時計はプログラムで動いています。洗面台から出る水の浄水システムも巨大かつ沢山のプログラムで制御されています。冷蔵庫の温度管理もプログラムなら、テレビ放映もテレビビジョンもプログラム、電車の運行・電話サービス・ビルメンテナンス、パチンコの玉の管理に飲み屋の会計、パソコンのOSも当然ですがプログラムです。全てプログラムで動いています。プログラムとは何らかの入力に対して出力をするものです。そのプログラムはなんらかのアルゴリズムに基づいて動いています。私たちはプログラムなしでは生活できない時代に生きているし、プログラムはアルゴリズムなしでは動きません。別にプログラムって怖いものでもないし、プログラムが人間をコントロールしているわけでもありませんのでご安心を。プログラムは全て人間が作ったものです。プログラムのアルゴリズムも人間が考えたものです。

ではアルゴリズムとはなんでしょう。理論、手順、方法、これらを総称してアルゴリズムと呼んでもいいでしょう。学術的なものもあれば、単純極まりないものもあります。プログラムを勉強している人がプログラムを作れないのは、アルゴリズムを第一に考えないのが大きな原因です。つまり、パソコンでキーボードを打っていてもアルゴリズムはできないのです。

アルゴリズム概念 プログラムとは単純に言えば何らかの入力をして、これを処理し、出力をするものです。ユーザーに対する入力や出力は最新のGUI(グラフィカルユーザーインターフェース)で簡単に作れるようになりました。データベースの入出力もRDB(リレーショナルデータベース)で仕様がほぼ統一されています。周辺装置への入出力もSCSI、シリアル、USB、専用入出力と大抵は仕様がはっきりと決まっています。 アルゴリズムとはプログラムの表面に出てこないのでちょっとわかりにくものです。実は手順が決まったアルゴリズムが沢山あります。アルゴリズムだけの本なども沢山出版されていますので参考にされると良いでしょう。定石と呼ばれるアルゴリズムもありますし、プログラムのサンプルを見ると並べ替え等は良く知られているアルゴリズムですね。ではアルゴリズムを使ったらプログラムは作れるのでしょうか。答えはノーです。

アルゴリズムとは「データの流れ」なのです。ですからプログラムを作るとき、まずデータをどのようにプログラム全体に流すかを考える必要があります。これがアルゴリズムを考える作業なのです。

アルゴリズムは互いに関連し合ったり、階層的な構造になることもあります。できるだけ汎用的なアルゴリズムを使って、データの流れを明確にする。これがよいプログラムを作る最も近道です。ここで「よい」プログラムとは、
を指します。


プログラムを複雑にする犯人

プログラムとは何かと複雑になるものです。一体誰がプログラムを複雑にする犯人なのでしょうか? それは「データ」です。ここで言うデータとは内容が変化するものつまり変数を示します。例えば次のようなプログラムを考えてみます。
    printf("これは10,000行のメッセージを標準出力するプログラムです\n");
    printf("プログラムは合計10,000回の標準出力関数が続きます\n");
    printf("このプログラムはMS-DOSプロンプトで動きます\n");
    printf("ちょっとプログラムをご存知の方ならば、\n");
    printf("このようなプログラムが意味がないことは直ぐにわかると思います\n");
    printf("単なるサンプルですからお許しを\n");
                 :
    printf("あと2行です\n");
    printf("あと1行です\n");
    printf("やっと終わりました。ちゃんちゃん\n");
このようなプログラムであればいくら長くったって誰でもわかります。変化するデータ(変数)がないからです。ここで変数が多いとプログラムの作成、保守は大変になります。変数を少なくする技法はこれまでいろいろと考えられてきました。
  1. データのローカル化
    データをプログラム全体から見れる(グローバル)のではなく、処理モジュールの中でのみ有効にする(ローカル)。FORTRANでは比較的初期の段階から導入されました。BASICでは文法の基本規定にはこの考えはありません。Visual BASICにはあります。
  2. データの構造化
    Pascalでレコードとして登場しました。Pascalと言えば構造化言語として手続きが構造化されましたが、実はデータの構造化の方が画期的な試みでした。数値や文字列などの基本型をまとめて構造化し、抽象化してわかりやすくする。非常に有効な手法です。
  3. データの抽象化
    FORTRAN、BASIC、Pascalと変数を少なくすることは徐々に進みました。しかしまだまだ十分ではありません。実世界をモデリングする時に問題になるのが「データとデータの関連」の表現でした。C言語ではポインタの概念が導入され、データとデータの関連性を簡単に表現できるようになりました(ポインタは実は非常にアセンブラに近い考え方ですが)。これでリスト構造が表現できるようになり、さまざまなデータをより抽象的に柔軟に表現できるようになりました。
  4. データのオブジェクト化
    C++言語ではC言語にオブジェクト指向が導入されました。これはデータを構造化し、これに手続きを一体化する考え方です。これをオブジェクトと言います。まずデータあり、次に手続きありと、これまでの言語の考え方とは一線をなす概念です。データが隠蔽され必要な手続きからのみデータをアクセスできるように保護できたり、オブジェクトの特性(クラス)を継承して機能を拡張できたりといろいろ便利です。BCBはこのオブジェクト指向のC++言語です。なお、Delphiはオブジェクト指向Pascal言語です。
私の作るプログラムにはポインタが沢山出てきます。C言語で行き詰まる人の多くはこの「ポインタ」が原因のようです。ポインタとは「データを指し示す」ものです。これは「データを重複させない」、「データの関連性を最も簡単に表現する」のにとても有効な手法です。もしポインタがわからないのであれば是非データ構造やアルゴリズムの本を読んで、基本的な内容は理解してください。オブジェクト指向よりもデータ構造手法を会得するのが大切です。

難しいことを実現するには、 のどちらかです。複雑に組合せていくと.... 一度絡んだ糸はなかなか解けませんよ。


DDTプログラムのアルゴリズム

具体的に私がDigital Design Technologyで公開しているソフトのアルゴリズムを簡単に紹介しましょう。
ZipFinder ZipFinderは郵便番号データが命です。郵政省のYOUNETで公開されているCSV形式の郵便番号テキストデータを使用します。ただ、このデータは10Mを超える巨大なものですし、高速に郵便番号を検索するには不向きです。そこでZipFinder同梱のZipDBで専用形式に変換しています。中身はファイルポインタチェーンとリスト構造の塊です。本来ならリレーショナルデータベースを組むほうがメンテナンスは良いかもしれませんし、実際MS-ACCESSでデータベース化して郵便番号検索しているソフトもあります。欠点としては検索速度が遅いのとデータが大きいことでしょう。 ZipFinderのファイル形式は結構古典的で、メンテナンス性やデータ独立性はよくありません。しかし、郵便番号データ自身が一括更新されるのと、専用のデータベースアクセスライブラリが不要なのが長所です。実は私自身がリレーショナルデータベースを扱ったことがないのが本当の理由です。ちなみに本人の名誉のために言いますが私はオブジェクト指向データベースをやってました。こちらのほうがC++言語との親和性は高いのです。でも何故か流行らないなあ。
ZipFinderは専用データベースを最小のアクセスで高速に郵便番号検索します。データ構造は都道府県→市区町村→町域の順番で検索する階層検索で最もパフォーマンスを発揮する構造です。キーワード検索はあまり早くありませんが、実用に耐える速度だと思います。
また、キーワード検索ではスレッド操作も行っています。検索と同時にユーザーからの中断をスムーズに受け付けるにはWindowsのマルチスレッド機能を生かすのが得策です。小難しいアルゴリズムを自分で考えるよりは、確立したアルゴリズムを使うほうが確実に早道です。他人の考えたアルゴリズムを活かすのもプログラムを作るには重要です。

異体字転 異体字転では異体字間の循環リストと再帰呼出しを使っています。循環リストとはリスト構造の一種でリンクチェーンとも言います。C++言語ですから当然ポインタを使います。折角のC言語系ですからBASICやFORTRANにはない(最近はイビツな形でもあるかもしれませんが)柔軟なデータ構造を活用してます。循環リストと再帰呼出しを使うことにより、最小のデータアクセスで高速に全ての異体字の組合せをリストアップします。加えて漢字・コード分類表示と言う結構重い処理を同時に行っても実用速度が保たれているのです。漢字・コード分類表示はWindowsのリッチエディットコントロールを行っています。残念ながらBCBのVCL(Visual Components Library)は処理速度が非常に遅いのでWindowsのAPIを直接使っています。
異体字転は元々ZipFinderのあいまい検索用に作ったクラスの活用アプリケーションです。異体字クラスと言うのを作り、ZipFinderでも使っています。これにGUIをかぶせたのが異体字転ですから、まさしく「まずはアルゴリズム」の言葉どおりのプログラムです。

TipCal TipCalは比較的難しい「数式処理」を行っています。これもリスト構造の一種の2分岐リストを採用しています。これにレキシカルアナライザーと呼ばれる字句解析アルゴリズム、解析したトークンと処理モードから次の処理を決定するイベントマトリックス、実際の計算をする再帰呼出し。TipCalはアルゴリズムだらけです。数式処理をさらに複雑にしているのが、数式のあいまいさです。例えば入力された数値文字列がただしい形式かどうかだけでも判定関数が必要となります。また、単なる文字列を数値に変換するのですが、コンピュータと言うのは取り扱える数値の範囲や精度に限界があります。この限界を超えたときのエラー処理等も必要になります。
さらに単なる演算処理だけではそこらへんの電卓プログラムと何ら変わりがありません。TipCalの数式処理エンジンはDML1仕様という動的数値関数ライブラリ接続に対応するようにプログラムしました。こちらは逆に特筆するようなアルゴリズムは使っていませんが、DLLの動的接続やDML1の仕様設計があります。

DMBasic DMBasicでは個々の関数でいろいろなアルゴリズムを使っています。大抵はC++言語(C言語)のランタイムライブラリを呼び出せば済むのですが、値によっては例外エラーを発生するものもあります。C++言語の例外処理に任せようと思ったのですが、OSによって挙動が違うという変な仕様に振り回されたため自前で事前チェックをふんだんに入れています。ここらへんは全くの数値計算アルゴリズムです。なお、シェアウェアプロテクトのアルゴリズムも入っていますが、それはヒ・ミ・ツです。

ドクターUnits ドクターUnitsはTipCalと同じ数式処理を行っています。数式処理はクラスライブラリ化しているので、TipCalと共通に使えます。ドクターUnitsでは換算元式の計算、換算元値→基準単位への計算、基準単位→換算値の計算と1回の換算で3回の数式処理を行っています。それ以外はさしたアルゴリズムはありません。強いて言えば単位換算テーブルをどのように流すかです。
ドクターUnitsに限らず多くのアプリケーションでも大変になるのが「編集」作業に対するプログラミングです。ドクターUnitsでは単位換算テーブルの専用編集画面があります。こちらはアルゴリズムと言うほどのものはありませんが、いろいろなユーザー入力に対応するためかなり処理が複雑になっています。プログラムの複雑さはプログラムの自由度が多くなるとねずみ算的に増していきます。そのためにWindowsのウィンドウ概念があるのですが、それでも複雑さはなかなか減りません。複雑さが増すとバグも増えるので、テストと修正の繰り返しになります。この複雑さを一掃するアルゴリズム、どなたか知りませんか?

上記全てのアプリケーションに共通して言えることは、BCBのVCLを活用しています。まさしくオブジェクト指向の恩恵を十二分に受けています。オブジェクト指向とはデータと手続きを一体化し、データ自身にその振る舞いをもたせる概念です。オブジェクトとは「自分がどのように振舞うかを知っているデータ」の意味です。VCLではウィンド一つ一つがデータであり、そのなかにWindowsのイベントドリブンの振る舞いを記述できます。またボタンやエディット、リスト等も全てオブジェクトになっていて、かつ手続きが共通化されています。これはVCLだけではなくWindowsのAPIそのものもオブジェクト指向だから実現できるものです。そしてオブジェクトを生成するクラスが継承関係をもつことができるので、同じような手続きを何度も記述する必要がありません。いわゆる「差分プログラミング」ができるます。これによってGUIが簡単に作れるわけです。でも、先ほど述べたようにアプリケーションの自由度はねずみ算的に増えていくので、「ねずみごっこ」ならぬ「イタチごっこ」が際限なく繰り返されるのがプログラミングの世界です。


さて、 ぐだぐだとアルゴリズムの話をしました。では、肝心の「寿印のファイル分割アクセサリ」のアルゴリズムはどうなるのでしょうか。その前に「寿印のファイル分割アクセサリ」では名前が長いので省略して「寿分割」としておきます。
寿分割のアルゴリズムは非常に単純です。分割もとのファイルを一定の大きさに分割し、それぞれファイルに吐き出します。最後にこれらを結合するバッチコマンド文字列を作成し、結合バッチファイルに書き込みます。アルゴリズムを記述する手法はいくつかあります。フローチャート、PAD図、自然言語がありますが、個人的な趣味でPAD図でこのアルゴリズムを書いてみましょう。

PAD図

たったこれだけの処理です。C++言語(C言語)で書くと、
char *buffer = new char [分割サイズ];               // 分割バッファ準備
FILE *SrcFP = fopen(分割元ファイル名, "rb");        // 分割元ファイル読込みオープン 

for (int i=0;i<分割数;i++){                              // 分割数繰り返し
    fread(buffer, FileSize, 1, SrcFP);                  // 分割元から分割サイズ分読込み
    FILE *DstFP = fopen(分割先ファイル, "wb");           // 分割先ファイル作成オープン
    fwrite(buffer, FileSize, 1, DstFP);                 // 分割先へ分割サイズ分書込み
    fclose(DstFP);                                      // 分割先ファイルクローズ
}
fclose(SrcFP);                                     // 分割元ファイルクローズ

結合バッチコマンド作成;
FILE *DstFP = fopen(結合バッチファイル, "wb");      // 結合バッチファイル作成オープン
fwrite(buffer, strlen(結合バッチコマンド), 1, DstFP);    // 結合バッチコマンド書込み
fclose(DstFP);                                    // 結合バッチファイルクローズ

delete buffer;                                    // 分割バッファ開放
となります。漢字の部分は処理や変数等が入ります。エラー処理はまだ入れていません。簡単でしょ。

プログラムの卵構造また本論から逸れてしまいますが、プログラムというのは卵のような構造です。アルゴリズムは卵の核です。鶏の卵だと核は爪の先ほどでしょうか。黄身はデータの準備や後処理、数値計算の世界ではプリポスト処理と呼ばれるものです。白身は外部とのインタフェースです。外部とのインターフェースにはユーザーインターフェースや周辺機インターフェース、データベースインターフェース、エラー処理が含まれます。殻はプログラムの顔(画面)です。全てがしっかりしていないと可愛い雛は生まれません。黄身と白身と核で雛の核を守っている、プログラムもこれに似ています。


次回は画面を作成します。これが一番楽しいかもしれません。ご期待ください。


目次に戻る目次に戻る トップに戻るトップに戻る