Hatena::ブログ(Diary)

くまメモ このページをアンテナに追加 RSSフィード Twitter

2015-01-31 embulk-plugin-input-randomを作った

データベースを使って何かする際に、ダミーデータが超大量に欲しくなることがあるのでembulkのinput-pluginを作ってみた。

githubのリンク



何もない環境からなら

$ wget https://bintray.com/artifact/download/embulk/maven/embulk-0.2.1.jar -O embulk.jar

でembulk本体のが降ってくるのでそれを使って

$ java -jar embulk.jar gem install embulk-plugin-input-random

とすればプラグインが降ってくる。

exec: {}
in:
  type: random
  rows: 100
  schema:
    id: primary_key
    name: string
    score: integer
out:
  type: stdout

こんな感じのconfig.ymlを書いて

$ java -jar embulk.jar preview

と打てば

Random generation started.
Random generator input thread 0...
+---------+---------------------------------------------+------------+
| id:long |                                 name:string | score:long |
+---------+---------------------------------------------+------------+
|       0 | 9zfeb1fG7Ha3xxjA_UBUY3QdR1R3ltKYjADjYCthSVc |      6,180 |
|       1 | Ry68YnNi9mQQ-9EEtdftd9R21Z78dMZBDqc0IhNgI_M |      1,914 |
|       2 | DGZUeG961dILfRLx-sdcO6AJIvS6ulAj0qvffdR_uNo |      3,316 |
|       3 | spIhxVLfvd1tjDnbJZ2-nsITY8kZnL6mjpaDJ2tBf_M |      5,319 |
|       4 | ZwuViDwHONHCX47bv-tN7m48mdcr-G4d_laWBXscAUA |      5,767 |
|       5 | QM3H4QUvFSrqRAEUjbHRxnEGgSVUtfpMqh7scp-aiZk |        628 |
|       6 | oHzeKtNeULRxTn2_5SPWapSTPxTS6bTCPGZBTBKY_qo |      7,244 |
....

とこんな感じの物が画面に出てくる。

出力先を適当に書き換えてプラグインを用意すれば任意のデータベースにぶっこむ事ができる。

使い方としては以上なんだけど、これから作ろうと思っている機能についてもちょっと書く。

コンフィグの書き方として以下のような書き方ができるようにしていきたいという妄想。

in:
  type: random
  schema:
    - key: phone
      type:
        - japan-phone-number # 日本の電話番号っぽいものを生成する
    - key: name
      type:
        - japanese-human-name  # 日本人っぽい名前を生成する
        - english-human-name  # 英語圏っぽい名前を生成する
    - key: place
      type:
        - japan-prefecture  # 日本の都道府県をランダムに選ぶ
    - key: score
      type:
        random:  # 50から200までの一様分布の乱数を生成
          min: 50
          max: 200

こういう風に書いて

+---------------+-------------------+--------------+------------+
|  phone:string |       name:string | place:string | score:long |
+---------------+-------------------+--------------+------------+
|  03-1111-1111 |         佐藤 裕太 |       東京都 |        123 |
| 052-1234-5678 |         鈴木 健二 |       東京都 |         98 | 
| 090-2345-6789 | Michael Johonston |     神奈川県 |        169 |
|  03-3456-7890 |         井上 裕子 |       千葉県 |        112 |

こんな感じの物がランダム生成(全部完全に適当にランダムなので一切気にしないで)できるようになるといいかなと思っていて、次の余暇のプログラミングの時にでも作る。

2014-12-16 ウェイトフリー性の証明について

気が向いたら書くと言ってしまったので忘れないうちに書く。

飢餓状態とは

  • スレッドAが操作xを試みる
  • スレッドBが操作yを試みる
  • スレッドCが操作zを試みる

という状況の時に、このアルゴリズムがLock-Freeである場合。すなわちスケジューラがどうスケジュールしても少なくともどれか1つのスレッドの操作が成功してしまう事が避けられない場合であってもスケジューラは特定のスレッドの操作だけを意図的に妨害する事は可能であることが多い。

例えば前回の記事のLock-Free Stackを例に話すと

  1. スレッドAがCAS(α→β)を試みようとする
  2. スケジューラがスレッドBのCASが成功するようスケジューリング
  3. 1〜2を繰り返し

こうすれば理論上スケジューラはスレッドAに無限クロックのCPUを食わせながらも、無限にスレッドAのCASを成功させない事が可能だ。

このような状況の事をStarvation(飢餓状態)と呼ぶ。

スケジューラが意図的に最悪のスケジューリングをしてくる環境下において「アルゴリズムが進行する」ことは必ずしも「全てのスレッドの1タスクが有限時間に終わる」事を意味しない*1

この飢餓状態が起きない、つまりスケジューラがどうあがいても有限のクロック数で全てのスレッドが目的を達成できる。という条件を満たす場合そのアルゴリズムWait-Freeと呼ばれる。

有限時間とはいえ、待つ事に変わりは無いのだからWait-Freeという名前は変だなと思っていたら 1974年のLamportの論文が初めてこのWait-Freeという言葉を使ったとTAoMP本に書いてあった。Lamport先生がそう言うんだから仕方ない。

ちなみに、有限のクロックで操作が完了できれば良いのだから「ただ単にメモリの値を読む」とか「ダイクストラ法で最小コストのパスを探す」「クイックソート」とかのシングルスレッドで解決できる問題をシングルスレッドで普通に書いている分にはそれはWait-Freeに分類される。

飢餓状態の回避方法

並行でWait-Freeで線形化可能*2なデータ構造の一般的な作り方というのはよく知られている。

universal constructionなどと呼ばれ、2010年のこの論文が手頃であるがもちろん読む必要はない*3

その一つの方法は簡単に言うとAnnounce Arrayという配列を用意して運用することである。

配列はスレッド数と同じだけの長さがあり、全てのスレッドは何かを操作する前に操作したい内容をその配列中の自分に割り当てられた場所に記述する。

全てのスレッドは自分の操作を実行する前にこの配列全体を調べ、既に自分以外のスレッドが操作を開始している場合にはそいつの操作を手伝う。

この手伝うというのが厄介で、自分自身の実行しようとした操作と全く同一の操作が自分以外のスレッドに1クロック前に達成されてしまう場合などもあるのでコードが非常に複雑になる。

詳しくは僕の魔導書に書かれたWait-Free Stackや、Wait-FreeなKP-Queueの論文あたりを読んでみると良い。

操作内容を書き込む歳にデータ構造の論理クロック*4を一緒に添えて置く事で、どの操作が最初に登録されたのか比較できるので、より古いものから優先的に実行できる。

証明の形

そうやって作ったWait-Freeな操作と、先ほどの「スレッド1の操作が未来永劫実行されなくなるよう配慮するがスレッド1にもCPU時間を割り当てないといけないスケジューラ」が対立した場合*5の最大動作クロックの1例は以下である。

  • スレッドはn本走っている
  • 操作は邪魔されなければkクロックで済むものとする
  1. スレッド1が操作xを行いたいとAnnounce Arrayに書き込む。aクロックかかる。この時の論理クロックはt。
  2. スレッド1の他にスレッド2からスレッドnの全スレッドがAnnounce Arrayに操作(論理クロックt未満)を書き込んでいるので先にそれらを手伝う。(n-1) * kクロックかかる。
  3. スレッド1が自分の操作xを実行しようとしたがスケジューラはそれを止めて他のスレッドに割り当てる。
  4. スレッドpが何か操作を行おうとしたが、スレッド1よりあとに開始したので論理クロックはt+1以上であり、Announce Arrayに操作x(論理クロックt)が先に入っているのを発見するのでそちらを手伝う事になる。aクロックかかる。
  5. 操作xが行われてしまうとスケジューラはスレッド1を足止めできた事にならないので、操作xを行おうとしたスレッドpも止める
  6. 上記4と5をn-1スレッド分繰り返す
  7. スケジューラはどのスレッドにCPUを割り当てても操作xが実行される事を見届けなくてはならなくなるので、どう転んでも操作x(=スレッド1)が進行する。結果として合計(n-1)*k + n * aクロック消費してスケジューラは投了。
  8. (n-1)*k + n * aは無限ではないので、このアルゴリズムはWait-Freeの条件を満たす

という証明をする。

発展的話題

個人的にはKP-Queueの次の年にでた論文、A methodology for creating fast wait-free data structuresが中々好きである。これは上記アルゴリズムを改造して、常時はLock-Freeなデータ構造の様に動かすが予め設定した上限に達しそうになったらWait-Freeに切り替えるという方法。上記アルゴリズムなら他スレッドがAnnounce Array内に居たら即手伝っていたが、こちらは各スレッドがローカルなカウンタを持っていて、予め設定した回数mに至るまではAnnounce Arrayにスレッドが居ても無視するという方法である。更に、自分がLock-Free的にトライした操作がk回失敗続きの場合にやっとAnnounce Arrayにデータを登録し始める、という方法を採用している。これによって各スレッドの操作完了までの最悪時間は「最初にk回Lock-Free的にトライするクロック数」や「他の全てのスレッドにm回見逃されるクロック数」を加算することになるのでクロック上限値が大きくなってしまうが有限の範囲なので依然としてWait-Freeの条件を満たしつつ、実測上Lock-Freeデータ構造に逼迫する性能が出る。という結果が出ている論文である。ここまでしてWait-Freeを実現する意義がいまいちな所も良い。

*1:これはもちろん次から次へと新しいタスクがくるという暗黙の前提に基づいている

*2:こっちの説明もいずれ書く

*3:というか僕もろくに読めていない

*4:操作するたびにインクリメントされるただの数字

*5:ややこしいけど従属的な進行の話はまた今度

2014-12-14 ロックフリー性の証明について

http://www.slideshare.net/kumagi/lock-free-safe?next_slideshow=1

とか過去に自分で書いておきながら、その当時の自分の認識が甘かった事もあるのでここに一度書き出しておく。

Lock-Freeは「ロックを使わない事」ではない

STMの事をもってしてLock-Freeと呼んでる文脈はいっぱいあるけれど、STMの実装にロックを使う事は一般的だし、それは正しい専門用語で言う所のLock-Freeとは呼ばない。

Lock-Freeとは「どんなスケジューリングが為されようともどれかの操作が進行する」という進行保証(Progress Guarantee)を表している。

スケジューリング?

マルチコアCPUでもシングルコアCPUでも、OSは実行中のプログラムを任意のタイミングで強制的に一時停止させて他のプログラムにCPUリソースを割り当てる事ができる*1。実行中スレッドからのOSによるCPUの引き剥がし・割り付けの事を並行プログラムの世界ではスケジューリングと呼ぶ。

シングルCPUコアの環境でついうっかりC言語あたりで無限ループを記述してもkillできるのはこの仕組みのお陰である。

普通の排他ロックは悪意あるスケジューリングに対して無力

悪意あるスケジューリング、という状況は世の中には普通無いが、最悪の場合を想定してシステムが満たす特性の下限を保証する必要がある状況というのはある*2

例えばあるスレッドが共有資源に対する排他ロックXを獲得した後にOSがそのスレッドを強制的に一時停止させて、他のプログラムやスレッドだけにCPUリソースを割り当て続けた場合、他のスレッドは何兆クロックのCPUサイクルを与えられようが排他ロックXが確保されたままの資源にアクセスしてはならないので、利用可能なCPUサイクル全てをドブに捨てる事になる。これを専門用語でブロッキングと呼ぶ。

悪意あるスケジューリングに対して耐性のあるロックの使い方例

他のスレッドが排他ロックを獲得したままであってもプログラムを進行させる使い方はありうる。

try_lock()を用いて「ロックを取ろうとは試みるけど、ロックが取れなかったら別の手段を講じる」というパターンはブロッキングが発生しないのでLock-Freeと呼べる事がある、ロックを利用しているにも関わらず、だ。典型的にはがちゃぴん先生のmallocの話がそれに該当するアルゴリズムの一例。

Lock-Freeの進行保証について

スケジューラの立場からLock-Freeというのを解釈し直すと「どんなスケジューリングを行っても絶対に進行してしまう」アルゴリズムであって、Lock-Freeであることを証明するためには「考えうる限り最悪のスケジューリングを行った場合に、アルゴリズム側が何らかの操作を実現するまでに必要なクロック数の上限が無限でない」という事を示せば良い。

例えばシンプルなLock-Free Stackの場合、

  • t個のスレッドで実行している
  • スケジューラはpushもpopも1つでも実行させないよう最悪ケースのスケジュールを行おうとする

という状況にて

  1. headポインタのアドレスPを読むのにaクロック(有限)
  2. mallocにbクロック(有限)
  3. mallocしたメモリ領域Qk*3に必要なデータを書き込むのにcクロック(有限)
  4. P→QkのCASを試みるのにdクロック(有限)
  5. スケジューラはCASを失敗させたいのでCAS実行の直前で他のスレッドにCPU時間を割り当てる
  6. ↑の1〜5の動作をt個のスレッド全部の分繰り返す
  7. スケジューラはどのスレッドにCPU時間を割り当ててもP→QkのCASを実行しようとしているスレッドばかり
  8. t個のスレッドのうちどれかが必ずCAS成功する。スケジューラは t * (a + b + c + d)クロックで投了
  9. t * (a + b + c + d)は有限なのでこのアルゴリズムには進行保証がある

というようにLock-Free性(=進行保証)を証明できる。

Wait-Freeに関してはまた気が向いたら書く。

*1:当然OSのレベルでプリエンプティブな機能を実現している場合だが、WindowsLinuxMacOSもいまどきのOSはデフォルトでは大抵これを実装している。スパコンだとこの機能のオーバーヘッドを気にしてノンプリエンプティブなOSを利用する場合もあるらしいが詳しくない

*2:銀行のシステムだと全ての操作がキャッシュミスした場合を想定してそこでも性能がちゃんと出るように血を吐くような努力をしていると聞いたことがある

*3:kはそのスレッド固有の数字

2013-08-03

userspace RCU(QSBR)の使い方と解説

10:15 |

http://lttng.org/urcu|Userspace RCU]

という大変クールなプロジェクトがあります。

「RCU(リードコピーアップデート)をユーザースペースで行うもの」という事で、そこだけ聞くとなんのこっちゃという感じ。

リードコピーアップデートって何よ

リードコピーアップデートそのものの正しい説明はWikipedia*1 でも読んでもらうとして、Wikipediaを読むのすら面倒な人の為に説明すると「みんなで共有してるデータをfree()しても良いタイミングを見極める技術」です。

特定の構造体をみんなで共有して書き換えたりしたいな → Lockとればよくね?

すごく頻繁にアクセスするし読み出しの方が多いからLockはやだな → Read-Write Lockでよくね?

Read-Write LockだとAtomic命令多すぎてパフォーマンスでないな → Lock無くしてデータをポインタで包んで書き換えの時だけ複製して差し替えればよくね?

読んでる最中のデータを他の奴が差し替えた後にこっちが読みかけのを勝手にfree()しやがるからSEGVするな → じゃあfree()の実行を遅延させればSEGVは避けられるんじゃね?

「じゃあ削除を遅延ってどれぐらい遅延させればいいのよ?」

が本題。長い道のりだった。

カーネル空間では古くから問題になっていた物で、その解決策としてRCUというものが使われている。

大雑把に説明すると

  • 大事なデータを読み出してる間にはプリエンプションを禁じる
  • データを削除する際にはそのスレッドをyieldし続けて他のスレッドに自分の載ってるプロセッサを貸し出す。他のスレッド全部が最低1度でも自分のCPUコアに載った事を確認したら消して良し(何故なら大事なデータを読みかけのスレッドはプリエンプションされないので、自分のCPUコアに載ってこない。載ってきたなら読みかけでない証拠)

という物。これは読み出し側に一切のペナルティが無くて素晴らしい。でも、カーネル空間内だからこそプリエンプションを禁じるとかスレッドのマイグレーションを検知するとかが出来るわけで、ユーザー空間で真似できる代物ではない。*2

そこで、アルゴリズムの力でユーザー空間でこれに近いものを実現しようぜってのがUserspace RCU。

個々のアルゴリズムを学ぶとおもしろいんだけど、日本語のドキュメント少なすぎて笑えるので日記に書こうと思った所存。

使ってみる

複数の実装を選べて、性能の特性や挙動が微妙に違うのだけど、目的はどれもおよそ一緒。

今回は僕の好きなQSBRを例に挙げて説明する。QSBRは他のアルゴリズムと比べて、Reader-Sideのパフォーマンスとスケーラビリティに優れる。*3

ロックフリーアルゴリズムではガベージコレクタに頼ったアルゴリズムが多くて、Javaで実装出来たものがCだと普通には実装できないことが多い。

そこでこういう方法でオブジェクトの寿命をちゃんと守ってあげると正しく使えるようになる。

インストール

urcuライブラリのインストールは何の変哲もない./configure && make && sudo make installで終わるので特に書くことはない。

使い方例

#include <urcu-qsbr.h>
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
#include <stdint.h>

int** global_array;
int array_length;

void* reader(void*) {
  // 配列内の適当な位置を読んで合計値を算出するだけのスレッド
  int local_sum = 0;
  int i;
  for (i = 0; i < 1000; ++i) {
    rcu_quiescent_state();
    // URCUで保護されているので安心してポインタの中身を参照できる
    local_sum += *global_array[rand() % array_length];
  }

  rcu_thread_offline();  // 処理が終わったので他のスレッドにこのスレッドを無視しろと伝える
  printf("my local sum is %d finish!\n", local_sum);
}

void* writer(void*) {
  // 配列内の適当な位置を適当な値にCASして回るだけのスレッド
  int i;
  for (i = 0; i < 1000; ++i) {
    rcu_quiescent_state();
    int* new_value = (int*)malloc(sizeof(int));
    *new_value = rand() % 100;
    int target = rand() % array_length;
    int* old_value;
    for (;;) {  // CASスピン
       old_value = global_array[target];
       if (__sync_bool_compare_and_swap_8(&global_array[target], (intptr_t)old_value, (intptr_t)new_value)) {
          break;
       }
    }
    synchronize_rcu();  // 他のスレッドのquiescent_stateが経過するのを待つ
    free(old_value);  // RCUが無かったらこの行は危険
  }

  rcu_thread_offline();  // 処理が終了したので他のスレッドにこのスレッドの状態を無視しろと明示
  printf("writer finish\n");
}

void array_init() {
  // int*の配列に適当な値を保持したint*を置いていく
  int i;
  array_length = 100;
  global_array = (int**)malloc(array_length * sizeof(int*));
  for (i = 0; i < array_length; ++i) {
    global_array[i] = (int*)malloc(sizeof(int));
    *global_array[i] = rand() % 100;
  }
}
void array_destroy() {
  // 上記の配列を解放する
  int i;
  for (i = 0; i < array_length; ++i) {
    free(global_array[i]);
  }
  free(global_array);
}

int main(void) {
  const int threads = 10;
  int i;
  pthread_t reader_thread[threads];
  pthread_t writer_thread[threads];

  // 配列初期化
  array_init();

  // スレッドを開始
  for (i = 0; i < threads; ++i) {
    pthread_create(&reader_thread[i], NULL, reader, NULL);
    pthread_create(&writer_thread[i], NULL, writer, NULL);
  }

  // 終わるのを待つ
  for (i = 0; i < threads; ++i) {
    pthread_join(reader_thread[i], NULL);
    pthread_join(writer_thread[i], NULL);
  }

  // 配列破棄
  array_destroy();

  printf("all threads finish\n");
}

実行例

$ gcc qsbr_test.cpp -lurcu-qsbr -lpthread -g

$ valgrind ./a.out

==14076== Memcheck, a memory error detector

==14076== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.

==14076== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info

==14076== Command: ./a.out

==14076==

my local sum is 52455 finish!

writer finish

my local sum is 53090 finish!

writer finish

writer finish

my local sum is 53159 finish!

my local sum is 50037 finish!

my local sum is 52187 finish!-

writer finish

writer finish

my local sum is 46717 finish!

my local sum is 45657 finish!

writer finish

writer finish

my local sum is 52845 finish!

writer finish

my local sum is 52102 finish!

writer finish

my local sum is 46073 finish!

writer finish

all threads finish

==14076==

==14076== HEAP SUMMARY:

==14076== in use at exit: 0 bytes in 0 blocks

==14076== total heap usage: 10,121 allocs, 10,121 frees, 47,280 bytes allocated

==14076==

==14076== All heap blocks were freed -- no leaks are possible

==14076==

==14076== For counts of detected and suppressed errors, rerun with: -v

==14076== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

no leaks are possible の文字が燦々と輝いてますね。素晴らしい。

解説

どうやってこんなのを実現してるかというと、スレッドローカルなストレージにカウンタを置くことで解決してます。

QSBR(Quiescent State Based Reclamation)の名前の通り、Quiescent State(=静止状態)の有無を他のスレッドに対して通知できれば良いのです。

適当な実装を書くならこんな感じ。ただし擬似コードなのでコンパイル通らないし、同時に1スレッドしかsynchronize_rcuできないけれどコンセプトを示すには充分です。

int global_counter = 0;
__thread local_counter = 0;

void rcu_quiescent_state() {
  // 他のスレッドに自分が一旦静止状態に入った事を明示
  local_counter = gloabal_counter;
}

void synchronize_rcu() {
  int old_counter = global_counter;
  ++gloabal_counter;  // ここでカウンタの値を増やす(※)
  local_counter = global_counter;
  for (他のスレッドのそれぞれのlocal_counterを見て回る) {
    if (個々のlocal_counter <= old_counter) {
      continue;  // まだ仕事中らしいのでquiescent_stateを待つ
    }
  }
  // ここに至ったという事は全てのlocal_counterは上の※で増やしたカウンタを観測した。
  // つまり自分がsynchronize_rcuを呼んでから、他のスレッドが最低1回はrcu_quiescent_state()を呼び出した事を意味する
  // つまり1回でも静止状態に入ったので自分以外に到達不能になったデータは消して良いことがわかった。
}

簡単ですね。

他のスレッドから特定のデータを到達不能にした後、到達不能なスレッドがそのアドレスに触らない事を保証できるようになるのを待つわけです。

この待ち期間を猶予期間(grace period)と呼びます。

f:id:kumagi:20130803101248j:image

他のスレッドが最低1回でもQuiescent Stateを宣言するのを待ちます。

厳密にはこれを使うとアルゴリズムはlock-freeではなくなるのですが、実用上充分な速度とスケーラビリティが出ます。

readが多数を占める処理の場合、rcu_quiescent_stateはキャッシュラインがSharedステートに落ちたglobal_counterを読み続ける事になるのでL1キャッシュに当たり続ける事が期待されます。

May god lock-free you!

*1http://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%BC%E3%83%89%E3%83%BB%E3%82%B3%E3%83%94%E3%83%BC%E3%83%BB%E3%82%A2%E3%83%83%E3%83%97%E3%83%87%E3%83%BC%E3%83%88

*2:プリエンプション禁止なんて物騒な物をほいほいとユーザー空間で使えるようにしちゃったら誤用・悪用された時のダメージ半端ない。

*3:僕の読んだことのある実装例では、読み出し側のオーバーヘッドはメモリ読み書き一回ずつとメモリバリア1回で済んでる。しかも書き換えが起こって無ければキャッシュラインすら汚さない優れもの。

ddk50ddk50 2015/02/24 08:47 こんにちは
ソースコードを読んでもどうしても理解できなかった点があるので質問させてください

writerスレッドで開放してるglobal_arrayをもう一度array_destroy()内で破棄してDouble free担ってる気がするのですが、writerスレッド内で確保してる新しいnew_valueをglobal_arrayに挿入する行がwriter()関数内にないとダメだと思うのですが理解が間違っていますでしょうか?

kumagikumagi 2015/03/01 22:09 >>ddk50
コメントありがとうございます。
今気づきました。

writerスレッド内でglobal_arrayに新しいデータを挿入する必要があるという理解は正しいです。
そしてnew_valueをglobal_arrayに挿入している行がまさに__sync_bool_compare_and_swap_8(&global_array[target], (intptr_t)old_value, (intptr_t)new_value)の部分です。
これは日本語で書き下すと
「global_arrayのtarget番目の要素がold_valueを指している場合に限りnew_valueに書き換えた上でtrueを返せ、もし異なっている場合には何もせずにfalseを返せ」
という操作を表しています。

2013-02-02

Stackを使ってQueueを作る

23:35 |

有名な話かと思ったら意外と知られていなかったのでメモ。

FILOを使ってFIFOを作るとも言います。StackでQueue作れてもQueueでStackを作る方法が思いつかないので誰か教えて下さい。もしくはこういう学問があったら紹介して頂けると嬉しいです。

簡単な説明としては、2つのStackを用意して、enqueueするときには1つ目にpush()し、dequeueするときには2つ目からpop()するだけ。

ただし2つ目のStackが空の場合は1つ目のスタックが空になるまで2つ目のスタックに移し替える。

template<typename T>
class MyQueue {
  std::stack<T> in, out;
  MyQueue(){}
  
  void enqueue(const T& v) {
    in.push(v);
  }

  T dequeue() {
    if (out.empty()) {
       if (in.empty()) {
         throw std::exception("Queue is empty!");
       }
       while (!in.empty()) {
         out.push(in.top());
         in.pop();
       }
    }
    T result = out.top();
    out.pop();
    return result;
  }
};

図に書くとこんな感じ。

f:id:kumagi:20130202232536j:image

実際にデータを貯めてみる。enqueue(1);enqueue(2);enqueue(3);

f:id:kumagi:20130202232853j:image

Stackなので最初に入れたデータが一番底に沈む。

ここからdequeueしてみる。out側のstackが空なのでin側から持って来る必要がある。

f:id:kumagi:20130202233320j:image

これでout側のstackを見るとあら不思議、最初に入れたものがStackの一番上に。これをpop()すればdequeueできる。

f:id:kumagi:20130202233457j:image

n_infty_kan_infty_ka 2013/02/03 00:12 Queue2つでStackは実装できますよ。
現在Queue Aにデータがあると仮定して、

1.Aのサイズが2以上ならばサイズが1になるまでdequeueして、それらはもう一つのQueue Bにenqueue
2.Aの最後の1つをdequeue、これがpopされるデータに相当
3.使用するQueueをAからBに変更

まあこの場合dequeue()がO(n)なんで性能は良くないですけどね

kumagikumagi 2013/02/03 00:17 >> n_infty_ka
うわすごいっすね。ありがとうございます。
でもdequeueの時にそいつ自身にenqueue,dequeueさせてn-1回自分のしっぽを自分で食べさせればQueue一本でできそうという。

n_infty_kan_infty_ka 2013/02/03 00:25 >>kumagi
>Queue一本でできそう
そっすね。確かに1本でいいと思います

foofoo 2013/02/03 17:16 http://www.kmonos.net/pub/Presen/PFDS.pdf
これに近い話のような? immutableなリスト(スタック)2本でキューを実装してます。

metalgluemetalglue 2013/02/04 11:05 これは洗濯したタオルを古い方から使う方法として有名ですね: 洗濯物は左の山においていく。タオルを使う人は右の山の上からとる。右の山がないときは、左の山をひっくり返して右の山にする(左の山は空になる)。