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

はやしつとむ
アナハイムテクノロジー株式会社

2009/3/13

循環キュー

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

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

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

図5 循環キューの概念図

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

図6 循環キューの再配置(1)

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

図7 循環キューの再配置(2)

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

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

図8 循環キューの再配置(3)

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
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の世界を体験してみよう
  Coding Edgeフォーラムフィード  2.01.00.91


Coding Edge フォーラム 新着記事
@ITメールマガジン 新着情報やスタッフのコラムがメールで届きます(無料)

注目のテーマ

>

Coding Edge 記事ランキング

本日 月間