参加しました
午前
構造化プログラミング入門の第三回。涙の最終回です。
テーブル駆動方式とは論理分の代わりにテーブルの情報を使ってプログラムを制御するもの。
状態遷移表を素直にプログラムにする感じ。講義の途中で演習がありました。自分は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と同じものを探す
という問題。
$ ls -rl --sort=none ./2020/ | awk 'max < $5{a=$0;max=$5}END{print a}'
$ 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 ディレクトリで
hoge.cgiのうちhogeにあたる部分でディレクトリを作る2020以下にあるファイルをそれぞれのディレクトリに移動させる(hoge.cgiならhogeディレクトリにmv)
という問題。
ls -U | sel -d. 1 | sort -u | sed 's:^:mkdir &:e'
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でつぶやいてるのを見て気になってはいた内容でした。聞けてうれしい。便利そうなので自分でも使ってみようと思います。
終わり
最終回ということでした。準備など本当にありがとうございました。演習問題があったおかげで理解もしやすかったです。テーブル駆動方式は個人的に良く書くコードにも使えそうなので試してみようと思います。
午後の部も毎回問題の整備ありがとうございます。今回はパフォーマンスをかなり意識する問題ということで、いつも通りの「うごけばええやろ」以外のアプローチをいろいろ考えられて良かったです。
