数学好きじゃ無かったんだけど、今の会社に2年いて徐々にアルゴリズムというものに興味が沸いている。とにかく普通だとアホみたいに時間がかかることが、アルゴリズムのマジックにかかると一瞬で終わることがあるのが凄い。とはいえ、数学は嫌いだし、自分で計算するのは嫌だ。とにかくラクをしたいからこの仕事をしている、というのだろうか、俺がラクをするということ=みんながラクになる、費用対効果がわかりやすい、そういう会社であると俺は感じている。
今抱えてる仕事で、segmented prefix scan というアルゴリズムがでてきたので世界に聞いてみた。
Qiita – プログラマの技術情報共有サービス
segmented prefixscanはグループ毎に集合演算をかけることができて、途中結果も各要素に出力できる。10要素なら4回、32要素なら5回演算するだけでいい(segmentedの場合はもっと少なくていい場合もある)ので、要素が多ければ多いほど階乗的に速くなるはずだが、いろんなボトルネックがあってそうもいかないのが面白い。
これをちょっと改良して、並列でグループ毎に累積を行い、累積を行わないところはゼロにする。なんてことができるようになったのだが、まだうまく動いていないようで今日は海に行くことができない(苦笑)
コメント