配列から指定した値を探す処理を色々ためしていたら、
自前で実装した線形探索よりfindメソッドの方が1.26倍遅かった。
条件:
1~10億までの数値が入った配列を、1から順に探索して10億を見つけたら終了
結果:
線形探索(自前)51.5秒
find:65.1秒
user | system | total | real | |
---|---|---|---|---|
linear_search | 50.140000 | 0.350000 | 50.490000 | ( 51.598446) |
find_method | 64.160000 | 0.260000 | 64.420000 | ( 65.156407) |
実行したコード
class Serarch
attr_reader :processed_array,:serarch_num
def initialize(processed_array,serarch_num)
@processed_array = processed_array
@serarch_num = serarch_num
end
def linear_search
processed_array.each do |n|
if n == serarch_num
return
end
end
end
def find_method
processed_array.find{|n| n == serarch_num}
end
end
理由
がわかりません!すみません!
組み込みのfindは線形ではなく別の方法で探してるのかなーとか。
findのソースだけ置いておきます。。
From: enum.c (C Method):
Owner: Enumerable
Visibility: public
Number of lines: 18
static VALUE
enum_find(int argc, VALUE *argv, VALUE obj)
{
struct MEMO *memo;
VALUE if_none;
rb_scan_args(argc, argv, "01", &if_none);
RETURN_ENUMERATOR(obj, argc, argv);
memo = MEMO_NEW(Qundef, 0, 0);
rb_block_call(obj, id_each, 0, 0, find_i, (VALUE)memo);
if (memo->u3.cnt) {
return memo->v1;
}
if (!NIL_P(if_none)) {
return rb_funcallv(if_none, id_call, 0, 0);
}
return Qnil;
}