TOPページへ戻る  PCページへ戻る  一覧へ戻る

整列の速度比較とより早く整列するTips

TListを使った整列」の自前でコードを書いた クイックソートと、「TList.Sortメソッドを使った整列」のSortメソッド を使った整列とどの程度差があるか比較してみました。TList.Sortメソッドを使う方には、整列時間を 計測できるコードがあるのでそれを使いました。一方、自前のコードを書いた方も、下に示すような TList.Sortメソッドを使ったコードを一部修正したコードを使いました。修正や追記した箇所は黄色で 表示されています。


procedure TForm1.Button2Click(Sender: TObject);
var i : Integer;
    st : TStringList;					// 乱数ファイル、保存ファイル用の文字列リスト
    val : TList;					// 整数を格納するためのリスト
    pf: PInteger;					// val変数に代入するための整数型ポインタ変数
    tm : Cardinal;					// 経過時間計測用変数
    QS : TSorts;					// クイックソート用変数
begin
QS : =TSorts.Create;					// クイックソートが使えるようTSortsを作成
st := TStringList.Create;
val := TList.Create;
if not OpenDialog1.Execute then exit;			// 乱数ファイルを指定
try
st.LoadFromFile(OpenDialog1.FileName);			// ファイル内文字列を読み込み
i := 0;
while i < st.Count do
    begin
    New(pf);						// メモリの確保
    try	
    pf^ := StrToInt(st[i]);				// 文字列リストを整数に変換し、整数型ポインタpfの実体に代入
    val.Add(pf);					// リストにポインタを追加
    except
        Dispose(pf);					// 整数への変換に失敗したら確保したメモリを解放
      end;
    Inc(i);
    end; 
tm := GetTickCount;					// 現在の時刻を取得
QS.QuickSort(val,0,val.Count-1);				// クイックソートを実行
tm := GetTickCount - tm;				// Sortの処理時間を計算

Label1.Caption := '経過時間: '+FloatToStr(tm/1000)+' 秒';	//処理時間を表示

if not SaveDialog1.Execute then exit;			// 保存用ファイルの指定
st.Clear;						// 文字列リストの要素を廃棄
i := 0;
while i < val.Count do
    begin
    st.Add(IntToStr(Integer(val[i]^)));			// リストの整数を文字列リストに追加
    Inc(i);
    end;
st.SaveToFile(SaveDialog1.FileName);
finally
    FreeAndNil(QS);					// CreateしたのでQSortをFreeする
    FreeAndNil(st);					// CreateしたものはFree
    i := 0;						// TListをFreeする前に、TListが保持するメモリを解放
    while i < val.Count do
        begin
        if Assigned(val[i]) then Dispose(val[i]);	// val[i]がメモリを参照していればそれをDisposeで解法
        val[i] := nil;					// val[i]の参照をnilにする(無くても良い)
        Inc(i);
        end;
    FreeAndNil(val);
  end;
end;

end.

比較結果

300万個の乱数を5回発生させ、そのファイルを各方法で整列した際の処理時間を下に示します。

1個目 2個目 3個目 4個目 5個目
自前のコード 3.078 3.110 3.250 2.969 3.078
Sortメソッド 5.688 5.687 5.656 5.625 5.687

TList.Sortメソッドを使った方が自前でコードを書くより1.8倍くらい時間が掛かっています。 TList.Sortメソッドで使われる整列方法に問題があるのかどうかを検証するため、TList.Sort メソッドで使われているQuickSortメソッドと等価のコードを書いてみました。 (TList.Sortで使われるQuickSort手続きは、{Delphiインストールフォルダ}\Source\Rtl\Common\Classes.pas のQuickSort手続きです。)
 具体的なコードは下のようになります。


unit QSort;

interface

USES Classes;

type
  TSorts2 = class(TObject)
    destructor Destroy;reintroduce;
  public
    procedure QuickSort2(Val:TList;start,last:integer);
  end;

implementation

destructor TSorts.Destroy;
begin
inherited Destroy;
end;

procedure TSorts2.QuickSort2(Val:TList;start,last:integer);
var
  i,j,n,m: Integer;
  t : Integer;
  S : String;
begin
repeat
i := start;
j := last;
n := Integer(val[(i+j) div 2]^);			// 比較の基準値を配列の中央の値に設定
    repeat
      while Integer(val[i]^) < n do			// 配列の昇順に、基準値より大きい値を検索
        Inc(i);
      while Integer(val[j]^) > n do			// 配列の降順に、基準値より小さい値を検索
          Dec(j);
      if i <= j then					// 入れ替え
            begin
            t := Integer(val[i]^);
            Integer(val[i]^) := Integer(val[j]^);
            Integer(val[j]^) := t;
            Inc(i);
            Dec(j);
            end;
    until i > j;					// iとjが交差するまで繰り返す
    if start < j then				// 開始よりも降順に検索したjが大きい場合、
      QuickSort2(val,start,j);				// QuickSort2を実行
    start := i;						// 先頭位置を更新
  until i >= last;					// ここまでの手順を昇順に検索したiが終了値
end;							// を越えるまで実施

end.

先ほどの結果に合わせて、上のコードで整列した際の結果を下に記します。

1個目 2個目 3個目 4個目 5個目
自前のコード 3.078 3.110 3.250 2.969 3.078
Sortメソッド 5.688 5.687 5.656 5.625 5.687
Classes.pasの方法 2.844 2.735 2.688 2.688 2.734

結果はごらんの通り、Classes.pasのアルゴリズムの方が自前で書いたものより高速でした。 自前で書いたコードでは、基準値と配列の先頭を入れ替えて後から戻すという工程がある分、遅くなった ようです。また、いろいろ調べてみたら、Classes.pasのアルゴリズムの方が一般的なようでした。 うーん、勉強不足・・・。

さて、TList.Sortメソッドで使われるQuickSortが整列の速度低下の要因ではない ことが分かりましたが、他に特に速度を下げるような処理は見あたりませんでした。 強いて言えば、CompareIntegerをコールバックすることぐらいでしょうか。。。 ちなみに、「数値配列の整列 〜QuickSort〜」でのように、 TListを使わずに動的配列を用いて先述の5つのファイルを整列した場合、さらに高速になります。 これは、TListのItemプロパティを呼び出すのに時間が掛かることを意味していると思われます。

1個目 2個目 3個目 4個目 5個目
自前のコード 3.078 3.110 3.250 2.969 3.078
Sortメソッド 5.688 5.687 5.656 5.625 5.687
Classes.pasの方法 2.844 2.735 2.688 2.688 2.734
動的配列(Classes.pasのアルゴリズム使用) 0.985 0.969 0.984 0.969 0.985

TOPページへ戻る  PCページへ戻る  一覧へ戻る