2016年12月19日月曜日

最近見た不思議なシェルスクリプトを直してみた

この記事は Shell Script Advent Calendar 2016 19日目の記事です。
18日目の記事はryuichiuedaさんの SHELQ: 怪しいシェル芸キュレーションサイト でした。

他の様々なプログラミング言語において良い書き方と悪い書き方があるように、シェルスクリプトにも良い書き方と悪い書き方があります。しかし特にシェルスクリプトの場合は不慣れな人がかなり悪い書き方をしている様です。そこで、幾つかの例を見ながら良い書き方と悪い書き方を比べてみます。

ディレクトリについて再帰的に処理をする

悪い例

$ ls -R | awk '{がんばる}' | 処理

"ls -R" を使うと再帰的にファイルをリストアップすることができます。ということはこの情報を使えば階層の深いファイルについても処理をすることができますね。やった!

良い例

$ find . -print0 | xargs -0 処理 find . -exec 処理 + (あるいは\;)

良く考えてみて下さい。ただ再帰的に処理をするためだけにわざわざ気合を入れてawkでパースする必要があるなら誰かが便利な道具を作っているはずです。こういう場合はfindを使います。findを使えばファイル名や種類、更新日時など様々な条件でファイルを列挙することができます。ただし、xargsに渡す際に空白入りファイル名があると変な場所で区切れるので所定のオプションを付けてヌル文字区切りにすると良いです。

特定のコマンドを実行しているプロセスを列挙する

悪い例

\$ ps ax | grep 実行ファイル名 | grep -v grep | awk '\$0=\$1'
\$ ps ax | grep [実]行ファイル名 | awk '\$0=\$1'

多分何も知らないと最初に挙げている、ps axの結果を実行ファイル名でgrepしてからgrepを弾くようになると思います。しかし実は、一文字に[]を付けても正規表現として内容が変わらないことを利用して自分自身を弾くこともできます。

良い例

$ pgrep 実行ファイル名

プロセス番号以外も取得したいのであれば二つめに挙げた方法を使うのが良いと思いますが、欲しいのがプロセス番号であればpgrepという正にこのために使うものがあります。 (実は少し結果が変わる場合もありますが多分pgrepの挙動が好ましい場合がほとんどだと思います。) さらにプロセスをkillしたいのであればpkillもあるので便利です。環境によっては無いかもしれません。今時のLinux以外の環境のことは知りません。

番外編 (timeout)

ところで僕がこの処理を見たスクリプトは定期的に走らせて前回と同じプロセスが走りっぱなしであれば強制終了するというものでした。これでもいいんですが、単にタイムアウトの処理をやれば済むのであればGNU coreutilsにはtimeoutが入っています。簡単ですね。

時系列ファイル名の最新版取得

ファイル名が「%y%m%d%H%M%S.log」とかで時系列につけられているファイル群のうち、一番新しいのを取得する方法です。ログとか取ってると良くありますね。

悪い例

$ exprを使ってがんばる

もうどうやるのか知りたくもない感じです。80行かけると書けるらしいです。ソートでも実装するんでしょうか。

良い例

$ sort -nr | head -n 1

ソートするだけです。日時は単に数値としてソートしても結果は同じですよね。GNU sortは優秀で、バージョンなど色々な方法でソートできるらしいです。実は数値と辞書順しか使ったことはないですが。

20日目はkunst1080さんの記事です。

2016年5月27日金曜日

第22回ゴールデンウィークの存在疑惑シェル芸勉強会 第1問

相変わらずシェル芸勉強会には参加できなかったので後日解いてみました。とりあえず第一問です。問題と解答はここにあります。

第1問

最初の解答

だいぶ狂った解答です。最初に全体の行数をwcで数えてそこからAWKでこねこねしてます。

場合分けのない解法

ここ
データ数が偶数と奇数の時で場合分けが必要で面倒くさいです。(場合分けのない方法絶賛募集中。)
と書いてあったので場合分けをしない解答も考えました。

気分がわかるようにAWKで一気に書かれている部分をほぐして説明します。 入力が

3.4
13
42
-4
-5
の時は sortして
-5
-4
3.4
13
42
反転したものと横に並べて
-5 42
-4 13
3.4 3.4
13 -4
42 -5
差の2乗と平均を出して
2209 18.5
289 4.5
0 3.4
289 4.5
2209 18.5
sortしたときの第二カラムの値が中央値です。
0 3.4
289 4.5
289 4.5
2209 18.5
2209 18.5

反転したものと横に並べる周りが汚い感じになっちゃってます。もう少し何とかならないものでしょうか(tukubaiとか?)

2016年2月21日日曜日

安心してください。AWKですから。【トポロジカルソート篇】

定期的に思うことですが、アルゴリズム力がないので諸々のアルゴリズムの復習をします。 最も書き慣れている言語のうちのひとつで、結構書きやすいと思うのでAWKで書くことにします。(布教の意味も込めて)

今回はトポロジカルソートを書こうと思います。トポロジカルソートと言えばGNU coreutilsでtsortとして実装されていることがシェルっぽい人のなかでは有名だと思います。 そうは言ってもシェルスクリプトの中でどうやったら上手く使えるのかはわかりません。 トポロジカルソートは入力に対して答えが一意に定まらないのでtsortとは結果がかわるかもしれません。

アルゴリズムの説明

細かい説明はWikipediaを参照してください。トポロジカルソートでは入力として有向グラフが与えられます。出力は有向グラフのnodeを、edgeの向きが逆転しないようにした順序になります。トポロジカルソートの解は一般に一意に定まりません。 有向グラフがリソースの依存関係を表わしていると考えるとき、トポロジカルソートの出力は依存関係を満たすようなbuildなどの順序になります。有向グラフがpartial orderを表わしていると考えるとき、total orderに拡張していると見ることもできます。

プログラムの仕様

AWKでは(gawkでは独自拡張で実装されてますが)多次元配列がなく、一次元の連想配列しかありません。 そのためグラフの辺の情報を


edge[source] = target0 target1 target2 ... targetn
のように空白区切りで実装しています。 sourceに向う辺を検索する部分は、各nodeについてsourceに向かう辺があるかどうかを線形に探索しています。 辺を削除した結果どこにも向う辺がないnodeについては、空白のtargetを代入することで実装しています。

入力はtsortとほぼ同じですが、各行ごとにsourceとtargetのnodeを書く必要があります。出力はtsortと同じ仕様です。

2016年1月1日金曜日

魚へんマッチングコーディング書き初め

先日のシェル芸勉強会で魚へんの漢字を探す問題が出題されました。本当はUnicodeで魚へんの漢字が連続して出てくることを利用して解く問題ですが、それだとなんか面白くないので画像マッチングで解くことにしました。

やったこと

やったことは非常にシンプルで、同一のフォントなら文字が変わっても大体魚へんの部分は一致するだろうという雑な推定を使いました。従って"魚"や"鯊"などの部首の区分では魚かもしれないが見た目が違うものについては対応する気がありません。魚の大きさが全く違うようなデータが来ても全然ダメです。

まあ普通にC++とかで実装すればいいんですが、芸がない (シェル芸という意味ではないですよ) のでC++でCLIのツールの様なものを実装してシェルで動かしたことにしました。

作ったもの

https://github.com/MasWag/image_utils にあります。Arch Linuxで動かしました。おまけで画面をキャプチャするツールも作りました。これはX11じゃないと動かないのでLinuxじゃないと動かないかもしれません。画面をキャプチャしてパターンとマッチした部分をクリックみたいなものを書けて便利です。

動かしかた

画像データは http://www.unicode.org/ から持ってきました。大量に持ってくると怒られそうなのでほどほどにしてください。ローカルに置くと良いと思います。OpenCVではgifは扱えないのでImageMagickなどで事前にpngに変換して下さい。魚へんの部分もImageMagickでcropとかして適当に作ってください。

./imread tachiuo.png gomi.png maguro.png | ./matchTemplate sakanahen.png

を実行すると

0.868365 6 23 0.473221 16 23 0.682904 6 23

みたいな出力がされます。第一フィールドが大きい方が正解っぽいデータです。第二、第三フィールドがマッチした部分の中央の座標です。第一フィールドを見てもわかりますが、今回は6が左側の中心なのでへんらしい場所にマッチしていることがわかります。多分Unicode全部の画像を持ってきてある程度以上マッチしたデータを全部集めると魚へんが残りますが、流石にそんなことはやってません。

2015年12月28日月曜日

第20回シェル芸勉強会でびっくりしたことまとめ

第20回シェル芸勉強会に参加しました。幾つか初めて知って(過去に見たことがあるかもしれないけど)びっくりしたことがあったので備忘録としてまとめてみた。基本的に午前中で燃焼したので午後のことは書いていない。manを読むべきということを再確認した。そもそもGNUの指針だとmanにいっぱい書いてあるのは良くないはずじゃなかったっけ、とか言う話は知らない。(本当はinfoに書くべき(?))

AWKのPattern Ranges

とりあえずman抜粋

A pattern range consists of two expressions separated by a comma; in this case, the action shall be performed for all records between a match of the first expression and the following match of the second expression, inclusive. At this point, the pattern range can be repeated starting at input records subsequent to the end of the matched range.
見たことあるかもしれないけど、知らなかった。というかパターンのとこにカンマをカンマ演算子のつもりで書いてうまくいかなかったことがあったかも。 つまり

awk 'NR==2,NR==4'

sed -ne '2,4 p'
と同じ意味になるらしい。ついでに言うと

awk 'NR==2,0'

sed -ne '2,$ p'
と同じ意味で使うらしい。

nawkとそれ以外の$0代入の挙動が微妙に違う

これはやばいやつ。MacOSXだとawkがnawkらしいので結構重要かも。

具体的には(i > 1)で


awk '$0=$i'
の挙動が怪しい。gawkとmawkでは全体の真偽値が$iの真偽値と一致すると思って良いがnawkではそうでもないらしい。manを読んでもよくわからなかったので適当にコードを実行して調べた。本を読むと良いのかも。少なくとも調べた限りでは$iの中身がstringの場合には思った通りの挙動をするが、numericの場合には常に偽を返すっぽく見える。

もちろん


nawk '$0=$i'

nawk '($0=$i)||($0)'
の結果は変わらないのだが、(numericだと偽)

nawk '($0=$2)||(($1=$1)&&$0)'
ということにして一回フィールドを書き換えると$0の真偽値が想定しているものに変わる。因みに$0の値はprintして見る限りでは特に変なことになっていない。この挙動が意図したものなのかバグなのかはよくわからないが、少なくともMacOSXでドヤ顔して$0への代入をすると冷や汗をかくことになりそう。

seqと{..}

seq 100 1はだめだけどecho {100..1}が動くの知らなかった。{1..10..2}ができることも知らなかった。

因みに{foo,bar}で色々やる話は知っているけど技術的に使えないやつなのでとりあえず置いておく。${foo:ここ色々}系列も見たことあるし使ったこともある(manを見ないと半分くらい使えない)から今回は置いておく。

午後も自分じゃない端末ってどうやって判別するのかとかよくわかっていない点はあった(今もちゃんとやるにはどうすればいいかよくわかっていない)が、サーバエンジニアじゃないしな、って言って忘却の彼方に投げやった。

2015年12月24日木曜日

どうしてGNU Grepは高速なのか

この記事は アルゴリズム Advent Calendar 2015 24日目の記事です。 あまりアルゴリズムらしい話題でもないですがGNU grepがどうして高速なのかという話について大して詳しくもないですが最近知ったので書きます。

決して最近の投稿ではないですがwhy GNU grep is fastという投稿がFreeBSDのメーリングリストにありました。これはGNU grepの最初の作者のMike Haertelによる投稿で、当時幾つか解説記事も書かれました。FreeBSDのgrepよりGNUのgrepの方がかなり速い(今の速度は知らないですが当時はだいぶ違ったみたいです)みたいで、どうしてGNU grepが速いかということを書いた投稿です。

とりあえず前提知識について確認しておきます。grepは文字列中で正規表現を探索するプログラムで、伝統的にはThompsonのアルゴリズムでオートマトンを求めてマッチします。fgrepは文字列中で文字列を探索するプログラムで、伝統的にはAho-Corasick法で求めます。これらのアルゴリズムについてはここでは特に説明しません。

さて、本題に戻ります。この投稿によるとGNU grepではこんなことが速さの秘訣みたいです。

  • すべてのバイトを読むことなく処理している
  • 各バイトについて実行される命令数を少なくしている

そりゃ速くなりそうということが書かれていますがどうやってこれを実行しているのかが問題です。アルゴリズム的でない点としては例えばstdio.hにある標準関数ではなくmmapなどのシステムコールを直接叩いて入力についてはバッファリングしていないようです。また、例えばa$のような正規表現はa\nに書き換えることで読み込みを行単位でなくて済むようにしています。他にもループアンローリングとかまあやりそうな最適化はやっているらしいです。

さて、これはアルゴリズムアドベントカレンダーの記事なのでアルゴリズム的な話に触れます。主にすべてのバイトを読むことなく処理しているという点に効きます。原文ではこんな感じの内容です。

GNU grep uses heuristics to look for a fixed string that any string matching the regex *must* contain, and uses that fixed string as the bases for its initial Boyer-Moore search. For example if your regex is /foo.*bar/, the initial Boyer-Moore search is (probably) searching for foo.

GNU grepではBoyer-Mooreアルゴリズムを使っています。Boyer-Mooreアルゴリズムとは、検索対象の文字列(長さn)の中からキーの文字列(長さm)を探すアルゴリズムです。ナイーブに全探索で求めるとO(mn)になります。Boyer-Mooreアルゴリズムではキーの文字列に対して事前にあるアルゴリズムでテーブルを作り、そのテーブルにしたがって適宜文字を読み飛ばすことで高速に探索を行うことができます。文字の種類が多いというそこそこ現実的な条件で大体O(n)とかO(n/m)位の性能が出るようです。Boyer-Mooreアルゴリズムの詳細についてもここでは扱わないので調べてください。

ところでBoyer-Mooreアルゴリズムはgrepとは違って、文字列の中から正規表現ではなく文字列にマッチさせるアルゴリズムです。なのでナイーブに考えるとgrepというよりfgrepに使えそうなアルゴリズムです。GNU grepでは正規表現の中で含まれなければならない断片の固定文字列にマッチさせて、そこから正規表現マッチを行うというヒューリスティックを使っているらしいです。どうも単純にこのヒューリスティックを使っているだけでもなく、どうやら本当は色々な実装を組み合わせているらしいです。また、もっと複雑な正規表現の場合はそもそも難しいし滅多に使われないから多少遅くてもいいよねというヒューリスティック(?)の元で実装をしているらしいです(超訳)。

本当にそんな感じになっているのか気になるのでベンチマークを取ってみます。

$ time grep test /usr/share/dict/words > /dev/null

real    0m0.009s
user    0m0.007s
sys     0m0.000s

まず固定文字です。まあ速いです。

$ time grep tes.*t /usr/share/dict/words > /dev/null

real    0m0.010s
user    0m0.007s
sys     0m0.000s

多分BMでtesを探してからtを探します。固定文字とあまり時間が変わりません。固定文字部分がもう少し長いともっと速くなります。

$ time grep [a-z] /usr/share/dict/words  > /dev/null

real 0m0.074s
user 0m0.073s
sys 0m0.000s

$ time grep [A-Z] /usr/share/dict/words  > /dev/null

real 0m0.142s
user 0m0.137s
sys 0m0.003s

$ time grep [A-Z].*[A-Z] /usr/share/dict/words  > /dev/null

real    0m0.168s
user    0m0.163s
sys     0m0.003s

$ time grep [a-z].*[A-Z] /usr/share/dict/words  > /dev/null

real 0m0.337s
user 0m0.337s
sys 0m0.000s

3つ目の例では[A-Z]がなかなか見つからないので時間がかかっています。ひとつ目の[A-Z]もあまり見つからないので[A-Z]のみの場合とそこまで時間が変わらないです。4つ目の例になると[a-z]はほぼ常に見つかるのに[A-Z]がなかなか見つからないので時間がかかっています。[a-z]にかかる時間や[A-Z]にかかる時間と比べてかなり時間がかかっています。

2015年12月17日木曜日

シェル芸初心者向け勉強会に後日自宅にてサテライト参加(参加とは言わない)【後半】

さて、ここからシェル芸勉強会の過去問です。シェル芸勉強会の方は「コワイ」のイメージが先行して敷居が高いのでawk縛りとかawk使わない縛りとかいうことは言わずに解きます。

シェル芸勉強会過去問第2回 問題1: 文字化けしたファイルの削除

問題

次のように、空ファイル abc, DEFG と、文字化けした空ファイルを作ってください。 【今回は問題データのQ1ディレクトリ以下に作成済み】

$ touch abc
$ touch DEFG
$ echo ほげ | nkf -s | xargs touch
$ ls

%82ق%B0        DEFG        abc

解法

rm $(ls | grep -a -v [A-z])

解説

今回は文字化けどころではなく[A-z]を含まないファイルを全部消しました。

シェル芸勉強会過去問第2回 問題2: 計算

問題

以下のファイル中の数字を全部足し算してください。

$ cat Q2/num

1
2 3 4
5 6
7 8 9 10

解法

cat /tmp/num | tr "\n " + | sed 's/+$/\n/' | bc

解説

前述の通りこういう問題は式をいじって最後に評価するタイプの解法が好きなのでこう解きました。

シェル芸勉強会過去問第2回 問題3: 条件でデータを取り出し

問題

下のhogeファイルから、aとbについてそれぞれ一番大きな数を求めましょう。

$ cat Q3/hoge

a 12
a 13
b 13
a 432
b 111
b 43

解法

awk '{if(s[$1] < $2){s[$1]=$2}}END{for(i in s){print i,s[i]}}'

解説

なんかここまで普通に書くと負けた気がするので怪しい解ですが

cat /tmp/hoge | sed 's/a/000/;s/b/999/' | tr -d " " | sort -rn | sed 's/000/a /;s/999/b /' | uniq -w 1
というものも作ってみました。

シェル芸勉強会過去問第2回 問題4: 計算

問題

以下のファイル中の数字を、キー(a,b)ごとに全部足し算してください。

$ cat Q4/num2

a 1
b 2 3 4
a 5 6
b 7 8 9 10

解法

cat /tmp/num2  | awk '{for(i=2;i<=NF;i++){s[$1]+=$i}}END{for (i in s){print i,s[i]}}'
cat /tmp/num2  | sort | sed 's/\([0-9]\) /\1+/g;s/ /+=/' | cat - <(echo a;echo b) | bc

解説

bcを使ったほうがたのしいよ!

シェル芸勉強会過去問第2回 問題5: 日付と曜日

問題

以下のようにファイルを作って、何曜日が何日あるか集計してください。 【今回は問題データのQ5ディレクトリ以下に作成済み】

$ seq 1990 2012 | awk '{print $1 "0101"}' > osyoga2
$ head -n 5 osyoga2

19900101
19910101
19920101
19930101
19940101

解法

cat /tmp/osyoga2 | xargs -I{} date --date={} +%u | sort | uniq -c

解説

date使って曜日を計算させました。さっきから集計のときにsort | uniq -cばっかり使ってますね。

シェル芸勉強会過去問第2回 問題6: ダミーデータの作成

問題

seq 1 100 の出力をランダムに並び替えてください。

解法

seq 1 100 | shuf

解説

shufという便利な(?)コマンドがcoreutilsにあります。awkで解くのは嫌です。

シェル芸勉強会過去問第2回 問題7: 検索

問題

大文字小文字を区別しない場合、以下の辞書ファイルから、重複する単語を検索してください。 asciiコード以外の字がありますが、 とりあえず気にしないでください。

$ head Q7/words

A
A's
AA's
AB's
ABM's
AC's
ACTH's
AI's
AIDS's
AM's

解法

cat words | tr '[:upper:]' '[:lower:]' | sort | uniq -d

解説

とりあえず全部小文字にして重複文字を出しましたがこれでいいんでしょうか?

シェル芸勉強会過去問第2回 問題8: ファイルの比較

問題

file2から、file1にない数字を抽出してください。

$ cat Q8/file1

1
3
4
6
9

$ cat Q8/file2

2
3
4
5
9

解法

grep -v -f file1 file2

解説

grepの逆マッチ、ファイル入力版です。

シェル芸勉強会過去問第2回 問題9: 形式変換

問題

gameから、resultように整形してください。

$ cat Q9/game

1 表 2
1 裏 2
2 表 0
2 裏 1
3 表 3
3 裏 0
4 表 3
4 裏 0
5 表 0
5 裏 0

$ cat Q9/results

   1 2 3 4 5
表 2 0 3 3 0
裏 2 1 0 0 0

解法

cat game | awk '$2=="表"{omote[$1]=$3}$2=="裏"{ura[$1]=$3}END{printf "  ";for (i=1;i<=NR/2;i++){printf " %d",i} printf "\n表";for (i=1;i<=NR/2;i++){printf " %d",omote[i]} printf "\n裏";for (i=1;i<=NR/2;i++){printf " %d",ura[i]} printf "\n"}'
cat game | awk '{score[$2=="裏"][$1]=$3}END{printf "  ";for (i=1;i<=NR/2;i++){printf " %d",i} for(j=0;j<2;j++){printf "\n%s",j?"裏":"表";for (i=1;i<=NR/2;i++){printf " %d",score[j][i]}} printf "\n"}'

解説

awkの配列に入れて最後にforで取り出しました。あまりの泥臭さに少しなんとかしましたがもっと良い解法があるはず。

シェル芸勉強会過去問第2回 問題10: ファイルの結合

問題

file1、file2 から、下の出力を得てください。

$ cat Q10/file1

001 うそ
002 笑止
003 矢追純

$ cat Q10/file2

001 800
002 10000000
003 1

欲しい出力

001 うそ 800
002 笑止 10000000
003 矢追純 1

解法

cut -d ' ' -f 2 file2 | paste -d ' ' file1 -

解説

横結合はpasteでできますが、流石に題意を取り違えているような気がする。