この記事はQiitaの記事をエクスポートしたものです。内容が古くなっている可能性があります。
問: ある配列において最大値とそのインデックス,最小値とそのインデックス、その配列の長さを求めたい。
解法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)
になる。
解法2は配列の長さを調べるために一回、最大値を求めるために一回、最大値のインデックスを求めるために一回、最小,,,で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はインタプリタ方式であるためである。それにしても、こんなに実行速度に差がでるとは思わなかった。まだまだ、無知だしガバガバなこといってるのでどんどんコメントお願いします🍺