キュー構造

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

サンプル・プログラム

待ち行列と Pythonによるキュー構造

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

""" * キューにIDを1つ追加する * @global deque Que キュー * @param なし * @return なし """ def pushID(): global Que id = 1 #IDの初期値 for i in range(10): time.sleep(1.0) #1.0秒待ち Que.append(id) #キューに追加 sys.stdout.write("追加:{0:2d}".format(id)) sys.stdout.write(" - 残り:{}\n".format(list(Que))) id += 1 return(0)
""" * キューからIDを1つ取り出し処理する * @global deque Que キュー * @param なし * @return なし """ def popID(): global Que for i in range(10): time.sleep(1.5) #1.5秒待ち id = Que.popleft() #キューから取り出し sys.stdout.write("処理:{0:2d}".format(id)) sys.stdout.write(" - 残り:{}\n".format(list(Que))) return(0)
# メイン・プログラム ====================================================== # キューを用意 global Que Que = deque([])
sys.stdout.write("\n")
# スレッドを用意 th1 = threading.Thread(target=pushID) th2 = threading.Thread(target=popID)
# スレッド開始 th1.start() th2.start()
待ち行列とキュー構造
プログラム "dt03-31-01.py" は、行列に並ぶ処理を pushID、発券する処理を popID として、それぞれマルチスレッドで走らせる。関数内部では、sleepを使って1.0秒、1.5秒待つようにしてある。

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

C++によるキュー構造

C++はPythonと同じクラス deque を備えており、マルチスレッド処理も記述できるので、Pythonプログラム "dt03-31-01.py" をほぼそのまま移植し、"dt03-31-03.cpp" とした

   9: #include <iostream>
  10: #include <iomanip>
  11: #include <unistd.h>
  12: #include <sstream>
  13: #include <thread>
  14: #include <deque>
  15: 
  16: using namespace std;
  17: 
  18: deque<int> *Que;        //キューを用意
  19: 
  20: /**
  21:  * キューの内容を成形して返す
  22:  * @param   deque キュー
  23:  * @return  string 整形した文字列
  24: **/
  25: string listQue(deque<int> *que) {
  26:     ostringstream res;
  27:     int i = 0;
  28:     res << "[ ";
  29:     for (deque<int>::iterator itc = que->begin(); itc !que->end(); itc++) {
  30:         if (i !0)     res << ", ";
  31:         res << *itc;
  32:         i++;
  33:     }
  34:     res << " ]";
  35:     return res.str();
  36: }
  37: 
  38: /**
  39:  * キューにIDを1つ追加する
  40:  * @global  deque Que キュー
  41:  * @param   なし
  42:  * @return  なし
  43: **/
  44: void pushID(void) {
  45:     int id = 1;                             //IDの初期値
  46:     for (int i = 0i < 10i++) {
  47:         usleep(1000000);                    //1.0秒待ち
  48:         Que->push_back(id);             //末尾に追加
  49:         cout << "追加:" << setw(2<< id;
  50:         cout << " - 残り:" << listQue(Que<< endl;
  51:         id++;
  52:     }
  53: }
  54: 
  55: /**
  56:  * キューからIDを1つ取り出し処理する
  57:  * @global  deque Que キュー
  58:  * @param   なし
  59:  * @return  なし
  60: **/
  61: void popID(void) {
  62:     for (int i = 0i < 10i++) {
  63:         usleep(1500000);                    //1.5秒待ち
  64:         int id = *Que->begin();         //先頭から取り出す
  65:         Que->pop_front();                   //先頭を削除
  66:         cout << "処理:" << setw(2<< id;
  67:         cout << " - 残り:" << listQue(Que<< endl;
  68:     }
  69: }
  70: 
  71: // メイン・プログラム ======================================================
  72: int main() {
  73:     Que = new deque<int>;       //キューの実体
  74:     cout << endl;
  75: 
  76:     //スレッドを用意
  77:     thread th1(pushID);
  78:     thread th2(popID);
  79: 
  80:     //スレッド完了を待つ
  81:     th1.join();
  82:     th2.join();
  83: 
  84:     return (0);
  85: }

まず、クラス deque へのポインタをグローバル変数として用意し、実体は main関数の中でnew演算子を用いて用意する。

クラス deque の内容を表示するメソッドは用意されていないので、関数 listQue として用意した。

それ以外は、Pythonプログラム "dt03-31-01.py" をほぼそのまま移植した。
なお、g++でコンパイルする場合は、マルチスレッドのためのオプション -pthread をお忘れ無く。

PHPによるキュー構造

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

1034:     if ($next == self::ANCHOR) {        //末尾を削除
1035:         $this->tail = $forward;
1036:     } else {
1037:         $this->list[$next]['__forward'] = $forward;
1038:     }
1039:     unset($this->list[$i]);         //要素の実体を削除
1040: 
1041:     //リスト長がゼロになった場合
1042:     if (count($this->list) == 0) {
1043:         $this->root = 1;
1044:         $this->tail = 1;
1045:         $this->imax = 1;
1046:         $this->pointer = self::ANCHOR;
1047:     }
1048:     return $i;
1049: }
1050: 
1051: /**
1052:  * リストの長さ(要素数)を返す
1053:  * @param   なし
1054:  * @return  int リストの長さ
1055: */
1056: function len() {
1057:     $l = 0;
1058:     $this->moveRoot();                  //リストの先頭へ
1059:     while (! $this->istail()) {     //リスト末尾まで繰り返し
1060:         $l++;
1061:         $this->moveNext();              //次の要素へ
1062:     }
1063: 
1064:     return $l;
1065: }
1066: 
1067: /**
1068:  * リストの末尾に別のリストを追加する
1069:  * @param   pahooList $list 追加するリスト
1070:  * @return  なし
1071: */
1072: function extend(&$list) {
1073:     $list->moveRoot();                  //リストの先頭へ
1074:     while (! $list->istail()) {     //リスト末尾まで繰り返し
1075:         $a = $list->get();
1076:         $this->append($a);              //要素を1つずつ追加
1077:         $list->moveNext();              //次の要素へ
1078:     }
1079:     $this->moveRoot();                  //リストの先頭へ戻す
1080: }
1081: 
1082: /**
1083:  * リストの内容を成形してを返す
1084:  * @param   なし
1085:  * @return  string リストの内容
1086: */
1087: function list2() {
1088:     $outstr = '[ ';
1089:     $this->moveRoot();                  //リストの先頭へ
1090:     while (! $this->istail()) {     //リスト末尾まで繰り返し
1091:         if (! $this->isroot())  $outstr .', ';
1092:         $data = $this->get();
1093:         $outstr .print_r($data, TRUE);
1094:         $this->moveNext();              //次の要素へ
1095:     }
1096:     return $outstr .' ]';
1097: }
1098: 
1099: // End of Class
1100: }
1101: 
1102: // pahooQue クラス ============================================================
1103: class pahooQue {
1104:     var $plist;             //キューの実体としての配列
1105:     var $error, $errmsg;        //エラーフラグ,エラーメッセージ
1106: 
1107: /**

キューに要素を追加するのは、リストの 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によるキュー

  11: //データ構造クラス
  12: require_once('pahooDataStructure.php');
  13: 
  14: // メイン・プログラム ======================================================
  15: // キューを用意
  16: $que = new pahooQue;
  17: 
  18: $id = 1;                    //IDの初期値
  19: while (TRUE) {
  20:     $rd = rand(1, 100);
  21: 
  22:     //IDを追加(40%の確率)
  23:     if (($id <10&& ($rd < 40)) {
  24:         $que->push($id);
  25:         printf("追加:%02d - 残り:%s\n", $id, $que->list());
  26:         $id++;
  27:     //IDを処理(60%の確率)
  28:     } else if ($que->len() > 0) {
  29:         $i = $que->pop();
  30:         printf("処理:%02d - 残り:%s\n", $i, $que->list());
  31:     //ループ終了
  32:     } else if ($id > 10 && $que->len() == 0) {
  33:         break;
  34:     }
  35: }

待ち行列とキュー構造
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