第1回 TListの実装と性能

2009/2/12

TList

　それではTListについて見ていきましょう。Delphiのコードは、Delphiのインストールディレクトリを基点として、Source\win32\rtl\common\classes.pasにあります。

　TListは、内部的には配列の拡張として実装されています。配列の大きさの最大値は MaxInt（DelphiではLongもIntも32ビットです）を16で割った値（134217728）になります。この数を超えてTListに要素を保持させたいのであれば、ちょっとした改修が必要になります。

　どうして最大値が固定なのかというと、array[0..MaxCount-1] of Pointerという配列の型を定義しておいて、後で動的にメモリを確保することで動的配列を実現しているからです。この内部の配列は、TListのPrivateのメンバーFListとして定義されています。

TList→FList→動的に確保されたポインタの配列

　配列を使って実装されてはいるものの、TListでは以下の各メソッド／プロパティが使用できます。

TList.Count;	データの個数を返す
TList.Insert[idx, p];	データを挿入する
TList.Items[idx];	データを返す／データを変更する
TList.Delete[idx];	データを削除する

　しかし、Insert／Deleteは配列を使用しているため、以下のような問題が発生します。

　つまり、1つの要素を挿入／削除するたびに最大ですべての要素を1つずつずらして移動する必要が出てきます。n個の要素がある場合、操作にかかる時間はnに比例するわけで、これをO(n)と表します。

　実際に、Insert／Deleteを実行するベンチマークを実施してみました。結果は以下のとおりです。単位は秒です。1日は86400秒ですから、1000万行のInsert／Deleteには約1日かかってしまっています。これでは困りますね。

TListのInsert／Deleteの実行時間（単位秒）：

TList Insert 100,000 needs 4.328
TList Delete 100,000 needs 4.172
TList Insert 1,000,000 needs 424.031
TList Delete 1,000,000 needs 413.233
TList Insert 10,000,000 needs 78575.384
TList Delete 10,000,000 needs 82193.337

TLinkList

　TListの実装と性能がある程度つかめたところで、通常リストといえばコレ！といわれる、リンクリストを実装してみます。リンクリストの特徴は、各データはそれぞれ独立したメモリ領域に保持されていて、各要素間はポインタで接続しているということです。

　こうすることで、リストへのデータの挿入／削除は、どの位置で実行しても同じ時間で完了することができるようになります。つまり、O(1)になるわけです。

【注】
O-記法については、ランダウの記号を参照してください

　TLinkListの各要素は、必要なときにメモリに確保されて、不要になったら破棄されるようにします。ある意味、原理主義的なリンクリストの実装をやってみました。

unit LinkList;



interface



uses

  Windows, SysUtils, Classes;



type

  PLinkListItem = ^TLinkListItem;



  TLinkListItem = record

    Prev : PLinkListItem;

    Item : Pointer;

    Next : PLinkListItem;

  end;



  TLinkList = class(TObject)

  private

    FCount: Integer;

    FBOF  : PLinkListItem;

    FEOF  : PLinkListItem;

  protected

    function Get(Index: Integer): Pointer;

    procedure Put(Index: Integer; Item: Pointer);

    function Search(Index: Integer): PLinkListItem;

  public

    constructor Create;

    destructor Destroy; override;

    function Add(Item: Pointer): Integer;

    procedure Delete(Index: Integer);

    procedure Insert(Index: Integer; Item: Pointer);

    property Count: Integer read FCount;

    property Items[Index: Integer]: Pointer read Get write Put; default;

  end;



implementation



{ TLinkList }



function TLinkList.Add(Item: Pointer): Integer;

var

  LinkListItem:PLinkListItem;

begin

  new(LinkListItem);

  FEOF.Prev^.Next    := LinkListItem;

  LinkListItem^.Prev := FEOF.Prev;

  FEOF.Prev          := LinkListItem;

  LinkListItem^.Next := FEOF;

  Inc(FCount);

  result := FCount;

end;



constructor TLinkList.Create;

begin

  inherited;



  //BOFとEOFを構成する

  new(FBOF);

  new(FEOF);

  FBOF^.Prev := nil;

  FBOF^.Next := FEOF;

  FEOF^.Prev := FBOF;

  FEOF^.Next := nil;

end;



procedure TLinkList.Delete(Index: Integer);

var

  i : integer;

  LinkListItem:PLinkListItem;

begin

  //引数の範囲チェックと例外処理

  if (FCount - 1 < Index) then

    raise Exception.CreateFmt('Index=%d is Exceed List Count',[index]);

  if (Index < 0) then

    raise Exception.Create('Index must be Exceed Zero');



  LinkListItem := FBOF;

  for i := 0 to Index do

  begin

    LinkListItem := LinkListItem^.Next;

  end;



  //削除対象のLinkListItemの前後をつなぎ合わせる

  LinkListItem^.Prev^.Next := LinkListItem^.Next;

  LinkListItem^.Next^.Prev := LinkListItem^.Prev;



  //リンクから外れたLinkListItemを破棄する

  dispose(LinkListItem);



  Dec(FCount);

end;



destructor TLinkList.Destroy;

var

  i : integer;

begin

  if (0 < FCount - 1) then



  //確保したメモリをすべて破棄する

  for i := 0 to FCount - 1 do

  begin

    Delete(0);

  end;



  dispose(FEOF);

  dispose(FBOF);



  inherited;

end;



function TLinkList.Get(Index: Integer): Pointer;

var

  LinkListItem:PLinkListItem;

begin

//引数の範囲チェックと例外処理

  if (FCount - 1 < Index) then

    raise Exception.CreateFmt('Index=%d is Exceed List Count',[index]);

  if (Index < 0) then

    raise Exception.Create('Index must be Exceed Zero');



  //リンクを指定位置までさかのぼる

  LinkListItem := Search(Index);



  result := LinkListItem^.Item;

end;



procedure TLinkList.Insert(Index: Integer; Item: Pointer);

var

  LinkListItem, newLinkListItem:PLinkListItem;

begin

  //引数の範囲チェックと例外処理

  if (FCount < Index) then

    raise Exception.CreateFmt('Index=%d is Exceed List Count',[index]);

  if (Index < 0) then

    raise Exception.Create('Index must be Exceed Zero');



  //リンクを指定位置までさかのぼる

  LinkListItem := Search(Index);



  new(newLinkListItem);



  //新しいLinkListItemと前後をつなぎ合わせる

  LinkListItem^.Prev^.Next := newLinkListItem;

  newLinkListItem^.Prev    := LinkListItem^.Prev;

  LinkListItem^.Prev       := newLinkListItem;

  newLinkListItem^.Next    := LinkListItem;



  Inc(FCount);

end;



procedure TLinkList.Put(Index: Integer; Item: Pointer);

var

  LinkListItem:PLinkListItem;

begin

  //引数の範囲チェックと例外処理

  if (FCount - 1 < Index) then

    raise Exception.CreateFmt('Index=%d is Exceed List Count',[index]);

  if (Index < 0) then

    raise Exception.Create('Index must be Exceed Zero');



  //リンクを指定位置までさかのぼる

  LinkListItem := Search(Index);



  LinkListItem^.Item := Item;

end;



function TLinkList.Search(Index: Integer): PLinkListItem;

var

  i : integer;

begin

  Result := FBOF;

  for i := 0 to Index do

  begin

    Result := Result^.Next;

  end;

end;



end.

　それではTLinkListでInsert／Deleteを実行するベンチマークを実施してみましょう。

TLinkListのInsert／Deleteの実行時間（単位秒）：

TLinkList Insert 100,000 needs 0.000
TLinkList Delete 100,000 needs 0.000
TLinkList Insert 1,000,000 needs 0.015
TLinkList Delete 1,000,000 needs 0.016
TLinkList Insert 10,000,000 needs 0.172
TLinkList Delete 10,000,000 needs 0.140

　こうやって見ると、TLinkListの方が、実行時間が短いことがよく分かります。ところが、いったんシーケンシャルにデータをアクセスする段になるとまったく逆の現象が起こってしまいます。

　TListでは、内部構造は配列のため0...nと順次アクセスする場合、ポインタをインクリメントするだけでデータにアクセスすることができる、つまりO(1)で実行できます。TLinkListの場合、内部に現在の位置を保持していれば順次アクセスには、現在のデータを示すポインタ+1の位置を見れば次のデータがあるので、これもO(1)で実行できます。

　ところが、ランダムな位置の値を読み取る場合には、TListでは配列のインデックスを直接加減すればいいので、O(1)でアクセスできますが、TLinkListの場合には、延々とリンクをたどっていかないとたどり着くことができません、つまりO(n)になってしまいます。両者の得意・不得意をまとめると以下のようになります。

	TList	TLinkList
Insert	O(n)	O(1)
Delete	O(n)	O(1)
Search	O(1)	O(n)

　TListとTLinkListでデータの検索（更新／削除）にかかる時間のベンチマークも実施してみましょう。

TListとTLinkListの検索（データ更新／参照）の実行時間（単位秒）：

TList Update 100,000 needs 0.000
TList Reference 100,000 needs 0.000
TList Update 1,000,000 needs 0.000
TList Reference 1,000,000 needs 0.000

TLinkList Update 100,000 needs 7.953
TLinkList Reference 100,000 needs 7.906
TLinkList Update 1,000,000 needs 1507.109
TLinkList Reference 1,000,000 needs 1506.797

　以上のように、Listクラスの異なる実装とそのテストを通して、アルゴリズムが違えば結果が大きく異なることを見てきました。ものすごく総論的にいうと、速度とメモリ使用量がトレードオフの関係にあったり、A機能が速ければB機能が遅かったりといった、トレードオフの関係がそこかしこで発生します。ノーベル物理学賞と文学賞を一遍に受賞できないのと一緒で、あちらを立てればこちらが立たずという関係があるわけです。

　今回の例でいうと、通常リストには最初にだーっとデータを入れていって、何度も参照を繰り返すという使い方が一般的なので、Insert／Deleteが遅くてもSearchが速い配列型の実装の方が実用的だということで、VCLではこちらを採用したのでしょうが、使用目的によってはLinkList型を採用した方が圧倒的に速いという可能性もあるわけです。

　さて、次回はキューを予定しています。また、お会いしましょう。

2/2

Index
TListの実装と性能
	Page1 君は用意されていない処理に対応できるか Delphiでのリスト Listとは何か
	Page2 TList TLinkList

Delphiアルゴリズムトレーニング

　Coding Edgeお勧め記事

	いまさらアルゴリズムを学ぶ意味コーディングに役立つ！アルゴリズムの基本（1）　コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう
	Zope 3の魅力に迫る Zope 3とは何ぞや？（1）　Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？
	貧弱環境プログラミングのススメ柴田淳のコーディング天国　高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？
	Haskellプログラミングの楽しみ方のんびりHaskell（1）　関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう
	ちょっと変わったLisp入門 Gaucheでメタプログラミング（1）　Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう
	more

　　Coding Edgeフォーラム

フィード　 2.0／1.0／0.91

Coding Edge フォーラム新着記事

プログラムの実行はどのようにして行われるのか、Linuxカーネルのコードから探る （2017/7/20）
　C言語の「Hello World！」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。最終回は、Linuxカーネルの中では、プログラムの起動時にはどのような処理が行われているのかを探る
エンジニアならC言語プログラムの終わりに呼び出されるexit()の中身分かってますよね？ （2017/7/13）
　C言語の「Hello World！」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。今回は、プログラムの終わりに呼び出されるexit()の中身を探る
VBAにおけるFileDialog操作の基本＆ドライブの空き容量、ファイルのサイズやタイムスタンプの取得方法 （2017/7/10）
　指定したドライブの空き容量、ファイルのタイムスタンプや属性を取得する方法、FileDialog／エクスプローラー操作の基本を紹介します
さらば残業！　面倒くさいエクセル業務を楽にする「Excel VBA」とは （2017/7/6）
　日頃発生する“面倒くさい業務”。簡単なプログラミングで効率化できる可能性がある。本稿では、業務で使うことが多い「Microsoft Excel」で使えるVBAを紹介する。※ショートカットキー、アクセスキーの解説あり

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）

Coding Edge

注目のテーマ

Coding Edge 記事ランキング

本日月間

＠IT

第1回 TListの実装と性能

TList

TLinkList

注目のテーマ

Coding Edge 記事ランキング

転職／派遣情報を探す

年収６００万円！エンジニア向けの求人満載。転職希望者必見

エンジニアの転職なら【転職サーチ】