Ruby_Array_10

Ruby

この記事は、以下のドキュメントを改変（自分なりに整理）して利用しています。

class Array (Ruby 3.0.0 リファレンスマニュアル)

インスタンスメソッド

push(*obj) -> self
append(*obj) -> self
  • 指定されたobjを順番に配列の末尾に追加する
    • 引数を指定しなければ何もしない
irb(main):001:1> arr = [1, 2, 3]
=> [1, 2, 3]

irb(main):002:0> arr.push(4)
=> [1, 2, 3, 4]

irb(main):003:0> arr
=> [1, 2, 3, 4]

irb(main):004:0> arr.push([5, 6])
=> [1, 2, 3, 4, [5, 6]]

irb(main):005:0> arr
=> [1, 2, 3, 4, [5, 6]]

irb(main):006:0> arr.push(7, 8)
=> [1, 2, 3, 4, [5, 6], 7, 8]

irb(main):007:0> arr
=> [1, 2, 3, 4, [5, 6], 7, 8]

irb(main):008:0> arr.push
=> [1, 2, 3, 4, [5, 6], 7, 8]

irb(main):009:0> arr
=> [1, 2, 3, 4, [5, 6], 7, 8]

# memo
# 引数を指定しなくてもエラーにはならない
# selfを返す
assoc(key) -> Array | nil
  • 配列の配列を検索し、その0番目の要素がkeyに==で等しい最初の要素を返す
irb(main):001:0> arr = [[1, 'a'], [5, 'b'], 'c', nil] 
=> [[1, "a"], [5, "b"], "c", nil]

irb(main):002:0> arr.assoc(1)
=> [1, "a"]

irb(main):003:0> arr.assoc(5)
=> [5, "b"]

irb(main):004:0> arr.assoc(10)
=> nil

irb(main):005:0> arr.assoc('c')
=> nil

irb(main):006:0> arr.assoc(nil)
=> nil

# memo
# 配列の要素全てが配列でなくてもエラーは起きない
bsearch { |x| ... } -> object | nil
bsearch -> Enumerator
  • ブロックの評価結果で範囲内の各要素の判定を行い、条件を満たす値を二分探索(計算量は O(log n))で検索する。
    • 要素が見つからない場合はnilを返す
    • selfはあらかじめソートしておく必要あり
  • ブロックを評価した結果により、以下のいずれかのモードで動作する
    • find-minimumモード
      • 特に理由がない限りこのモードを使った方がいいみたい
      • 条件の判定結果を次のようにする必要がある
        • 求める値がブロックパラメータの値か前の要素: trueを返す
        • 求める値がブロックパラメータより後の要素: falseを返す
      • ブロックの評価結果が true になる最初の要素を返すか、nil を返す
    • find-anyモード
      • bsearchのように動作する
      • ブロックは真偽値ではなく、以下のような数値を返す必要がある。求める要素が配列のi番目からj-1番目までに入っているとする。またブロックパラメータの値のインデックスを k とする。
        • ブロックパラメータの値が求める値の範囲よりも小さい（0 <= k < i）: 正の数を返す
        • ブロックパラメータの値が求める値の範囲に合致する（i <= k < j）: 0を返す
        • ブロックパラメータの値が求める値の範囲よりも大きい（j <= k < self.size）: 負の数を返す
      • ブロックの評価結果が0になるいずれかの要素を返すか、nil を返す
  • 2つのモードを混在して使用しないこと
    • ブロックの評価結果は常にtrue/false、数値、いずれかを一貫して返すこと
  • ブロックが与えられなかった場合はEnumeratorのインスタンスを返す
irb(main):001:0> arr = [1, 3, 5, 7, 9]
=> [1, 3, 5, 7, 9]

irb(main):002:1> arr.bsearch {|x| x >= 5 }
=> 5

irb(main):003:0> arr.bsearch {|x| x >= 6 }
=> 7

irb(main):004:0> arr.bsearch {|x| x >= -5 }
=> 1

irb(main):005:0> arr.bsearch {|x| x >= 10 }
=> nil

irb(main):001:1> ary = [0, 4, 7, 10, 12]
=> [0, 4, 7, 10, 12]

irb(main):002:0> ary.bsearch {|x| 1 - x / 4 }
=> 7

irb(main):003:0> ary.bsearch {|x| 4 - x / 2 }
=> nil

# memo
# これはサンプルの例だが、理解ができていない
# 一つ目が「# 4 <= v < 8 になる要素を検索」
# 二つ目が「# 8 <= v < 10 になる要素を検索」
# どういうこと？なんでそれを検索することになる？

irb(main):001:0> require 'benchmark'
=> true

irb(main):002:0> arr = (1..100000).to_a
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,...

irb(main):003:0> Benchmark.bm do |x|
irb(main):004:0>   x.report('select:  ') { arr.select {|v| v >= 99999 } }
irb(main):005:0>   x.report('bsearch: ') { arr.bsearch {|v| v >= 99999 } }
irb(main):006:0> end
       user     system      total        real
select:    0.005500   0.000024   0.005524 (  0.005558)
bsearch:   0.000005   0.000001   0.000006 (  0.000005)
=> [#<Benchmark::Tms:0x00007fef103724e8 @label="select:  ", @real=0.005558000004384667, @cstime=0.0, @cutime=0.0, @stime=2.4000000000024002e-05, @utime=0.005499999999999616, @total=0.00552399999999964>, #<Benchmark::Tms:0x00007fef10371c50 @label="bsearch: ", @real=5.00003807246685e-06, @cstime=0.0, @cutime=0.0, @stime=9.999999999732445e-07, @utime=4.999999999810711e-06, @total=5.999999999783956e-06>]

# memo
# 探したい要素が後ろにあるとbsearchが速い。結構差がある。
# 要素が見つからなかったら、selectは[]、bsearchはnilを返すという違いはある

irb(main):001:0> require 'benchmark'
=> true

irb(main):002:0> arr = (1..100000).to_a
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,...

irb(main):003:0> Benchmark.bm do |x|
irb(main):004:0>   x.report('select:  ') { arr.select {|v| v >= 10 } }
irb(main):005:0>   x.report('bsearch: ') { arr.select {|v| v >= 10 } }
irb(main):006:0> end
       user     system      total        real
select:    0.008674   0.000352   0.009026 (  0.023405)
bsearch:   0.010142   0.000219   0.010361 (  0.021525)
=> [#<Benchmark::Tms:0x00007fbad7212f98 @label="select:  ", @real=0.02340499998535961, @cstime=0.0, @cutime=0.0, @stime=0.00035199999999996345, @utime=0.00867400000000007, @total=0.009026000000000034>, #<Benchmark::Tms:0x00007fbad7212700 @label="bsearch: ", @real=0.021524999989196658, @cstime=0.0, @cutime=0.0, @stime=0.00021900000000002473, @utime=0.010141999999999207, @total=0.010360999999999232>]

# memo
# 探したい要素が前にあるとselectが若干早い。差があまりない。
# 要素が見つからなかったら、selectは[]、bsearchはnilを返すという違いはある
bsearch_index { |x| ... } -> Integer | nil
bsearch_index -> Enumerator
  • ブロックの評価結果で範囲内の各要素の判定を行い、条件を満たす値の位置を二分探索(計算量は O(log n))で検索する
    • 要素が見つからない場合はnilを返す
    • selfはあらかじめソートしておく必要がある
  • Array#bsearchとの違いは、見つかった要素自身を返すか位置を返すかのみ
irb(main):001:0> arr = [1, 3, 5, 7, 9]
=> [1, 3, 5, 7, 9]

irb(main):002:0> arr.bsearch_index {|x| x >= 5 }
=> 2

irb(main):003:0> arr.bsearch_index {|x| x >= 6 }
=> 3

irb(main):004:0> arr.bsearch_index {|x| x >= -5 }
=> 0

irb(main):005:0> arr.bsearch_index {|x| x >= 10 }
=> nil

irb(main):001:0> ary = [0, 4, 7, 10, 12]
=> [0, 4, 7, 10, 12]

irb(main):002:0> ary.bsearch_index { |x| 1 - x / 4 }
=> 2

irb(main):003:0> ary.bsearch_index { |x| 4 - x / 2 }
=> nil

メモ

  • assocはどんな場面で使うのだろう
  • bsearchは二分探索アルゴリズム自体をしっかり把握していないのでそのものの理解をしたい