GAWK スタックを作る
スタックのデータ構造
LIFO (Last In First Out) この略語がスタックのデータ構造を的確に表しています。お皿を1枚づつ重ねていくイメージです。一番上のお皿は、ついさっき重ねたお皿であり、それを取って使うと、その前に重ねたお皿が一番上にきます。
一番上に置く動作を push()、一番上から取り去る動作を pop()といい、大概の言語には最初から備わっている基本的な関数です。が、AWKにはないので、作ります。
余談ですが、筆者がよく使うバッチファイルのコマンド 「pushd %0\..」、この pushd もスタックに現在のディレクトリを保存するものです。popd で直前の pushd されたディレクトリに戻ることができます。 まぁ、筆者はカレントディレクトリの変更だけを目的にしているので、popd することはないのですけど。
スタックの実装
スタックを初期化する
1 : #. _stack_init();スタックを(再)初期化する
2 : function _stack_init() {
3 : _stack_index = 0;
4 : _stack[0] = "";
5 : delete _stack;
6 : }
グローバルな変数を２つ使います。ひとつの変数は配列のインデックス(添字)で、もう1つは入れ物である配列です。このセットでスタックを構成します。5行目で delete (全要素を破棄)してしまうので、4行目はあまり意味がありませんが、1次元の配列に数値インデックスを用いることを明示しています。
この関数をBEGIN先頭で1度使用します。宣言替わりみたいなものです。あまりありませんが、途中でスタックをリセットする場合にも使用します。
データをスタックに積み上げる (push)
1 : #. st_push();スタックの最上部にデータを積む
2 : function st_push(str) {
3 : _stack[_stack_index++] = str;
4 : }
現在のインデックスでデータ格納後、インデックスをインクリメント(後置)します。プッシュ後のインデックスは、常に次の配列(未だ存在しない)を指しています。
スタックの最上部データを取り去る(スタックから無くなる pop)
1 : #. st_pop();スタックの最上部のデータを取る error⇒\0(ヌル文字)
2 : function st_pop() {
3 : return (_stack_index) ? _stack[--_stack_index] : "\0";
4 : }
3項演算子を使っています。_stack_index が 0 ではない真の時、自身をデクリメント(前置)し最上部のデータを指すインデックスとなり、最上部のデータを返します。以後 この対応要素(データ)は st_push() によって書き換えられ消えるか、使用されないままであるため、実質的に取り去った形になります。
_stack_index が 0 の時、すなわちスタックが空の状態にあるときは、配列/インデックスは操作せず、ERROR値として「\0」(ヌル文字)を返します。
スタックの最上部データを参照する(スタックから無くならない top)
1 : #. st_top();スタックの最上部のデータを参照する
2 : function st_top() {
3 : return (_stack_index) ? _stack[_stack_index - 1] : "\0";
4 : }
配列データの取得だけを行います。_stack_index - 1 が最上部(最大)インデックスです。_stack_index 自体に変化はありませんので、配列も変化しません。_stack_index == 0 の時は pop 時と同様、ERROR値として「\0」(ヌル文字)を返します。
スタックの現在サイズを知る (size)
1 : #. st_size();現在スタックサイズを取得
2 : function st_size() {
3 : return _stack_index;
4 : }
_stack_index は常に格納したデータのインデックス + 1 を指していますので、概念上のゼロベース配列の大きさと一致します。しかし実態は、配列を全く delete しませんので _stack_index が最大となった時の大きさの配列が依然として残っています。
スタックが空かどうか調べる (empty)
1 : #. st_empty();スタックが空か調べる 空なら1 空でないなら0
2 : function st_empty() {
3 : return _stack_index == 0;
4 : }
スタックが空の状態であれば 1 を、空でなければ 0 を返します。
スタックを検証する
1 : #. awk_stack.awk;stackの検証
2 : BEGIN {
3 : _stack_init();
4 : print "_stack_init()";
5 : print "st_empty() = " st_empty();
6 : print "st_top() = " st_top();
7 : print "st_push(\"foo\")" st_push("foo");
8 : print "st_push(\"bar\")" st_push("bar");
9 : print "st_push(\"baz\")" st_push("baz");
10 : print "st_empty() = " st_empty();
11 : print "st_top() = " st_top();
12 : print "stack_size = " st_size();
13 : print "st_pop() = " st_pop();
14 : print "stack_size = " st_size();
15 :
16 : print "\nst_push(\"qux\")" st_push("qux");
17 : print "st_top() = " st_top();
18 : print "stack_size = " st_size();
19 :
20 : print "\nst_pop() = " st_pop();
21 : print "stack_size = " st_size();
22 : print "st_pop() = " st_pop();
23 : print "stack_size = " st_size();
24 : print "st_pop() = " st_pop();
25 : print "stack_size = " st_size();
26 : print "st_empty() = " st_empty();
27 :
28 : print "\nst_top() = " st_top();
29 : print "st_pop() = " st_pop();
30 : print "stack_size = " st_size();
31 : }
実行結果
スタックが2個欲しいときは、この関数群を2セット使わないといけない.....
実行速度比較
以下のスクリプトで速度比較してみました。以下は配列から pop するたびに delete します。
二つのファイルを作成して、100 万回ループで検証しています。
上述の _stack_index を用いた関数群の場合は、4行目を _stack_init() に書き換え、7-14行目まで第一引数を削除する必要があります。
1 : @load "time";
2 : BEGIN {
3 : st = gettimeofday();
4 : delete ar_stack;
5 :
6 : for (i = 0; i < 1000000; i++) {
7 : st_push(ar_stack, "foo");
8 : st_push(ar_stack, "bar");
9 : st_push(ar_stack, "baz");
10 : ret = st_pop(ar_stack);
11 : st_push(ar_stack, "qux");
12 : ret = st_pop(ar_stack);
13 : ret = st_pop(ar_stack);
14 : ret = st_pop(ar_stack);
15 : }
16 :
17 : result = st_size();
18 : et = gettimeofday();
19 :
20 : print "delete バージョン";
21 : printf("elapsed_time = %d msec\n", (et - st) * 1000);
22 : }
23 :
24 : function st_push(ar, data) {
25 : ar[length(ar)] = data;
26 : }
27 : function st_pop(ar, ret) {
28 : ret = ar[length(ar) - 1];
29 : delete ar[length(ar) - 1];
30 : return ret;
31 : }
32 : function st_size(ar) {
33 : return length(ar);
34 : }
実行結果
