重み付きランダム選択アルゴリズムを考えてみる

200回ぐらい回せば大体、Weightに従って分布してくる…と思う。

def wrr(addr_weights, n)
  addrs = []
  ary = []

  addr_weights.each do |a, w|
    w.times {
      ary << a
    }
  end

  ary = ary.sort_by{ rand }

  loop do
    addrs << ary.shift
    addrs.uniq!

    if addrs.size >= n or ary.empty?
      break
    end
  end

  return addrs
end

h = {}
ipaddrs = [
  ['10.0.0.1', 100],
  ['10.0.0.2', 150],
  ['10.0.0.3',  50],
  ['10.0.0.4', 100],
  ['10.0.0.5', 200]
]

200.times {
  wrr(ipaddrs, 2).each do |i|
    h[i] ||= 0
    h[i] += 1
  end
}

sum = h.values.inject(0) {|r, i| r + i }

h.sort_by {|a, b| a }.each {|i, n|
  puts '%s=%3d (%.2f)' % [i, n, n.to_f / sum * 100]
}

~$ ruby test.rb

10.0.0.1= 66 (16.50)

10.0.0.2=104 (26.00)

10.0.0.3= 42 (10.50)

10.0.0.4= 70 (17.50)

10.0.0.5=118 (29.50)

~$ ruby test.rb

10.0.0.1= 70 (17.50)

10.0.0.2=100 (25.00)

10.0.0.3= 39 (9.75)

10.0.0.4= 72 (18.00)

10.0.0.5=119 (29.75)

~$ ruby test.rb

10.0.0.1= 76 (19.00)

10.0.0.2= 93 (23.25)

10.0.0.3= 35 (8.75)

10.0.0.4= 64 (16.00)

10.0.0.5=132 (33.00)

~$