【問題と解答】jus共催 第50回記念我々は50回も何をやってるんだろうシェル芸勉強会

Mon Nov 9 09:39:28 JST 2020 (modified: Mon Nov 9 09:48:07 JST 2020)
views: 499, keywords: プログラミング,勉強会,シェル芸,シェル芸勉強会

  このエントリーをはてなブックマークに追加 
  • もっとよい解答はTwitter上にあります。
  • 問題で使われているデータファイルはGitHubにあります。クローンは以下のようにお願いします。
  • 環境: 解答例はUbuntu Linux 20.04で作成。Macの場合はcoreutilsをインストールすると、GNUのコマンドが使えます。BSD系の人は玄人なので各自対応のこと。

Q1

 un.txt.gzから、UNITY, UNKO, unity, unkoの数をそれぞれなるべく短時間で数えてください。 単語の途中に改行が入っているものも数えてください。

解答例

 改行をとってgrepすると、メモリに文字列を読みはじめて遅くなります。aを除去してからカウントすると早く処理できます。

$ time zcat un.txt.gz | grep -vE '^a+$' | sed -E 's/a+/@/g' | tr -d \\n | grep -Eio 'un(ity|ko)' | sort | uniq -c
      2 UNITY
      2 UNKO
      3 unity
      3 unko

real    0m3.585s
user    0m6.037s
sys 0m0.248s

Q2

 un.txt.gzaのみが書いてある行の行数をなるべく早くカウントしてください。

解答例

 peeなどで並列処理すると時短できることができます。(ただし行が混ざることがあるので注意。)

### 並列なし ###
$ time zcat un.txt.gz | grep -cE ^a+$
9999985

real    0m3.445s
user    0m6.009s
sys 0m0.181s
### 並列あり ###
$ time zcat un.txt.gz | pee 'sed -n 1~2p | grep -cE ^a+$' 'sed -n 2~2p | grep -cE ^a+$' | numsum
9999985

real    0m2.739s
user    0m9.878s
sys 0m1.812s

Q3

 un.txt.gzを展開しておきます。

$ zcat un.txt.gz > a

次のようにcatして出力を捨てると一瞬で終わりますが、システムをワンライナーでいじって、このcatにかかる時間を遅くしてみてください。

### 普通にcatするとすぐ終わる ###
$ time cat a > /dev/null

real    0m0.124s
user    0m0.000s
sys 0m0.124s
### なにか細工をする ###
$ ワンライナー
$ time cat a > /dev/null

real    0m1.810s   ←遅くなる
user    0m0.000s
sys 0m0.413s

解答例

 ページキャッシュを開放します。

$ echo 1 | sudo tee /proc/sys/vm/drop_caches 
1
$ time cat a > /dev/null

real    0m1.810s
user    0m0.000s
sys 0m0.413s

Q4

 1から1億までの数字をシャッフルして2列にしたデータ(ファイル名はaにしましょう)を作ってください。速いワンライナーを考えてください。例を示します。

$ head -n 5 a
30704298 56976301
61041738 68147433
99052527 91351967
63294008 15458140
3840917 37301114

解答例

 もっと速い方法があるかもしれませんが、手元の環境ではsort -Rよりshufawkよりpasteという結果でした。

$ time seq 100000000 | shuf | awk 'NR%2{printf $1" "}!(NR%2)' > a

real    0m58.922s
user    1m15.053s
sys 0m3.069s
### awkよりpasteの方が速い ###
$ time seq 100000000 | shuf | paste - - | tr '\t' ' ' > a

real    0m29.393s
user    0m33.804s
sys 0m4.624s

Q5

 このワンライナーを、出力の内容は変えずに高速になるように改良してください。

$ time cat a | sort -k2,2n > b

real    0m59.258s
user    0m54.078s
sys 0m3.841s

解答例

 sortにファイルを指定するだけで、sortがマルチスレッドで動作して速くなることがあります。

$ time sort -k2,2n a > b

real    0m29.940s
user    2m9.304s
sys 0m3.155s

Q6

 aについて、両方の数字が素数の行を抽出してファイルに保存してください。

解答例

$ time cat a | teip -f 2 -- factor | awk 'NF==3{print $3,$1}' | teip -f 2 -- factor | awk 'NF==3{print $3,$1}' | grep -wv 1 > ans1
### 前処理してどちらかが偶数のある行を消しておくと速くなります(2が消えるので&&はダメ) ###
$ time awk '$1%2 || $2%2' a | teip -f 2 -- factor | awk 'NF==3{print $3,$1}' | teip -f 2 -- factor | awk 'NF==3{print $3,$1}' | grep -wv 1 > ans2
### teipなしの方法(これも2が消えるので前処理) ###
$ time ( awk '$1%2 || $2%2{print $1 > "b";print $2 > "c"}' a  && paste <(factor < b) <(factor < c) | awk 'NF==4{print $2,$4}' | grep -wv 1 > ans3 )

Q7

 aについて、次の操作をしてください。

  • 上の行からA, B, C, D, E, ..., Z, A, B, C, ...と記号をつける。
A 4796421 46315959
B 37830772 88906806
C 81382245 28729184
D 32681244 48378429
E 66092656 22445817
・・・
  • 記号を与えられた数字を1行にまとめてansというファイルに保存する。
$ awk '{print $1,$2,$3, "...", $(NF-1),$NF}' ans | head -n 3
A 4796421 46315959 ... 90741157 92659988
B 37830772 88906806 ... 70859873 22640999
C 81382245 28729184 ... 98481095 67292404

解答例

 ファイルに分けてあとからくっつけるという戦法の例を示します。

$ time ( yes {A..Z} | tr ' ' \\n | head -n 50000000 | paste - a | awk '{printf $2" " > $1; printf $3" " > $1}' ; grep . {A..Z} | tr : ' ' > ans)

real    0m36.832s
user    0m38.767s
sys 0m4.637s

Q8

 Q7について、さらに各行の数字を小さい順にソートするという条件をつけてください。ans2というファイルに保存します。

$ awk '{print $1,$2,$3, "...", $(NF-1),$NF}' ans2 | head -n 3
A 21 41 ... 99999966 99999973
B 5 29 ... 99999946 99999958
C 11 105 ... 99999970 99999994

解答例

 ansのように一つにまとまったファイルをソートすると時間がかかるので、さきほど作った中間ファイルそれぞれに並列にソートをかけると早く終わります。

$ time ( echo {A..Z} | tr ' ' \\n | xargs -I@ -P0 bash -c "cat @ | tr ' ' '\n' | sort -n | paste -sd ' ' > s@" ; grep . s{A..Z} | tr -d s | tr : ' ' > ans2 )

real    0m22.454s
user    2m4.237s
sys 0m10.099s


prev:日記(2020年10月15日) next:【問題】jus共催 第50回記念我々は50回も何をやってるんだろうシェル芸勉強会





このサイトではGoogle Analyticsやその他ソーシャルボタンのためにCookieを使用しています。もし同意いただけない場合はブラウザでクッキーを無効にして閲覧をお願いします。This site uses cookies for Google AdSense and some social buttons. If you cannot accept our use of cookies, please disable cookies on your browser.