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

　第1回「TListの実装と性能」では、リンクリスト構造を実装したLinkedListと配列をベースにしたTListについての比較を通して、アルゴリズムの選択によるトレードオフについて解説しました。

　今回は、キュー構造を取り上げます。引き続き、筆者の環境ではDelphi 2009でサンプルプログラムを作成していますが、Delphiをお持ちでない方は下記のURLからTurboDelphiをダウンロードしてぜひインストールして見てください。

関連リンク：
	Delphiトライアル版／無償バージョン http://www.codegear.com/jp/downloads/free/delphi

キューとは何か？

　まず、キューとは何であるかということですが、Wikipediaには以下のような記述があります。

キュー（queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し（FIFO：First In First Out）のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー（Enqueue）、取り出すことをデキュー（Dequeue）という。

図1　キューの概念

　キューがどういったところで使われているかというと、一番身近なのはWindowsのMessageキューになるでしょうか。Windowsでは、各Window間での通信にWindowMessageという仕組みを利用しています。

　あるWindowへ送信されたWindowMessageは、Messageキューに入ります。その後、各WindowがWindowプロシージャの中でぐるぐると無限ループしながらキューからメッセージを取り出して処理しています。

図2　Windowsのメッセージキュー

　ところで、キューはデータを先入れ先出し（FIFO）するリスト構造ですが、対照的な構造としてスタックがあります。スタックは、データを後入れ先出し（LIFO：Last In First Out）するデータ構造です。

　スタックは、最近でこそ目にしなくなった「スタックオーバーフロー」というエラーが起きる原因（？）になっていたもので、コンピュータの中では日常的に使用されているものです。

図3　スタックの概念図

　それでは、第1回に倣ってキューをクラスとして定義するとどうなるのかを以下に書き出してみました。2番目の要素は必須とはいえませんが、内部的には必要な要素なので外形的にも値を返せる方がいいでしょう。

Queueクラスの定義：

• Queueは複数のデータを保持することができる
• Queueは保持しているデータの個数を返すことができる
• Queueはデータをエンキューすることができる
• Queueはデータをデキューすることができる

Delphiでのキュー

　さて、DelphiのVCL（Visal Component Library）では、各所でキューが使われています。その中ではっきりとQueue()というメソッドやプロパティを見掛けたのは、Delphi 2005から実装されたTThread.Queue()メソッドではないかと思います。TThreadは、Delphiでのスレッドプログラミングを行う際に利用するクラスです。

　TThreadには、元々Synchronize()というメソッドがあって、これを利用することでThread側からメインスレッド側に処理を委譲できるという便利なものでした。

　ところが、このSynchronize()はメインスレッド側の処理が終わるまで「帰ってこない」ようになっています。つまり、本来並行動作しているはずのThreadが、Synchronize中は止まってしまっていたわけです。

　そこで、Thread側の処理を中断しないように、Queue()というメソッドが追加されました。Queueメソッドは、メインスレッド側に譲渡するメソッド／プロシージャをキューに突っ込むとすぐに戻ってくるようになっています。

　ちょうど、WindowsのAPIでSendMessage()とPostMessage()の違いと同じようなものですね。SendMessage APIは、Windowメッセージをメッセージキューに突っ込んで、相手がそれを処理するまで待ち続けます。一方、PostMessage APIはメッセージを送ったら処理を終了してすぐに戻ってきます。

　ところで、TThreadのQueueの実装はどうなっているのでしょうか。まずは、TThreadの定義されているClasses.pasをのぞいてみましょう。Queueに渡されたTThreadProcedure／TThreadMethodは、SynchronizeRecordというレコード型（Cでいう構造体）に登録されて【注1】、そのままSynchronizeに渡されます。

　Synchronizeには、QueueEventという第2パラメーターがあって、それがTrueの場合にはQueueモードでの処理を行うようになっています。そして、どちらもTList(!)型のSyncListというグローバルオブジェクトに追加されていきます。

　QueueモードがFalseの場合には、ここでCreateEvent APIによって生成されたEventオブジェクトをWaitForSingleObject APIでINFINITE、つまり無限に待つという処理が行われます。一方、QueueモードがTrueの場合には、メインスレッド側の処理を待たずにそのまま終了します。

　メインスレッド側の処理はどうなっているかというと、Forms.pasで定義されているTApplication.WndProc()、つまりWindowプロシージャの中で、CheckSynchronizeというプロシージャを呼んでいます。

　CheckSynchronizeは、内部でSyncListから1つずつTThreadProcedure／TThreadMethodを取り出して実行していきます。ここで、Synchronizeで設定されたEventがあると、各処理の終了後にそのEventをSetして終わったことを知らせるようになっています。

　そして、SyncListは0番目の要素を取り出してからDelete(0)を呼び出す作業を、要素の個数分繰り返し、先入れ先出しを実現しています。

　ちなみに、SyncListを処理している間、スレッド処理を止めることがないように、ローカル変数であるLocalSyncListに中身を移して処理をしています。その際、InterlockedExchange APIというポインタをアトミックに入れ替えるAPIを利用しています。LocalSyncListに内容を移したSyncListはnilに設定されて、メインスレッドの裏側で各スレッドが非同期に処理を突っ込んでいくわけです。

図4　DelphiでのThread処理

1/2

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

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

	いまさらアルゴリズムを学ぶ意味 コーディングに役立つ！ アルゴリズムの基本（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