日々之迷歩

世の中わからんことだらけ

ITが複雑で難しくなっていく様に翻弄される日々です。微力ながら共著させていただいた「シェル・ワンライナー160本ノック」をよろしくお願い申し上げます。

真・マイナンバーシェル芸

Shell シェル芸 Ruby Tukubai

マイナンバー。それは12桁の数字で表現されるシークレットなアイデンティティ・・・アイデンティティがシークレットとはこれいかに？？？

  これはTwitterでリプライをいただきながら進化していった物語である。Twitterでリプライしていただいた皆様、本当に感謝！

ということで、少し前にマイナンバーをひたすら列挙するシェル芸の話題が上がっていた。しかしながらこれは、純粋に0から9までの数字を12桁並べるという単純なものだった。

togetter.com

最近、どこかは忘れてしまったが「マイナンバーシェル芸はチェックデジットを考慮されてないやんけ」、というツッコミが目にとまった。チェックデジットって何？ってことでググると下記のページが見つかった。

qiita.com

Rubyを使って、チェックデジットを計算。不正なマイナンバーがどうかを判定いている。他の言語でも、このページを参考にしてチェックデジットの計算をされているようだ。なーるほど、12桁目の数字がチェックデジットってやつなのか。

では上記のページを参考にして、チェックデジットが適正なマイナンバーの一覧を出してみようか。シェルのワンライナー一撃で。  

環境

  • パソコンはMac
  • OSX Yosemite
  • HomebrewでGNU系ツールとmawkを導入

Linuxな人は、gseqをseqに、gsedをsedに、gheadはheadに読み替えること。

考え方その1

チェックデジットに適合したマイナンバーを列挙することを考える。 最初は下記の処理を考えた。

  1. 12桁の数字を順に列挙する
  2. 先頭11桁からチェックデジットを計算
  3. チェックデジットと12桁目が一致する行を出力

注意点

ここに出てくるワンライナーは負荷が高い。Ctrl-Cなどで止める、もしくはプロセスの止め方を確認しておくことを忘れずに。

ワンライナー作成

では真のマイナンバーを列挙するワンライナーを作ろう。まずは12桁の数字を1桁ずつ空白で区切ったものを作成。それをmawkに渡してチェックデジットの計算をする方針で。

12桁の数字を1桁ずつ区切る処理をどうやって高速化するか？1桁ずつ区切る処理をGNU sedを使ってLANG=C gsed 's/./& /g'とやっていたが、ここがどうしてもボトルネックになってしまう。ということでTwitteで助けを求めてみた。

するとリプライが。

意味が分からなかったのでおたずねするとリプライが。ありがたや。

どのくらい処理速度が変わるかためしてみた。1000万行分の処理で計測。

$ time gseq -w 0 999999999999 | LANG=C gsed 's/./& /g' | ghead -n 10000000 > /dev/null
real   0m29.489s
user   0m34.109s
sys    0m0.362s

$ time gseq -w 0 999999999999 | mawk NF=NF FS= | ghead -n 10000000 > /dev/null
real   0m5.763s
user   0m10.311s
sys    0m0.339s

GNU sedを使うより大幅な高速化が出来た。ありがたや。

ということで、真のマイナンバーを列挙するワンライナーがこちら。GNUのseqとmawkコマンドを利用。パイプでつなぐコマンドの数は減らせるが、わかりやすさ重視で。

$ gseq -w 0 999999999999 | mawk NF=NF FS= | mawk '{print $0,($1*6+$2*5+$3*4+$4*3+$5*2+$6*7+$7*6+$8*5+$9*4+$10*3+$11*2)%11}' | mawk '$13<=1{$13=0;print}$13>1{$13=11-$13;print}' | mawk '$12==$13{$13="";print}' | LANG=C gtr -d ' '
000000000000
000000000019
000000000027
000000000035
000000000043
000000000051
000000000060
000000000078
000000000086
000000000094
....

最初のgseqで12桁の数値を連続列挙。それをmawkに渡して、チェックデジットの計算と適合した行のみ抜き出す処理をしている。1桁ずつスペース区切りにする処理はmawk NF=NF FS=で。

実はこの記事、Twitterで@ebanさんから指摘されるまで、チェックデジットの計算を間違っていたのだ。今は修正してある。だが、更に短くて高速な書き方のリプライが。

ただ、{アクション}の後ろに$12==(c<=1?0:(11-c))書かれている意味が分からん・・・ナニコレ？？リプライで意味を教えていただいた。

そして更なる高速化が。ワンランナーも超シンプルに。

$ gseq -w 0 999999999999 | mawk '{c=($1*6+$2*5+$3*4+$4*3+$5*2+$6*7+$7*6+$8*5+$9*4+$10*3+$11*2)%11}$12==(c<=1?0:(11-c))' FS=

考え方その2

しかしその後、Twitterでこんなリプライが。なんで指摘されるまで気が付かなかったのか？？？更なる飛躍的な高速化が期待出来るではないか。

ということで新しい考え方がこちら。処理するデータ量が10分の1になるね。

  1. 11桁の数字を順に列挙する
  2. チェックデジットを計算
  3. 12桁目に計算したチェックデジットを付加

ワンライナー作成

そして出来たワンライナーがこちら。なんだかとってもシンプルになった。

$ gseq -w 0 99999999999 | mawk '{c=($1*6+$2*5+$3*4+$4*3+$5*2+$6*7+$7*6+$8*5+$9*4+$10*3+$11*2)%11;d=c<=1?0:(11-c);print $0 d}' FS=

どのくらいの処理速度なのか？最初の1億人分の出力時間を計測。考え方その1に比べて約10倍近い速度になっている。

$ time gseq -w 0 99999999999 | mawk '{c=($1*6+$2*5+$3*4+$4*3+$5*2+$6*7+$7*6+$8*5+$9*4+$10*3+$11*2)%11;d=c<=1?0:(11-c);print $0 d}' FS= | ghead -n 100000000 > /dev/null
real   2m6.589s
user   2m52.486s
sys    0m3.472s
オマケ1

MacというかOSX標準装備のコマンドのみを利用したワンライナーがこちら。やっている内容は上記とほぼ同じ。処理速度はかなり遅くなる。

$ jot - 0 999999999999 | /usr/bin/awk '{c=($1*6+$2*5+$3*4+$4*3+$5*2+$6*7+$7*6+$8*5+$9*4+$10*3+$11*2)%11;d=c<=1?0:(11-c);print $0 d}' FS=
オマケ2

先日USP研究所様から、Personal Tukubaiが発売された。Open版に比べて処理速度が高速で、便利なコマンドが追加されている。

usp Tukubai

USP研究所: 出版 - ソフトウェア

Personal Tukubaiのコマンドを使ったワンライナーがこちら。利用しているPersonal Tukubaiのコマンドは、yarr、loopx、lcalcだ。特にloopxとlcalcの高速さがポイント。

$ yes '<(seq 0 9)' | head -n 11 | yarr | sed 's/^/loopx /' | bash | lcalc '$0,$1*6+$2*5+$3*4+$4*3+$5*2+$6*7+$7*6+$8*5+$9*4+$10*3+$11*2' | lcalc '$[1:11],$12%11<=1?0:11-$12%11' | gtr -d ' '

このくらい計算式が複雑になってくると、mawkとlcalcで処理速度はあまり変わらないようである。ただ上記のように計算を2つに分ける場合はlcalcの方が並列化による速度向上効果が高かった。

$ time yes '<(seq 0 9)' | head -n 11 | yarr | sed 's/^/loopx /' | bash | lcalc '$0,$1*6+$2*5+$3*4+$4*3+$5*2+$6*7+$7*6+$8*5+$9*4+$10*3+$11*2' | lcalc '$[1:11],$12%11<=1?0:11-$12%11' | gtr -d ' ' | ghead -n 100000000 > /dev/null
real   1m46.147s
user   3m9.883s
sys    0m4.496s
オマケ3

11桁の数字列挙する処理で、100000000000番台以降の場合は、Personal Tukubaiのloopxコマンドを使うより、GNU seqを使う方が処理速度が速い。桁を揃えるgseq -wオプションが遅くなる原因。

$ time gseq 100000000000 999999999999 | ghead -n 100000000 > /dev/null
real   0m2.856s
user   0m3.041s
sys    0m1.611s

$ time yes '<(seq 0 9)' | head -n 11 | yarr | sed 's/^/loopx /' | bash | ghead -n 100000000 > /dev/null
real   0m4.347s
user   0m5.901s
sys    0m1.592s

これは下記のTwtterつぶやきが参考になった。

おまけ4

@ebanさんと@kunst1080さんから下記のリプライをいただいた。チェックデジットの計算をawkのforループを使って計算する方法だ。この方が数式の表現により近い計算方法になる。なるほど。

この方法を適用してみたところ、速度が倍以上遅くなってしまった。forループなどの処理が速度面でボトルネックになってしまったのだろう。今回の場合はベタに数式を書いた方が処理が高速になった。色々と参考になる。

@kunst1080さんからリプライいただいた方法の場合は、下記のように最初にsum=0を追加して毎行sumを初期化しておこう。

$ gseq -w 0 99999999999 | mawk '{sum=0;for(i=1;i<=11;i++){a=int($0/(10^(i-1)));b=a-int(a/10)*10;if(i<=6){sum+=b*(i+1)}else{sum+=b*(i-5)}};r=sum%11;if(r==0||r==1){cd=0}else{cd=11-r}print $0 cd}'

そして並列化へ

いろいろとやっていると、この記事のブコメに上田さんから並列化〜というコメントをいただいた。ああそうか並列化出来ちゃうね。ワンライナーは辛かったので、Gistにバックグラウンドで並列化するシェルスクリプトを載せておいた。パソコンに高負荷がかかり、危険を伴うので注意して実行すべし。バックグラウンド処理の速度計測するため、グループ化とかwaitとかを使っている。

gist.github.com

そしたらGNU seqとmawkを使った場合で、xargsの-Pオプションを使った並列化についてリプライをいただいた。

おおお、結局ワンライナーで10並列書けたぞ。これならCtrl-Cですぐに停止も出来て安全！

$ seq 0 9 | xargs -P10 -I@ sh -c 'gseq $([ @ -eq 0 ] && echo -w) @0000000000 @9999999999 | mawk '\''{c=($1*6+$2*5+$3*4+$4*3+$5*2+$6*7+$7*6+$8*5+$9*4+$10*3+$11*2)%11;d=c<=1?0:(11-c);print $0 d}'\'' FS='