またまた「perlで配列の引き算」をやってみた

「perlで配列の引き算」をやってみたで、さらに違うアルゴリズムでやっていたので、面白そうだから、さっそくベンチ。 (array_minus2としています。ただし、sort済み前提)

              Rate  array_diff array_minus  acme_tools array_minus2
array_diff  2.43/s          --        -50%        -83%        -91%
array_minus 4.86/s        100%          --        -65%        -82%
acme_tools  13.9/s        474%        187%          --        -48%
array_minus2 26.7/s       1002%        450%         92%          --

アクメToolsを抑えてトップスコアをたたき出しました。 並び替えておくと早いんですな。

ソートしながら配列に挿入する方法が多分ありそうだなぁ。 algorithm - ソート済み配列をソートしなおすべからず perlでモジュールないかな。 この辺は、まだまだ学習余地がいっぱいありそう・・ ぼちぼち調べていこう。

さて、sortをはさんだら、AcmeToolがやはり早い。ただ、Acme::Toolsは ハッシュに変換してから処理するのでメモリ的には消費すると思われ これもまた単純比較はできませんね。

               Rate   array_diff  array_minus array_minus2   acme_tools
array_diff   3.68/s           --         -52%         -77%         -82%
array_minus  7.63/s         107%           --         -52%         -62%
array_minus2 16.0/s         335%         110%           --         -20%
acme_tools   20.1/s         445%         163%          25%           --

外部のキーバリューストアを使う場合に、キーバリューストアにソートを頼むとか、そういう使い方をすればいいかも。キーバリューストアそのものに、配列の引き算機能があるかもかもだけど。。

Redisにはsdiffというコマンドがあった！ http://redis.shibu.jp/commandreference/sets.html#command-SDIFF

というわけで、RedisのSDIFFを使ってみた。驚愕のスピードですが、 データを入れるところはカウントしていません。 そもそも、データをRedisに格納しているならば、 素直にRedisを使うべしですなぁ。

                           Rate          array_diff        array_minus       array_minus2         acme_tools redis
array_diff               2.32/s                  --               -54%               -80%               -83% -100%
array_minus              5.09/s                119%                 --               -56%               -64% -100%
array_minus2             11.4/s                392%               125%                 --               -18% -100%
acme_tools               14.0/s                501%               175%                22%                 -- -100%
redis        5000000000000000/s 215199999999999968% 98300000000000048% 43700000000000032% 35800000000000012%    --