ソート
　　

update: 10/10/2006


ソートアルゴリズムの改良の話。そのベンチマークレポートです。




Top Page へ


Contents





◎　ソートの仕組み 




◎　MaxAverage Sort




◎　ベンチマーク




◎　ベンチマーク評価値あれこれ 




◎　文献







◎ 　ソートの仕組み

代表的なソートには、次のものがあります。

(1) 隣接交換法 ( Adjacent exchange method )

      隣接する値を 1つ ずつ比較して、順序を交換していく

(2) 二分探索法 ( Binary Search )

      平均値などで、数値を 2つの部分配列に分け、
      できた部分配列をさらに二分探索してゆく。

もとの配列がソートしやすいものかどうかで、
計算回数は大きく変化しますが、要素数が n の時、
(1) n２  (2) nlog2n  のオーダーで計算回数は
増加していくと定義されています。演算回数では、
二分探索法の方が早いですが、プログラムの記述的には、
隣接交換法が最も簡単で作成時間が少なくすみます。

　

top 





◎ MaxAverage Sort 

隣接交換法をファイル数の少ない場合に限定して、
ファイル数の多い場合は、MaxAverage Sort (仮名)を使います。。

これは学生アルバイトでやった仕分け作業の流れからひらめきました。
渦中の物流系企業で時代の流れに残った方式だけあり、
少人数でも大量の仕分け物に対応できるのだと思います。

そのアルゴリズムを以下に説明します。

① 配列の中から、最大値(max)と平均値(ave)を計算します。

② 最大値が判明したので、配列長を 1 減らします。

③ 残りの配列を平均値と比較して、２つの部分配列に分けます。

④ ２つの部分配列をそれぞれ、隣接交換法します。

つまり、①～③までの処理により、演算オーダーを
半分にしています。


top 





◎ ベンチマーク 

テキストファイルに１～２５の "google" と書いてあるファイル
１００個を作成しました。ファイル名読み込み順が早いものから、
"google"と書く回数を増やしていきます。検索結果のソート時は、
なるべく比較、交換が多くなることになります。

演算回数による比較



 演算の種類隣接交換法MaxAverage Sort


 if 文比較65864829 (0.73)


 変数宣言716


 数値代入1856415032


 算術計算1945514996




演算時間による比較



 演算の種類 演算１回あたりの処理秒[ms]隣接交換法MaxAverage Sort


 if 文比較 0.6944570.73351.3


 変数宣言 1.2008.419.2


 数値代入 1.38825766.820864.4


 算術計算 1.11521692.316720.5


 合計処理時間 -52038.240955.4 (0.79)





理論的演算比は 10000：5000+α なので、演算回数・処理時間は、
半分ぐらいになる可能性がありますが、今回のベンチマークテストでは、
比較回数は0.73倍、演算処理時間で0.79倍の性能向上が達成されました。
実際には、5秒:4.5秒ぐらいですが...  (^-^）

結論として、MaxAverage Sort による前処理による負担は有効で、
後処理の隣接交換法の負荷を確かに減少させており、
演算理論を実証していると言えます。今回のプログラムは、
無駄な部分も多く、良く設計されたフローチャートでは、
理論的演算比への接近が可能と思います。
 

top 






◎ 　ベンチマーク評価値あれこれ




 ベンチマーク名正式名称評価方法


 TPCTransaction
Processing
Council		TPC-C （１分あたりのトランザクション処理数）

＄/tmpC (１トランザクションあたりのコスト）などがある


 SPECintStandard
 
Performance
 Evaluation
 Corporation
 int		整数計算のための値で、基準マシンと比較した
処理時間の相対値


 


 






top 





◎ 　文献

・情報処理教科書「ソフトウェア開発技術者」日高哲郎著　翔泳社



top 






  調査レポート作成 :tmlbworks