擬似乱数の生成にdSFMT ver.2.2を使用して実験してみる。 せっかくなのでSSE2を使用するコードを生成させ、 周期はたぶんデフォルトのDSFMT_MEXP=19937を指定する。 まず、#1のルールにしたがって、一億回ダイスを振ってみる。 dice1.c #include <stdio.h> #include "</stdio.h>…

インクルードガードは必要だよね。 school_record.h #ifndef SCHOOL_RECORD_H_INCLUDED #define SCHOOL_RECORD_H_INCLUDED typedef struct tag_school_record school_record_t; typedef struct tag_grade grade_t; school_record_t *school_record_new(const…

インタフェイスを実装する。 school_record.c #include <stdlib.h> #include <string.h> #include "school_record.h" struct tag_school_record { char *name; const grade_t *maths; const grade_t *physics; }; typedef enum { EGRADE_A = 5, EGRADE_B = 4, EGRADE_C = 3 } egr</string.h></stdlib.h>…

成績が列挙型で公開されていたので隠すように変更する。 school_record.h typedef struct tag_school_record school_record_t; typedef struct tag_grade grade_t; school_record_t *school_record_new(const char *name, const grade_t *maths, const grade…

安定な整列の有用性の例として基数ソートを挙げたが、 そんな狭い問題領域の話ではね、ということもあるだろう。 ということで、唐突に、学生の二つの教科の成績が一塊のレコードであるようなデータの整列の話。 school_record.h typedef struct tag_school_…

前回の計測結果は大まかな傾向しか見えず、プロット点が少ないと思うので増やしてみた。 ...snip int main(void) { const int nelems[] = {1000, 1778, 3162, 5623, 10000, 17782, 31623, 56234, 100000, 177828, 316228, 562341, 1000000}; const int ntria…

これまで比較による整列に遠慮していたので、 非比較による基数ソートのみで所要時間を計測して時間計算量をみてみる。 ...snip int main(void) { const int nelems[] = {3162, 10000, 31623, 100000, 316228}; const int ntrials[] = {2000, 632, 200, 63, …

#92の処理時間計測プログラムでは基数ソートの計測をするにはデータサイズが小さいようである。 ...snip int main(void) { const int nelems[] = {500, 707, 1000, 1414, 2000, 2828, 4000}; const int ntrials[] = {200, 140, 100, 70, 50, 35, 25}; ...sni…

非比較整列法であるバケツソートを利用した基数ソートでは、 整列にどれくらいの時間がかかるのか計測してみる。 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <time.h> #include "intlist.h" static intlist_t rsort(intlist_t list, int n) { int i, s; intlist_t buck</time.h></assert.h></stdlib.h></stdio.h>…

これまで、基数ソートにおけるステップごとの整列アルゴリズムに隣接交換法を使ってきた。 そのためこの基数ソートは要素数の二次オーダ、もしくはリストの実装次第ではそれ以上の時間計算量となる。 今回は、in-placeな整列という前提を崩すことになるが、 …

RAND_MAXを表現するときに必要なビット数を4ビット単位で。 セットされている最上位ビットの位置を見るのでもいいかもしれないがシンプルに。 #include <stdio.h> #include <stdlib.h> int main(void) { int i, n = 0; for (i = RAND_MAX; i != 0; i /= 16) n++; printf("%d %d\</stdlib.h></stdio.h>…

前回の二つの例の結果から見えてくるように、 整数値の各桁を構成する数字にその整数値の符号を付けたもので順位を比較するようにした場合、 最後の符号による比較は不要になる。 それより前の段階で、負数よりも非負数の方が順位が上になるように自然に定義…

負数から10進数での各桁の数字を取り出すときに9からその数字を減じた値でもって比較した。 つまり、10進法での9の補数で順位を定義したことになる。 しかし、わざわざ補数表現にせずに、 負数の場合はその桁の数字に負符号を付けたものを値とすることでも問…

これまで3桁の自然数という範囲にリスト要素の値がある場合の基数ソートだったが、 桁数に制限は付くのは同じだが負の場合も含む整数値に拡大した時の整列について。 とりあえず10進数一桁を単位とする基数ソートで行ってみる。 #include <stdio.h> #include <stdlib.h> #includ</stdlib.h></stdio.h>…

前回、十進数での一桁単位で基数ソートを行ったわけだが、 別に十進数一桁でなければならないなんてことはない。 ...snip static int issup(cintelem_t p, cintelem_t q, void *base) { return intelem_get_val(p) / (int)base % 16 > intelem_get_val(q) / …

同じ順位の要素の順序が入れ替わっても別に問題ないと言われればそうなのだが、 整列法が安定であると便利な使い方もできる。3桁の自然数が収められたリストを昇順に整列することを考える。 これはこれまでやってきたことであり、 普通に各要素の自然数間の…

前回示したように基本選択法は隣接交換法に比べて時間性能が随分よくなっている。 しかし、基本選択法には、問題にしなくていいのなら問題にならないが、 場合によっては困ったことになるようなある性質がある。 #include <stdio.h> #include "intlist.h" #define UNU</stdio.h>…

例によって整列に要する時間を計測する#71のプログラムに基本選択法の整列コードをリンクして実行する。 単連結リストintlistを利用した場合、 # nelems ncmps nswps elapsed 200 19900.0 194.2 36.5 300 44850.0 293.8 78.1 400 79800.0 393.5 135.4 600 17…

単連結リストを双方向連結リストに書き換えたときと同じで、 整列関数listsortのインタフェイスを変えたわけではないため、 今まで作ってきたlistsortを利用するコードはそのまま使える。 例によって、#65のコードをlistsort-s.cのオブジェクトとリンクする…

整列のアルゴリズムとしてこれまで隣接交換法のみで実装してきたが、他の方法を使ってみよう。 これまでリストの実装の変更などで行っていたのと同様に、 整列関数のインタフェイスはそのままにlistsortの実装を基本選択法に書き換える。 listsort-s.c #incl…

単連結リストを用いた#71のコードによる整列の所要時間の計測を双方向連結リストで行ってみる。 コンパイル時に-DNOSORTオプションを与えて整列処理なしで実行すると、 # nelems ncmps nswps elapsed 200 0.0 0.0 0.0 300 0.0 0.0 0.0 400 0.0 0.0 0.0 600 0…

intdlist.cはintlist.cと共通のインタフェイスを介して呼び出されるので、 これまでintlist.cをリンクしていたプログラムについて、 替わりにintdlist.cをリンクしてもどれも問題なく動作するはずである。 例えば、#65のコードをコンパイルしたものをintdlis…

双方向連結リストでインタフェイスintlist.hを実現してみた。 intdlist.c #include <stddef.h> #include <stdlib.h> #include <assert.h> #include "listsort.h" #include "intlist.h" #define UNUSED_ARG(x) (void)(x) struct tag_intlist { intelem_t head; intelem_t tail; unsigned lon</assert.h></stdlib.h></stddef.h>…

タイトルから外れる気もするが、intlistの実装を双方向連結リストに変更してみる。 インタフェイスは変更しないので利用する側からは今までと全く変わらない扱いができるはずだ。 双方向連結リストのデータ構造にはバリエーションがある。 とりあえず、リス…

整列処理の途中で対象のリストが整列済みになっても最後まで整列処理を続けるバージョンのlistsortをリンクして、 前回と同じ測定プログラムを実行してみる。 # nelems ncmps nswps elapsed 200 19900.0 9878.0 307.3 300 44850.0 22434.0 929.7 400 79800.0…

整列に要する時間を実測して整列処理の時間計算量に関して考えてみる。 #include <stdio.h> #include <stdlib.h> #include <time.h> #include "intlist.h" #define UNUSED_ARG(x) (void)(x) static int issup(cintelem_t p, cintelem_t q, void *arg) { UNUSED_ARG(arg); return intelem</time.h></stdlib.h></stdio.h>…

整列順と完全に逆順に並んでいる場合と既に整列させたい順序に並んでいる場合について、 整列処理時の比較と交換の回数とリストの要素数との関係を見てみる。 #include <stdio.h> #include "intlist.h" #define UNUSED_ARG(x) (void)(x) static int issup(cintelem_t </stdio.h>…

一通りの走査で隣接要素の交換が一度も行われなかった場合に整列処理を打ち切るという変更を行ったわけだが、 ついでなので、順序が逆だが、この変更前のものについても前回行ったように無用な比較を行わないように変える。 これまで述べたようにそうしなく…

無用な比較は最初のループ以外のループであるので、listsort関数の listsort.c ...snip for (; b == 0 && q != next(list, head(list, listarg), listarg); q = s) { ...snip while (p != q) { ...snip if (issup(p, s, arg)) { ...snip の部分、二回目以降…

推測にしたがって何と何を比較しているかの詳細を見てみる。 そのために前回のコードで整列用に提供している順位定義関数issupに一文付け加える。 ...snip static int issup(cintelem_t p, cintelem_t q, void *arg) { UNUSED_ARG(arg); printf("issup: %d, …