LoginSignup
6
1

More than 5 years have passed since last update.

組み込みのfindよりも、eachで回した線形探索の実行速度が1.26倍早かった

Last updated at Posted at 2018-09-06

配列から指定した値を探す処理を色々ためしていたら、
自前で実装した線形探索より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;
}

6
1
6

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6
1