🍺Rubyでプログラミングテストをしているとき、愚直な実装とライブラリの実行速度が気になって調べた漢の話

問: ある配列において最大値とそのインデックス,最小値とそのインデックス、その配列の長さを求めたい。

解法1

ループを一度実行することですべてを求める。

array = Array.new(10000000).map{ rand(0..10000000) }

result = Benchmark.realtime do

  count = 0
  max_i, max = 0, 0
  min_i, min = 0, 10000000000
  array.each_with_index do |num, i|
    count += 1
    max_i, max = i, num if num > max
    min_i, min = i, num if num < min
  end

end
puts "loop: #{result}s"

解法2

全てライブラリを使って求める。

array = Array.new(10000000).map{ rand(0..10000000) }

result = Benchmark.realtime do

  count = array.length
  max = array.max
  max_i = array.index(max)
  min = array.min
  min_i = array.index(min)

end
puts "lib: #{result}s"

昨日の僕の考え

解法1の計算量は、一度のループなので計算量は

O(n)

になる。

解法２は配列の長さを調べるために一回、最大値を求めるために一回、最大値のインデックスを求めるために一回、最小,,,で5回ループを回しているはずなので計算量は

O(5n)       =>     O(n)

になる。　　
したがって、計算量は変わらないがそれでも5回ループを回しているので解法1の方が多少早いと考えていた。(薄々、解法2の方が早いのではないかと考えていたから調べることになったのだが。)

結果

以下のような結果になった。

# ライブラリなしループ
loop: 0.792141999991145s

# ライブラリ
lib: 0.09372099999745842s

なんと、ライブラリを用いた方が8倍程度高速に実行した。思ったよりも全然早かった。
そうなると、なぜこうなるのかライブラリの内部実装を調べてみた。

内部実装

調べ方
まず。REPLであるpryとpry-docをインストールしpryコマンドで起動する。

$ gem install pry
$ gem install pry-doc

# REPL起動
$ pry

show-sourceコマンドを用いることでrubyのソースコードを読むことができる。

[2] pry(main)> show-source Array#index

From: array.c (C Method):
Owner: Array
Visibility: public
Number of lines: 37

static VALUE
rb_ary_index(int argc, VALUE *argv, VALUE ary)
{
    const VALUE *ptr;
    VALUE val;
    long i, len;

    if (argc == 0) {
    RETURN_ENUMERATOR(ary, 0, 0);
    for (i=0; i<RARRAY_LEN(ary); i++) {
        if (RTEST(rb_yield(RARRAY_AREF(ary, i)))) {
        return LONG2NUM(i);
        }
    }
    return Qnil;
    }
    rb_check_arity(argc, 0, 1);
    val = argv[0];
    if (rb_block_given_p())
    rb_warn("given block not used");
    len = RARRAY_LEN(ary);
    ptr = RARRAY_CONST_PTR(ary);
    for (i=0; i<len; i++) {
    VALUE e = ptr[i];
    switch (rb_equal_opt(e, val)) {
      case Qundef:
        if (!rb_equal(e, val)) break;
      case Qtrue:
        return LONG2NUM(i);
      case Qfalse:
        continue;
    }
    len = RARRAY_LEN(ary);
    ptr = RARRAY_CONST_PTR(ary);
    }
    return Qnil;
}
[3] pry(main)> show-source Array#max

From: array.c (C Method):
Owner: Array
Visibility: public
Number of lines: 32

static VALUE
rb_ary_max(int argc, VALUE *argv, VALUE ary)
{
    struct cmp_opt_data cmp_opt = { 0, 0 };
    VALUE result = Qundef, v;
    VALUE num;
    long i;

    rb_scan_args(argc, argv, "01", &num);

    if (!NIL_P(num))
       return rb_nmin_run(ary, num, 0, 1, 1);

    if (rb_block_given_p()) {
    for (i = 0; i < RARRAY_LEN(ary); i++) {
       v = RARRAY_AREF(ary, i);
       if (result == Qundef || rb_cmpint(rb_yield_values(2, v, result), v, result) > 0) {
           result = v;
       }
    }
    }
    else {
    for (i = 0; i < RARRAY_LEN(ary); i++) {
       v = RARRAY_AREF(ary, i);
       if (result == Qundef || OPTIMIZED_CMP(v, result, cmp_opt) > 0) {
           result = v;
       }
    }
    }
    if (result == Qundef) return Qnil;
    return result;
}

それほど、Cのコードは読めないしこれだけじゃ明らかに読めないが配列の長さのループを回していることはなんとなくわかる。なので、魔法を使って最大値を求めていたりはしない。よって、ライブラリにより計算量も

O(n)

である。

なぜ,Array#max Array#indexは早いのか

これは、Cの実行速度がrubyよりも高速であるためだと考えられる。Cはコンパイル方式であるが、rubyはインタプリタ方式であるためである。それにしても、こんなに実行速度に差がでるとは思わなかった。まだまだ、無知だしガバガバなこといってるのでどんどんコメントお願いします🍺