C言語で無限リストを実装して、100万の素数リストを作ってみた
リスト構造について
カーニハン著「プログラミング作法」で、C言語によるリスト構造の実装がありました。他のテキストやサイトに載っているやり方なのですが、副作用があります。そこで、ちょっと改善したコードを思いついたので試してみました。
無限リストっぽいこともできるはずです。
コードの説明
まずは、インクルードで標準ライブラリを読み込んでおきます。
#include#include #include #include #include #include #include #include #include
assert.hとtime.hはチェックのために使っています。また、stdbool.hはC11(やC99)対応のコンパイラが必要となります。
続けて、構造体を作っておきます。ここでは、順序対を参考にしながら実装しています。詳しくは後出のpair関数で述べることとしましょう。
typedef struct OrderedPair Ord_t;
/*OrderdPair 構造体
* 順序対を作るための構造体
* ただし、属性fだけは操作として、next関数で使われる*/
struct OrderedPair {
int32_t first; /*対となる一番目*/
Ord_t *second; /*対となる二番目*/
int32_t lifepoint; /*参照カウンタ*/
int32_t (*f)(Ord_t*); /*無限リストの新しい項目を作るための関数*/
};
普通は空リストを作るのに、NULLを使うのですが、今回は新しく構造体のEMPTYを作ります。
int32_t dummy (Ord_t*);
/*定数EMPTY
* 空リストを表現する構造体*/
const Ord_t EMPTY = {
0,
NULL,
0,
dummy
};
こうしておけば、バグを増やす要因となるNULLを排除できます。
関数の実装
関数のプロトタイプ宣言は以下の通りです。
bool isEmpty (Ord_t*); int32_t first (Ord_t*); Ord_t *second (Ord_t*); void eprintf (char*, ...); void *emalloc (size_t); void freelist (Ord_t*); Ord_t *pair (int32_t, Ord_t*); Ord_t *next (Ord_t*); typedef bool(*Ord2bool_t)(Ord_t*); typedef Ord_t *(*Ord2Ord_t)(Ord_t*); /*Ord2Ord_t = Ord_t* -> Ord_t**/ Ord_t *setChurchNumber (int32_t, Ord2Ord_t, Ord_t*); int32_t getPrimeNumber (Ord_t*); bool isPrimeNumber (int32_t);
リストのインタフェースとして、isEmptyとpairとfirstとsecondがあれば、理屈の上では十分です。
ただし、C言語では、そのほかにも動的にメモリを管理する必要があるので、eprintf関数とemalloc関数と、freelist関数を実装しておきます。
isEmpty関数は、引数にEMPTYのアドレスが渡された時、つまり、isEmpty(&EMPTY)のときだけ、trueを返します。
/*isEmpty 関数
* 引数のlistがEMPTYかどうかをチェックするときに使う。EMPTYならばtrue( = 1)
* NULLは不具合が起きるので、入力すればエラー*/
bool isEmpty (Ord_t *list) {
if (list == NULL) {
eprintf("NULL argument error on the function isEmpty");
return false;
} else if (list == &EMPTY) {
return true;
} else {
return false;
}
}
pair関数に必要なfirst関数やいろいろな関数を実装していきます。今は、詳しく説明しないでおきましょう。
/*first 関数
* 順序対の一番目を返す
* pair関数で指定された第一引数（例えば、pair(a,b)ならばa)を返す)*/
int32_t first (Ord_t *list) {
if (isEmpty(list)) {
return 0;
} else {
return list->first;
}
}
/*second 関数
* 順序対の二番目を返す
* pair関数で指定された第二引数（例えば、pair(a,b)ならばb)を返す)*/
Ord_t *second (Ord_t *list) {
if ( isEmpty(list) || (list->second == NULL) ){
/*ペアの二番目を取得できない場合は、自分自身を返す*/
return list;
} else {
return list->second;
}
}
/*eprintf 関数
* プログラムを中止させるためのエラー処理を担当。入力値はエラーを報告する文章*/
void eprintf (char *fmt, ...) {
va_list args;
fflush(stdout);
va_start(args, fmt);
vfprintf(stderr, fmt, args);
va_end(args);
fprintf(stderr, "\n");
exit(EXIT_FAILURE);
}
void *emalloc(size_t n) {
void *p;
p = malloc(n);
if (p == NULL) {
eprintf("%u bytes failed on the function emalloc", n);
}
return p;
}
/*freelist関数
* 引数のlistを解放させる
* 他から参照されていない限り、EMPTY以外のリストすべてが対象*/
void freelist (Ord_t *list) {
Ord_t *next;
for (;!isEmpty(list) || (list->lifepoint >= 1);list = next) {
next = second(list);
if (list == next) {
break;
} else {
free(list);
list = NULL;
}
if (!isEmpty(next)) {
/*すでに死んだため参照カウンタを減らす*/
next->lifepoint--;
}
}
}
さて、pair関数でリストを作っていきます。まずは、pair関数のコードを見てください。
/*pair関数
* 第一引数と第二引数とで順序対を作る*/
Ord_t *pair (int32_t n, Ord_t *p) {
Ord_t *s;
s = (Ord_t *) emalloc(sizeof(Ord_t));
s->first = n;
s->second = p;
s->lifepoint = 0;
if (!isEmpty(p)) {
p->lifepoint++;
}
return s;
}
pair関数の引数に、二つの値を入力すると、二つを組とするデータ構造を返します。これらをつなげていくと、連結リストとなります。
使い方としては、前出のfirst関数とsecond関数を使います。
Ord_t *p = pair(1, &EMPTY); first(p); // 1を返す second(p); // &EMPTYを返す freelist(p);
freelist関数の解放忘れに注意してください。通常のリスト構造もこんな感じで使えます。
Ord_t *p = pair(3,
pair(2,
pair(1, &EMPTY)
)
);
first(p); // 3を返す
first(second(p)) // 2を返す
first(second(second(p))) // 1を返す
freelist(p);
それで、次のnext関数とsetChurchNumber関数を使うと、無限リストのようなこともできます。
/*next 関数
* 無限リストの次の項目を生成して返す*/
Ord_t *next (Ord_t *list) {
int32_t n = list->f(list);
Ord_t *s = pair(n, list);
s->f = list->f;
return s;
}
/*setChurchNumber 関数
* C言語でラムダ計算のチャーチ数を部分的に再現するための関数*/
Ord_t *setChurchNumber (int32_t length, Ord2Ord_t f, Ord_t *list) {
int32_t i;
for (i = 0; i < length; i++) {
/*lengthが4の場合、list = f(f(f(f(list))));*/
list = (*f)(list);
}
return list;
}
int32_t dummy (Ord_t *p) {
return first(p) + 2;
}
OrderedPair構造のf属性に、dummy関数を入れると、初期値が2の場合は偶数リストを作ることができます。
Ord_t *s = pair(2, &EMPTY);
s->f = dummy;
s = next(s);
first(s); // == 4
s = next(s);
first(s); // == 6
freelist(s);
pair(2, &EMPTY)をpair(1, &EMPTY)に書き換えると、奇数リストとなります。今度はこれを応用して素数リストを作ってみます。
素数リストの実装
素数を得るためのgetPrimeNumber関数と、素数かどうかをチェックするisPrimeNumber関数を実装します。このうち、getPrimeNumber関数をさっきのdummy関数と同じようにします。
/*getPrimeNumber 関数
* 素数リストであるlistから次の素数の算出する*/
int32_t getPrimeNumber (Ord_t *list) {
int32_t i = first(list);
if (i == 2) {
return 3;
}
if ( (i % 2) == 0) {
i++;
}
/*iは2以外の素数と考えると、奇数でもある。そこで、偶数を避けるために2ずつ足していけばよい*/
for (i+=2;is->fにgetPrimeNumber関数を入れてみましょう。素数リストとなっているはずです。
Ord_t *s = pair(2, &EMPTY);
s->f = getPrimeNumber;
first(next(s)); // == 3
first(next(next(s)); // == 5
first(next(next(next(next(s))))) // == 11
freelist(s);
メモリやデータ型の制約に引っかからない限りは、無限にリストを作っていけます。
それでは、今度は、setChurchNumber関数を使って、百万の素数リストを作っていきます。
Ord_t *s = pair(2, &EMPTY);
s->f = getPrimeNumber;
s = setChurchNumber(1000000, next, s);
printf("%d\n", first(s));
freelist(s);
これをgcc5.1.0 (TDM-GCC-64)で実行すると、約十三秒後に、
15485867
がコンソールに出力されました。isPrimeNumber関数でチェックすると、素数なのですが、念のため、検索エンジンでこの数値を調べてみますと、http://www.bigprimes.net/cruncher/15485867/ では、「It is the 1000001st prime number」となっています。
ということは、正確には、「百万飛んで一個の素数リスト」です。
追記（2017年5月9日）
確認した動作環境は、gcc (tdm64-1) 5.1.0です。TDM GCCでオプションに-std=c11を使っています
