|
「TListを使った整列」では、自前でクイックソート
のコードを記述しました。ところが、DelphiのヘルプでTListを見ると、Sortメソッドがあることが分かる
と思います。これを使えないのでしょうか？
一見、TList型の変数をvalとすれば、val.Sortとするといいような感じがしますが、ヘルプに記述されている
通り、SortメソッドはTListSortCompare型の引数を取ります。
さて、TListSortCompare型とはどのような型なのでしょう。これは、
2つのポインタを引数とし、引数の実体（型キャストしたもの）の大小によって負の値、0、正の値を返す
関数です。
要するに、”TListの要素の型はコンパイラには分からないから、ユーザーが比較する関数を定義してね”と
いうことでしょう。
例を用いて使い方を下に示します。このアプリケーションは、フォームに２つのButtonと
１つの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メソッド前後で差を取ることで処理時間を取得
しています。
|