実は一ヶ月ほどまえに嫁に10000円以上する分厚いアルゴリズムの教科書を買ってもらった。
MIT Press の Introduction to Algorithm という本である。技術書については日本語だと読解力が極端に落ちるし苦痛なので、オリジナルのものを海外から取り寄せてもらった。
ちょうど今350ページくらいのところで、4分の１以上は読破したんだけどそれでも分厚い。分厚すぎて死ぬ.... つうかこの本で筋トレできるぞ....
と思っていた。正直、アルゴリズムとかCSってそもそもエンジニアやるうえで役に立つのかよ、と思っていたし、数式とかをひたすら追っかけるよりもコードをやったほうがいいんじゃ... と思った時期もあった。
だがそれは違っていた。
今日、あるバグが起こって、もちろん細かいことは言えないんだけど仕様として、
.sort { x -> "{x.attr1}-{x.attr2}" }
という記載があった。{} のところは String interpolation として、こいつによってソートにバグが起こってて、つまり
5001-1
50011-1
5002-2
みたいな３つのデータがあったときに、上記ソートだと 5001-1, 50011-1, 5002-2 みたいな順列になり、本来数字の順番からいえば 5001-1, 5002-2, 50011-1だからおかしい。
じゃあフォーマットするか、という発想になるがそれはおおよそ「愚か」で、桁数なんていくつまで増えるかわかんないし、そもそもそういうのは文系SE的な発想でそもそもいけてない。
ここで僕は一瞬思いとどまった。アルゴリズムの教科書の内容を思い出したのである。
radix sort だ！！！！！
radix sortってのは例えば日付データなんかをプログラミング言語がソートするときに使うんだけど、例えば、
123, 67, 12, 55, 4, 999 っていう数字があり、これを小さい順に並べ替えたい。
この際この数を縦に並べて（そして２桁目３桁目がないところは０、として）
123
067
012
055
004
999
ってなる。まずこれについて、一の位だけをみてソートする。
012
123
004
055
067
999
そうすると、１の位だけにフォーカスしてるから、 2 < 3< 4< 5 < 7 < 9で上になる。
次は、２の位だけをみてソートする
004
012
123
055
067
999
0 < 1 < 2 < 5 < 6 < 9 でこの組み合わせになる。次に３の位をみて、
004
012
055
067
123
999
0 < 0 < 0 < 0 < 1 < 9
でフィニッシュである。
見るとわかると思うけど、きちんと小さい順に並んでいることがわかる。
ちなみに radix の一つの位自体をソートするのにどのソートをかませるかは作る側に選ぶ権利が与えられているが、例えば counting sort を使ったりするらしい。
日付で考えてみよう
1992/12/13
2020/1/8
2001/5/2
2019/5/12
2001/1/1
1992/1/1
まず日付でソート
2001/1/1
1992/1/1
2001/5/2
2020/1/8
2019/5/12
1992/12/13
次に月でソート
2001/1/1
1992/1/1
2020/1/8
2001/5/2
2019/5/12
1992/12/13
最後に年でソート
1992/1/1
1992/12/13
2001/1/1
2001/5/2
2019/5/12
2020/1/8
無事、日付が昔の順に並んだ。
さて、今回私が業務でぶち当たった問題についても、
.sort { x -> "{x.attr1}-{x.attr2}" }
こんな愚かなハイフン区切りの文字列で実装するのではなく、
.sortBy(x -> x.attr2)
.sortBy(x -> x.attr1)
とすればよかったのでした。重要なのは、一番下の位からソートしていくこと。計算量も爆発的に増えることはないので、まあよしというところでしょう。
このように、問題とか複雑系について、いろいろな困難にぶちあたったときに、まるで格闘技の型みたいに脊髄反射で適切な対処を一発で当てることができる.... そういう意味でアルゴリズムは貴重だと思いましたし、やっぱり1万円の本って1万円の価値があるねんなあ。。。。と思ったわけです。
まあ、そんなかんじで。
No comments:
Post a Comment