การชักตัวอย่างอ่างเก็บน้ำ

การชักตัวอย่างอ่างเก็บน้ำ (reservoir sampling) เป็นกลุ่มของอัลกอริทึมแบบสุ่ม สำหรับการสุ่มเลือกตัวอย่าง k จากรายการ S ที่มี n รายการ โดยที่ n เป็นจำนวนที่มากหรือไม่ทราบค่า โดยปกติ n มีขนาดใหญ่พอที่ไม่พอดีกับหน่วยความจำหลัก ตัวอย่างเช่นรายการข้อความค้นหาใน Google และ Facebook

ดังนั้นเราจึงรับอาร์เรย์ขนาดใหญ่ของตัวเลข (เพื่อให้ง่ายขึ้น) และเราจำเป็นต้องเขียนฟังก์ชันที่มีประสิทธิภาพเพื่อสุ่มเลือกหมายเลข k ที่ 1 <= k <= n ให้อาร์เรย์อินพุตเป็น stream[]

วิธีง่ายๆคือการสร้างอาร์เรย์ reservoir[] ขนาดสูงสุด k สุ่มเลือกรายการจาก stream[0..n-1] ทีละรายการ หากรายการที่เลือกไม่ได้เลือกไว้ก่อนหน้านี้ แล้วใส่ไว้ใน reservoir[] หากต้องการตรวจสอบว่ามีการเลือกรายการก่อนหน้าหรือไม่ เราจำเป็นต้องค้นหารายการใน reservoir[]

ความซับซ้อนของเวลาของขั้นตอนนี้จะเป็น O(k)² อาจมีค่ามากถ้า k มีขนาดใหญ่ นอกจากนี้ยังไม่ได้ผลถ้าอินพุทอยู่ในรูปแบบของสตรีม

สามารถแก้ไขได้ในเวลา O(n) โซลูชันนี้เหมาะกับการป้อนข้อมูลในรูปแบบของสตรีม

  ตัวอย่าง : Sample size 10 
สมมติว่าเราเห็นลำดับรายการหนึ่งทีละรายการ เราต้องการที่จะเก็บสิบรายการในหน่วยความจำ และเราต้องการให้พวกเขาได้รับเลือกโดยสุ่มจากลำดับ ถ้าเราทราบจำนวนรวมของรายการ (n) จากนั้นการแก้ปัญหาจะเป็นเรื่องง่าย: เลือกดัชนีที่แตกต่างกันสิบรายการระหว่าง 1 ถึง n กับความน่าจะเป็นเท่ากันและเก็บ i-th ไว้ ปัญหาคือเราไม่ทราบ n ล่วงหน้าเสมอ ทางออกที่เป็นไปได้คือ

เก็บสิบรายการแรกไว้ในหน่วยความจำ

เมื่อรายการที่ i-th มาถึง (for i > 10):

 ความน่าจะเป็น 10/i เก็บรายการใหม่ไว้ (ทิ้งแบบเก่าหรือเลือกว่าจะแทนที่แบบสุ่มแต่ละครั้งมีโอกาส 1/10)
 ความน่าจะเป็น 1-10/i เก็บรายการเก่า (ละเว้นรายการใหม่)

ดังนั้น:

 เมื่อมี 10 รายการหรือน้อยกว่าแต่ละรายการจะถูกเก็บไว้ด้วยความเป็นไปได้ 1
 เมื่อมี 11 รายการแต่ละรายการจะถูกเก็บไว้ด้วยความน่าจะเป็น 10/11 สำหรับรายการเก่านั่นคือ (1)(1/11 + (10/11)(9/10)) = 1/11 + 9/11 = 10/11
 เมื่อมี 12 รายการรายการที่สิบสองจะถูกเก็บไว้กับความน่าจะเป็น 10/12 และแต่ละ 11 รายการก่อนหน้านี้จะถูกเก็บไว้ด้วยความน่าจะเป็น (10/11)(2/12 + (10/12)(9/10)) = (10/11)(11/12) = 10/12
 เมื่อพิสูจน์ได้ว่ามี n รายการแต่ละรายการจะถูกเก็บไว้ด้วยความน่าจะเป็น 10 / n

 การจัดเรียงแบบสุ่ม 
อัลกอริธึมของการชักตัวอย่างอ่างเก็บน้ำแบบง่าย ๆ สามารถออกแบบโดยใช้การจัดเรียงแบบสุ่ม และดำเนินการโดยใช้โครงสร้างข้อมูลคิวลำดับความสำคัญ อัลกอริทึมนี้กำหนดจำนวนสุ่มเป็นคีย์แต่ละรายการและเก็บรักษา k รายการที่มีค่าต่ำสุดสำหรับคีย์ ในสาระสำคัญนี้เทียบเท่ากับการกำหนดหมายเลขสุ่มให้แต่ละรายการเป็นคีย์ การเรียงลำดับรายการโดยใช้คีย์เหล่านี้และรับรายการ k ด้านบน เวลาทำงานที่แย่ที่สุดของอัลกอริทึมคือ O(n log k) ขณะที่เวลาที่ดีที่สุดคือ O(n) (*
  S is a stream of items to sample, R will contain the result
  S.Current returns current item in stream
  S.Next advances stream to next position
  max-priority-queue supports:
    Count -> number of items in priority queue
    Maximum -> returns maximum key value of all items
    Extract-Max() -> Remove the item with max key
    Insert(key, Item) -> Adds item with specified key
 *)
ReservoirSample(S[1..?], R[1..k])
  H = new max-priority-queue
  while S has data
    r = Random(0,1)
    if H.Count < k
      H.Insert(r, S.Current)
    else
      if H.Maximum > r
        H.Extract-Max()
        H.Insert(r, S.Current)
    S.Next

 อ้างอิง 
https://www.geeksforgeeks.org/reservoir-sampling/
หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:ขั้นตอนวิธีแบบสุ่ม