前々回にやった二分木で単語の出現回数を数えるプログラムと、 それ以外の素朴なアルゴリズムで数えるプログラムとで、所要時間をはかってみよう。 いずれも、引数で指定されたファイルの中の異なる単語を数えるように書いてある。
関数がページの境目をまたぐことを避けるため、プログラム中に空行を置いた箇所がある。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#define MAXWORD 100 /* 単語の長さの最大 */
struct Tnode *addtree(struct Tnode *, char *);
void treeprint(struct Tnode *, int depth);
char *strduplicate(char *s);
int getword(char *word, int lim, FILE *in);
struct Tnode {
char *word; /* 単語へのポインタ */
int count; /* 出現回数 */
struct Tnode *left; /* 左の子へのポインタ */
struct Tnode *right; /* 右の子へのポインタ */
};
int main(int argc, char *argv[]) {
struct Tnode *root; /* root */
char word[MAXWORD];
FILE *in;
time_t start, end;
if ((in = fopen(argv[1], "rt")) == NULL) {
printf("ファイル %s が開けません.\n", argv[1]);
exit(1);
}
time(&start); /* 開始時刻 */
root = NULL;
while (getword(word, MAXWORD, in) != EOF) {
root = addtree(root, word); /* word を root の下に追加 */
}
time(&end); /* 終了時刻 */
treeprint(root, 0);
printf("%0.f 秒かかりました.\n", difftime(end, start));
}
/* 木 tp に文字列 w を加える。tp が返る */
struct Tnode *addtree(struct Tnode *tp, char *w) {
int cond;
if (tp == NULL) {
tp = malloc(sizeof(struct Tnode));
tp->word = strduplicate(w);
tp->count = 1;
tp->left = tp->right = NULL;
} else {
cond = strcmp(w, tp->word);
if (cond == 0) {
tp->count++; /* 既出の単語 */
} else if (cond < 0) {
tp->left = addtree(tp->left, w); /* 左の subtree に追加 */
} else {
tp->right = addtree(tp->right, w); /* 右の subtree に追加 */
}
}
return tp;
}
/* 木を出力 */
void treeprint(struct Tnode *p, int depth) {
int i;
if (p != NULL) {
treeprint(p->left, depth + 1); /* 左の部分木を出力 */
// for (i = 0; i < depth; i++) { /* この 3 行をコメントで */
// printf(" "); /* なくすると、木の構造が */
// } /* 見やすくなる */
printf("%4d %s\n", p->count, p->word); /* その node を出力 */
treeprint(p->right, depth + 1); /* 右の部分木を出力 */
} /* p == NULL なら何もしない */
}
/* 文字列を複製 */
char *strduplicate(char *s) {
char *p;
p = malloc(strlen(s) + 1);
if (p != NULL) {
strcpy(p, s);
}
return p;
}
/* 次に入力される単語を返す。アルファベット以外は無視 */
int getword(char *word, int lim, FILE *in) {
int c, i;
i = 0;
while ((c = fgetc(in)) != EOF && isalpha(c) == 0) {
; /* アルファベット以外を飛ばす */
}
if (c == EOF) {
return EOF;
}
word[i] = c; i++;
for ( ; i < lim; i++) {
word[i] = fgetc(in);
if (isalpha(word[i]) == 0) {
ungetc(word[i], stdin); /* 読みすぎた分を戻す */
break;
}
}
word[i] = '\0';
return word[0];
}
最後にアルファベット順に並べ替えねばならないのだが、それは省略してある。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#define MAXWORD 100 /* 単語の長さの最大 */
#define MAXWORDS 100000 /* 異なる単語の総数 */
int addword(char *word, int m);
char *strduplicate(char *s);
int getword(char *word, int lim, FILE *in);
struct Tnode {
char *word; /* 単語へのポインタ */
int count; /* 出現回数 */
};
struct Tnode words[MAXWORDS];
int main(int argc, char *argv[]) {
char word[MAXWORD];
FILE *in;
time_t start, end;
int i, m;
if ((in = fopen(argv[1], "rt")) == NULL) {
printf("ファイル %s が開けません.\n", argv[1]);
exit(1);
}
time(&start); /* 開始時刻 */
for (m = 0; getword(word, MAXWORD, in) != EOF; ) {
m = addword(word, m);
}
time(&end); /* 終了時刻 */
for (i = 0; i < m; i++) {
printf("%4d %s\n", words[i].count, words[i].word);
}
printf("%0.f 秒かかりました.\n", difftime(end, start));
}
/* 単語を表に加える */
int addword(char *word, int m) {
int i;
for (i = 0; i < m && i < MAXWORDS; i++) {
if (strcmp(words[i].word, word) == 0) {
words[i].count++;
return m;
}
}
words[m].word = strduplicate(word);
words[m].count++;
return m+1;
}
/* 文字列を複製 */
char *strduplicate(char *s) {
char *p;
p = malloc(strlen(s) + 1);
if (p != NULL) {
strcpy(p, s);
}
return p;
}
/* 次に入力される単語を返す。アルファベット以外は無視 */
int getword(char *word, int lim, FILE *in) {
int c, i;
i = 0;
while ((c = fgetc(in)) != EOF && isalpha(c) == 0) {
; /* アルファベット以外を飛ばす */
}
if (c == EOF) {
return EOF;
}
word[i] = c; i++;
for ( ; i < lim; i++) {
word[i] = fgetc(in);
if (isalpha(word[i]) == 0) {
ungetc(word[i], stdin); /* 読みすぎた分を戻す */
break;
}
}
word[i] = '\0';
return word[0];
}
二分探索を利用している。 二分探索について説明する。 単語は表の中で常にアルファベット順に並んでいるので、 きた単語は、まず、表の中央の単語と比較する。 もしもそれと一致すればそれでよし。 それよりも前あるいは後なら、 次は範囲を半分にして繰り返す。
二分探索は、みつからない場合は「みつからない」と答えて終わりだが、 われわれの場合は、みつからなかったら、しかるべき位置にその単語を挿入しなければならない。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#define MAXWORD 100 /* 単語の長さの最大 */
#define MAXWORDS 100000 /* 異なる単語の総数 */
int addword(char *word, int m);
char *strduplicate(char *s);
int getword(char *word, int lim, FILE *in);
struct Tnode {
char *word; /* 単語へのポインタ */
int count; /* 出現回数 */
};
struct Tnode words[MAXWORDS];
int main(int argc, char *argv[]) {
char word[MAXWORD];
FILE *in;
time_t start, end;
int i, m;
if ((in = fopen(argv[1], "rt")) == NULL) {
printf("ファイル %s が開けません.\n", argv[1]);
exit(1);
}
time(&start); /* 開始時刻 */
for (m = 0; getword(word, MAXWORD, in) != EOF; ) {
m = addword(word, m);
}
time(&end); /* 終了時刻 */
for (i = 0; i < m; i++) {
printf("%4d %s\n", words[i].count, words[i].word);
}
printf("%0.f 秒かかりました.\n", difftime(end, start));
}
int addword(char *word, int m) {
int i, left, right, mid, cond;
if (m == 0) { /* 表が空のとき */
words[0].word = strduplicate(word);
words[0].count = 1;
return 1;
} else {
left = 0; right = m-1; /* 二分探索が始まる */
while (left <= right) {
mid = (left + right) / 2;
cond = strcmp(words[mid].word, word);
if (cond == 0) { /* 見つかったとき */
words[mid].count++;
return m;
} else if (cond > 0) {
right = mid - 1;
} else {
left = mid + 1;
}
}
if (strcmp(words[mid].word, word) < 0) { /* 見つからなかったとき */
mid++;
}
for (i = m; i >= mid; i--) { /* ずらし */
words[i] = words[i-1];
}
words[mid].word = strduplicate(word); /* 単語の登録 */
words[mid].count = 1;
return m+1;
}
}
/* 文字列を複製 */
char *strduplicate(char *s) {
char *p;
p = malloc(strlen(s) + 1);
if (p != NULL) {
strcpy(p, s);
}
return p;
}
/* 次に入力される単語を返す。アルファベット以外は無視 */
int getword(char *word, int lim, FILE *in) {
int c, i;
i = 0;
while ((c = fgetc(in)) != EOF && isalpha(c) == 0) {
; /* アルファベット以外を飛ばす */
}
if (c == EOF) {
return EOF;
}
word[i] = c; i++;
for ( ; i < lim; i++) {
word[i] = fgetc(in);
if (isalpha(word[i]) == 0) {
ungetc(word[i], stdin); /* 読みすぎた分を戻す */
break;
}
}
word[i] = '\0';
return word[0];
}
英文からなる巨大なファイルを作り、 上の三つのプログラムでの処理時間をレポートせよ。
巨大ファイルは、Wikipedia などからコピーすればよいだろう。 1,000,000 バイトぐらいでは 1, 2 秒で終わってしまうのでつまらない。
レポートの本文冒頭に、氏名を、なるべく大学に届けるある通りの文字で書け。 次に、処理時間の結果のみを、本文に貼りつけよ。 （巨大ファイルは送ってはならない。）
件名は「??? kadai7」（←全て半角文字、小文字、 ??? は自分の履修者番号、その後ろに半角スペース一つ、 kadai と 7 の間にはスペースを入れない）とせよ。