Hatena::ブログ(Diary)

プラグインレスでSVGを表示する「SIE」開発ブログ RSSフィード Twitter

JavaScriptで書かれたオープンソースのSVGレンダリングエンジン「SIE (シー)」開発記

2016-09-08

C言語で無限リストを実装して、100万の素数リストを作ってみた

リスト構造について

カーニハン著「プログラミング作法」で、C言語によるリスト構造の実装がありました。他のテキストやサイトに載っているやり方なのですが、副作用があります。そこで、ちょっと改善したコードを思いついたので試してみました。

無限リストっぽいこともできるはずです。

コードの説明

まずは、インクルードで標準ライブラリを読み込んでおきます。

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdarg.h>
#include <limits.h>
#include <math.h>
#include <assert.h>
#include <time.h>

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;i<INT_MAX;i+=2) {
        if (isPrimeNumber(i)) {
            return i;
        }
    }
    /*もし、データ型の上限(INT_MAX)を超えそうな場合は、最初に戻ってループ*/
    return 2;
}

/*isPrimeNumber 関数
 * nが素数かどうかをチェックする
 * ただし、nは奇数であることを前提とする。偶数はチェックしない
 * リストを手掛かりにする方法は遅くなるのでここでは採用しない*/
bool isPrimeNumber (int32_t n) {
    /*次の二つの条件を同時に満たす合成数nは存在しないため、調べるのはnの平方根+1まででよい
     * 条件1, nの平方根以下に、nの因数はない
     * 条件2, nの平方根より上に、nの因数がある*/
    int32_t max = (int32_t) sqrt( (double) n ) + 1;
    for (int32_t i = 3; i < max; i+=2) {
        /*nは奇数を前提にしているので、偶数でわりきることはない*/
        if ((n % i) == 0) {
            return false;
        }
    }
    return true;
}

s->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」となっています。

ということは、正確には、「百万飛んで一個の素数リスト」です。

2016-08-24

SIEでサポートしたSMILアニメーションについて

実装したSMILアニメーションの要素と属性

SIE 29では、SMILアニメーションをいくつか実装しています。その要素と属性を、ここに挙げて、今後の課題を見つけていくことにします

実装したアニメーション要素
  1. animate 要素
  2. set 要素
  3. animateMotion 要素
  4. animateTransform 要素
実装したアニメショーン属性
  1. accumlate 属性
  2. additive 属性
  3. attributeName 属性
  4. attributeType 属性
  5. begin 属性
  6. by 属性
  7. calcMode 属性
  8. dur 属性
  9. end 属性
  10. from 属性
  11. keyPoints 属性
  12. keySplines 属性
  13. keyTimes 属性
  14. max 属性
  15. min 属性
  16. path 属性
  17. repeatCount 属性
  18. repeatDur 属性
  19. restart 属性
  20. roate 属性
  21. to 属性
  22. type 属性
  23. values 属性
  24. xlink:href 属性

合わせて、SIEは4つの要素と、24の属性をサポートしています。

今後の課題

しかし、begin属性とend属性については、リストをサポートしていないなど、不十分な実装が見られます。

今後は、その点を修正していきます

2016-08-11

SIE 29の公開について

モーションパスの向き制御をサポートしたSIE 29

本日、SIE 29を公開しました。今回のバージョンから、MITライセンスに移行しています。大きな変更点は、モーションパスの向きを制御できるanimateMotion要素のrotate属性を実装したことです。ダウンロードは以下からできます

ダウンロード

sie29.zipをダウンロードしてください。ZIP形式なのでダウンロードしたファイルを解凍すると、sie.jsを手に入れることができます

今後の予定

ほぼ、SMILアニメーションの要素と属性を実装できましたので、どの要素と属性が使えるのかを、この開発日誌で公開します

2016-08-02

SIE 29 beta の公開

ベータ版のSIE 29 beta

本日、ベータ版としてSIE 29 betaを公開しました。MITライセンスに移行するなど、変更があります

ダウンロード

sie29.zip (ZIP形式, 342.7KB)をダウンロードして、解凍すれば、sie.jsを手に入れることができます

今後の予定

今回からEdgeもテストの対象とすることにしました。IE11とEdgeでのテストをしたうえで、正規版をリリースします

2016-07-26

animateMotion要素のrotate属性をサポート

rotate属性の実装

今、animateMotion要素のrotate属性を実装しました。これで、モーションパスとモーショントゥイーンができるようになって、ほぼすべてのSMILアニメーションの要素と属性は実装が済みました。バグの修正に注力していきます。今回の変更は次回のリリースで反映されます

今後の予定

テストをした後で、新しいリリースを公開します