pockestrap

Programmer's memo

RubyのArray#include?, Array#bsearch, Set#include? をベンチマークしてみた

2014-11-28 追記. Rubyのバージョンを記すのを忘れていました。

$ ruby -v
ruby 2.1.5p273 (2014-11-13 revision 48405) [x86_64-linux]

追記ここまで

コード

Array#include?, Array#bsearch, Set#include? benchm ...

計測方法

偶数の集合に対して、同じ範囲の整数の集合からランダムに選んだ数が含まれているかを試した。 100回行った場合の合計を表示する。

結果

Testcase size: 1000
Array#include?: 0.00197845s
Array#bsearch:  0.00008448s
Set#include?:   0.00004563s


Testcase size: 10000
Array#include?: 0.02032835s
Array#bsearch:  0.00011510s
Set#include?:   0.00008727s


Testcase size: 100000
Array#include?: 0.19844236s
Array#bsearch:  0.00023755s
Set#include?:   0.00018410s


Testcase size: 1000000
Array#include?: 2.07430474s
Array#bsearch:  0.00057104s
Set#include?:   0.00036839s

まとめ

Array#include?はO(n), Array#bsearchはO(log n), Set#include?もO(log n)っぽい。

Array#bsearchよりもSet#include?のほうが2倍弱高速。

Setって内部でHashを使ってるからO(1)だと思ってた。計算量よく分かってない。

その他

Array#sortEnumerable#to_set についてのベンチマークもした場合が下記。 to_setにめっちゃ時間かかるから、ループの中でやらないほうがいい。

Testcase size: 1000
Array#include?: 0.00207466s
Array#bsearch:  0.00009623s
Set#include?:   0.00005463s
-------------
Sort Init:    0.01157470s
Set Init:     0.02141142s


Testcase size: 10000
Array#include?: 0.02078428s
Array#bsearch:  0.00018172s
Set#include?:   0.00008997s
-------------
Sort Init:    0.19191684s
Set Init:     0.27025256s


Testcase size: 100000
Array#include?: 0.22206284s
Array#bsearch:  0.00053120s
Set#include?:   0.00028283s
-------------
Sort Init:    1.88486825s
Set Init:     5.17953896s


Testcase size: 1000000
Array#include?: 1.99422674s
Array#bsearch:  0.00073466s
Set#include?:   0.00034992s
-------------
Sort Init:    52.06801335s
Set Init:     59.17232136s