今回は、sed スクリプトを取り上げます。取り上げるテーマは、フィボナッチ数列の自動生成です。 フィボナッチ数列とは、最初と２番目の数字が１で、それ以降３番目からの数字はその前の２つの数字の和になる数列です。
1 1 2 3 5 8 13 21 34 55 89 ...
sed ではご存知のように、直接的な数値演算の機能はありません。sed に 3 + 5 という数式を与えて、計算させることはできません。そのため、フィボナッチ数列を生成するためには、 すべて文字列として処理する必要があります。
s/^.*$/1/
h
p
p
:loop
H
x
s/\n/+/
s/^/=/
:calc
/+[0-9]/ {
s/^\(.*\)\(.\)$/\2\1/
s/^9/zzzzzzzzz/
s/^8/zzzzzzzz/
s/^7/zzzzzzz/
s/^6/zzzzzz/
s/^5/zzzzz/
s/^4/zzzz/
s/^3/zzz/
s/^2/zz/
s/^1/z/
s/^0//
}
/=[0-9]/ {
s/^\(.*\)\(.\)+/\2\1+/
s/^9/zzzzzzzzz/
s/^8/zzzzzzzz/
s/^7/zzzzzzz/
s/^6/zzzzzz/
s/^5/zzzzz/
s/^4/zzzz/
s/^3/zzz/
s/^2/zz/
s/^1/z/
s/^0//
}
s/^\([0-9]\)/0\1/
s/^zzzzzzzzzzzzzzzzzzz/y9/
s/^zzzzzzzzzzzzzzzzzz/y8/
s/^zzzzzzzzzzzzzzzzz/y7/
s/^zzzzzzzzzzzzzzzz/y6/
s/^zzzzzzzzzzzzzzz/y5/
s/^zzzzzzzzzzzzzz/y4/
s/^zzzzzzzzzzzzz/y3/
s/^zzzzzzzzzzzz/y2/
s/^zzzzzzzzzzz/y1/
s/^zzzzzzzzzz/y0/
s/^zzzzzzzzz/9/
s/^zzzzzzzz/8/
s/^zzzzzzz/7/
s/^zzzzzz/6/
s/^zzzzz/5/
s/^zzzz/4/
s/^zzz/3/
s/^zz/2/
s/^z/1/
s/^y/z/
/=+$/!b calc
s/^z/1/
s/=+$//
p
b loop今回の sed スクリプトは、通常の sed スクリプトとは大きく異なります。通常の sed スクリプトでは、ファイルから１行読み込んで、スクリプトに書いてあるコマンドを適用して、 スクリプトの末尾に達したら編集加工した行を出力します。その繰り返しで、ファイル全体を処理します。 今回のスクリプトは、ファイルからの入力は必要なく、スクリプトの起動は次のようになります。
$ echo "dummy" | sed -f fibo.sed
スクリプトを起動するために、ダミーの入力を用います。 スクリプトがダミーの文字列１行を受け取ったら、前処理を行います。 前処理は、受け取った文字列を１に変換してホールドスペースに保存しておきます。 これで、パターンスペースとホールドスペースの内容は、共に１となります。 次に、１を２回出力して前処理は終わりです。
前処理が終了したら、残りのコードは無限ループになっています。ラベル :loop から最終行の b loop の間のコードが繰り返し実行されることになります。ここからは、次の２つの数字を例にとって、 説明することにします。
... 610 987 1597 2584 ...
太字で示してある２つの数字 987 と 1987 を加算して、2584 になる過程を見ていきます。 ループのサイクルの最初は、パターンスペースに直前の数字 1987 が、ホールドスペースにはその１つ前の数字 987 が入っています。
H PS: 1597 HS: 987
上の行の見方について、説明しておきます。先頭の赤字で示している (この場合は H) のは、適用するコマンドです。次の「PS: .... HS: ....」が、 コマンドの適用対象となる現在のパターンスペースとホールドスペースの内容になります。
ここでは、 H コマンドを使っています。H コマンドは h コマンドと対になっていて、h コマンドが現在のホールドスペースの内容を破棄してパターンスペースの内容をコピーするのに対し、H コマンドはパターンスペースの内容をホールドスペースの末尾に改行を挟んで追加します。
x PS: 1597 HS: 987\n1597
x コマンドを使って、パターンスペースとホールドスペースの内容を入れ替えます。 パターンスペースの 1597 は、次回のサイクルの 1957 + 2584 のときに使いますので、 それまでの間ホールドスペースに保存しておきます。
s/\n/+/ PS: 987\n1597 HS: 1597 s/^/=/
まず、987\n1597 の \n を + (Perl ではメタ文字ですが、sed ではリテラル文字) に変換します。\n のままでも構わないのですが、ただ単に数式らしく見せるだけのものです。次に、先頭に = を追加します。ここで、987+1597= のようにしてもいいのですが、正規表現の効率を考えて =987+1597 のようにしています。このようにすると、各桁の計算を行頭で行えるので、行頭の位置指定を多用することができます。
/+[0-9]/{ PS: =987+1597 s/^\(.*\)\(.\)$/\2\1/ s/^9/zzzzzzzzz/ ... s/^0// } /=[0-9]/ { s/^\(.*\)\(.\)+/\2\1+/ s/^9/zzzzzzzzz/ ... s/^0// }
２つの数字の同じ位の数字を行頭に移動して、その数字の数の z に変換します。 ここで注意を要するのは、0 を最後に変換することです。0 を最後に変換しないと、0 の後の数字も変換してしまうことがあります。
s/^\([0-9]\)/0\1/ PS: zzzzzzzzzzzzzz=98+159 s/^zzzzzzzzzzzzzzzzzzz/y9/ ... s/^zzzzzzzzzz/y0/ ... s/^z/1/
行頭の z の数は、０個 (0 + 0) から 19 個 (9 + 9 で桁上がりあり) になります。この場合には、最初に 0 を変換してしまうことが必要です。z が 10 個以上ある場合は、10 個の z をいったん y に変換しておきます。
s/^y/z/ /=+$/!b calc
行頭に y がある場合には、z に変換しておきます。変換した z は、次の位の数字と一緒に処理することになります。最上位の位の加算で桁上がりあるときは、 z がそのまま残り 5. のところで１に変換することになります。
/=+$/! は、ループの終了条件を判定します。末尾の ! は正規表現のマッチをを反転するもので、/=+$/ にマッチしなければ後続の b calc コマンドが実行され、 a. に戻って次の位の処理に移ります。２つの数字のすべての位の数字の処理が終わると、/=+$/ にマッチしループから抜けることになります。
s/^z/1/ PS: 2584=+ s/=+$// p b loop
まず、行頭に z がないかどうかチェックして、ある場合は１に変換します。 ２つの数字が同じ桁数で最上位の加算で桁上がりがある場合 (610 + 987 など) は、先頭に z が残ったままで内側のループが終了します。次に、末尾の =+ を削除して、出力します。この時点でのパターンスペースは 2584 であり、ホールドスペースは 1597 ですので、b loop で 1. のところから次のサイクルに移ることができます。
このスクリプトを実行すると、コンソールに延々とフィボナッチ数列を表示します。 スクリプトに終了条件は、特に設けてありません。スクリプトが終了するのは、リソース不足になったときです。 リソース不足になると、以下のようなエラーメッセージが出て異常終了します。
sed: Couldn't re-allocate memory
私のパソコン (CPU: Celeron M 1.4GHz, Memory: 1GB, OS: OS/2 Warp v4.52, sed: GNU sed v1.18) でスクリプトを実行したところ、48 時間で 3,049 桁まで生成することができました。 最初はものすごい勢いで出力されますが、48 時間近くになるとゆっくりと桁数を数えられるほど出力が遅くなります。 残念ながら、パソコンの使用の都合上リソース不足になるまで実行できませんでした。 では、実際に何桁まで生成することができるのでしょうか。実行環境によって異なるでしょうが、 次のような簡単なスクリプトを使って調べてみました。
$ echo "dummy" | sed -f ps_full.sed
ps_full.sed
s/.*//
:loop
s/^/z(x 10240)/
s/$/A/
s/AAAAAAAAAA/B/
s/BBBBBBBBBB/C/
s/CCCCCCCCCC/D/
s/DDDDDDDDDD/E/
p
b loop |
上のスクリプトで s/^/z(x 10240)/ と表記してあるところは、実際に 10,240 個の z を入力します。上のスクリプトを実行すると、ループの１サイクルでパターンスペースを 10KB 増やすことができます。そして、パターンスペースの容量をカウントするために、末尾にアルファベットの大文字 (A: 10KB, B: 100KB, ....) を付加しておきます。
私のパソコンで上のスクリプトを実行すると、...zzCCCCCBBBAAAAAA と表示されて異常終了しました。数値表記に直すと 5,360KB、バイト数では 5,488,640 (5,360 x 1,024) となります。今回のスクリプトで生成できるフィボナッチ数列の桁数は、バイト数の半分近くということになります。 48 時間で 3,049 桁ですから、どうやら最後まで実行するのは、計算できない (私に計算できないのは本当) くらい膨大な時間がかかり無理のようです。
(2007/04/01)