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

gnuplotの回帰分析機能を使って、 所要時間を要素数の冪関数へフィッティングして、そのパラメータを求めてみる。 f(x,a,b) = a * x + b fit f(x,a4,b4) 'plot2.dat' using (log($1)):(log($3)) via a4, b4 fit f(x,a5,b5) 'plot2.dat' using (log($1)):(log…

単連結リストを用いた#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の実装を双方向連結リストに変更してみる。 インタフェイスは変更しないので利用する側からは今までと全く変わらない扱いができるはずだ。 双方向連結リストのデータ構造にはバリエーションがある。 とりあえず、リス…

所要時間が要素数の三次のオーダになるのは、 整列機能がリストに求める交換処理機能が任意の要素二つを指定しての交換であるからである。 その場合、一つ前の要素を得るという処理が必須であり、 リストを先頭方向にたどることができないという純粋な単連結…

直線的なプロット点が描かれれば直線を引きたくなるのは当然である。 gnuplotには回帰分析を行って与えられた関数に当てはめる機能があるので、 これを使って直線のパラメータを求めてみる。 f(x,a,b) = a * x + b fit f(x,a1,b1) 'plot1.dat' using (log($1…

数値では分かりにくいので、横軸を要素数、縦軸を操作回数や所要時間で両対数プロットしてみる。 プロットには超定番gnuplotを使う。 set key left top set logscale xyy2 set pointsize 1.5 set xlabel "number of elements in a list" set ytics nomirror …

整列処理の途中で対象のリストが整列済みになっても最後まで整列処理を続けるバージョンの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, …

さて、intlistを使ってみよう。 #include <stdio.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_get_val(p) > intelem_get_val(q); } static intlist_t make</stdio.h>…

計数処理についてなんとかなりそうなのでintlistの全体をコーディングしてみる。 intlist.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; unsigned lo</assert.h></stdlib.h></stddef.h>…

さて。#60の最後で書いたように、 > 利用者が提供する比較処理にカウント処理を埋め込むことはできない わけで、それならどうするかを考える必要がある。 利用者が提供する比較処理中に利用者自身が計数処理の埋め込みを強制させないのなら、 リスト側で利用…

インタフェイスで定義した不完全型を具象化する構造体の定義を考える。 struct tag_intlist { intelem_t head; unsigned long compare_counts; unsigned long swap_counts; }; struct tag_intelem { int val; intelem_t next; }; struct tag_intiter { intel…

とりあえず整数値を持つ要素のリストのインタフェイスを宣言しておく。 intlist.h #ifndef INTLIST_H_INCLUDED #define INTLIST_H_INCLUDED typedef struct tag_intlist *intlist_t; typedef const struct tag_intlist *cintlist_t; typedef struct tag_inte…

役に立つといっても単に整列処理時にリスト側で用意した処理が何回くらい呼び出されたかをカウントできるものを、という程度。 この機能はリスト側が用意し、利用者にその情報を提供するようにする。 単なるカウント処理でなく利用者が任意の処理を埋め込め…

計算量の話とかやってるので、それに役立つようなリストを作ってみようと思う。

前回の方針に従ってlistsortを変更する。 インタフェイスは変えないのでヘッダファイルに変更はない。 listsort.c #include "listsort.h" void listsort( void *list, void *(*head)(const void *, void *), void *(*next)(const void *, const void *, void…

最近、リストの実装特異的な話題ばかりだったので、本来の題目の整列関係について。 整列関数listsortは隣接交換法を使ってリストの要素を整列している。 隣接交換法ではリストの要素を要素数個回走査するため要素数の二次オーダの平均時間計算量になるが、 …

実際の整列処理においてはどの程度時間的性能が変化しているのか確かめてみた。 次のような計測プログラムを書いた。 test_ilist2_2.c #include <stdio.h> #include <stdlib.h> #include <time.h> #include "ilist2.h" #define UNUSED_ARG(x) (void)(x) static int issup(ielem_t p, iel</time.h></stdlib.h></stdio.h>…

前回書いた関数prev2をilist2.cに組み込み、適当にリストを整列させてみる。 ilist2.c ...snip 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 &…

前回述べた二つの要素の一つ前の要素を同時に求める関数を書いてみる。 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</assert.h></time.h></stdlib.h></stdio.h>…

ilistやilist2、ilist3で定義している関数prevは、 与えられた要素の一つ前の要素を返す関数だが、 単連結リストであるがゆえにその時間計算量は要素数の一次オーダーになる。 この性能は純粋な単連結リストであれば緩和のしようがないと思う。 ここでの問題…

以前に行ったようにインタフェイスを介さずに参照からリストの情報を見たり操作したりできるだろうか。 #include <stdio.h> #include <stdlib.h> #include <time.h> #include "ilist3.h" #define UNUSED_ARG(x) (void)(x) static int issup(ielem_t p, ielem_t q, void *arg) { UNUSED_A</time.h></stdlib.h></stdio.h>…