การชักตัวอย่างเรซัฟวาร์
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