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#sort
と Enumerable#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