เชี่ยวชาญการสร้างเลขสุ่มแบบมีน้ำหนัก: เทคนิคและการประยุกต์ใช้

เลขสุ่มปกติมักจะเป็น uniform distribution หมายถึงโอกาสที่เลขแต่ละตัวจะถูกเลือกเท่ากัน แต่ถ้าต้องการให้บางเลขถูกเลือกบ่อยกว่าอื่นๆ ต้องใช้กลยุทธ์อื่น: weighted random number generator

การประยุกต์ใช้จริง:

• Loot table ในเกม: ศัตรูวางไอเทมต่างๆ ด้วย drop rates ที่แตกต่างกัน
• การจับฉลาก: คนที่ซื้อตั๋วมากกว่า มีโอกาสชนะมากกว่า

กลยุทธ์ง่ายๆ

คิดจากตัวอย่างการจับฉลาก: สร้าง array ที่มี item หนึ่ง copy ต่อหนึ่ง 'ticket'

เช่น John ซื้อ 4 ตั๋ว David ซื้อ 1 ตั๋ว John จะมีโอกาสชนะมากกว่า David 4 เท่า

Implementation ที่ทำงานได้:

users = { john: 4, david: 1 }
raffle = []
users.map do |name, tickets|
  tickets.times { raffle << name }
end
p raffle # [:john, :john, :john, :john, :david]
p raffle.sample # :john

เพิ่มชื่อคนละครั้งต่อตั๋วที่ซื้อ แล้วสุ่มชื่อจาก list ด้วยการอยู่ใน list หลายครั้ง โอกาสถูกเลือกจึงเพิ่มขึ้น วิธีนี้ง่าย และเร็วมากตอนสุ่มหลังจากมี list แล้ว

Sum of Weights

อีกวิธีที่ประหยัด memory กว่า แต่วิธีแลกมาคือการสุ่มช้ากว่า แนวคิดคือสุ่มเลขระหว่าง 1 ถึงผลรวมของ weights ทั้งหมด แล้ววนลูปหา weight ที่น้อยกว่าหรือเท่ากับเลขนั้น

โค้ด:

def random_weighted(weighted)
  max = sum_of_weights(weighted)
  target = rand(1..max)
  weighted.each do |item, weight|
    return item if target <= weight
    target -= weight
  end
end

def sum_of_weights(weighted)
  weighted.inject(0) { |sum, (item, weight)| sum + weight }
end

รับ hash ที่ keys คือ items และ values คือ weights เรียกได้แบบนี้:

random_weighted(cats: 5, dogs: 1) # :cats

ทดสอบว่าทำงานถูกต้องโดยดู distribution หลังรันหลายครั้ง:

counts = Hash.new(0)
def pick_number
  random_weighted(cats: 2, dogs: 1)
end
1000.times { counts[pick_number] += 1 }
p counts

รันหลายครั้งดู output ว่า ratio ตรงตามที่คาดไว้ไหม

สรุป

แม้จะมี algorithms ที่ซับซ้อนกว่า แต่สองวิธีนี้ควรเพียงพอแล้ว หวังว่าบทความนี้จะมีประโยชน์ โปรดแชร์ให้เพื่อนๆ เพื่อให้ผมเขียนต่อได้! 🙂