1台ディスクソーティングの解析

溝口 徹夫  厚井 裕司  

誌名
電子情報通信学会論文誌 D   Vol.J59-D   No.4   pp.237-244
発行日: 1976/04/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(561.2KB)>>
論文を購入




あらまし: 
1台のディスクソーティングの高速化を計るために,本文では置換とマージにおけるソーティング終了に必要な時間の解析を行った.1台ディスクソーティングの所要時間の大きな部分を占めるのはディスクシリンダのシーク回数,シーク距離である.シリンダ数をnとすると,シーク距離は最大,平均共n2,シーク回数は1シリンダ内のデータ数が多くなるとn・lognのオーダー必要であることがここに示された.すなわちオーダーの単位での高速化はできないことが裏付けられた.次に本文では置換についてシーク距離をほぼ最少にするアルゴリズムとその評価を与え,マージについてはシーク順を予測する方法を使って,読出しを行うシリンダへその直前の書込みを行う方法,および内部記憶容量が充分でないときの予測によるシリンダシーク順決定と入力容量決定の方法を示し,共に係数の範囲での高速化を試みた.又,本解析と実現法が仮想記憶を利用したソーティングにも適用できることが論じられた.