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でできますが、流石に題意を取り違えているような気がする。

2015年12月12日土曜日

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

シェル芸初心者向け勉強会が福岡であったようなので問題を解いてみました。ウォーミングアップ問題はawkを封じて解いた解法とawkで解いた解法を書きました。因みにtukubaiは全く使えない(僕の技術的に)ので使っていません。

ウォーミングアップ問題1

問題

1から10まで合計を計算してください

解法

seq -s + 10 | bc
seq 10 | awk '{t+=$1}END{print t}'

解説

awk封じでもかなり色々な解法があると思いますが個人的にはseqで式を生成してbcに食わせるのが好きです。

awkの方はかなりシンプルな感じで書きました。

ウォーミングアップ問題2

問題

下記のファイルを2列目の数字の小さい順に並べ替えてください。

$ cat list

b 11
d 5
a 3
e 4
c 2

解法

cat list | sort -k2,2 -n
cat list | awk '{s[$2]=$0}END{for (i in s){print s[i]}}'

解説

sortのオプションで二列目についてソートするようにしていすると簡単です。

awkでソートといえば連想配列ですが、今回は最初にふたつ目のキーの範囲がわかっていないという体裁で解きました。gawkだとこれで整列されるみたいですがmawkだと別の順になったのであんまり正当派解法ではないです。

ウォーミングアップ問題3

問題

文字列の並びを逆にしてください。

$ echo 'a b c'

解法

echo 'a b c' | rev
echo 'a b c' | awk '{for (i = NF;i>1;i--){printf "%s%s",$i,FS}print $1}'

解説

revというまさにこの用途のコマンドがあるので使いました。ちなみに行レベルでひっくり返したいときはtacを使います。

awkの方は普通に書きました。

ウォーミングアップ問題4

問題

下記の日付一覧から、月毎の日の数を数えてください

$ cat date1

20150101
20150121
20150201
20150202
20150203
20150310

解法

cat date1 | cut -c1-6 | uniq -c
cat date1 | awk '{s[substr($0,1,6)]++}END{for (i in s){print i,s[i];}}'

解説

cutで月のデータだけを切り出してuniq -cで行数を数えました。ソート済みでない場合はuniqの前にsort -nとかをしないといけないです。

awkの方も大体同じ感じで解きました。uniq相当のものは配列で作ります。

ウォーミングアップ問題5

問題

日付と商品が売れた数があります。月毎の商品の売れた数を数えてください。

$ cat date2

20150101 1
20150121 2
20150201 5
20150202 2
20150203 3
20150310 2

解法

cat date2 | cut -c 1-6,9-10 | xargs -I{} bash -c "yes \$(echo {}| cut -d ' ' -f 1) | head -n \$(echo {} | cut -d ' ' -f 2)" | uniq -c
cat date2 | awk '{s[substr($1,1,6)]+=$2}END{for (i in s){ print i,s[i];}}'

解説

awkを使わない方はかなり気合を入れて書きました。回数を数えるのにuniqを使おうとすると月ごとの行を商品の個数回繰り返す必要があります。それをyesとheadで各月について繰り返して、xargsで回しました。awkもtukubaiも使わなくてももう少し良い解法があるような気がします。

awkの方は普通に足し算をしました。

ウォーミングアップ問題6

問題

下記のファイルの積集合と和集合を出力してください。(註: ここで言う積集合とは直積(product)集合ではなく結び(intersection)の方です。)

$ cat data1

a
b
c
d

$ cat data2

b
d
e

解法

cat data1 | grep -f data2
cat data1 data2 | sort | uniq
cat data1 |awk '++s[$1];END{while((getline < "data2")>0){if(!s[$1])print;}}'
cat data1 | awk '{s[$1]++}END{while((getline < "data2")>0){if(s[$1])print $1;}}'

解説

awkを使わない方は大したことないです。grep -fを知らないと辛いかもしれません。

awkの方はちょっと辛いです。awkで複数ファイルを扱うときにはgetlineを使います。あとは大体前に書いたuniq相当の連想配列の使い方と同じ感じです。

ここから本題とは関係ない補足です。このgetlineの使い方はそんなに問題ないですが、BEGIN/END以外の場所で特にファイル指定をしないでgetlineを使ったりすると何を言っているのかわかりづらい挙動をするので、回避できるならやめたほうが良いとされています。

途中で力尽きたので第二回シェル芸勉強会の問題は後半ということにします。

2015年12月10日木曜日

そこまで遅くないShellスクリプトの書き方

この記事は Shell Script Advent Calendar 2015 10日目の記事です。
9日目の記事はryoana14さんの麗しきawkの世界でした。

Shellスクリプトがいつまで経ってもまともに書けないMasWagです。書けないなりにも人の書いた(昔の自分が書いたものも多く含む)スクリプトを見てこれは遅いなと思うことはたまにあります。書き方のコツというか考え方が幾つかあると思うのでまとめてみようと思います。基本的な話なので多分Shellスクリプトをあんまり普段書かない人向けだと思います。ShellはBashを前提として書きます。zshだともっと色々できるのかもしれないです。細かい説明は(そんなに細かくなくても?)省いているので適宜manやinfoを参照すると良いでしょう。

forkを減らす

Shellでコマンドを使うということは多くの場合プロセスをforkしていることになります。Cygwinでプロセスを立てるコストが非常に高いということが問題になったりしますが、*nixでもプロセスを立てるコストは多くの場合無視できません。そうとなるとshellの組み込みの機能でできることはやりたくなります。 Bashの組込み機能で使用頻度が高そうなものを挙げていきます。

まず数式処理"(())"があります。これは大体exprの代替だと思って間違いないです。案外使える機能に((t++))でインクリメントできたり((t+=2))のようなものもあります。

下の結果を見ると解ると思いますが、やはりforkの回数を減らすと目に見えて速度が速くなります。一回だけ実行するタイプではbcもかなり健闘しています。

次にtest/[]の代替の[[]]があります。過去の記事にもあるように単にtestの代替として使うだけでもちょっと速くなりますが、実は[[]]は正規表現マッチができます。grepを使って正規表現マッチしている分岐があったら書き直した方がいいです。またこれは正規表現の話ですが、複数の正規表現のorで分岐するならひとつの正規表現にまとめた方がいいです。

下の結果のようにまあ[[]]を使うと速いです。testとの比較だとそこまで時間が変わっていないですがgrepとの比較だとかなり時間に差が出てしまいます。

 最後に変数展開時の文字列操作があります。変数に対してsedとかを使いたくなったらこっちを使えないか考えるといいと思います。幾つか種類があるので詳細はmanやinfoを参照してください

pipeで繋げられるものは積極的に繋ぐ

Shellスクリプトでコマンドをpipeでつなげると、マルチプロセスで前の処理がすべて終わるのを待たずに次の処理を行うことになるので大抵速いです。特にこのご時世マルチコアなので本当に並列化ができて速いです。良い時代になりました。

専用コマンドがあったらそれを使う

専用コマンドがあったらそれを使うというのはシンプルですが有効な方法です。Shellスクリプトで使うコマンドは基本的にCで実装されているものが多く、まあ速いです。機能が少ない(用途に特化している)物のほうが大抵速いので専用のコマンドがあればそっちを使ったほうがいいです。例えば高機能なcutとしてawkを使うことはあると思いますが、cutで足りる場合にはcutの方が速かったりします。awkが悪者みたいですがshellでloopの処理があったときにawkに置き換えて高速化できることは良くあります。

while readはawkで書きなおしたほうが大体速い(こんなこと書くと怒られうる)

あんまり滅多なこと書くとShell界隈のいろんな人に怒られますが、while readはawkで書きなおしたほうが簡潔にかけて速いことが多いと思っているので僕はawkを使います。僕は基本的にawkが好きな人です。awkはShellスクリプトではない派の人もいるので気をつけましょう。while内部の変数は扱いに注意が必要なので僕はawkを推します。


$ time seq 100000 | awk '$0=(t=$1+t)' | tail -n 1
5000050000

real 0m0.102s
user 0m0.103s
sys 0m0.007s

$ time seq 100000 | while read a ;do echo $((t+=$a));done | tail -n 1
5000050000

real 0m1.712s
user 0m1.490s
sys 0m0.557s

11日目はzayarwinttunさんです。