ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »Ruby
カテゴリー「Ruby」の記事一覧

【Ruby】二分探索, lower_bound, upper_bound  


 Ruby2.3 以降には見つけた値のインデクスを返す Array.bsearch_index() があるのだが、自作した方が使い勝手が良いことも多いので、Java 版をそのまま移植してみた。


なお、組み込み関数の場合は以下のようになる。

●Ruby の bsearch_index で lower_bound, upper_bound 的な動作 (Ruby 2.3以降)
     #[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3;
lower = arr.bsearch_index{|x| x >= v} #lower_bound 的(ただし、見つからない=nil) (Ruby 2.3以降)
upper = arr.bsearch_index{|x| x > v} #upper_bound 的(ただし、見つからない=nil) (Ruby 2.3以降)
print "lower = #{lower}\n"
print "upper = #{upper}\n"

lower = 2
upper = 5

 値の意味は lower_bound 的な方は「指定した値以上の先頭の要素を返す」ことになるので、配列 arr 内で v = 3 が続く値の先頭インデクス = 2 を、upper_bound 的な方は「指定した値より大きい先頭の要素を返す」ことになるので、v = 3 が続く値より後ろのインデクス = 5 という意味になる。

 ちなみに Array.bsearch() の方は要素の値そのものを返す。今回の関数と組み込み関数との大きな違いは、値が見つからないとき nil (組み込み関数)か、近いインデクスを返す(今回の関数)かという感じだ。実は見つからないとき値を返すようにしておくと、色々利用できるのでわざわざ Java から(元はC++) 移植したわけだ。

●二分探索:binary_search, lower_bound, upper_bound (オープンクラス版)
#オープンクラス版
class Array
#二分探索(同値連続はインデクス不定となる)
#見つからないとき=負の値となり、~index で挿入位置になる
def binary_search(value, from = 0, to = self.size)
low = from
high = to - 1
while low <= high
mid = (low + high) / 2
if self[mid] < value
low = mid + 1
elsif self[mid] > value
high = mid - 1
else
return mid
end
end
-(low + 1) #見つからない(~index で挿入位置)
end

#指定した値以上の先頭のインデクスを返す
def lower_bound(value, from = 0, to = self.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if self[mid] < value
low = mid + 1
else
high = mid
end
end
low
end

#指定した値より大きい先頭のインデクスを返す
def upper_bound(value, from = 0, to = self.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if self[mid] <= value
low = mid + 1
else
high = mid
end
end
low
end

end


#メインでは...
#[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3; #検索する値
print "binary_search = #{arr.binary_search(v)}\n"
print "lower_bound = #{arr.lower_bound(v)}\n"
print "upper_bound = #{arr.upper_bound(v)}\n"

print "bsearch_index(lower) = #{arr.bsearch_index{|x| x >= v}}\n" #lower_bound 的(ただし、見つからない=nil) (Ruby 2.3)
print "bsearch_index(upper) = #{arr.bsearch_index{|x| x > v}}\n" #upper_bound 的(ただし、見つからない=nil) (Ruby 2.3)

binary_search = 3
lower_bound = 2
upper_bound = 5
bsearch_index(lower) = 2
bsearch_index(upper) = 5

 意味は組み込み関数の例とだいたい同じになる。違いは値が見つからないときの戻値だ。例えば検索する値を v = 2 とすると、組み込み関数の場合 nil となるが、lower_bound()、upper_bound() は 2 となる。binary_search() の場合は -3 という値が返るが、この値はビット反転すると(~index = ~(-3))2 となる。つまり、binary_search() の場合、同値が連続しているとき、どのインデクスになるかは不定だが、負の値が返ってきたとき見つからなかったことがわかるので、処理分岐がしやすい利点がある。

 また、Ruby には関数のオーバーロードがないので、検索範囲を決める引数(from = 開始インデクス、to = 終了インデクス[このインデクスは含まない] はデフォルト値を設定してある(デフォは配列の最初から最後まで)。検索するインデクス範囲がわかっているなら、絞り込めば更に高速に動作する。余談だが、範囲を決める引数を関数に持たせる場合、終了インデクスは「含まない」としておくと、差分計算や連続検索などしやすくなる(標準ライブラリ等もだいたいそうなっている)。

 あと lower_bound() も upper_bound() も要素の最大より上の値を検索すれば、配列の長さと同じ値が返ってくる(例えば、v = 9 とすれば、どちらもインデクス = 15 が返る)。これらは値が見つからないとき、配列の最後に値を追加するのに使える。この方法を使えば、リアルタイムにソート済み配列を作ることも可能だ。試しにやってみよう。

●二分探索でソート済み配列を作る
arr = [3, 5, 6, 4, 2, 0, 8, 7, 1, 9]
sorted = []

arr.each{|e|
sorted.insert(sorted.upper_bound(e), e)

# sorted.insert(sorted.lower_bound(e), e)

# idx = sorted.binary_search(e)
# if idx < 0
# idx = ~idx
# end
# sorted.insert(idx, e)
}

p arr
p sorted

[3, 5, 6, 4, 2, 0, 8, 7, 1, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 この場合は binary_search(), lower_bound(), upper_bound() どれを使っても同じになる。しかし実際には同値がある場合、binary_search() は同値の中ではそのどこかに、lower_bound() の場合は同値の先頭に、upper_bound() の場合は同値の一番最後(=検索値の次の値の先頭)に挿入されることになる。追加順序が必要な場合は使い分けた方が良いだろう。もちろんこの例の場合は最後にソート(Array.sort())でも良いが、リアルタイムに追加・削除を繰り返す場合は、何度もソートするより負荷が軽くなる。

 もう1つ、lower_bound() と upper_bound() を上手く使う例として、指定範囲内の値の個数を求めてみよう。

●lower_bound() と upper_bound() で検索範囲内の値の個数を求める
arr = [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 9, 9]

lo, hi = 1, 3 #検索する値の範囲
fr = arr.lower_bound(lo) #開始インデクスを表す
to = arr.upper_bound(hi) #終了インデクスを表す[このインデクスは含まない]

p arr
print "fr = #{fr}, to = #{to}, cnt = #{to - fr}\n" #差分が個数
p arr.slice(fr, to - fr) #範囲を抜き出し

[0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 9, 9]
fr = 3, to = 17, cnt = 14
[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]

 この例は配列の中から、検索する値 = 1~3 のインデクス範囲(3~17 [17は含まない])を取得し、差分から個数を求めている。Array.slice() はおまけでその範囲を抜き出して表示しているだけだ。もちろんこのくらいの数なら逐次検索でもそれほど差がないかも知れないが、要素数が多くなると効果はてきめんとなる。

 最後にオープンクラスで使いたくない人のためにも通常のメソッドでも書いておこう。内容は全く同じになるので、好きな方を使えば良い。

●二分探索:binary_search, lower_bound, upper_bound (通常メソッド版)
#二分探索(同値連続はインデクス不定となる)
#見つからないとき=負の値となり、~index で挿入位置になる
def binary_search(arr, value, from = 0, to = arr.size)
low = from
high = to - 1
while low <= high
mid = (low + high) / 2
if arr[mid] < value
low = mid + 1
elsif arr[mid] > value
high = mid - 1
else
return mid
end
end
-(low + 1) #見つからない(~index で挿入位置)
end

#指定した値以上の先頭のインデクスを返す
def lower_bound(arr, value, from = 0, to = arr.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if arr[mid] < value
low = mid + 1
else
high = mid
end
end
low
end

#指定した値より大きい先頭のインデクスを返す
def upper_bound(arr, value, from = 0, to = arr.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if arr[mid] <= value
low = mid + 1
else
high = mid
end
end
low
end


#メインでは...
#[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3; #検索する値

print "binary_search = #{binary_search(arr, v)}\n"
print "lower_bound = #{lower_bound(arr, v)}\n"
print "upper_bound = #{upper_bound(arr, v)}\n"

s, e = 3, 6 #検索する値の範囲
fr = lower_bound(arr, s)
to = upper_bound(arr, e)
print "fr = #{fr}, to = #{to}, cnt = #{to - fr}\n"

binary_search = 3
lower_bound = 2
upper_bound = 5
fr = 2, to = 12, cnt = 10


 オンラインジャッジの問題でも上級レベルになるほど、逐次検索では計算量が間に合わずタイムアウトしやすくなる。CodeIQ でも paiza でもランク A, S(★★★★)問題には必要となるシーンも多いので、使える場合は積極的に使ってみると良いだろう(要するに単純な昇順・降順データ・累積和・フィボナッチのような増加数列には使った方が安全)。標準ライブラリにあるものでも、その実装に近いものを知っていれば柔軟に対応できるようになるので、色々改造して使うと良いだろう。


(関連記事)
【Java】lower_bound(), upper_bound() 関数を作る
【Java】二分探索を汎用的に使えるようにする


■参考になる書籍


スポンサーサイト

category: Ruby

thread: プログラミング

janre: コンピュータ

tag: 配列操作  二分探索 
tb: 0   cm: --

【Ruby】階乗・順列・組合せの個数を求める  


 配列の生成ではなく、場合の数としての個数が欲しかったので、Java と同じ factorial, permutation, combination を移植してみた。ただ、Ruby には「inject」のような便利な畳み込み計算があるので、そこだけ修正。ループで計算もやってみたが、巨大な値の計算になると実行速度は inject の方がわずかに速いようだ。手抜き(笑)で負の値や不正値のエラーなどは書いてないので、必要であれば自分で付け足して使って欲しい。

●階乗・順列・組合せの個数(オープンクラス版)
#階乗・順列・組合せの個数(オープンクラス)
class Integer
def factorial
return 1 if self == 0
(1..self).inject(:*)
end

def permutation(r)
return 1 if self == 0
s = self - r + 1
(s..self).inject(:*)
end

def combination(r)
r = [r, self - r].min
return self if r == 1
return 1 if r == 0
self.permutation(r) / r.factorial
end
end


#メインでは...
n = 6
r = 3
print "#{n}! = #{n.factorial}\n"
print "#{n}P#{r} = #{n.permutation(r)}\n"
print "#{n}C#{r} = #{n.combination(r)}\n"

6! = 720
6P3 = 120
6C3 = 20

 Java 版のときにも少し書いたが、この手の単純な計算の場合、再帰では書かない方が良いだろう。やってみればわかるが、特に combination(組合せの数) などは再帰でやると、大きな値を計算するときに非常に重くなる。オンラインジャッジではタイムアウトし兼ねないので、単純なコードの方が安全だ。

 オープンクラスで使いたくないなら、下記の通常のメソッド版でも良いだろう。Java から見ると C# の拡張メソッドなども羨ましい限りだけどね(Java8 でもインターフェイスの default 実装で同じようなことができるという話もあるが…)。確かに複数人で開発するときは、勝手に上書きされるのを嫌う人もいるかもしれない。

●階乗・順列・組合せの個数(通常のメソッド版)
#階乗・順列・組合せの個数(通常のメソッド)
def factorial(n)
return 1 if n == 0
(1..n).inject(:*)
end

def permutation(n, r)
return 1 if n == 0
s = n - r + 1
(s..n).inject(:*)
end

def combination(n, r)
r = [r, n - r].min
return n if r == 1
return 1 if r == 0
permutation(n, r) / factorial(r)
end


#メインでは...
n = 6
r = 3
print "#{n}! = #{factorial(n)}\n"
print "#{n}P#{r} = #{permutation(n, r)}\n"
print "#{n}C#{r} = #{combination(n, r)}\n"

6! = 720
6P3 = 120
6C3 = 20

 Ruby は巨大な桁になる計算でもオーバフローを気にしないでいい所が良いね。順列や組合せの個数は解法そのものに必要なくても、計算量を算出したり、おおよその答えの個数を考えたりするのに非常によく使う。私はちょっとしたコードを試したり、ネットで見つけたコードを分析したりするだけなので、Rails ではなく、Eclipse にプラグインを入れて試しているが、環境を作るのが面倒だと思ったら、「paiza.io」や「ideone」などのオンライン環境を使うのも手だ。実際に私は書いたコードをオンライン環境でよく試している(オンライン環境でタイムアウトしないコードが書ければ、オンラインジャッジは全て通過できる)。特に「paiza.io」は日本語に対応しているから使いやすいしね。使ったことない言語でも、ググって見つけたコードをすぐに試せるのでオススメだ(笑)。それにしても、いつでもオンラインで調べものも勉強も環境も簡単にできるし、いい時代になったもんだ…。最後に環境構築に役立つURLを参考に載せておこう。

(参考)
WindowsでEclipse+Ruby
eclipseでRuby開発を行ってみる
EclipseでRubyの開発環境を構築した時のメモ
Pleiades All in One - Eclipse プラグイン日本語化プラグイン

(オンラインIDE)
paiza.io
ideone


(関連記事)
【Java】組合せの数を求める
【Java】順列の数を求める
【Java】プリミティブ型での階乗計算


category: Ruby

thread: プログラミング

janre: コンピュータ

tag: 算術関数 
tb: 0   cm: --


プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop