Subscribed unsubscribe Subscribe Subscribe

sci

最果て風呂

mto を C 言語で実装してみる

小さな部品を作って組み合せる

多次元配列

C 言語で辞書を作成する部分を作ってみた。C 言語は入門書しか持っていなかったので、ネットで各人の記事を参考にした。かなり詳しく書かれている人もいて、情報量はかなり多い。そして有用なものばかりだった(すみません、ゴミ記事を増やしてしまって……)。

ソースの中に直接要素を書き込んだ状態で配列の配列の配列を作ることができた。こういう場合は構造体にした方が良いのだろうか?でも、収納するデータは char 型だけだし……。変数名が cons なのは Emacs Lisp で実装した時からの癖なので特に意味はない。hoge, fuga, piyo, orz, noz は無意識に良く使ってしまう。

#include <stdio.h>

int noz(); // プロトタイプ宣言

int main(void) {
  noz();
  return 0;
}

int noz() {
  // a: 辞書の要素数。ここでは初期化する際に要素数がわかるので無くても良い
  // b: ここでは 2 個の要素を持つ配列を作る
  // c: 単語のバイト数 UTF-8 なので一文字 3 バイトで計算する。4 バイトのもあり
  //       a  b  c
  char cons[][2][32] = {
                        {"植え", "植ゑ"},
                        {"据え", "据ゑ"},
                        {"飢え", "飢ゑ"},
                        {"餓え", "餓ゑ"},
                        {"会い", "会ひ"},
                        {"会う", "会ふ"}, // ここのカンマあってもエラーにならん
  };

  int orz = sizeof cons / sizeof cons[0]; // cons[]/cons[][] とか何度か実験した
  printf("辞書の要素数は %d です。\n", orz);

  for (int i = 0; i < orz; ++i) {
    printf("%s, %s\n", cons[i][0], cons[i][1]);
  }
  return 0;
}

すでに [] が多すぎてわけがわからなくなっている。文字列自身が配列なので、自分が普段二次元配列だと思っているものは三次元配列になるという……。コメントに a, b, c を用いてメモをしてあるけれど、ここの数値を大きくしたり小さくしたりして「この [] は配列のこの部分のことなのね」とエラーを繰り返した。

実行してみると、各要素がカンマ区切りで出力されているし、要素の数も合っている。とりあえず内部辞書は出来たような感じがするけど、確証はない。文字列の配列は難しいな。ポインタがわかってないんだなぁ。

ファイルの読み込み

ファイル名を指定して開いて標準出力に表示するだけの典型的な例。

#include <stdio.h>
#include <stdlib.h> // exit(EXIT_FAILURE) を使える
                    // EXIT_SUCCESS 使うか return 0 か、違うらしい。

int cat();

int main(int argc, char *argv[]) {
  cat(argv[1]);
  return 0;
}

int cat(char *ifile) {
  FILE *fp;
  char str[1024];

  if ((fp = fopen(ifile, "r")) == NULL) {
    printf("ひらけませんがな\n");
    exit(EXIT_FAILURE);
  }

  while (fgets(str, 1024, fp) != NULL) {
    printf("%s", str);
  }
  fclose(fp);
  return 0;
}

argcargv は何度も使っているので、とりあえずわかっているつもり。FILE 構造体の中身は知らなくて「こうやればファイルを読めるんじゃ〜」程度の認識。自分が悩んだのが char str[1024];fgets(str, 1024, fp) のところ。他の言語では下記に相当する部分ね。

with open(jisyo, encoding='utf-8') as ifile:
    for line in ifile:
File::open(jisyo, "r") { |ifile|
    while line = ifile.gets
ifile, _ := os.Open(jisyo)
    scanner := bufio.NewScanner(ifile)
    for scanner.Scan() {
        line, _ := scanner.Text()

ファイルを一行ずつ読み込んで処理をする典型的な例なのだけれど、Python3 をはじめとして、一行のサイズを気にすることなんて今まで必要がなかったのだ。「改行のところで区切って読み込んでくれるんでしょ〜」って。だから裏で面倒臭いことをやってくれてありがたや〜ってスクリプト言語に感謝しちゃった。

今回はこのバイト数をおろそかにしていて後の実験でバグが出ちゃったんだわ。あらかじめ変数の型だけでなく大きさまで決めておかなければならないなんて……。C 言語つらい。

正規表現

ファイルを一行ずつ読み込むことができたら、あとは正規表現を使って不要な部分を取り除いて配列に加工していける。C 言語では正規表現を使うためには regex.h が必要で文字列を扱うのに string.h を読み込んでおく。

Python3 や Ruby では正規表現を使う際に前もってコンパイルしておく必要はない。そうしなければならない言語にはじめて遭遇したのは C# だったと思う。Go も Objective-C もそうなので、コンパイル型の言語はそういうものらしい。なんて面倒なんだろう……。コンパイル言語つらい。

Regex reg1 = new Regex("^;.*|^$");
Regex reg2 = new Regex("\\s+;.*");
regexp.MatchString("^;.*|^$", scanner.Text()) // これはマッチだけど
re := regexp.MustCompile("[\t\n\f\r ]+;.*") // Perl 形式ないんだって
NSString *pat1 = @"^;.*|^$";
NSRegularExpression *regexp1 =
  [NSRegularExpression regularExpressionWithPattern:pat1
                                            options:0
                                              error:nil];
NSString *pat2from = @"\\s+;.*";
NSRegularExpression *regexp2 =
  [NSRegularExpression regularExpressionWithPattern:pat2from
                                             options:0
                                               error:nil];

かなり話が逸れてしまった。まぁ、上記のような経験があったので、C 言語での実装はそれほど苦労しなかった。何度も試行錯誤をしたし、まだすっきりしない部分(不明点)もあるけれど、一番初めに出会ったものが C 言語だったら挫折していた。最初に C# と出会えていたことが幸運だったと思う。見てみろ Objective-C を。何だコレ?

ということで C 。

static char *commentLinePattern = "^;.*|^$";
regex_t clpReg;
regcomp(&clpReg, commentLinePattern, REG_EXTENDED|REG_NOSUB);

static char *notePattern = "[\t\n\f\r ]+;.*"; // Perl 形式は?
regex_t npReg;
regcomp(&npReg, notePattern, REG_EXTENDED);
regmatch_t match[1];
int matchElem = sizeof match / sizeof match[0];

...

while (fgets(str, MAX_LINE, fp) != NULL) {
  if (regexec(&clpReg, str, 0, NULL, 0) == REG_NOMATCH) {
    if (regexec(&npReg, str, matchElem, match, 0) == REG_NOMATCH) {
      sscanf(str, "%s /%s",
             &*innerDict[elemSize][0],
             &*innerDict[elemSize][1]);
      elemSize++;
    }
    else {
      char tmp[TMP_LINE];
      strncpy(tmp, str, match[0].rm_so);
      tmp[match[0].rm_so] = '\0';
      sscanf(tmp, "%s /%s",
             &*innerDict[elemSize][0],
             &*innerDict[elemSize][1]);
      elemSize++;
    }
  }
}
regfree(&clpReg);
regfree(&npReg);
...

sscanf() は便利だね。これは指定した書式で対応したものを変数に入れてくれるというもの。例えばイメージとして「悪 /惡」[["悪", "惡"],] のように配列に代入していく。

と、今気付いたのだけど、npRegif 文 も一つ不要じゃない?つまり「悪 /惡 ;備考のうんちく」であっても [["悪", "惡"],] にしてくれるんじゃないかと。うん、この処理を無くしても期待通りの結果になった。もうけた!(うんこの処理を無くしても期待通り!うほっ!アッー!)

正規表現オブジェクト(?)も手動で開放してやらないといけないんだね。regmatch_t 構造体(今回は不要になってしまったが)のところがいまいち良くわからないので、時間を置いてからまた何か作ってみよう。

検索・置換

今回いちばん時間のかかったところ。検索してみると C 言語には便利なライブラリが存在しないのだそうだ。いろいろな方が色々な方法で実装されていたのだけれど、malloc とか使うのは怖いのでここのものを利用させてもらった。

int strgsub(char *str, char *car, char *cdr) {
  char *ptr;
  char tmp[MAX_STRG];

  while ((ptr = strstr(str, car)) != NULL) {
    *ptr = '\0';        /* car で見かった部分に '\0' を挿入して文字列を切る*/
    ptr += strlen(car); /* 後ろの文字列を得るためにポインタをずらす */
    strcpy(tmp, ptr);   /* cdr を挿入すると消えちゃうので tmp に保存しておく */
    strcat(str, cdr);   /* cdr を挿入する */
    strcat(str, tmp);   /* tmp に退避していた文字列を結合する */
  }                     /* ポインタ渡しなので実引数 str が変更される */
  return 0;
}

原理はわかるし実際に動くのだけど、やっぱわかってない……。

引数処理等

引数処理は Lua など他の言語でやっているのと同じようにした。strcmp() を使って文字列比較という方法。これが C 言語的に良い方法なのかは知らない。

if (strcmp(argv[1], "tradkana") == 0) {
   ...
    } else if  (strcmp(argv[1], "modernkana") == 0) {
   ...

環境変数getenv() で受け取ることができるのだけれど、いろいろとエラーが……。エラーの内容はよくわからないけれども「実行時にわかるからうんぬん」と言っているような気がする。結局 main() 関数の中に入れたらビルドは通るようになった。

実行してみるとパスが通っていない。実は文字列のコピーは基本参照渡しなので、他のところから変数を触るとそれが変更されてしまうみたいだ。

自分の場合は MTODIR に対して kana-jisyokanji-jisyo の文字列をそれぞれ別に付加して使おうとしたのだけど、/Usrs/hoge/dev/mto/dict/kana-jisyo/dict/kanji-jisyo のようになってしまうのだった。自分は strcpy() を使ってパスをコピーすることで解決した。

char kanajisyo[256];  /* パスの長さってどのくらいになる?*/
strcpy(kanajisyo, getenv("MTODIR"));

部品を組み合わせて実行

とりあえず完成したので、他のスクリプトで出力したものと結果を比較してみた。4 箇所に違いがあった。C 言語で実装した方に置換できていない部分があったのだ。どういうことだろう?生成される内部辞書については同じものができているので、置換する処理がおかしいということになる。置換されなかった部分も、読み込ませる文字列の長さを短かくしてやると置換される。漢字置換の方は問題なかった。

一部置換されない箇所が生じる原因がわかった。上記でちょろっと出ていたけれども、変換対象のファイルを読み込んで置換させる際に、while でまわす fgets() のバッファ量が少なかったのだ。そのため文章が途中で改行されたのと同じ状態となり、検索でヒットせずまた置換されなかったという訳だ。

このプログラムのアルゴリズム的に一行が分割されるとダメなんだわ。fgets() は指定したバッファもしくは改行で返してくるので、大きくしておいても大丈夫かな?実際みんなは一行に何文字くらいで改行しているのだろう?とりあえず 40 文字x4 行x3 バイトで 512 にしておくか?1024 にしておこう(実験で大きいファイルを使ったら Abort trap: 6 とかで落ちちゃったので 4096 にしておいた)。

ベンチマーク

C で実装できたのでベンチマークをする。Python3 で 4s のやつが 20s もかかってしまっている(参考)。でも使用メモリ量は 732KB しか使ってないのはすごい。

ソースをコメントアウトしながら time で測ってみるかな。時間がかかるので読み込ませるファイルは小さいやつにしておこう。

内部辞書の作成のみでは 0.018s なのでそれ程時間はかかっていないみたい(上記の余分な処理を無くしたら 0.010s になった!)。printfコメントアウトして実行すると 0.106s となり、 0.110s という標準出力をした場合と変わらないので、printf が遅いという訳ではなさそう。つまり 置換する部分が遅いというわけだわ。

Python3 の場合は内部辞書作成のみだと 0.049s で C よりも時間がかかってるね。print 文をコメントアウトして実行した場合は 0.068s となった。また普通の動作をさせると、0.069s なので、print の影響はほぼ無し。ただし Python3 は変換対象の文字列を一気に読み込んで一気に出力しているので、単純に比較はできないが。

Python3 C
辞書作成 0.049 0.018
文字列変換 0.068 0.106
標準出力 0.069 0.110

こうして表にして内部辞書作成の部分だけを見ると、C は速いんだよ。ここは emacs を除くすべてのスクリプトで同じアルゴリズムで処理しているからちゃんとした比較になる。問題は検索・置換の部分だね。

Python3 は 1 行に対して 3622 回の処理。C は 138 行に対して 3622 回の処理。C の方が大変だわ。変換と出力の部分を改善(一気に読んで一気に放つ)できれば Python3 よりも速くなるだろうか?でも、その「一気に」やる方法がわからないんだよね。あらかじめメモリを自分で確保しなくちゃいけないし。fgets の代りに何を使うべきなのか?バイナリモードの fread というやつを使えそう?

fread(str, MAX_STRG, 1, fp);
for (int i = 0; i < elemSize; ++i) {
  strgsub(str, innerDict[i][1], innerDict[i][0]);
}

こんな感じでバイナリモードで読み込んで fread を使ってみたけど、0.125s とかえって遅くなってしまった。利用している置換関数がネックなのかな?というか、Python3 が速すぎるんだわ。どういうアルゴリズムになっているのだろうか?

おわり。

全体のソースはいつものところです。

おまけ

ThinkPad が起動したので Windwos XP で mto.c をビルドしてみた。が、MinGWregex.h が無いよと言われてしまった。そこでここからダウンロードして各所にコピー。その後下記のコマンドによりビルドすることができた。

cc -std=c99 mto.c -lregex -o mto

実行すると文字化けしていたので、nkf32 をダウンロードして併用。割と速かった。

引数について。 値渡し:実引数の値をコピーして仮引数に渡す。関数の中で仮引数を変更しても、実引数は影響を受けない。

参照渡し:実引数の番地を仮引数に渡す。関数の中で仮引数を変更すると、番地を通して共有しているので、実引数は影響を受けて変更される。

参照の値渡し:配列データなどデータ量が大きくなるものは、その変数への番地が渡されるので、共有される結果となり、実引数の方も影響を受けて変更される。オブジェクト指向の場合、オブジェクト ID が渡されるので、これになるのかな?