これから30分、あなたの目はあなたの体を離れ、この不思議な時間の中に入って行くのです
キューは以前書いた通り、先っちょだけ挿れて中で出す先入れ先出し(FIFO: First In, First Out)のデータ構造だ。別に難しい概念でも何でもなく、Pythonユーザーなら標準ライブラリに含まれるqueueモジュールを利用すれば簡単にキューを使用する事が出来る。Racketには生憎、公式にはqueueは存在しないが(※1)、リスト万能説のLispなら、別に取り立ててなにかを用意する必要もなく、consが先入れだとすればlastでdequeueが成立する、ってそれだけだ。
例えばRacketだと次のような実装が考えられる。
(define (make-Queue)
(let ((queue '()))
(hasheq 'enqueue (lambda (data)
(set! queue (cons data queue)))
'dequeue (lambda ()
(let ((len (length queue)))
(begin0
(last queue)
(set! queue (take queue (sub1 len)))))))))
(define (enqueue queue data)
((hash-ref queue 'enqueue) data))
(define (dequeue queue)
((hash-ref queue 'dequeue)))
破壊的にデータ(リスト)を変更してるが、そもそもキューも「低レベルデータ構造」で、こういうモンだ、って事だ。つまり、原則、字面通りだと関数プログラミングの為のデータ構造ではない(※2)。
いずれにせよ、そんなに「難しい」データ構造ではないだろう。実行例を見たら分かるが、単にキューに対してenqueueでデータを挿入した順に、dequeueでは値を取り出せる事が分かる(※3)。
> (define q (make-Queue))
> (enqueue q 1)
> (enqueue q 2)
> (enqueue q 3)
> (dequeue q)
1
> (dequeue q)
2
> (dequeue q)
3
GLibにはスタックがないが、どういうわけかキューがGQueueとして用意されている。そしてGQueueの動作の基本は上でのRacketでのモノと同じだ。
GQueueの定義は次のようになっている。
GQueueは構造体で定義されているが、面白いのはheadスロットとtailスロットの型がGLibの双方向連結リスト(GList)になってる辺りだろう。
- g_queue_new: GQueueのコンストラクタ。空のキューを生成する。
- g_queue_is_empty: 一引数関数。引数にはGQueueを取る。返り値は真偽値(gboolean)。引数に与えられたGQueueが空ならTRUE、そうでないならFALSEを返す。
- g_queue_push_tail: enqueue手続きで二引数手続き。第一引数はGQueueで第二引数にenqueueしたいデータを取る。破壊的変更目的で当然返り値はない。GQueueの後方からデータを追加する。
- g_queue_peek_head: 一引数関数。引数にはGQueueを取る。返り値はgpointer(void*)。引数の先頭の値を返す。なお、peekとは「覗き見」の事で、この関数によってGQueueの構造に変化がない、と言う事を保証している。なお、与えられたGQueueが空だったらNULLを返す。
- g_queue_peek_tail: 一引数関数。引数にはGQueueを取る。返り値はgpointer。引数の最後の値を返す。非破壊的操作関数。与えられたGQueueが空だったらNULLを返す。
- g_queue_get_length: 一引数関数。引数にはGQueueを取る。与えられたGQueueの長さを返し、返り値は符号なし整数(guint)になる。
- g_queue_pop_head: dequeue関数で一引数関数。引数にはGQueueを取る。GQueueの先頭の値を返す。返り値の型はgpointer。また、値を「取り出す」のでGQueueを更新する。
- g_queue_push_head: enqueue手続き。g_queue_push_tailと逆に、引数で貰ったデータをGQueueの先頭に追加する。
- g_queue_free: 引数で与えられたGQueueを破棄してメモリを開放する手続き。
さて、基礎コンピュータサイエンス的な話はさておき、GQueueはかなり高機能に設計されている。「データの中身を覗いたり」、双方向にデータを追加したり取り出したりする事が可能だ。つまり、事実上、GQueueはスタックとしても使える、と言う事なんだけど、言い換えると、データの追加を先頭から行うか後方から行うか、取り出しをどっちから行うかしっかり決めておかないとバグを作り込む可能性がある、って事だ。
繰り返すが、一般的に想定されているスタックとキューの「データ追加」と「データ取り出し」を良く覚えておこう。ごちゃまぜにしない事(笑)。
また、GQueueのスタックやキューとしての「使い方」はぶっちゃけ、これで全部なんだけど、無駄に高機能な(笑)GQueueではスタックやキューに対しての「望まれてる機能」以上の機能がてんこ盛りで(笑)、以降はその「あってもなくてもいいんだけど、何故かこういう機能がある」と言う話になっていく(笑)。
- g_queue_index: GQueueの何番目の要素が目的のデータなのか調べる二引数関数。第一引数はGQueue、第二引数は目的のデータ(NULLでも構わない)、返り値は整数(gint)になる。データが見つからなかった場合、-1が返る。
- g_queue_remove: GQueueから目的のデータを削除する二引数関数。第一引数はGQueue、第二引数は目的のデータ。返り値は真偽値(gboolean)。削除が
性交成功すればTRUEが返る。 - g_queue_peek_tail_link: g_queue_peek_tailと似たような関数だが、返り値はGQueueの定義に従ってGListとなる。
- g_queue_insert_before: GQueueの特定の要素の前に別のデータを挿入する三引数手続き。第一引数はGQueue、第二引数は目標とする要素、第三引数は挿入したいデータ、となる。
- g_queue_peek_nth: GQueueのn番目の要素を返す二引数関数。非破壊的。第一引数はGQueue、第二引数は要素番号となる。
さてさて、そもそもスタックやキューって言うデータ構造は「途中にデータを挿入」したり、「途中のデータを返したり」するようなモンじゃない(笑)。あくまで先頭(あるいは末尾)からデータを取り出し、中は触れないんだ。
しかし、GQueueは見た通りオーバースペックだ(笑)。どこからでもデータを取れるし内側にもデータを挿入出来る。
事実上、GQueueと言う実装はリストのようになっている。いや、上の方で構造体での定義を見たが、実際問題、GQueueと言うデータ型は双方向連結リスト(GList)のラッパーのようになっている。
つまり、GQueueは実質的にはGListの先頭と末尾を指すポインタを持ってるだけ、の構造体で、要素自体及びその操作自体はGListに負うトコが多い、と言う事だ。
従って、GListで出来る事はほぼGQueueでも可能だ、と言う事になる。
またそれ故に、g_queue_peek_tail_linkで取り出した値を変数に代入する場合、変数の型はGList型にしないといけないわけだ。決してGListに含まれてる値を取り出してるわけではない。
GQueueの本体がGListだ、と言う事は、本来のスタックやキューには必要ないんだけど(笑)、当然検索関数なんかもある、って事になる。
- g_queue_find: GQueueから望んだデータを見つける二引数関数。第一引数はGQueue、第二引数は探したいデータ(NULLも可)、となる。返り値は探したいデータを含むGListになるんで、返り値を変数に代入したい場合は、変数の型はGList*になる。
- g_queue_find_custom: g_queue_findの高階関数版でコールバック関数として比較関数を指定する。第一引数はGQueue、第二引数は比較対象データ、第三引数にコールバック関数(比較関数)を指定する。コールバック関数の形式はGCompareFuncに従い、条件を満たした際には0を返すようにする事。なお、条件を満たすデータが見つからなかった場合にはNULLが返る。
まぁ、キュー内に望んだデータがあるかどうか探す必要性があるのか知らんが(大体、そういう形式のデータを望むのなら、素直にGListやGSListを使うだろ・笑)、一応検索は出来る。
そして、GQueueもコピーを取ったり、反転させたり、foreachを掛ける事が可能だ。
- g_queue_foreach: その名の通り、GQueue用のforeach。三引数の手続きで、第一引数はGQueue、第二引数はコールバック関数(GFuncはvoidを返す関数を要請するんで実質上は手続き)、第三引数はGQueueで引っこ抜いて来たデータと共に処理したいデータを指定出来る(何もない場合はNULLを指定する)。上の例ではg_printをラップした関数を作って渡している・・・GStringに書式設定を組み合わせるだけ、なんだけど、ラムダ式が使えないC言語ではわざわざ関数を新しく作らざるを得ない、って辺りがなんともはや。
- g_queue_reverse: そもそもスタックやキューだとデータの追加順が重要だろ、と言うツッコミを無視するようなGQueueを反転させる一引数手続き(笑)。当然、引数にはGQueueを与える。
- g_queue_copy: GQueueをコピーする一引数関数。ただし、そのコピーは「浅いコピー」(シャローコピー: Shallow Copy)と言われるモノで、ポインタだけコピーするだけで、データの実態そのものをコピーするわけではない、と言う事に注意。
関数の使い方に付いてはいいが、ここでPython辺りでも問題になる「浅いコピー」「深いコピー」に付いて補足しておく・・・実は関数型言語による関数型プログラミング(あるいはPythonで行う関数型プログラミング)ではあまりこの辺は問題にはならない。と言うのも、関数型プログラミングでは「非破壊的操作」による「返り値の連鎖」でプログラミングしていくので、このテの問題が表面化しないんだ(結果、常に新しい値を生成する・・・そしてガベージコレクタが走り回る・笑)。
一方、「破壊的操作前提」だと「いつの間にやらオリジナルのデータが変更されてる」事となり、「浅いコピー」「深いコピー」の違いを概念的に知っておかなければプログラミングに於いて障害になりうる、ってわけだ。
概念図としては次のようになる。
例えば、Object OneがDataと結びついていた時、「浅いコピー」でObject Twoを作ると、Object Oneが指してたDataのアドレスだけがコピーされてObject Twoが生成される。結果両者は「同じモノを指してる」わけだ。一方、「深いコピー」の場合は参照先のDataそのものを複製する。それが両者の違いとなる。
なんでこんなにシチメンド臭い事を、って思うだろうが、一般にコンパウンドデータ(合成データ)は単純なデータに比べると単にデカい。よってメモリ効率の為にこういう「浅いコピー」が良く行われるんだけど、結果、Object Oneを利用してDataそのものが改変されてしまった場合、「浅いコピー」だとObject Twoも影響を受けてしまうわけだ。
関数型言語や関数型プログラミングと言う方策が「破壊的操作を好まない」のはこれを避ける為、なんだ。
そして破壊的操作を避け続ける以上、プログラムする側は「それ」が浅いコピーなのか深いコピーなのか、は全くと言って良い程気にする必要がなくなる。
- g_queue_peek_nth_link: g_queue_peek_nthのリンク版。つまり返り値はGListになる二引数関数。第一引数はGQueue、第二引数は符号なし整数(guint)で位置を指定する。第二引数がGQueueの長さを超えていた時にはNULLが返る。
- g_queue_unlink: GQueueから要素(GList)を削除する二引数手続きだが、GListそのものをfreeするわけではないので、その要素を廃棄する場合には自分でg_list_freeする必要がある。第一引数はGQueue、第二引数は目的の値を含むGList。なお、「スタック/キューなのに中のデータが削除出来るなんてwww」とかツッコんではいけない(笑)。
- g_queue_delete_link: g_queue_delete_linkと殆ど同じだが、こっちはGListを自動的にfreeする。ただし、GListに含まれるデータが動的なコンパウンドデータ(例えばGStringとか)だった場合、そこまでfreeするわけではないので、そっちは別途手作業でfreeする必要がある。あくまでGListと言う「ガワ」を自動で廃棄するのみ、だ。なお、「スタック/キューなのに中のデータが削除(ry
- g_queue_sort: 「スタック/キューはデータの追加順が重要なのにソーティングなんてwww」と言うツッコミはナシの方向で(笑)。結果、本体はやっぱりGListなんだ。g_queue_sortも三引数手続きで、第一引数にGQueue、第二引数にコールバック関数として比較関数(GCompareDataFunc)、第三引数にコールバック関数に手渡すオプショナルなデータを取る(何もない場合はNULL)。この例だとTaskと言う構造体を定義して、中にpriority(重要度)と言うスロット作り、それを比較するような比較関数を書いている。なおg_newというのはマクロで、フツーにユーザーが構造体を定義してインスタンスを作成する際に、直接malloc(動的メモリ確保)する代わりに色々と面倒を見てくれる。
繰り返すが、GQueueをスタック/キューとして使う、とマジメに考えるなら最初の例示だけを参考にすればいい。それが「本来の」スタック/キューの役割で、あとの例は、基本的に本体である「GListが出来る事」をそのままGQueueがなぞってるだけ、なんで参考程度に留めるだけでいいだろう。「出来るは出来る」けど、かと言って、ここに書かれてる「本来のスタック/キューから外れた使い方」をするくらいなら、最初からGListと言う「正しいデータ形式」を選ぶべき、だからだ。当然データ型選択は「目的に合った適切なブツ」にすべきだ。
と言うわけで、GQueueの項目は終わる。
そしてここで紹介するGLibが提供する抽象データ型はこれで終わり、となる。
※1: もちろん、有志によるライブラリはある。
※2: もちろん、「裸のキューだから」だ。何らかの関数内での処理にキューを用いる、と言う判断だった場合、当然ながら「非破壊的な」実装は可能だ。
※3: 逆にスタックは、あとに入れたデータが先に取り出され、キューとは取り出し順が逆になる。
(define (make-Stack)
(let ((stack '()))
(hasheq 'push (lambda (data)
(set! stack (cons data stack)))
'pop (lambda ()
(begin0
(car stack)
(set! stack (cdr stack)))))))
(define (push stack data)
((hash-ref stack 'push) data))
(define (pop stack)
((hash-ref stack 'pop)))
> (define s (make-Stack))
> (push s 1)
> (push s 2)
> (push s 3)
> (pop s)
3
> (pop s)
2
> (pop s)
1
