演習問題 第5回 B木(2016、2018年度)
■ 実験用データ
整数集合: 集合の濃度(要素数): 1,000,000、 キーの型: 整数、 ファイル: integer1MR.dat
文字列集合: 集合の濃度(要素数): 100,000、 キーの型: 文字列、 ファイル: wordE100KR.dat
(文字列集合: 英単語集合)
■ 計測値出力単位
整数集合 U = 100,000 (要素数の1/10)
英単語集合 U = 10,000 (要素数の1/10)
■ 集合、パラメーター設定
前半のグループ: 文字列集合、 後半のグループ: 整数列集合
・学籍番号の最下位桁の値によって、演習問題に対する集合、パラメーター(対象集合、等)が異なります)
番号 KKの値
0: 4, 8, 12
1: 8, 12, 16
2: 12, 16, 20
3: 16, 20, 24
4: 20, 24, 28
5: 24, 28, 32
6: 28, 32, 36
7: 32, 36, 40
8: 36, 40, 44
9: 40, 44, 48
・4bは選択問題です。
■ 留意事項
・誤った問題番号、誤った設定値でレポートを提出、また複数の問題に対してレポート提出は受理されません。
5a B木の記憶効率
指定されたファイルを読み込み、指定された次数KK( = K × 2)でB木を生成する(追加関数)。このとき、U要素単位で、以下の項目を計測する。
(a)木の高さ、 (b)節(ノード)数、 (c)格納可能要素数、(d)構築時間
格納可能要素数(c): KK × 節数
出力書式のイメージは以下のとおり。
多分探索木(KK = **)
格納要素数 高さ 節数 格納可能要素数 構築時間(ミリ秒)
1U *** *** ****** **.**
2U *** *** ****** **.**
・ ・ ・ ・
・ ・ ・ ・
9U *** *** ****** **.**
10U *** *** ****** **.**
B木の高さ計測については、多分探索木の高さ計測用プログラムコードがそのまま使用できる(あたりまえです!!)。
上記操作を3種類のKKに対して行う。
異なる3種類のKKに対する上記計測結果を比較し、様々な観点から分析せよ。さらに、多分探索木(前回の演習課題4a)の計測結果と比較することが望ましい(両者の記憶効率の相違が明確に理解できる)。なお、提出exeファイルは、1つのKKについてのB木main関数のexeファイルだけでよい。
5b 巡回関数の作成【選択問題】
指定されたファイルを読み込み、B木を構築する(追加関数)。このとき、B木において、次数 K = 8とする(KK = 16) 。
次の巡回関数を作成する。
void out_leafA(NODE *) : 葉のキーの昇順出力
構築したB木に対しこの関数を適用し、先頭(最左端)から10個の葉にあるキーを出力する出力する際に、1つの節の要素を出力後に空白行を出力する。レポートの内容としては、作成した関数のアルゴリズムおよびプログラムコードについての明確かつ詳細な説明を含むものとする。
◆演習問題プログラム作成における注意事項
下記の要件を必ず満たすようにプログラムを作成せよ。
(1) 最初に読み込むファイル名は絶対パスとしてmainプログラム中で記述し、コマンドライン上の引数による指定、およびリダイレクトによる入力指定はしないこと。
例. char infile[80] = "/home/algorithm_data/texte.dat" ;
(2) 比較回数、実行時間等、測定結果をプログラムの最後に出力する。