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