การชักตัวอย่างเรซัฟวาร์

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

Reservoir with Random Sort

อัลกอริธึมเรซัฟวาร์แบบง่ายๆสามารถออกแบบโดยใช้การจัดเรียงแบบสุ่ม และดำเนินการโดยใช้โครงสร้างข้อมูลคิวลำดับความสำคัญ อัลกอริทึมนี้กำหนดจำนวนสุ่มเป็นคีย์แต่ละรายการและเก็บรักษา 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/