演習問題 第4回 多分探索木(2017、2019年度)
■ 実験用データ
整数集合: 集合の濃度(要素数): 1,000,000、 キーの型: 整数、 ファイル: integer1MR.dat
文字列集合: 集合の濃度(要素数): 100,000、 キーの型: 文字列、 ファイル: wordE100KR.dat
(文字列集合: 英単語集合)
■ 計測値出力単位
整数集合 U = 100,000 (要素数の1/10)
英単語集合 U = 10,000 (要素数の1/10)
■ 集合、パラメーター設定
・学籍番号の最下位桁の値によって、演習問題に対するパラメーター(KKの値)が異なります)
前半のグループ 後半のグループ
集合: 文字列集合 集合: 整数集合
番号 KKの値 KKの値
0: 4 8 12 24, 32, 48
1: 8 12 16 32, 48, 64
2: 12 16 24 48, 64, 96
3: 16 24 32 64, 96, 128
4: 24 32 48 96, 128, 192
5: 32 48 64 128, 192, 256
6: 48 64 96 192, 256, 384
7: 64 96 128 256, 384, 512
8: 96 128 192 384, 512, 768
9: 128 192 256 512, 768, 1024
■ 留意事項
・誤った問題番号、誤った設定値でレポートを提出、また複数の問題に対してレポート提出は受理されません。
4a 多分探索木の記憶効率の検証
指定されたファイルを読み込み、多分探索木を生成する(追加関数)。次数Kを上記のように設定する。1U, 2U, ・・・・・、9U、10Uレコード読み込んだときの各時点で、次の項目を測定する。
高さ、ノード数、最大要素数、構築時間
ここで、最大要素数とは格納可能最大要素数であり、ノード数 × KK の値である。多分木の高さを測定する関数は、2分木の高さを計るプログラムコードが参考になる。
これらの項目を指定されたKKおよび2×KKの値について計測し、以下のような書式で出力する。なお、提出する実行形式ファイル(".exe")は、先頭のKKの際の実行形式ファイルでよい
KK = **のとき
要素数 高さ ノード数 最大要素数 構築時間(msec.)
----------------------------------------------------------
1U ・ ・ ・ ・ ・
2U ・ ・ ・ ・ ・
・ ・ ・ ・ ・
・ ・ ・ ・ ・
9U ・ ・ ・ ・ ・
10U ・ ・ ・ ・ ・
KK = **のとき
要素数 高さ ノード数 最大要素数 構築時間(msec.)
----------------------------------------------------------
1U ・ ・ ・ ・ ・
2U ・ ・ ・ ・ ・
・ ・ ・ ・ ・
・ ・ ・ ・ ・
9U ・ ・ ・ ・ ・
10U ・ ・ ・ ・ ・
KK = **のとき
要素数 高さ ノード数 最大要素数 構築時間(msec.)
----------------------------------------------------------
1U ・ ・ ・ ・ ・
2U ・ ・ ・ ・ ・
・ ・ ・ ・ ・
・ ・ ・ ・ ・
9U ・ ・ ・ ・ ・
10U ・ ・ ・ ・ ・
記憶効率を中心に様々な観点から分析せよ。上記以外の項目も測定することが期待される。
4b 多分木の巡回関数の作成【選択課題: グループ共通】
上記の整数集合ファイルを読み込み、多分探索木を構築する(追加関数)。このとき、多分探索木において、次数 K = 16とする(KK = 32) 。
次の巡回関数を作成する。
全節のキーの昇順出力
上述した多分探索木に対しこの関数を適用し、先頭の512個のキーを出力する。レポートの内容としては、作成した関数のアルゴリズムおよびプログラムコードについての明確かつ詳細な説明を含むものとする。