関数ポインタを利用した文字列の入出力

関数ポインタを利用した文字列の入出力の例です。

関数ポインタ（int (*func_p)(char **, int *);）により、文字列を入力する関数、出力する関数を交互に呼び出し、文字列の入出力を行なっています。

実行結果

ソートアルゴリズムの比較

ソートアルゴリズムを各種準備し（昇順、降順含む）、その計算時間を比較した例です。

単純に値の大小を比較し並べ替えるシンプルなソート、C言語でクイックソートを実装したもの、qsort 関数によりクイックソートを行うもの、の 3 種類準備しています。
100,200,400,800,1600,3200,6400,12800,25600,51200,102400 個（計11回の処理時間比較）の値を並べ替えた際の計算時間結果は以下のグラフになっています（Y軸はログスケール）。

（黒：シンプルソート、赤：クイックソート、青：qsort 関数）

グラフを見てみると、それぞれ指数関数的に計算時間が増えていることが分かりますが、それぞれの傾きが異なり、qsort よりも自前のクイックソートを用いた処理時間が短いことが分かります。
（コンパイルオプションには -ffast-math -O4 を指定）

CPUや処理系にも依存する部分ですが、102400 個程度の配列では 1 秒にも満たない時間なので、どちらでも良さそうですが、非常に大きな配列を扱う場合には参考になるかと思います。


実行結果

qsort を用いたソート

C言語の標準関数である qsort() 関数を用いたソートの例です。

qsort の引数：

void qsort(void * base, size_t nmemb, size_t size, int (* compar)(const void *, const void *) );
void* base : データ元となるデータを指し示すポインタ用配列
size_t nmemb: 配列の数
size_t size: データの型のサイズ(sizeof で指定)
int (*compar)(const void*, const void*)): ソートで用いる大小比較用関数

qsort() の関数内では、データ元となるデータもしくは配列をそれぞれポインタで指し示し、ポインタが指し示すデータの順番を入れ替えていくことになります。

例題では、

文字列のデータを指し示すポインタ用配列：char* c_table[3];
数値列のデータを指し示すポインタ用配列： int* i_table[5];

のそれぞれのアドレスを

c_table[0] = a; → 配列aの先頭アドレス
i_table[i] = &idata[i]; → idata[]配列のi番目のデータのアドレス

というように指定し、qsort() 関数が指し示されたアドレスの順番を入れ替えていくことになります。

qsort() で指定する大小規定用の関数 compare() は、文字列、数値列用それぞれに準備しています。
compare() の関数は、２つのデータの大小を正負の値を使って表現するような関数を自分で規定するものですが、今回は、単に文字列の長さと、データの大きさで指定しています。

実行結果

はさみうち法による平方根の解法

はさみうち法は、レギュラ・ファルシ (regula falsi) 法とも言います。
例題では、はさみうち法と2分法により平方根を求めています。

はさみうち法と2分法は、連続関数 f(x) と区間 a < = x < = b が与えられたとき、その区間で方程式 f(x)=0 の解を探す方法の一つです。

両端での関数値 f(a),f(b) は異符号でなければなりません。
２点 ([a,f(a)],[b,f(b)]) を直線で結び、それが x 軸と交わる点 c を求める形になります。
その点での関数値 f(c) が f(a) と同符号なら、解は c < x < b にあり f(c) が f(b) と同符号なら解は a < x < c にあります。
このようにして解の存在範囲を狭めることを繰り返します。
しかし、必ずしも２分法より早いとは限りません。
また、区間の両端での関数値の絶対値に大差があると、補間点 c が区間の端点に一致してしまいます。
このような場合は、c を強制的に極わずか (隣の不動小数点数まで) 移動します。

プログラムの tolerance は解の許容誤差（計算機イプシロンを利用）、戻り値は f(x)=0 の解、imax 回繰り返しても収束しないなら 2分法に切り換えます。
(imax=0 で呼び出せば最初から2分法になります。)

Newton 法 による解法に比べ、計算回数が多くなっていることは分かると思います。


実行結果

構造体データの並べ替え

構造体により定義されたデータを並べ替える例です。

本例題では、データの挿入時に日付毎 (char hday) に並べ替えて挿入されるようになっていますが、データ挿入後に再度、別の条件で並べ替えを行っています。

並び替えの部分 (sort_list 関数) では、関数ポインタ (int (* const comp[2])()) により並び替えの手法を変更しています。
また、sort_list 関数に指定する引数により、昇順/降順の指定を行うことができます．

例：
売り上げ金額毎に昇順に並べる：
sort_list(SORT_ASC,&start,uk_compare);
日付毎に降順に並べる：
sort_list(SORT_DESC,&start,date_compare);

→ それぞれの条件を計算するための比較関数を用意し、ASC(昇順)、DESC(降順) を指定しています。


sample.txt

004 東京 20050524 00001 東京商店 25000
003 横浜 20050321 00002 横浜商店 20000
002 千葉 20050103 00001 東京商店 30000
004 東京 20050603 00003 関東商事 15000
004 東京 20050603 00003 関東商事 18000
004 東京 20050603 00003 関東商事 17000
004 東京 20050603 00003 関東商事 16000
004 東京 20050603 00003 関東商事 11000
004 東京 20050603 00003 関東商事 12000

実行結果