演習問題 第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) 比較回数、実行時間等、測定結果をプログラムの最後に出力する。