第2回単純なキューと循環キュー

2009/3/13

循環キュー

　前回、TListの実装でも見たように、こうしたデータ構造を実現する場合に配列を使うことは容易に想像できます。そして、実際にTListがキューに使われているわけですが、これにはちょっと疑問があります。

　というのも、キューの場合には新しい要素を最後に追加して、最も古い要素を先頭から削除していくことになります。するとリストの項でベンチマークを取ってみたように、配列を利用したリストでは先頭から要素を取り出しつつ削除するたびに、配列全体の再配置が起きてしまうので効率が悪いのです。

　そこで、要素を取り出すたびに再配置が発生しないデータ構造として、循環キューというものが考え出されました。配列の先頭と最後尾が接続されていると考えて、要素を取り出すべき位置と追加すべき位置を管理しながら、ぐるぐると配列の中を使い回していくわけです。

図5　循環キューの概念図

　しかしながら、この循環キューにも問題があります。要素数が用意した配列の大きさを超えてしまう場合には配列の拡張と要素の再配置が必要となり、それが結構ややこしいのです。図を見ながら考えてみてください。

図6　循環キューの再配置（1）

　まず、キューの要素数が配列の大きさを超えてしまった場合には、まず配列自体を拡張する必要があります。

図7　循環キューの再配置（2）

　次に考えなくてはならないのは、配列の拡張は配列自体の最後尾で実行されるので、たまたまそこがキューの最後尾でない限りはキュー自体が空の要素で分断されることになってしまいます。そこで、先頭以降のキューの要素を順繰りに最後尾へと移動をさせてしまいます。

　すると、キューの最後尾と先頭の間に空要素が発生するため、そこに新しい要素を追加できるようになります。

図8　循環キューの再配置（3）

　取りあえず、簡単に実装してみたのが以下のソースコードです。TListの実装に倣って、配列の大きさをCapacityとして保持しておいて、要素数が上限に達したら配列の拡張と要素の再配置を行っています。

unit CyclicQueue;



interface



uses

  Windows, SysUtils, Classes;



const

  MaxQueueSize = Maxint div 16;



type



  PQueueArray = ^TQueueArray;

  TQueueArray = array[0..MaxQueueSize - 1] of Pointer;



  TCyclicQueue = Class(TObject)

  private

    FQueue: PQueueArray;

    FCount: Integer;

    FCapacity: Integer;

    FEnqueue: Integer;

    FDequeue: Integer;

  protected

    procedure ReAlignment;

  public

    constructor Create(InitialCapacity:Integer);

    destructor Destroy; override;

    procedure EnQueue(Value:Pointer);

    function DeQueue:Pointer;

    property Capacity: Integer read FCapacity;

    property Count: Integer read FCount;

  end;



implementation



{ TQueue }



constructor TCyclicQueue.Create(InitialCapacity:Integer);

begin

  inherited Create;



  if (InitialCapacity > MaxQueueSize) then

    raise exception.CreateFmt('Capacity must less than %d', [MaxQueueSize]);



  if (InitialCapacity > 0) then

  begin

    ReallocMem(FQueue, InitialCapacity*sizeof(Pointer));

    FCapacity := InitialCapacity;

  end;



end;



function TCyclicQueue.DeQueue: Pointer;

begin

  if (FCount = 0) then raise exception.Create('Queue is empty');

  Dec(FCount);

  Result := FQueue^[FDequeue];

  Inc(FDequeue);

  if (FDequeue = FCapacity) then FDequeue := 0;

end;



destructor TCyclicQueue.Destroy;

begin



  FreeMem(FQueue);

  inherited;

end;



procedure TCyclicQueue.EnQueue(Value: Pointer);

begin

  Inc(FCount);

  if (FCount > FCapacity) then ReAlignment;

  FQueue^[FEnqueue] := Value;

  Inc(FEnqueue);

  if (FEnqueue = FCapacity) then FEnqueue := 0;

end;



procedure TCyclicQueue.ReAlignment;

var

  Delta, NewCapacity: Integer;

begin

  if (FCapacity > 64) then

    Delta := (FCapacity div 4)

  else

    Delta := 16;

  NewCapacity := FCapacity + Delta;

  ReallocMem(FQueue, NewCapacity * SizeOf(Pointer));

  if (FCapacity > 0) then

  begin

    System.Move(FQueue^[FDequeue], FQueue^[NewCapacity - FCapacity + FDequeue],

      (FCapacity - FDequeue) * SizeOf(Pointer));

    FDequeue := FDequeue + Delta;

  end;

  FCapacity := NewCapacity;

end;



end.

キューをリストに使う

　Delphiのスレッド処理で、TListがキューとして利用されていることは前述しました。TListに限らず、リストとしての機能を満たしたものであればキューとして利用できます。前回設計したTLinkList【注2】も、もちろんキューとして利用できます。

【注2】
前回掲載したTLinkListのソースコードがどうも最終版ではなかったようで、今回差し替えました。あろうことか（！）Itemを追加する際に、内部の受け皿は作ったにもかかわらずデータそのものがそこへ入れられていませんでした

図9　リストをキューとして利用する

　リストをキューとして利用する場合、要素の追加はAddメソッドによってリストの最後尾へ追加していきます。要素の取り出しについては、Items[0]で先頭の要素を取り出した後で、Delte(0)としてリストの要素全体を1つずつ前へ移動させることになります。

　この場合、TListのような配列型で実装されたリストの場合には、要素の再配置が全要素に対して発生してしまうので、要素数が多くなってくると途端に性能が悪化することが考えられます。

ベンチマークを取って性能を比較する

　それでは早速、TCyclicQueueのベンチマークを取ってみましょう。比較対象として、TListをそのまま使った場合とTLinkListを使った場合も実行してみました。

　テストでは、10万件／100万件／1000万件のデータをキューに追加する時間とキューから取り出す時間のそれぞれを測定しました。

テスト環境：

ハード：CPU Core2Quad6600 2.4GHz + RAM 4GB
OS：Windows Vista Ultimate

　テスト結果は以下のとおりです。予想どおり、TListの要素取り出しが極端に遅いことがよく分かります。TCyclicQueueは循環していく際に一度使用した領域の再利用がそのまま行えますが、Listをキューとして使用する場合には0位置から取り出してそのデータを消さないと領域の再利用ができないからです。

　前回と同様に、TListでDelete(0)を実行するのにものすごく時間がかかるため、1000万件のデータ計測はあきらめました。もちろん、TLinkListではDelete(0)も行っています。

TCyclicQueue Test	経過時間
キューに10万件の要素を追加	0.00秒
キューから10万件の要素を取り出し	0.00秒
キューに100万件の要素を追加	0.02秒
キューから100万件の要素を取り出し	0.00秒
キューに1000万件の要素を追加	0.14秒
キューから1000万件の要素を取り出し	0.06秒
1000回のランダムな追加／取り出し	0.00秒
1万回のランダムな追加／取り出し	0.00秒
10万回のランダムな追加／取り出し	0.05秒

TList Test	経過時間
キューに10万件の要素を追加	0.00秒
キューから10万件の要素を取り出し	5.08秒
キューに100万件の要素を追加	0.01秒
キューから100万件の要素を取り出し	521.00秒
キューに1000万件の要素を追加	未実施
キューから1000万件の要素を取り出し	未実施
1000回のランダムな追加／取り出し	0.30秒
1万回のランダムな追加／取り出し	30.73秒
10万回のランダムな追加／取り出し	未実施

TLinkList Test	経過時間
キューに10万件の要素を追加	0.00秒
キューから10万件の要素を取り出し	0.00秒
キューに100万件の要素を追加	0.01秒
キューから100万件の要素を取り出し	0.02秒
キューに1000万件の要素を追加	0.20秒
キューから1000万件の要素を取り出し	0.20秒
1000回のランダムな追加／取り出し	0.00秒
1万回のランダムな追加／取り出し	0.01秒
10万回のランダムな追加／取り出し	0.14秒

　今回は、循環キューの実装を通じて、キューの構造や機能について、またリストを利用した場合の向き不向きについて見てきました。VCLの中を見ても多用されているTListですが時と場合によってはかなり足を引っ張る可能性があるのかな、ということも分かりました。やはり、適材適所で必要なデータ構造に見合ったアルゴリズムでクラスを設計し実装しないと性能的な問題が発生することがよく分かりますね。

2/2

Index
単純なキューと循環キュー
	Page1 キューとは何か？ Delphiでのキュー
	Page2 循環キューキューをリストに使うベンチマークを取って性能を比較する

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を紹介する。※ショートカットキー、アクセスキーの解説あり