参加しました
午前
構造化プログラミング入門の第三回。涙の最終回です。
テーブル駆動方式とは論理分の代わりにテーブルの情報を使ってプログラムを制御するもの。 状態遷移表を素直にプログラムにする感じ。講義の途中で演習がありました。自分はC#で解答したので以下に貼っておきます。
int[,] nextState = new int[8,6]{ {-1, 1,3, 2,-1,-1}, {-1,-1,3, 2,-1,-1}, {-1,-1,4, 2,-1,-1}, {-1,-1,3, 4, 5,-2}, {-1,-1,4,-1, 5,-2}, {-1, 6,7,-1,-1,-1}, {-1,-1,7,-1,-1,-1}, {-1,-1,7,-1,-1,-2}, }; int getCharType(byte b) { if(b == '+' || b == '-') return 1; if('0' <= b && b <= '9') return 2; if(b == '.') return 3; if(b == 'E' || b == 'e') return 4; return 0; } bool IsFloat(string s) { var state = 0; foreach(var b in System.Text.Encoding.UTF8.GetBytes(s)) { var type = getCharType(b); state = nextState[state, type]; if(state < 0) break; } if(state == -1) return false; if(state == -2) return true; return nextState[state,5] == -2; } var tests = new [] { ("", false), ("+", false), ("-", false), (".", false), ("+.", false), ("-.", false), ("+1+", false), ("-1-", false), ("+1", true), ("-1", true), ("1", true), ("+1.", true), ("-1.", true), ("1.", true), ("+.1", true), ("-.1", true), (".1", true), ("+1.1", true), ("-1.1", true), ("1.1", true), ("+1.1E", false), ("+1.1E+", false), ("+1.1E-", false), ("+1.1E.", false), ("+1.1E1", true), ("+1.1E+1", true), ("+1.1E-1", true), ("+1.1E.1", false), ("+1.1E1.", false), ("+1.1e+1", true), ("+1234567890.1234567890E+1234567890", true), }; foreach (var t in tests) { Console.WriteLine("'{0}'\t{1}",t.Item1, t.Item2 == IsFloat(t.Item1) ? "OK" : "NG"); }
演習2はnextState
をint[8,256]
に書き換える問題でした。ここまでするとコードから状態遷移表を読み取ることができなくなる。つまり使いすぎ注意ということ。
午後
問題1
1億カラムあるファイルの 87654321 カラム目を出力する問題
$ awk '{print $87654321}' yoko
これだと遅いので後ろから読むなどすれば速いと思うので sel
の後ろから読むモードで…と思ったけどラインバッファを超えて読み込めなかったです。笑っちゃうね…。
問題2
nums.gz
に逆順の行番号をつける問題。
$ seq 1e8 | tac | paste - <(zcat nums.gz)
seq 1e8 -1 1
も試したけどこれは遅い。stepが1の時は最適化されてるからというのをtwitterでみてなるほどなあと思いました。
問題3
nums.gz
から漢数字を覗いて数値順にソートする問題。できるだけはやいと良いとのこと
zgrep '^[0-9]*$' nums.gz | split --lines=1000000; ls x*|xargs -n1 -P0 -I@ zsh -c 'sort @ | sponge @'; sort -nm x* > ans
split
を使ってファイルを分割。それぞれをいったんソートして sort
でマージソートするというもの。そこそこの時間で終わるのでいい感じだけど、ソートの結果あってるんかなこれ。
問題4
2020.tar.bz2
を展開して出てきたファイルから
- 最もファイルサイズが大きいものを探す
- 展開せずに小問1と同じものを探す
という問題。
# 小問1 $ ls -rl --sort=none ./2020/ | awk 'max < $5{a=$0;max=$5}END{print a}' # 小問2 $ tar -tvf ./2020.tar.bz2 | awk 'max < $5{a=$0;max=$5}END{print a}'
エントリ数がスゲーのでls
にソートさせると相当時間がかかってしまいます。というわけで--sort=none
でこれを無効に。あとはawk
で最大値を探すだけです。小問2の方はtar -tvf
の出力から同じことをするだけですね。
ところでいつもalias ls=exa
してるので素のlsを使おうってなったときちょっとハマります
問題5
2020.tar.bz2
を展開して出てきた 2020
ディレクトリで
という問題。
# 小問1 ls -U | sel -d. 1 | sort -u | sed 's:^:mkdir &:e' # 小問2 fd . --type=f --max-depth=1 | rargs -j10 -p './([^\.]+).(.+)' mv {} ./{1}/
小問1はまぁはい。という感じの回答です。もしかしたら sort
の前に uniq
をはさんだ方が速いかもしれないです。
小問2はfd
とrargs
で。並列化もできるしまぁそこそこの時間で終わるんじゃないかな…?
問題6
たくさんのログファイルからコマンドを数え上げる問題。LANG=Cみたいなひっかけもあるのでこれを除外しながらいい感じにしないといけないとのこと。
$ fd . --type=f | surge -P10 -- zsh -c 'read A;grep -e "^+ " $A|grep -oPe "^\++ [^ ]+"|grep -v =|sel 2|sort -u' | sort -u | fmt -1 | sort | uniq -c | sort -rn
fd
ですべてを列挙、surge
にファイルを渡して並列で検索!爆速!みたいなのを考えて描いたんですが愚直にgrep
に全部渡す野に比べて激おそでした。まぁそうだよね。grep
ってよくできてるんだわ
LT
ぐれさんの teip
コマンドアップデート
最強のteip
コマンドに新しい機能が入ったよ。という内容のLT。めちゃめちゃ便利そうでした。
次郎さんのPEGについて
https://www.slideshare.net/jiro4989/peg-251688145
Parsing Expression Grammar(PEG)についての話でした。以前次郎さんがTwitterでつぶやいてるのを見て気になってはいた内容でした。聞けてうれしい。便利そうなので自分でも使ってみようと思います。
終わり
最終回ということでした。準備など本当にありがとうございました。演習問題があったおかげで理解もしやすかったです。テーブル駆動方式は個人的に良く書くコードにも使えそうなので試してみようと思います。
午後の部も毎回問題の整備ありがとうございます。今回はパフォーマンスをかなり意識する問題ということで、いつも通りの「うごけばええやろ」以外のアプローチをいろいろ考えられて良かったです。