キュー構造

待ち行列とキュー構造
コンビニのレジ待ち行列をデータとして扱うときのように、先に入った要素を先に処理していくときによく使われるデータ構造がキュー構造である。リスト構造を拡張することで表現できる。

サンプル・プログラム

待ち行列とキュー構造

待ち行列とキュー構造
待ち行列では、キュー構造がよく使われる。
たとえばコンビニでレジ待ちの行列ができているとする。行列の先頭を root、最後尾を tail としてみれば、リスト構造 の一種であることが分かる。
ここでは、1秒に 1 人ずつ行列に並んでいき、レジ処理に 1.5秒かかるとする(人間業とは思えない早さ)。これを Python のプログラムにしてみよう。Python には deque オブジェクトというデータ構造が用意されており、これを使うことにする。

0009: from collections import deque
0010: import systimethreading
0011: 
0012: """
0013:  * キューにIDを1つ追加する
0014:  * @global deque Que キュー
0015:  * @param なし
0016:  * @return なし
0017: 
"""
0018: def pushID():
0019:     global Que
0020:     id = 1                          #IDの初期値
0021:     for i in range(10):
0022:         time.sleep(1.0)           #1.0秒待ち
0023:         Que.append(id)               #キューに追加
0024:         sys.stdout.write("追加:{0:2d}".format(id))
0025:         sys.stdout.write(" - 残り:{}\n".format(list(Que)))
0026:         id += 1
0027:     return(0)
0028: 
0029: """
0030:  * キューからIDを1つ取り出し処理する
0031:  * @global deque Que キュー
0032:  * @param なし
0033:  * @return なし
0034: 
"""
0035: def popID():
0036:     global Que
0037:     for i in range(10):
0038:         time.sleep(1.5)               #1.5秒待ち
0039:         id = Que.popleft()               #キューから取り出し
0040:         sys.stdout.write("処理:{0:2d}".format(id))
0041:         sys.stdout.write(" - 残り:{}\n".format(list(Que)))
0042:     return(0)
0043: 
0044: # メイン・プログラム ======================================================
0045: # キューを用意
0046: global Que
0047: Que = deque([])
0048: 
0049: sys.stdout.write("\n")
0050: 
0051: # スレッドを用意
0052: th1 = threading.Thread(target=pushID)
0053: th2 = threading.Thread(target=popID)
0054: 
0055: # スレッド開始
0056: th1.start()
0057: th2.start()

待ち行列とキュー構造
プログラム "dt03-31-01.py" は、行列に並ぶ処理を pushID、発券する処理を popID として、それぞれマルチスレッドで走らせる。関数内部では、sleep を使って 1.0秒、1.5秒待つようにしてある。

プログラムの実行結果は左図の通りである。
先に入れた ID が、先に取り出されて処理されてゆく様子が分かる。

PHPによるキュー構造

PHP にはキュー構造が用意されていないので、前に作ったリスト構造向けのクラス "pahooList" を利用してキュー構造を実装する。

0762: class pahooQue {
0763:     var $plist;              //キューの実体としての配列
0764:     var $error$errmsg;     //エラーフラグ,エラーメッセージ
0765: 
0766: /**
0767:  * コンストラクタ
0768:  * @param なし
0769:  * @return なし
0770: */
0771: function __construct() {
0772:     $this->error  = FALSE;
0773:     $this->errmsg = '';
0774:     $this->plist = new pahooList();
0775: }
0776: 
0777: /**
0778:  * デストラクタ
0779:  * @param なし
0780:  * @return なし
0781: */
0782: function __destruct() {
0783:     $this->plist = NULL;
0784: }
0785: 
0786: /**
0787:  * キューに要素を1つ追加する
0788:  * @param object $data 追加する要素
0789:  * @return なし
0790: */
0791: function push($data) {
0792:     $this->plist->append($data);
0793:     $this->error = $this->plist->error;
0794:     $this->errmsg = $this->plist->errmsg;
0795:     return (! $this->error);
0796: }
0797: 
0798: /**
0799:  * キューから要素を1つ取り出す
0800:  * @param object $data 追加する要素
0801:  * @return object 取り出した要素/NULL 要素がない
0802: */
0803: function pop() {
0804:     if ($this->len() == 0) {
0805:         $this->error  = TRUE;
0806:         $this->errmsg = 'que: No data';
0807:         return NULL;
0808:     } else {
0809:         $this->plist->moveRoot();
0810:         $data = $this->plist->get();
0811:         $this->plist->delete();
0812:         return $this->error ? NULL : $data;
0813:     }
0814: }
0815: 
0816: /**
0817:  * キューに残っている要素数を数える
0818:  * @param なし
0819:  * @return int キューの要素数
0820: */
0821: function len() {
0822:     return $this->plist->len();
0823: }
0824: 
0825: /**
0826:  * リストの内容を成形して返す
0827:  * @param なし
0828:  * @return string リストの内容
0829: */
0830: function list() {
0831:     return $this->plist->list();
0832: }
0833: 
0834: // End of Class
0835: }

キューに要素を追加するのは、リストの tail に追加すればいいから、[pahooList::append] メソッドを利用する。
キューから要素を取り出すには、リストの root から取り出し、これを削除すればいいから、pahooList::moveRoot] メソッドを使って root へ移動し、pahooList::get メソッドと、pahooList::delete メソッドを利用する。

キュー構造を実現する pahooQue クラスには、以下のメソッドを用意した。
メソッド機能
push()キューに要素を1つ追加する。
pop()キューから要素を1つ取り出す。
len()キューに残っている要素数を数える。
list()リストの内容を成形して返す。

 

クラス pahooQue を使って Python プログラム "dt03-31-01.py" を PHP に移植したものが "dt03-31-02.php" である。
PHP による push のイメージ
push - PHPによるキュー
PHP による pop のイメージ
pop - PHPによるキュー

0011: //データ構造クラス
0012: require_once('pahooDataStructure.php');
0013: 
0014: // メイン・プログラム ======================================================
0015: // キューを用意
0016: $que = new pahooQue;
0017: 
0018: $id = 1;                 //IDの初期値
0019: while (TRUE) {
0020:     $rd = rand(1, 100);
0021: 
0022:     //IDを追加(40%の確率)
0023:     if (($id <= 10) && ($rd < 40)) {
0024:         $que->push($id);
0025:         printf("追加:%02d - 残り:%s\n", $id$que->list());
0026:         $id++;
0027:     //IDを処理(60%の確率)
0028:     } else if ($que->len() > 0) {
0029:         $i = $que->pop();
0030:         printf("処理:%02d - 残り:%s\n", $i$que->list());
0031:     //ループ終了
0032:     } else if ($id > 10 && $que->len() == 0) {
0033:         break;
0034:     }
0035: }

待ち行列とキュー構造
PHP はシングルスレッドの処理系であることから、行列に並ぶ処理と発券処理をマルチスレッドにするのではなく、乱数関数  rand  を使って場合分けすることにした。

プログラムの実行結果は左図の通りである。

PHPによるマルチスレッド処理(参考)

ここからは参考情報である。
PHP はシングルスレッドの処理系だと書いたが、マルチスレッド処理のための仕組みが用意されている。たとえば、pecl で用意されているクラス pthreads を使うことでマルチスレッド処理が可能となる。
ただし、いくつかの制約がある。
  1. ZTS版の PHP が必要である。
  2. PHP のバージョンによって pthreads のバージョンを選ぶ必要がある。
  3. pthreads のバージョンによっては、スレッドの中で他のインスタンス・メソッドを呼び出すことができない。
たとえば Windows版PHP バージョン 7.2.1 で動作する pthreads は、ここからダウンロードする。解凍して得られたファイルのうち、"php_pthreads.dll" は extension で指定するディレクトリへコピーする。
"pthreadVC2.dll" は、PATH の通ったディレクトリ――"PHP.EXE" のあるディレクトリか "C:\Windows\System32"――へコピーする。
最後に、"php.ini"に "[extension=php_pthreads.dll:blue" を追記する。
(この項おわり)
header