単連結リストの整列 #54 二つの要素の一つ前の要素を一緒に求める

前回述べた二つの要素の一つ前の要素を同時に求める関数を書いてみる。
ilist2.cを利用する。
同時に二つの一つ前の要素を求める関数はprev2とする。

test_ilist2_prev.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include "ilist2.h"

#define UNUSED_ARG(x) (void)(x)

typedef struct tag_ielem ielem, *ielem_p;
struct tag_ielem {
    int v;
    ielem_p n;
};

#ifndef NELEM
#define NELEM 10
#endif
static ielem ilist = {0, NULL};
#if NELEM == 0
static ielem elem[1];
#else
static ielem elem[NELEM];
#endif

#ifndef PREV2

static ielem_p prev(ielem_p p)
{
    ielem *q = &ilist;
    for (;;) {
        if (q->n == p) break;
        q = q->n;
        if (q == NULL) break;
    }
    return q;
}

#else

static void prev2(ielem_p p1, ielem_p *pp1, ielem_p p2, ielem_p *pp2)
{
    int b1 = 1, b2 = 1;
    ielem *q = &ilist;
    *pp1 = *pp2 = NULL;
    for (;;) {
        if (b1 && q->n == p1) {
            *pp1 = q;
            b1 = 0;
        }
        if (b2 && q->n == p2) {
            *pp2 = q;
            b2 = 0;
        }
        if ((b1 | b2) == 0) break;
        q = q->n;
        if (q == NULL) break;
    }
}

#endif

void iinit(void)
{
    int i;
#if NELEM > 0
    ilist.n = elem;
#else
    ilist.n = NULL;
#endif
    for (i = 0; i < NELEM; i++) {
        elem[i].v = (int)(rand() / (RAND_MAX + 1.0) * 90) + 10;
        elem[i].n = i < NELEM - 1 ? &elem[i + 1] : NULL;
    }
}

int main(void)
{
    clock_t s, e;
    ielem_p p;
    srand(1234567);
    iinit();
    s = clock();
    for (p = ilist.n; p->n != NULL; p = p->n) {
#ifndef PREV2
        ielem_p q1 = prev(p), q2 = prev(p->n);
#else
        ielem_p q1, q2;
        prev2(p, &q1, p->n, &q2);
#endif
        assert(q1->n == p && q2 == p);
    }
    e = clock();
    printf("%.3f\n", (double)(e - s) / CLOCKS_PER_SEC);
    return 0;
}

ilist2のヘッダファイルilist2.hをインクルードしてはいるが、
同じソース内のmain関数を動作させる関数を実装するだけで外に公開するわけではないので、
ヘッダファイルで宣言している関数全てを書いてはいない。
要素数10000個のリストを作り、
先頭の要素から順番に最後の要素の一つ前の要素まで、
その要素とその次の要素の一つ前の要素を、
prevを二回呼び出すかprev2を一回呼び出すかして求め、
かかった時間を表示する。

$ gcc -std=c89 -pedantic -Wall -Wextra -Werror -o test_ilist2_prev test_ilist2_prev.c -s -DNELEM=10000

$ ./test_ilist2_prev
0.531

$ gcc -std=c89 -pedantic -Wall -Wextra -Werror -o test_ilist2_prev test_ilist2_prev.c -s -DNELEM=10000 -DPREV2

$ ./test_ilist2_prev
0.359

prev2を使用するとprevの二回呼び出しの三分の二ほどの時間で済むようになった。