第2回 単純なキューと循環キュー
はやしつとむ
アナハイムテクノロジー株式会社
2009/3/13
オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか(編集部)
第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に渡されます。
【注1】 さすがにここはスマートに書けなかったようで、SynchronizeRecordにはTThreadMethod型のFMethodとTThreadProcedure型のFProcedureの両方のフィールドがあり、FMethodがnilの場合にFProcedureを評価、実行するようになっています |
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アルゴリズムトレーニング |
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の世界を体験してみよう |
|
- プログラムの実行はどのようにして行われるのか、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を紹介する。※ショートカットキー、アクセスキーの解説あり
|
|