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

TList.Sortメソッドを使った整列

TListを使った整列」では、自前でクイックソート のコードを記述しました。ところが、DelphiのヘルプでTListを見ると、Sortメソッドがあることが分かる と思います。これを使えないのでしょうか? 一見、TList型の変数をvalとすれば、val.Sortとするといいような感じがしますが、ヘルプに記述されている 通り、SortメソッドはTListSortCompare型の引数を取ります。

さて、TListSortCompare型とはどのような型なのでしょう。これは、 2つのポインタを引数とし、引数の実体(型キャストしたもの)の大小によって負の値、0、正の値を返す 関数です。 要するに、”TListの要素の型はコンパイラには分からないから、ユーザーが比較する関数を定義してね”と いうことでしょう。

例を用いて使い方を下に示します。このアプリケーションは、フォームに2つのButtonと 1つのLabelが配置されています。Button1を押すと、0から1億の間の整数で3百万個の乱数を発生して ファイルに保存します。Button2を押すと、先ほどのファイルを指定して読み込み、整列を終えたら 新たに指定したファイルに書き込むというものです。Labelには整列に要した時間が表示されます。


unit Unit1;

interface

uses
  Windows, SysUtils, Classes, Controls, Forms,
  StdCtrls, Math, Dialogs;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    OpenDialog1: TOpenDialog;
    SaveDialog1: TSaveDialog;
    Label1: TLabel;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Private 宣言 }
  public
    { Public 宣言 }
  end;

function CompareInteger(item1,item2:Pointer):Integer;	// TListの比較に使う関数をグローバル関数として宣言する
							// これでSortメソッドの引数になることができる

var
  Form1: TForm1;

implementation

{$R *.dfm}

function CompareInteger(item1,item2:Pointer):Integer;	// TListの整列用関数。
begin
Result := PInteger(item1)^ - PInteger(Item2)^;		// TListの要素が整数なのでIntegerのポインタ型でキャストし、
end;							// 実体を^演算子で参照して比較

procedure TForm1.Button1Click(Sender: TObject);
var i: Integer;
    st : TStringList;					// 乱数格納用の文字列リスト
begin
if not OpenDialog1.Execute then exit;			// 乱数保存用ファイルを指定
st := TStringList.Create;
try
i := 0;
while i < 3000000 do
    begin
    Randomize;						// 乱数の種を初期化
    st.Add(IntToStr(RandomRange(0,100000000)));		// 0-100000000の範囲で乱数を生成。Mathユニットが必要
    Inc(i);
    end;
st.SaveToFile(OpenDialog1.FileName);			// OpenDialog1で指定したファイルに保存
finally
    FreeAndNil(st);					// Createしたので必ずFreeする
  end;
end;

procedure TForm1.Button2Click(Sender: TObject);
var i : Integer;
    st : TStringList;					// 乱数ファイル、保存ファイル用の文字列リスト
    val : TList;					// 整数を格納するためのリスト
    pf: PInteger;					// val変数に代入するための整数型ポインタ変数
    tm : Cardinal;					// 経過時間計測用変数
begin
if not OpenDialog1.Execute then exit;			// 乱数ファイルを指定
st := TStringList.Create;
val := TList.Create;
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;					// 現在の時刻を取得
val.Sort(@CompareInteger);				// Sortメソッドを実行
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(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.

コードの説明

TListのSortメソッドを使うと、コードがずいぶんスッキリします。 val.Sort(CompareItneger)とCompareInteger関数を記述するだけで済みます。

TListSortCompare型の関数は、Sort手続きの中で呼び出されるため、 コールバック関数と言われるものです。 コールバック関数を引数で渡す際は、関数のアドレス、即ち”@関数名”で渡します (でも、@を付けなくても渡せてしまうようです。なぜだろ?デフォルトがポインタ渡しなのかも知れません)。 また、CompareIntegerがTListのSortメソッドの引数となるためには、 Form1のメンバー関数ではなくグローバル変数として宣言する必要があります。 Form1のメンバー関数や他の関数のローカル関数にするとSortメソッドの引数に取ることができなくなります。

さらに、Sortメソッドの変数はTListSortCompare型であるため、CompareInteger関数を その型に合うように記述します。 TListSortCompare型は2つのポインタ型の引数を取り、引数1(の実体)より引数2(の実体)が小さい場合は負、 等しい場合は0、大きい場合は正の値を取ります。そのため、CompareIntegerの場合、 実体は整数なので、単にitem1からitem2を引けばTListSortCompare型を満たします。 ちなみに、今回のCompareIntegerでは昇順に整列しますが、降順に整列したい場合は正負が逆になるよう CompareIntegerを記述します(item1とimem2を逆にするだけですね)。

乱数生成はRandomRange関数で行います。乱数生成は関数で行われるようで、 その関数の引数を初期化するために直前でRandomize手続きを呼び出しています。Randomizeしなくても 適当な整数を生成したいだけならば無くてもかまいません。

一般にDelphiでは、プログラマがCreateした変数はFreeしなくてはなりません。 それはTList型の変数valも同様ですが、TList型の場合、単にFreeを行うとItemに格納されたメモリを 解放しないままTList型の変数だけがFreeされてしまい、メモリリークを引き起こします。そのため Itemプロパティにメモリアドレスが確認されているのをAssigned関数で確認し、メモリが確保されている 場合にはDispose手続きでそれを廃棄します。但し、Assigned関数は引数がnilかどうかだけを チェックしていることに注意してください。 例えば、DisposeしたItemをAssigned関数で評価するとTrueと評価されます。 これは、Dispose手続きによってメモリは廃棄されますが、Dispose手続きはメモリ廃棄後にnilを代入しないためです。 そこで、Disposeした後には必ずnilを代入しておくと安心です。(同様に、PackメソッドでTListを 整理するときもItemがnilか否かで判別します。そのため、単にDisposeしてPackしても Count値は変わりません。)

上述のプログラムでは、処理時間を測定するためにSortメソッドの前後で GetTickCountを取得しています。GetTickCountはコンピュータ起動後の時間をミリ秒単位で返す関数です。 GetTickCountが返す型はCardinal型です。そのため、Sortメソッド前後で差を取ることで処理時間を取得 しています。

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