RubyのArray#include?, Array#bsearch, Set#include? ベンチマーク
Arrayクラスにbsearch(Binary Search: 二分探索)なるものがあるということでその速さを検証してみました
二分探索
二分探索ってなんだ？って人はこちらを参照してください
https://www.codereading.com/algo_and_ds/algo/binary_search.html
要約すると配列の真ん中からだんだん範囲を絞って行くということです
そのため事前にソートしておく必要があります
大学の授業で、C言語で二分探索実装したのを思い出しました(懐かしい
Ruby version 2018年2月25日現在
ruby 2.4.1p111 (2017-03-22 revision 58053) [x86_64-darwin17]
ソースコード
実行結果
TestArray size: 1000000
| method | execution time |
|---|---|
| Array#include? | 0.30897300s |
| Array#bsearch | 0.00052300s |
| Set#include? | 0.00031000s |
| SetInIt time | 29.90226800s |
考察
各メソッドの実行時間のみを見るとSet#include?が一番早いが、Array#to_setに時間がかかるため、bsearchの方が実用的だと考えられます
参考サイトの3年以上前のものと比べると、Array#include?とArray#to_setが高速化されているのがわかります↓↓↓