วิธีสร้างตัวเลขสุ่มแบบถ่วงน้ำหนัก

ตัวเลขสุ่มมักจะเป็นไปตามสิ่งที่เราเรียกว่า 'การกระจายแบบสม่ำเสมอ' ซึ่งหมายความว่ามีโอกาสเท่ากันที่จะมีการเลือกหมายเลขใดๆ

แต่ถ้าคุณต้องการให้เลือกหมายเลขบางหมายเลขบ่อยกว่าหมายเลขอื่น คุณจะต้องใช้กลยุทธ์ที่แตกต่าง:ตัวสร้างตัวเลขสุ่มแบบถ่วงน้ำหนัก .

การใช้งานที่ใช้งานได้จริง ได้แก่:

• โต๊ะยกเค้าในวิดีโอเกมที่ศัตรูสามารถดรอปไอเท็มต่างๆ โดยมีอัตราการดรอปที่แตกต่างกัน
• ราฟเฟิลที่ผู้ที่มีตั๋วมากกว่ามีโอกาสถูกรางวัลมากกว่า

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

หากคุณนึกถึงตัวอย่างการจับฉลาก คุณจะพบวิธีแก้ปัญหาที่ชัดเจน:สร้างอาร์เรย์ที่มีหนึ่งสำเนาของรายการสำหรับ "ตั๋ว" แต่ละรายการ

ตัวอย่างเช่น หาก John ซื้อสลาก 4 ใบและ David ซื้อเพียง 1 ใบ John จะมีโอกาสชนะมากกว่า David ถึง 4 เท่า

นี่คือการใช้งานจริง :

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

ฉันกำลังเพิ่มชื่อของบุคคลนั้นหนึ่งครั้งสำหรับตั๋วทุกใบที่พวกเขาซื้อ จากนั้นฉันจะสุ่มชื่อจากรายการนั้น โดยอาศัยการอยู่ในรายชื่อมากขึ้นเรื่อยๆ จะเพิ่มโอกาสในการเลือกชื่อนั้น

ฉันชอบแนวทางนี้เพราะมันง่ายมาก และเมื่อคุณมีรายชื่อแล้ว ก็จะสามารถเลือกผู้ชนะได้รวดเร็วมาก

ผลรวมของน้ำหนัก

มีอีกวิธีหนึ่งที่คุณสามารถทำได้ซึ่งมีประสิทธิภาพหน่วยความจำมากกว่า ข้อเสียคือการเลือกค่าแบบสุ่มจะช้ากว่า

แนวคิดคือการเลือกตัวเลขสุ่มระหว่าง 1 และผลรวมของน้ำหนักทั้งหมด จากนั้นวนซ้ำจนกว่าคุณจะพบน้ำหนักที่ต่ำกว่าหรือเท่ากับตัวเลขนี้

นี่คือรหัส :

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

รหัสนี้ใช้ในแฮชโดยที่คีย์คือรายการและค่าคือน้ำหนัก คุณสามารถเรียกวิธีนี้ดังนี้:

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

คุณสามารถทดสอบว่าการทำงานนี้เป็นไปตามที่คาดไว้หรือไม่โดยดูจากการกระจายผลลัพธ์หลังจากเรียกใช้หลายครั้ง

นี่คือตัวอย่าง :

counts = Hash.new(0)

def pick_number
  random_weighted(cats: 2, dogs: 1)
end

1000.times { counts[pick_number] += 1 }
p counts

เรียกใช้สองสามครั้งแล้วดูที่ผลลัพธ์เพื่อดูว่าอัตราส่วนนั้นควรเป็นหรือไม่

บทสรุป

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