2015/11/03
勝手にお題---テキストフィルタ
こちらのblogでGaucheを使って頂いた：
メインロジック以外にコマンドラインオプション処理やエラーハンドリングなども入り わりと実用向けの良い課題になっていると思う。
メインロジックは上記blogより引用:
テキストファイルの先頭から指定したbyte数（または文字数）だけ出力し、改行を出力し、先頭から1byte（または1文字）シフトした位置から同じように出力し、改行を出力し、再びシフトし――ということをファイル終端まで繰り返すコンソールアプリだ。例えばこんな感じ。
$ echo -n abcd | hcasl -n 1 a b c d $ echo -n abcd | hcasl -n 2 ab bc cd $ echo -n abcd | hcasl -n 3 abc bcd
オリジナルのGaucheのコードも特におかしいというわけではないけれど、 面白い課題なので別解をステップバイステップで書いてみよう。
Step1. リストの先頭n個を取る
入出力は後で考えるとして、まずはリストからリストへの変換を考えてみる。 たとえばこんな動作をする関数だ。
gosh> (shift-slice '(a b c d) 2) ((a b) (b c) (c d))
リストの先頭n個を取るにはtakeが使える。素直に再帰でループを回すと
この通り。
;; バージョン1
(define (shift-slice lis n)
(if (< (length lis) n)
'()
(cons (take lis n) (shift-slice (cdr lis) n))))
しかしこのコードには気になるところがいくつかある。
- 末尾再帰でないので、入力長Nに比例するスタックを消費する。
(length lis)はO(N)の処理で、それをlis-n回のループで繰り返すから そこだけでO(N^2)だ。
最初の問題は教科書どおり、累積変数を導入して末尾再帰に書き換えることで解消できる。
2番目の問題については、最初のn個までしかリストをチェックしない
length<=?という組み込み手続きが使える。
;; バージョン2
(define (shift-slice lis n)
(let loop ([r '()] [lis lis])
(if (length<=? lis (- n 1))
(reverse r)
(loop (cons (take lis n) r) (cdr lis)))))
以上は「リストの頭からn個取る、リストをずらして繰り返し」というアルゴリズムを 素直に実装したものだ。けれど、このアルゴリズムの入力と出力の関係を 静的に見てみると、別の考え方もできる。
入力(a b c d)、n=3の場合について考えよう。入力をひとつづつずらしたものを n個並べてみる。
a b c d <-- 入力
b c d <-- シフト
c d <-- シフト
この図を縦に見ると出力が得られる。
a b c d <-- 入力
b c d <-- シフト
c d <-- シフト
| |
v v
出力1 2
入力lisをひとつづつずらしたリストのリスト、は次の式で得られる
(dropはリストの要素が足りないとエラーになるが、
drop*だと足りない場合は()になるだけなので今回は都合が良い):
(map (cut drop* lis <>) (iota n))
確認：
gosh> (let ([lis '(a b c d)] [n 3])
(map (cut drop* lis <>) (iota n)))
((a b c d) (b c d) (c d))
これだけ見るとリストがn個複製されてるみたいだけど、実際には
共通部分は共有されてるのでメモリ使用量は増えていない。そのことは
上の式の直後に結果をwrite-sharedしてみればわかる。
gosh> (write-shared *1) ((a . #0=(b . #1=(c d))) #0# #1#)#<undef>
#0=などはその部分が共有されてるということ。最後の#<undef>はwrite-sharedの戻り値。
一方、 リストのリストに対して「その先頭だけを集めたリスト」「2番目を集めたリスト」… というリストを作るのはこう書ける:
(apply map list <リストのリスト>)
リストのどれかの要素が使い尽くされるとmapが終わるので、出力の長さは 入力リストの一番短いものに揃う。
gosh> (apply map list '((a b c d) (b c d) (c d))) ((a b c) (b c d))
合わせると次のとおり:
;; バージョン3 (define (shift-slice lis n) (apply map list (map (cut drop* lis <>) (iota n))))
Step2. 入力と出力とlazy sequence
課題では、入力は標準入力やファイルから取られるのでかなり長くなる可能性がある。 また、出力の長さも入力長に比例する。処理に必要なデータサイズはnで限定されるのに、 一旦全てのデータをメモリに置かなければならないとしたら何か無駄っぽい。
でもlazy sequenceを使えば、リストを使っている気分で、必要なところまで計算する ことが出来る。
例えば、port->char-lseqを使うと、ポートから読んだ文字のリストが得られる。
ただし文字は必要な部分までしか読まれない。次の例ではtakeで最初の10要素
だけ取ってるので、それ以降のファイルは読まれない。
gosh> (call-with-input-file "/usr/share/dict/words"
(^p (take (port->char-lseq p) 10)))
(#\A #\newline #\A #\' #\s #\newline #\A #\A #\' #\s)
(注：port->char-lseqは0.9.4リリース以降に入ったので、
0.9.4を使う場合は次のとおり定義してほしい。ついでにバイト単位のport->byte-lseqも
示しておく。)
(define (port->char-lseq :optional (port (current-input-port))) (generator->lseq (cut read-char port))) (define (port->byte-lseq :optional (port (current-input-port))) (generator->lseq (cut read-byte port)))
入力をlazyに読むのはこれを使えば良いとして、出力をlazyに生成するには
先のshift-sliceにもうひとつだけ工夫が必要だ。mapは貪欲で
入力リストを全部食べて出力を生成する。これをlmapに変えるだけで、
出力はlazy sequenceになり、必要に応じて計算されるようになる。
(内側のmapは変える必要がない。このmapの入力はn個の整数に決まってるから。)
(use gauche.lazy) ; lmap ;; バージョン4 (define (shift-slice lis n) (apply lmap list (map (cut drop* lis <>) (iota n))))
入力をポートから取り、出力をcurrent-output-portに出して要素ごとに 改行するのは次のとおり書ける:
(define (process-1 port n)
(dolist [r (shift-slice (port->char-lseq port) n)]
(for-each write-char r) (newline)))
テスト:
gosh> (call-with-input-string "abcd" (cut process-1 <> 2)) ab bc cd ()
最後の()はdolistの戻り値。
Step3. 複数の入力、出力先の変更
実用的なコマンドでは、入力や出力がコマンドライン引数によって 様々に変わり得る。
- 複数の入力が指定された場合、それらを順に処理する
- 入力はファイル名指定、もしくは "-" の場合は標準入力
- 入力が指定されなかったら標準入力
- 出力は無指定もしくは"-"なら標準出力、そうでなければファイル名指定
いっぺんに全部やろうとすると条件がごちゃごちゃするので、 レイヤに分けてゆこう。まずは複数の入力の処理。 「入力が無い場合は標準入力」についてはcaller側でcurrent-input-portを 補ってやることにする。
もう一つ、元の仕様では、
- 途中でエラーがあった場合はエラーメッセージを標準エラーに表示しそのファイルをスキップして 実行を続ける
- 途中でエラーが起きたかどうかを最終的に知りたい
というのがあるようなので、foldでループしてエラーコードを持ち回る。
;; inputs - ポートもしくはファイル名のリスト
;; return - 0 on success, 1 on error
(define (process-multi inputs n)
(fold (^[in c]
(guard (e (format (current-error-port) "~a\n" (~ e'message))
1)
(cond [(port? in) (process-1 in n)]
[(equal? in "-") (process-1 (current-input-port) n)]
[else (call-with-input-file in (cut process-1 <> n))])
c))
0 inputs))
最後に出力でのディスパッチ。output は - もしくはファイル名。
(コマンドラインでのoutput省略時は、コマンドラインパーザ側で-をデフォルト値に
してやれば良い)。
(define (hcasl n inputs output)
(if (equal? output "-")
(with-output-to-port (current-output-port) (cut process-multi ifiles n))
(with-output-to-file output (cut process-multi ifiles n))))
コマンドライン引数処理などを含めた全コードはこちら:
(https://github.com/eel3/hcasl からの派生物なのでライセンスは本家に準じる)
Tags: Gauche, Programming
Post a comment