前回の投稿ではsleep sortと、それに対抗したrunning sortを紹介したよ。

sleep sortに対抗してrunning sortだ!(失敗に終わる編)

それらのアルゴリズムではRubyのThreadを使ったけど、Threadってなんか毎回書き方を忘れるよ。引数の受け渡し方とかjoinとか、もっと簡単にスレッディングしたいのにねぇ…

それでEnumerableなオブジェクトに対して、渡したブロックを並列処理してくれるメソッドがあれば便利かなと考えたんだよ。それならスレッドの実装のことを忘れて、対象の処理のことだけ考えればいいからね。

で、Enumerable#thread_withというメソッドを書いてみたよ1

module Enumerable
  def thread_with
    mem = []
    map do |*item|
      Thread.new(*item) do |*_item|
        mem << yield(*_item)
      end
    end.each(&:join)
    mem
  end
end

Enumerable#thread_withがあればsleep sortは簡単だよ。

a = (1..10).sort_by { rand } # => [9, 3, 10, 8, 4, 5, 7, 2, 6, 1]
a.thread_with { |i| sleep i } # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

効率を良くしたければ、次のようにすればいいし。

a = (1..10).sort_by { rand } # => [9, 3, 10, 8, 4, 5, 7, 2, 6, 1]
a.thread_with { |i| sleep Math.log(i); i } # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

もう少し真面目な例を挙げるね。

複数のWebサイトに並列的にアクセスして、そこからimgタグを拾ってくる例を示すよ。ここではベンチマークを取って、スレッドを使わない例と比べているよ。

require "benchmark"
require "open-uri"
a = %w(www.nintendo.co.jp www.google.com www.yahoo.co.jp www.nikkei.com www.ruby-lang.org)
blk = ->item { open("http://#{item}").read.scan(/<img .*?>/) }
Benchmark.bmbm do |x|
  x.report { a.map(&blk)  }
  x.report { a.thread_with(&blk) }
end
# >> Rehearsal ------------------------------------
# >>    0.110000   0.040000   0.150000 (  1.112704)
# >>    0.020000   0.020000   0.040000 (  0.243304)
# >> --------------------------- total: 0.190000sec
# >> 
# >>        user     system      total        real
# >>    0.040000   0.010000   0.050000 (  0.756259)
# >>    0.020000   0.010000   0.030000 (  0.242218)

なんかThreadが身近になった感じがしない?

ただ先の実装には1つ問題があるよ。それはもとの配列の順位がthread_withの返り値として保証されないことだよ2

a = (1..1000).map { |i| i**2 }
b = (1..1000).thread_with { |i| i**2 }
a == b # => false

でも以下のようにすれば一応もとの順位は保証できるんだ。

module Enumerable
  def thread_with(order=false)
    mem = []
    map.with_index do |*item, i|
      Thread.new(*item) do |*_item|
        mem << [i, yield(*_item)]
      end
    end.each(&:join)
    (order ? mem.sort : mem).map(&:last)
  end
end

a = (1..1000).map { |i| i**2 }
b = (1..1000).thread_with(true) { |i| i**2 }
a == b # => true

つまりthread_withが引数を取るようにしてtrueを渡せば、最後にもとの配列の順位にソートしてくれる。

まあ、たいしたネタじゃなかったね..

  1. まあThreadの使い方そのまんまなんだけど..
  2. まあそれがスレッドなんだけど


blog comments powered by Disqus
ruby_pack8

100円〜で好評発売中!
M'ELBORNE BOOKS