演習問題 第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個のキーを出力する。レポートの内容としては、作成した関数のアルゴリズムおよびプログラムコードについての明確かつ詳細な説明を含むものとする。