読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】正規表現、階乗(Hashの遅延評価を利用)、集合(Setクラス)

 

正規表現

#後方参照は\1
"h\"hh'aa'g\"e" =~ /(['"])[^\1]*\1/
p $~

#名前つきグループ
"hpijiph" =~ /(?<first>\w)(?<second>\w).*\k<second>\k<first>/
p $~

"RUBY" =~ /ruby/i
p $~

#部分的な大文字小文字の無視
"RUBY" =~ /R(?i:uby)/
p $~.end(0)

#マッチ終端
/(foo)(bar)(BAZ)?/ =~ "foobarbaz"
p $~.end(0)   # => 6
p $~.end(1)   # => 3
p $~.end(2)   # => 6
p $~.end(3)   # => nil
p $~.end(4)   # => `end': index 4 out of matches (IndexError)

 
■実行結果

#<MatchData "\"hh'aa'g\"" 1:"\"">
#<MatchData "hpijiph" first:"h" second:"p">
#<MatchData "RUBY">
#<MatchData "RUBY">

 
 

Enumrator#with_index

with_indexメソッドによって、インデックスも渡すEnumratorが取得できる

p "ruby".each_char.with_index
p "ruby".each_char.with_index.next
"ruby".each_char.with_index.each{|ch,index| puts "#{ch}, #{index}"}

 
■実行結果

#<Enumerator: #<Enumerator: "ruby":each_char>:with_index>
["r", 0]
r, 0
u, 1
b, 2
y, 3

 
今まで「なんか無駄なこと書いてるぽいな」と感じつつもこうやって書いてた

"ruby".each_char.each_with_index {|ch,index| p "#{ch}, #{index}"}

each_charメソッドでEnumeratorになってるから、わざわざEnumerableのメソッドを使わなくてもいい。
知ったからには活用しよう。

 

階乗

Hashのデフォルトブロックを使って階乗を実装する。
ポイントは計算した値をキーに対応付けているところ( hash[key] = XXX の部分)。

fact = Hash.new{|hash, key| hash[key] = ( key>1 ? key*hash[key-1] : 1 )}
p fact[10]
p fact

 
■実行結果

3628800
{1=>1, 2=>2, 3=>6, 4=>24, 5=>120, 6=>720, 7=>5040, 8=>40320, 9=>362880, 10=>3628800}

 
キーに対応付けないと、都度計算になってしまう。

fact = Hash.new{|hash, key| key>1 ? key*hash[key-1] : 1 }
p fact[10]
p fact
||< 
■実行結果
>||
3628800
{}

 

集合を使う

集合の実装の特徴は、メンバかどうかのテスト、挿入、削除を高速にサポートすることである。

メンバかどうかのテストを高速に行える!
これはおいしい。

しかし使いどころが?
既存のEnumrable(Arrayとか)をわざわざSetインスタンスにするメリットがある位はやいのかな?
 
ベンチマークしてみた

require 'set'
require 'benchmark'
sample = (1..10**7).to_a.shuffle
set = Set.new(sample)
Benchmark.bm do |x|
  x.report { p set.include?(1) }
  x.report { sample.include?(1) }
end

 
■実行結果

       user     system      total        real
 true
  0.000000   0.015000   0.015000 (  0.001000)
   0.297000   0.000000   0.297000 (  0.305017)

やばい!
ぜんぜん時間が違う!

setだけ pメソッドで結果を表示表示させてるのは、
あまりに早くてちゃんと動いてるのかなーって疑ってしまったから。
疑ってごめんね。。
 
でもSetインスタンスを作るのにすごい時間がかかる。

sample = []
Benchmark.bm do |x|
  x.report("test1") do
    sample = (1..10**7).to_a.shuffle
  end
  x.report("test2") do
    set = Set.new(sample)
  end
end

■実行結果

       user     system      total        real
test1  0.905000   0.000000   0.905000 (  0.892051)
test2  6.911000   0.093000   7.004000 (  7.011401)

うーん。。。だめだこりゃ。

ArrayをわざわざSetに変える方法ではなくて、
要素の順序を気にしないときは最初からSetで実装する。
を意識する方法でいこう。