2007-11-06

このへん説明してみようかと思いました。花嫁修行のお供に。

http://shinh.skr.jp/m/?date=20071104#p06

 seq 1 1000 | sed '
 # : はラベル。なんか知らんけど少なくとも GNU sed は無名ラベルも OK 。
 :
 # 0 があるなら {} の中身を実行。
 /0/{
   # 入力をホールドスペースに退避しつつパターンスペースにホールドスペースを。
   # パターンスペースには数値であらわしたカウンタを入れる予定。
   x
   # 数値に _@0123456789_0 というサフィックスをつける。
   # 19 って数値が入ってたとしたら 19_@0123456789_0
   s/$/_@0123456789_0/
   # も一個ラベル。
   :a
   # 先頭に _ があったら 1 に変える。
   # 最初は空文字だってのと繰上がった後の処理を兼ねる。
   s/^_/1/
   # インクリメントを行う正規表現。
   # サフィックスの左にある文字が今インクリメントしようとしている数値。
   # この数値が \1 に入るんだけど、そのすぐ右には次の数値 (\3) が入ってるので、
   # \1 をその \3 に変えることによってインクリメントができる。
   # \3 の中身が少しややこしいのは \1 が 9 の場合に _0 に置換するため。
   # その場合、 19_@0123456789_0 => 1_0@0123456789_0 => 20@0123456789_0
   # という手順で繰上がりの処理が行われる。
   # 9 だった場合は _0 になるので一つ前の正規表現にひっかかる。
   s/\(.\)_\(.*@.*\1\(_*.\).*\)/\3\2/
   # インクリメントに成功したらさっきの :a に飛ぶ。
   ta
   # 加えてあった @ から先を削除して
   s/@.*//
   # ホールドスペースにしまいつつまた入力を持ってくる。
   x
   # 入力から 0 を一個削除。
   s/0//
   # : の行に飛ぶ。
   b
 }
 # 最終行なら
 ${
   # カウンタ取ってきて
   x
   # 表示。 q とかでもいい。
   p
 }
 # 入力は表示して欲しくないので削除。
 d'

これとやってること同じだけどまぁ洗練されてる感じ。

これをぐるぐる回せば任意の加算ができるわけだけど、さすがにそれでは遅すぎるので各ケタの計算とかを一気にやる方法を考えることになる。 sed の examples とかに入ってる dc.sed とかはそれをやっていて、アイデアとしては、 Perl で書くと、

 $_='5+2';
 print;
 s/$/;9876543210;9876543210/;
 print;
 s/(.)\+(.);.*\1(.*);(.*\2(.*))/\3\5\4\4/;
 print;
 s/.{19}(.).*/\1/;
 print;

の実行結果の

 i@umu ~/wrk/ag> perl -l adder.pl
 5+2
 5+2;9876543210;9876543210
 432101098765432109876543210
 7

とかを見るとなんとなくわかるんじゃないかなぁと思う。要は数値をうまいこと文字数に変換して、その文字数だけ "98765432109876543210" っていう文字列の左っかわに置くと、 20 番目の数字が足し算の結果になっている、っていう。

で、それに加えて繰上がりの計算とかゴルフとかすると、以下みたいにフィボナッチが sed で求められる、と。

 s/$/1/
 :
 /^18/q
 p
 x
 G
 s/\n/:0/
 s/$/@ 9876543210/
 :a
 s/ .*/&&/
 s/\(.\?\)\(:.*\)\(.\)\(@.*\)\( .*\1\(.*\) \(.*\3\(.*\)\)\)/\2\4\6\8\7\7\5/
 s/\(.*@\).\{19\}\(.\).\{0,9\}\(.\?\).* .* /\2%\1\3 /
 /:@/!ba
 s/^0\|%\|:.*//g
 b

追記: ループ無しでインクリメントってできるんだなーと気付いた。無限精度じゃなくなるけど。

 $_='9199';
 s/$/;0000000000000000/;
 s/(9*);/;\1/;
 s/;.{16}(.*)/;\1/;
 s/$/;01234567891/;
 s/(.?);(.*);.*\1(.).*/\3\2/;
 print;

兼雑記

カウンタとか加算器とか