場合 - みる会図書館


検索対象: 月刊 C MAGAZINE 1990年4月号
95件見つかりました。

1. 月刊 C MAGAZINE 1990年4月号

五ロ く第 5 回〉 キーポー圦カプログの作成 ( 1 ) 高橋良明 と次回の 2 回にわたって , 前回作成した関 前回は , 画面上の任意の場所にテータを 数を利用して , キーボード入力プログラ 表示する関数をはじめ , いろいろなテキ ムを作成します。 スト画面表示関数を作成しました。今回 ライプラリのキー入力関数は , 挿入 / 削 除 , 上書きなど細かい仕様になっていませ ん。そこて , 今回作成するキーボ、一ド入力 関数の仕様は , 次のようにしました。 キー入力関数の基本仕様 ( 1 ) 画面上の任意の場所で入力する 前回作成した , カーソルのポジショニ ング関数 , 画面表示関数を利用すること て、実現て、きます。 一部のキーコード なお , すべてをプログラムて、制御する は内部で処理する ため , 1 文字入力関数はエコーなしの関数 ( [ で 0 社〕など ) (MS-DOS て、は , getch) を使用します。 これは , DOS のファンクションを呼び出 す関数を自作してもかまいません。 ( 2 ) 漢字の入力ができること とくに , 全角文字のデータを上書きす かを判別することて、 , 対応て、きます。 る場合や挿入 / 削除する際の扱いがポイン 漢字は 2 バイトコードて、す。そのため , ( 4 ) 挿入 / 上書きモード切り換え ANK ( 1 バイトコード ) を入力するときと トとなります。 亠キーを押すことて、 , 挿入モード / こて、は , 文字列データの任意の 1 バイ は , 別な処理を行います。 上書きモードの切り換えを行います。挿 幸い , 漢字の第 1 バイトコードと ANK トが ANK なのか全角文字の 1 バイトなの 入の場合には入力域内に挿入てきる余地 の文字コードとは区別て、きるのて、 , 1 バイ Fig. 2 ESC コードで始まるキーテータの入力 ト入力があった時点て ANK と漢字の処理 を分けます。 亠を押す ( 3 ) 漢字の処理ができること ・・・ 0X1b55 が入力されてくる ~ を押して , 続いて回を押す・ ・・・ 0X1b55 が入力されてくる 入力データ中 ( バッフアの中 ) に , ANK ↓ このため , 0xIb が入力された時点では , 押されたキーがなのか ~ なのかが判断できない ( 1 バイトコードの英字 , 数字 , カナ ) と全 角文字が混在するのて , そのカーソルと ポインタの処理を行います。 110 CMAGAZINE 19 4 Fig. 1 キー入力の模式図 通常の場合 日本語 FEP が動作している場合 キー入力 ↓ BlOS(Basic I/O System) ↓ハードウェア独自のキーコードを返す ↓ 日本語 FEP OS ↓ OS / 日本語の文字コードを生成して返す ↓ コマンドインタブリタ / アプリケーション 一部のキーコードは 内部で処理する ( [ 変キーなど )

2. 月刊 C MAGAZINE 1990年4月号

ライフホート 0 「 m 面 on from (ompiler Ma 「 5 Lattice C 0 警告メッセージ、 w 。。。 ig : cannot open library s \ . lib. ″が出て , リンクできないので すが , どうしてですか ? A コンパイラはオプジェクトコ ードを生成するとき , デフォルト のライプラリ名をオプジェクトフ ァイルに出力します。このデフォ ルトのライプラリ名は , Lattice C のインストールプログラムによっ て作成されるツリー構造になって いることを前提としています (Fig. 1 参照 ) 。しかし , インストー ルプログラムを使わないて、 , ライ プラリをそのままフロッピーディ スクからコピーして使用している 場合て、も , コンパイラはオプジェ クトファイルにメモリモデルに対 応したディレクトリ名を頭につけ たライプラリ名を出力しています。 リンカは , コマンド引数や応答フ ァイルて、指定されているライプラ リを最初に探しにいきますが , そ の中て見つからないシンポルがあ る場合 ( タイプミスて , 関数名がま ちがっている場合など ) , デフォル トのライプラリを探しにいくため に *VVarnig : cannot open library s \ lc. lib. クが表示されるこ とになります。これを防ぐには , ①コンパイル時に一 1 オプションを 指定してデフォルトライプラリ 名をオプジェクトファイルに出 力しないようにする。 ②リンカオプション / NODE FAULTLIBRARY を指定し 0 &A て , デフォルトライプラリを探 しにいかないようにする。 ③ファイル構成を Fig. 1 のようにし て , デフォルトライプラリ名を 使用する。 以上 , 3 つの方法があります。な お , デフォルトライプラリを使用 する場合には , 環境変数 LC と LIB に各メモリモデルのディレクトリ の親ディレクトリバス名をセット しておく必要があります。 *Error 3 : ″が出て , イルできません。 0 コン′ 、、 Error 3 : クは , 指定された インクルードファイルが見つから ないというエラーて、す。この場合 , ふたつの可能性があります。 ①入力したファイル名がまちがっ ている。 ②インクルードのネストが深すぎ まず , ①の場合は , プログラム 中の # include 文の引数がまちがっ Fig. 1 Lattice C ティレクトリ構造 ルートティレクトリ LC A ているか , インクルードファイル を作成するときに , 工デイタに指 定するファイル名を打ちまちがえ たかて、す。②の場合 , Lattice C< は , 最大 16 レベルのネストが可能 なようにコンパイラは作られてい ますが , MS-DOS て、は , 同時にオ ープンて、きるファイル数が最大 20 個に限定されているのて、 , 実際に は , 13 レベルまて、になってしまい ます ( コンソール入出力などて、 5 個 , . C のソースファイルて 1 個 , コ ンパイラのワークファイルて、 1 個の ファイルを使っているため ) 。ま た , CONFIG. SYS ファイルて FILES を指定していなかったり , 20 より小さい値を指定していると , のメッセージが表示されます。② んくインクルードファイル名 > 〃 いて , ファイルが見つかりませ ①の場合は , *Error 3 : クに続 のエラーは出なくなります。 FILES を 20 に指定することて、 , CONFIG. SYS ファイルの中の くなります。ネストを浅くするか , ネストて、きるレベルはさらに小さ されません。なぜならば , オープ ンファイル数の制限により , 工ラ ーメッセージファイルを開くこと がてきないからて、す。 0 フィル名の検索をサプディ レクトリの中まで行っていきたい のですが , dfind, dnext 関数は再 ( 付録ディスク収載の List1 参照 ) 。 どこかに退避する必要があります い場合には , API DTA の内容を ん。どうしても再帰的に使用した 本的には再帰的には使用て、きませ API DTA を初期化しますから , 基 使用しています。 dfind 関数は AP 工 DTA を仮想的な DTA として Ver. 4.1 て、は , グローノヾル変数 DTA< 行います。 Lattice C/DOS -DOS とのデータのやり取りを EH,4FH を使用しているのて、 , MS DOS ファンクションコールの 4 dfind, dnext 関数は , MS ー A 帰的に使用できますか ? の場合は , このメッセージが表示 lnformation from CompiIer Makers 153 ( L モテル用オプジェクトモジュールとライプラリ ) L ティレクトリ ( D モテル用オプジェクトモジュールとライプラリ ) D ティレクトリ ( P モテル用オプジェクトモジュールとライプラリ ) P ディレクトリ ( S モテル用オプジェクトモジュールとライプラリ ) S ティレクトリ (. EXE ファイルや . H ファイル )

3. 月刊 C MAGAZINE 1990年4月号

一目瞭然て、す ) 。必要に応じて cprintf() を 使用すべきて、しよう。ただし , リダイレク ションが使用てきなくなる , ほかの 0 S へ の移植性が低くなる , という欠点がありま す。 ーどう最適化するか まずハードウェアの制限を避ける対策を リストしましよう。 プロセッサ / メモリ プロセッサ / メモリのスピードに関して , プログラマがて、きることは , 実行するイン ストラクションの数を少なくしたり , 別の 効率のよいインストラクションを使って高 速化を図ることくらいて、しよう。 V25 などの チップを使う組み込みシステムのプログラ マはバンクごとのウェイトステートの設定 が可能て、す。 インタラクテイプデパイス キーポード入力 ( インタラクテイプデバイ ス ) は通常 , 人間の入力時間のほうがはるか に遅く , あまり問題にはなりません。しか し , 一部のソフトて、は 1 文字入力ごとになん らかの処理を行っている ( FEP などは好例 ) ために , その時間が人間の入力インタバル より長く不自然に感じる場合があります。 ディスクのキャッシュ ディスクキャッシュの影響に関しても 「 lnside! 」ははっきりしたスピードの違い を見せてくれます。とくに「 lnside! 」は DOS のアクセスごとに最大値 , 最小値をレポー トしますから , ヒットしたデータとそうて ないデータとのアクセス時間が明確になり ます。 コーノレ / リターンの オーバーヘッドを避ける ある関数 (funcl( ) ) が複数の関数 ( Ca111 ( ) , Ca112 ( ) , Ca115 ( ) ) からコールされている が , 実行回数が多く時間もかかっている場 合には , funcl( ) を Ca111 ( ) , Ca112 ( ) , Ca115 ( ) ! のどれか ( ひとつまたは複数 ) にインライン 展開すればコール / リターンのオーバーヘッ ドを回避て、きます。 問題は , funcl( ) をコールしたときにも っとも時間のかかる関数がわからないかぎ り , 3 つの関数のどこにインライン化するこ とが効果的なのかわかりません。もちろん すべての関数内へインライン化してもよい のて、すが , コールしている関数の数が増え るにしたがってコードサイズが膨らんて、し まいます。 この場合は「 lnside! 」の関数コール解析 を使って funcl ( ) をコールしている関数ごと に funcl ( ) の実行回数 / 時間を計測し , 多く の時間を消費している関数を探しあてて , その関数内に funcl( ) をインライン化しま す。もちろんインライン化によってコード が散らばるため , メンテナンスの負担が増 えることになります。この点も考慮に入れ てインライン化すべきかどうかを決定して ください アセンプラ化 コール / リターンのオーバーヘッドてはな く , 関数内て、時間がかかっている場合には ( 「 lnside! 」のイベントタイミング解析て、関 数の最初から最後まてを指定して計測して みてください ) , この関数自身を ( アセンプ ラ化などによって ) 高速化するか , アルゴリ ズムの変更を含めて , グローバルな視点か ら大幅な変更をする以外に手はありません。 関数内部の時間計測にはソース行タイミン グ解析が役に立ちます ( 「 lnside! 」の—lt オプ ション ) 。 ーレジスタ宣言 変数のレジスタ割り付けはコンパイラに 任せておけばよいのて、すが , 自動的にコン ンパイラが最適に割り付けるのは事実上不 可能て、す。なぜならある変数のアクセス回 数は関数へのパラメータやデータに依存す るからて、す。実行時のダイナミックな結果 を見る以外に手はありません。まずレジス タ宣言をもっともアクセス回数の多いと思 われる変数へ割り付け , 関数のスビードを 計測してみてください ループて、の例を見てみましよう。小さな ループて、はループカウンタ ( 普通 i , j などの 変数名 ) へのレジスタ宣言は効果があります が , ループ内部て、の処理が増えるにしたが って相対的な効果が減っていきます。ルー プカウンタへの割り付けがあまり効果的て、 ないと判断したら , 次にループ内部て、もっ ともアクセスの頻繁な変数へ割り付けます。 この割り付けを変えて繰り返してみてくだ 忘れてならないのはレジスタ割り付け可 能な数は各コンパイラて、違う点て、す。宣言 を行っただけて、割り付けられたと思ったら 大まちがいてす。 また繰り返しになりますが , このような 最適化の効果は全体の実行時間を見てもわ かりません。マイクロ秒単位の変化を計測 しなければなりません。 ポインタ宣言 ポインタ宣言するにはいくつか理由があ ります。データへのアクセスがポインタを 使ったほうが自然な ( パラメータをポインタ て受け取った ) 場合や , やりやすい場合 , ま たはサプスクリプションを使った場合より も高速化したい場合などてす。ポインタ割 り付けには ( レジスタ割り付けのように ) 数 の制限はありませんから自由にポインタ宣 言を行い「 lnside! 」て結果を比較してくだ パラメータて渡された値を一度ポインタ Conference Room 137

4. 月刊 C MAGAZINE 1990年4月号

コンヾイラ の内部を詳解 LAND, op LOR というノードになりま す。これらの演算子は , オプジェクトコー ド中て、は比較命令 ( CMP 命令 ) と条件分岐 命令の組み合わせに展開されます。 比較・論理演算子を処理する関数は , genbool( ) , gencompare( ) , gencond jump( ) の 3 って、す ( List5 ) 。このうち , gen b001 ( ) が外部から呼び出される関数て、 , 残 りのふたつは下請けの関数て、す。まず ,gen b001 ( ) から説明しましよう。 genbool( ) は 3 つのパラメータを受け取り ます。第 1 パラメータは式の木へのポインタ て、 , ノードは op BOOL,OP LAND,OP BOOL のいずれかて、なければなりません ( と いうより , プログラムが正しければ , この いずれかになるはずて、す ) 。第 2 パラメータ は式を評価した結果が真だったときにジャ ンプするラベル番号 , 第 3 パラメータは偽だ ったときにジャンプするラベル番号て、す。 ラベル番号として 0 を渡すと , ジャンプする かわりに下に抜けるコードを生成します。 たとえば , genbool(), 10 , 0 ) ; とすると , 「式 e を評価して , 真だったら、、 @ 10 〃 このように , 「副作用のみが必要とされる 式が文として使われるときて、す。このよう というラベルにジャンプし , 偽だったらそ 場合には , 最適化したコードを出力する」と な場合には , genexp( ) のかわりに genex のまま下に抜ける」というコードを生成し いう方法は , ほかの演算子にも応用するこ ptop( ) を呼び出します。 genexptop( ) は , とがて、きます。このような演算子には代入 List4 のようになっており , 代入演算子とイ Fig. 1 論理演算子のコード生成 演算子 ( 十 = , / = など ) と , インクリメント / ンクリメント / デクリメント演算子を別扱い ( 1 ) A & & B ー ) がありま するようになっています。その他の演算子 デクリメント演算子 ( 十十 , す。代入演算子は genassignop( ) と genas の場合には ,genexp( ) を呼んて、従来どおり if A が偽 then 90t0 F signopref( ) て、処理されます。前者はオペラ の処理を行います。 if B か偽 then goto F ンドが数値て、ある場合 , 後者はオペランド goto T 比較演算子と論理演算子 がポインタて、ある場合を処理します。イン クリメント / デクリメント演算子は , 副作用 のみが必要な場合には genincdectop( ) , 式 前回に説明しましたように , Cm コンパイ の値も必要となる場合には genincdec( ) て、 ラの内部て、は比較演算 , 論理演算の結果を 処理されます。これらの関数は , パラメー 表す型として b001 型を導入しています。比 タとして , 木構造へのポインタのほかに , 較演算子 ( = 式の値が必要とされているかを示すフラグ 理否定演算子 ( ! ) は正規化され , op BOOL を受け取るようになっています。 というノードて表現されます。また , 論理 演算子の副作用のみが必要とされるのは , AND 演算子と論理 OR 演算子は , それぞれ op List 3 genexp(left->e_left) ; if (i sConst (right) & & ! needValue) gencode ("YtmovYt%oCbx] , %dYn" else { pushbx() : genexp(right) : popdi ( ) : gencode ("YtmovYt[di] , %rYn" ・ 4 戸 0 《 0 行ー 8 0 》 0 1 よっ 0 っ 0 -4 11 、 1 1 よ 11 1 人 11 っ 0 っ乙っ 0 っ 0 っ 0 right->e value) : p->optype, p->optype) : 関数 genexptop( ) 1 : / * genexptop generate COde for expression (with some optimization for top level) 3 : public void genexptop(EXPR *p) = NU しい 5 : 6 : switch (p->opcode) { 7 : Case op-ASSIGN: 8 : genass ign(), (O) : / * we only need side effect * / 9 : Case op-ASSIGN_0P: genassignop(), (O) : / * we only need side effect * / Case OP-ASSIGN-OP_R: genass ignopRef (), (O) : / * we only need side effect * / Case op-PREINC or op_POSTINC or op_PREDEC or 叩 _POSTDEC: 14 : genincdectop (P) : / * we only need side effect * / Default: genexp (p) : 18 : } List 4 return; ( 2 ) A ロ B if A が真 then goto T if B が真 then goto T goto F ※ T は真のときの飛び先 . F は偽のときの飛び先 yacc による C コンバイラブログラミング 79

5. 月刊 C MAGAZINE 1990年4月号

emental String 5e0 代 h in ( コーディングの詳細 26 CMAGAZINE 19 4 インデクス範囲が返されます。 ( いずれも整数へのポインタ ) に , arr [ ] の合致した の合致を見つけると , 形式引数 ptr start と ptr end ルーチンが , 探索文字列に対するひとつまたは複数 に参照て、きる最初の最大インデクスて、す。この探索 元配列へのポインタて、あり , 整数 imax は arr を安全 ptr end)" となっています。ここて、 arr は文字の 2 次 ヘッダは , 、 \int inc search(arr, imax, ptr start, inc search( ) が実際の探索をします。この関数の 戻り値は O て、す。 す。 get range( ) が合致を見つけなかったら , その クスの範囲を引数リストを介してコール側に渡しま と , その値を返すとともに , それに対応するインデ ことがて、きません。 get range( ) が合致を発見する からなければ , ソートずみの配列を正しく探索する 大インデクスを知らなければなりません。それがわ た理由により get range( ) は , 配列の参照て、きる最 が入力文字と合致する項目を探します。前節て、述べ get range( ) は文字列の配列中に , 冒頭の数文字 字列全体との合致を求めよ , という意味になるのて、す。 れた文字から成る部分文字列て、はなく , ひとつの文 列終端子の O と等しいことになり , それまて、に入力さ ひとつの文字列全体を指定するのて、 , 値 0 は C の文字 単純て、す。引用符は ( 文字列の前後を囲むことにより ) は値 0 を返します。この特別な戻り値を選んだ理由は 入力されると , そのキーはエコーされずに , getkey ( ) ョンマークまたはダブルクオーテーションマークが 例外がいくつかあります。シングルクオーテーシ key( ) は , 押されたキーの ASCII コードを返します。 を何て、も読んて、画面にエコーします。その場合 get ンも含む , キーポードから入力された表示可能文字 します。 getkey( ) は基本的には , キャリッジリター らの関数の定義と必要な補助的コードを , List2 に示 かのふたつの関数を使って探索を実行します。これ ス範囲を判定します。 3 つ目の inc search( ) は , ほ は , 文字列の配列中の入力文字に合致するインデク は , 単純なキーポードフィルタて、す。次の get range( ) な関数は , わずか 3 つだけて、す。最初の getkey( ) 漸進的文字列探索をインプリメントするのに必要 inc search( ) はまず , 合致インデクス範囲を探索 配列 arr の全配列インデクスへとセットします。これ によって , ユーザが 1 文字も入力せずにキーを押し た場合には , 「すべての項目が合致している」という 正しい結果を関数は返せます。また , 配列の探索開 始位置を表す変数て、ある base の値を , arr へと初期 化します。 次に , inc search( ) は getkey( ) をコールして , 入力文字を取得します。この文字が、、 ESC" や以 外だと , それは get range( ) に渡され , get range( ) は文字との合致が見つかったか否かを報告します。 合致が見つからないか , または見つかった合致がた だひとつの場合は , 探索は終了します。これ以外の 可能性は , 合致が配列中の複数の項目に存在すると いう場合て、す。その場合 , first と last に合致するイ ンデクス範囲がセットされます。そして配列ポイン タ base を , base[first] の第 2 の文字をポイントす るよう更新します。 C て、は , これは , base = &baseCfirst] [ 1 ] ; という文により , 容易に実現て、きます。 このようにして探索の起点を移動した後て、 , 同じ 処理サイクルを再び開始します。すなわち入力文字 を求め , 合致を調べ , その結果に従って配列ポイン タを更新します。処理は最終的に , 探索成功 , 失敗 , またはアボ、一トて、終わります。 こて、ご紹介した inc search( ) の実行効率は , 配 列のサイズがあまり大きくなければ十分て、す。しか し項目数が数百にもなる配列に応用するときには , いくつかの変更が必要て、す。たとえば現状て、は get range( ) は線型探索を使っていますが , 配列が大き い場合は二分木探索を使い , インデクス範囲が 100 以 下になれば線型探索に切り替える , といったくふう が必要て、す。また探索文字列をエディットて、きる機 能を , 盛り込みたい場合もあるて、しよう。 いずれにしても , ここに示したルーチンは , あな たのニーズに , 十分に簡潔て、 , そして明快に応えて くれるものだと思います。 Jim Kerr 氏は元数学教授て、 , 現在はカリフォルニア 大学サンタクルーズ校て、計算機科学を学んて、います。 彼のおもな関心は , コンパイラの設計と言語理論て、 す。

6. 月刊 C MAGAZINE 1990年4月号

高速化とノヾフォーマンスアナライサ 野口修男 プログラムを作成し , 実行してみると期待どおりのスピードで動作しない , 時間の かかっていそうなところにあたりをつけて書き直すが , たいしてスピードが上がら プログラマならだれでも経験したことがあるはずです。パフォーマンス アナライサとしては UN Ⅸのプロファイラが知られていますが , DOS 上では実用的な ものがありませんでした ( UN Ⅸのプロファイラが実用的かどうかは疑問の残るとこ ろですが ) 。 DOS アナライサ rlnside! 」は従来のプロファイラより機能的に一歩進 んだプログラムです。 , こでいう「パフォーマンス」という単語はたんに英語での スピードというよりも , もう少し大きな概念を表しています。日本語の「性能」に 近い意味がこめられています。今回はプログラムの高速化を中心に [lnside! 」がど んな場合に役立つかを実践的に解説します。卩 nside ! 」には QA の分野でも役立つ機 能があります。この方法論は C 言語に限定されませんが , コードは MS ー C を想定して います。また , 最初にお断りをしておきますが , この記事を読んだ途端にプログラ ムのスピードが 2 倍になるようなマジックはありません。 こに記載した高速化の 手法は常識的なことばかりです。違いはいかに計測するかにあります。 いつ「 lnside! 」を 使うか 誕十 / プロトタイピンク段階での 高ヒに対する考慮 プログラムの高速化を考えるのは , ある 場合には設計者てあり , またプログラマ自 身が実際のコーディングのときに変史 / 追加 / 削除を行うこともあります。 「 lnside ! 」は設計者には役に立たないてし よう。なぜなら , 設計者は経験と理論を駆 使して机上て、設計するのが仕事だからて、 す。しかし , 「 lnside! 」はプロトタイピング の段階からは確実に役立ちます。プログラ ムが完成に近づいてから行う高速化の多く は , ほとんどがモジュール内部に限定され ます。したがってグローバルな最適化に比 べてあまり効果がありません。効果を増す ために , モジュール構成などを変更すれば かなり大規模な変更に発展する可能性があ ります。 設計段階て、はなかなか実行時間の予測は 難しいのてすが , プロトタイヒ。ングの段階 て、は「 lnside! 」を使いマイクロ秒単位の時 間計測が可能になります。この段階て、かな り入念な最適化を行うべきてしよう。プロ トタイヒ。ングの段階て、正確な実行時間とと もに行 / 関数単位の実行回数もチェックし , 繰り返し文の繰り返し回数に誤りがないか などのバグを取り除くことも可能て、す。 この段階て、のファインチューニングは , 最終製品に近いものがてき上がってからプ ログラム全体のスヒ。ードを測って行う場合 よりも大きな意味があります。また , 全体 の実行時間の計測 / 修正に要する時間 ( ター ンアラウンド ) は , プロトタイピングの場合 に比べて数倍から数十倍を要することから も , プロトタイピング段階てのファインチ ニングは明らかに効率的なはずて、す。 もしこの段階て、パフォーマンスが不十分 だとプログラマが判断した場合には , 設計 者との相談によって設計変更を余儀なくさ れることもしばしばあります。 全モジュールリンク後の ファインチューニング 各モジュールまたは機能ごとのプロトタ イプが完了すると , 全モジュールをリンク して製品の初期段階がてき上がります。プ ログラマはもう製品がてき上がったとよく いいますが , 実際にはこの段階から製品出 荷まて、の時間 / 労力が相当にかかります。い くらプロトタイビングて、ファインチュー ングしても , 最終製品はなかなか希望する スピードに達しないものて、す。 なぜか ? プロトタイピングの段階ては一連のプロ グラムの流れをすべてチェックてきないか らてす。たとえばあるメニューからあるパ ラメータを設定し , この設定にしたがって ランしてみると , 別の設定の場合とはパフ ォーマンスが大きく異なることがあります。 その大きな要因のひとつがデータてす。 プロトタイプの段階て作成てきるデータの 種類 , および大きさが限られているのが通 常て、す。なぜなら , その段階てはデータ作 成ツールがまだ完成していないために , マ ニュアルて作成しなければならないからて す。データの種類 , 大きさによってパフォ ーマンスに大きな違いが生じます。さらに ディスク上のデータの分散化も大きな要因 てす ( ここても「 lnside! 」の DOS コール解析 てファイルの RD / WR に要する時間の違いを Conference Room 135

7. 月刊 C MAGAZINE 1990年4月号

し , さらに ③挿入する要素の next ポインタ A3 ④挿入する要素の back ポインタ A2 としておけばいいのて、す。そして , この場 合 , リストボインタは挿入された要素を指 し示すのが自然てすから , ひとつ進めて、、 ls A4 クとします。 また Fig. 3 は Fig. 2 の状態からリストボイ ンタをひとつ前に移動したうえて、その位置 の要素 ( = A2 ) を削除する場合を示していま す。この場合は , ① ls の back ポインタが指し示している構 造体 ( = AI ) の next ポインタを A4 に ② ls の next ポインタが指し示している構 造体 ( = A4 ) の back ポインタを AI に 書き換えるだけて、十分て、す。リストボイン タはひとつ前に進めて , A4 を指し示すよう にするのが自然て、しよう。すなわち、、 ls ls ー > next" とします。 ( 3 ) 例外処理 リストの初期状態て、は , 要素はなく , NULL 〃て、すから , 最初の 1 個目 、、 ls の要素を挿入するのは例外処理にしなくて はいけません。たとえば , アドレスが AI の 要素を挿入する場合 , ① ls = AI ・② ls— >next = NULL ③ ls— >back = NULL リストの先頭や末尾に挿 とします。また , 入する場合は , back ポインタや next ポイン タを NULL とする処理が必要になります。 プグラミングの実際 明しておきます。 タなどが代表的な例て、す。 まず , 第一にこのポイントは「マルチリス そこて , このライプラリて、は , open ト」にするということて、す。これは , ひとつ 以上見てきたように , アルゴリズムは比 list, close list という関数て、 , あたかもフ 較的簡単て、す。自分て、図を書いてみながら のアプリケーションプログラムて , ふたっ ァイルのようにリストを開いたり閉じたり 考えると理解しやすいて、しよう。て、はどの 以上のリスト構造を同時に操作する必要が て、きるようにしました。同時に開けるリス あるのて , これはとても重要て、す。たとえ ようにしてこのアルゴリズムを実現するか , トの数は , いちおう最高 20 本としてありま ば複数のテキストを同時に編集するエディ 次にプログラミングの実際について少し説 す。そのため , Fig. 4 に示すような構造体を Fig. 2 要素の挿入 NULL A3 A4 NULL ( 1 ) ( 3 ) ( 4 ) ( 2 ) A2 リストボインタはから ばに移動する A4 ( 3 ) ( 4 ) Fig. 3 要素の削除 AI NULL A4 A3 A4 N U LL リストボインタはから に移動する 1 4 CMAGAZINE 19 4 140

8. 月刊 C MAGAZINE 1990年4月号

ne Oint Edition 0 P て、す。ラインの端がどこに位置するかによ って , Fig. 2 の 9 種類のアウトコードのどれ かが決まります。両端のアウトコードの AND をとって , 0 て、ない場合はラインを引く必要 がありませんにのとき引こうとするライン 囓 は直線 U よりも上 , もしくは D よりも下 , L よ りも左 , R よりも右にその両方の端をもつわ けて、す ) 。 AND の結果が 0 になった場合は , どちらかはまだわかりませんから , アウト コードによって直線を分断します。たとえ ば , アウトコードの最後の桁が 1 の場合は , その端はウインドウの左にあるわけて、すか ら , その端を直線 L と引こうとする直線の交 3 点に移動し , その点のアウトコードを得ま す。これを両端て、繰り返していけば , 最大 第 4 回の繰り返しののち , 次のふたつのどちら かの結果が得られます。 ①アウトコードが双方とも 0 になる ②双方のアウトコードの AND が 0 以外になる ①の場合は安心して両端を結んて、直線を 引けばいいて、すし , ②の場合は直線を引か ずにリターンしてよいわけて、す。 C によるコーティング例 C 言語によるコーディング例を List6(cIip) に示します。 List6 の 76 行の c cline( ) 関数が クリッビングっきライン関数て、す。 82 行目 て、アウトコードの AND が 0 て、ないとき , 何も せず戻ります。そうて、ない場合 , ループに 入り , 前にあげた条件①か②のどちらかに なるまて、 , 切断と AND を繰り返します。① のときだけ 92 行のライン描画を実行します。 次にこれをアセンプリ言語化したもの (cline. asm) およびウインドウ設定関数 (setwindow) のソースリストをディスクに掲 載しておきます。最適化がこうじて C 言語プ ログラムの List6 とはほとんど対応づけがて きていませんが , 基本的には , 同じことを やっていると思ってください 0 List 5 68 : even 69 : 心 11 : 76 : even 77 : n 1 011 : 80 : even 81 : 心 01 : 82 : 87 : even 88 : n 1 3 : 90 : 92 : 93 : 94 : 95 : 96 : 99 : 100 : 101 : 102 : 103 : 104 : even 105 : 心 77 : 106 : 107 : 108 : even 109 : n17: 110 : 112 : 114 : ende : 115 : 116 : 1 18 : even 1 19 : 心 9 : ror 120 : adc 121 : ー 00P 122 : 123 : out 124 : endproc 125 : even 126 : shift2 dw 127 : shift dw 128 : 129 : setA し : 130 : 131 : 132 : @dy, @s n 1 0 11 : 右上がり 4 5 度 setAL @dy dx,-81 CX short n101 _setA し CX dx, 79 test call neg mov lnc JCIP : jz : 右下がり 4 5 度 call lnc mov stosb ror adc IOOP JIDP @Y, dx 心 0 1 short ende dS, CX ; push CX, ax : @dx equ DX だから必要なし dx, @dx ;dx:ax=dx*2-16 ax, ax ; d i v @ady CX ;st=dx * 2 ・ 16 / ady @st, ax : POP ax, CX CX, dS @dy, @s n 177 : 右上がり 4 5 度以上 0 r 真上 setAL @dy @dx, ー 81 CX short 心 7 setA し @dx, 79 CX mov mov mov xor d i v mov mov mov test JZ call neg mov lnc JLIP call mov IIIC stosb add JC add ー 00P : jz : 右下がり 4 5 度以上 0 r 真下 @s, @st n 19 @y, @dx n 17 : キャリーが立っことは少ない a l, ah 7ch, mov out endproc ;grcg-off 1 ー 0 ) cd 0 ) 0 ー 'grcg-off 32768 , 16384 , 8192 , 4096 , 2048 , 1024 , 512 , 256 128 , 64 , 32 , 16 , 8 , 4 , 2 , 1 : ビットシフトテープル : ドットセットマスク A しのセット ()H のリセット ) ds, bx bx,7 bx, 1 mov and shl 超高速グラフィックライプラリ 69

9. 月刊 C MAGAZINE 1990年4月号

この手順に従って生成したコードが List2(A) て、す。ここて、 , ( 1 ) については異論 はないと思いますが , ( 2 ) ~ ( 4 ) については 改良の余地があります。 ②のようなケースて、は , word ptr i, 1 mov とすれば , 1 命令て、すむはずて、す。また , 同 様に ( 4 ) のケースて、も , bx, word ptr p 用 OV word ptr Cbx] ユ mov とすれば , 2 命令にまて、縮まります。 しかしよく見ると , この最適化版て、は代 入式の値が正しく設定されないことがわか ります。 Cm( そして C ) の定義て、は , 代入さ れた値 ( 右辺 ) がそのまま代入式の値になり ます。つまり , 「 i=j 」という式を実行した直 後には , AX レジスタには変数 j の値が入っ ていなければなりません。これらのケース て、は , AX レジスタをバイバスしてしまって いますから , 明らかに規則違反て、す。 こて、見方を変えてみましよう。代入式 は「式」とはいうものの , たいていのケー スて、は実質的には「文」として扱われてい ます。いい換えれば , 代入式の値が使われ るケースはまれて、 , ほとんどの場合は「代 入する」という副作用のみが必要とされ , 代入式の値は無視されます。これは , ほか の代入演算子についても同様のことがいえ ます。そこて、 , ▽代入式の値が必要とされる場合 ▽副作用のみが必要で , 値は不要の場合 というふたつのケースを区別して , 後者の 場合についてのみ , 最適化を行うようにし ます。そうすれば , 「代入文」として使われ るケース ( ほとんどがこのケースに該当する ) て、は効率のよいコードが生成され , 値が必 要とされる「代入式」て、は正しく値が設定 され , すべてがまるく収まることになりま す。値が必要とされない代入文用に最適化 したコードを List2 ( B ) に示します。単純な 代入式のコード生成を行う関数は genas sign( ) て、す (List3) 。 78 CMAGAZINE 19 4 代入式のオプジェクトコード ※変数 i , j, p は次のように定義されているものとする。 i, j, *P, a [ 10 ] : int (A) 代入式の値が必要となる場合 ax, word ptr -j word ptr _i, ax List 2 ( 1 ) i mov mov ( 2 ) 、 i mov mov ax, 1 word ptr _i,ax ( 3 ) *p mov push 田 OV POP mov ( 4 ) *p mov push mov POP mov bx, word ptr -p bx ax, word ptr ・ 1 [di],ax 0 (B) 副作用のみが必要で , 代入式の値は不要なケー ス ( 1 ) i ax, word ptr -j mov word ptr -i,ax mov 0 2 word ptr —i, 1 ( 3 ) *p mov push mov POP mov ( 4 ) *p mov mov bx, word ptr -P bx ax, word ptr 1 [di],ax bx, word ptr -P word ptr [bx] , 1 代入式のコード生成 genassign( ) generate code for assignment * / genasslgn genassign(EXPR *P' bOOl needValue) 2 : v 0 i d *left = p->e_left, *right ニ p->e-right; 4 : EXPR 5 : if (isVariable(Ieft)) { 6 : if (isConst(right) & & ! needValue) 7 : right->e-value) : gencode ("YtmovYt%v, %dYn" left, 8 : else { 9 : genexp(right) ; gencode ("YtmovYt%v, %rYn" List 3 p->optype) : left, } else {

10. 月刊 C MAGAZINE 1990年4月号

① List 1 bms. C List 1 6 : 7 : #include <stdio. h> 8 : #define DEBUG 9 : 10 : #ifdef DEBUG 11 : nain() 13 : Char *key, *text; int c コ ocsu 魲 0 : key="PCG" text="CMZ 円 PCPCGABPCCEXPCG ”・ 01234567890 3456789 事 / loc=bn-search(key, text) : 20 : locsun 十 =loc: printf("Key word is XsYn".key) : 21 : printf("text isYnXsYn", text) : 22 : printf("location is XdYn",loc) : 23 : whi 厄 00C > = の { 24 : loc=bn-search(key. text+locsun + 1) : 25 : if (loc く 0 ) break; ー ocsu 引 oc + 1 : printf("location is XdYn",locsun) : 28 : 29 : 30 : 31 : #endif 32 : 33 : bn-search(key. text) 34 : Char *key, *text : int i, cur-pos. key-length. skip-array(256) : 36 : 37 . initialize skip array 38 : key-length=strlen(key) : 39 : for ( i : 0 : i く 256 : i + + ) { 40 : skip-array[i]=key-length; 42 : fo 「 (i=0; i<key_lengthä + + ) { skip-array[(int)key[i]]=key-length-i -1 : 43 : 44 : 45 sea rch key word 46 : cur_pos=O; while (cur-pos く strlen(text)) { if (skip-array[text[cur-pos + key-length-l]] く key-length) { 48 : 49 . found a letter in the key word * / cur-pos 十 =skip-array [text[cur-pos 十 key-length-l]] : 50 : 52 : if(key[i] !=text [cur-pos + i)) break; 53 : if (key[i]= 54 : ・ \ 0 ・ ) return (cur_pos) : 55 : e ー se 56 : 57 . skip 58 : else cur_pos + =key_length; 59 : return ( - 60 : Boyer-Moore Sea rch ・ 89.7. 26 f 「 0 田 DDJ July ・ 89 F. Awa / * found り / * fail * / つの比較てキーワードを見つけられれば , 、、 IIIIIIIIIAAAI" ′から、、 AAAI" してリンクして用いる。 そのロケーションを返して終了する。キー を探すようにキーワードに重複が多い場合 Fig. 3 にコンパイルの方法を示した。外か ワードと違う部分が見つかれば , 1 文字ずつ ら呼ばれる関数は , bm search()< ふたっ や , 探すべき文字列にキーワードの最後の の比較は中止され , 位置をひとつ進めて , の引数をとる。第 1 引数はキーワードて、 , 第 文字 ( スキップ 0 ) が多い場合は不利て、 , むし 2 引数として与えられたストリング中からこ ろ順々に探すほうが速い場合もあり得る。 もとのループに戻る。 比較した文字がキーワードの長さより小 さらに Boyer ー Moore 法て、はスキップ用の れを探し , 最初に見つけたロケーションを さくない ( 等しい ) 場合は , キーワードはな 配列を用いているのて、 , 複数のキーワード 返す。 を同時に検索することが効率的にて、きそう いのて , その数 ( = キーワードの長さ ) だけ DEBUG を定義したままコンパイルし , とばせばよい 実行した結果を Fig. 4 に示す。 だ。すなわち , キーワードに含まれる文字 このように探して , 最後まて、行った場合 にはそのうち最小の数を割り当て , 含まれ まとめ はキーワードはないのて、あるから , ー 1 を返 ない文字にはキーワードの中のもっとも短 すようにした。 い長さとすればよい。実際にどの程度速く Boyer-Moore 法はスキップ用の配列を必 要とするだけに , 記憶域と初期化の時間が なるかは試していない コンバイ ) 順と呼び出し方法 余分にかかる。しかし , キーワードの長さ ソースファイルを BMS. C としてセープす だけ比較をさばれるのて、 , トータルて、は順 る。前節て、も述べたが , #define DEBUG 次先頭から比較するより速い場合が多いだ ろう。キーワードが長いほど有利て、あるこ を残せば , 単体テスト用の実行形式を作る。 とは容易に想像て、きる。 DEBUG が定義されなければ , BMS. OBJ と Fig. 4 実行例 Fig. 3 コンバイルの手順 #define DEBUG のまま Key wo 「 d is PCG BMS. OBJ—>BMS. EXE ( 例題を実行 ) text iS CMZPIPCPCGABPCCEXPCG BMS. C location is 7 BMS. OBJ ( リンクして使う ) location is 1 7 #define DEBUG を消去 0 参考文献 1 ) COStas MeniCO : Faster String Searches, Dr. D0bb's Journa し # 153 ′ pp. 74 ー 75 ( 1989 ) 2 ) Boyer. R. S. Moore. J. S. : A Fast string 劑 go 「 - ithm,CACM,Vol.20,No.1 の pp. 762 ー 772 ( 1977 ) 3 ) Knuth,D. E. Morris,J. H. Pratt,V. R. : Fast Pat- tern Matching in Strings,SlAM J . of Comput. Vo に 6 ′ No. 2 June, pp. 323 ー 350 ( 1977 ) 4 ) Davies. G. Bowsher. S. : Algorithms for Pattern Matching,Softw. Pract . Exper,VOL . 16. NO. 6 ′」 une pp. 575 ー 601 ( 1986 ) 144 CMAGAZINE 19 4