- Reservoir Sampling คือเทคนิคการสุ่มตัวอย่างที่ให้ทุกรายการมีโอกาสถูกเลือกเท่ากัน แม้เป็นสตรีมข้อมูลที่ไม่รู้ขนาดทั้งหมด โดยเก็บไว้ในหน่วยความจำเพียงจำนวนที่กำหนด
- สำหรับอาร์เรย์ที่รู้ขนาด การสับลำดับหรือการ เลือกดัชนีแบบสุ่ม ก็เพียงพอ แต่สำหรับสตรีมที่ไม่สามารถย้อนกลับไปยังรายการที่ผ่านไปแล้วได้ จำเป็นต้องใช้แนวทางอื่น
- ในการเลือกรายการเดียว จะรับรายการลำดับที่ n ด้วย ความน่าจะเป็น 1/n เพื่อถ่วงดุลระหว่างโอกาสที่รายการใหม่จะถูกเลือกกับโอกาสที่รายการเดิมจะอยู่รอด
- เมื่อต้องการเลือกหลายรายการ จะรับรายการใหม่ด้วย ความน่าจะเป็น k/n ตามจำนวนที่เก็บไว้ k และหากจำเป็นก็สุ่มแทนที่รายการหนึ่งจากรายการที่เก็บอยู่ในปัจจุบัน
- เมื่อนำไปใช้กับการเก็บ log จะช่วยไม่ให้เกิน ขีดจำกัดการประมวลผล เช่น สูงสุด 5 รายการต่อวินาที พร้อมลดทั้งการสูญเสีย log ในช่วงเงียบและการใช้หน่วยความจำ
การสุ่มตัวอย่างจากชุดที่รู้ขนาด
- หากสุ่มเลือกไพ่ 3 ใบจากไพ่ 10 ใบ แค่สับไพ่ทั้งหมดแล้วเลือก 3 ใบแรกก็ทำให้ไพ่แต่ละใบมีความน่าจะเป็นที่จะถูกเลือกเท่ากันได้
- เมื่อจำนวนไพ่เพิ่มเป็น 1 ล้านใบ การสับจริงอาจทำได้ยาก แต่ในโครงสร้างที่เข้าถึงด้วยดัชนีได้เหมือนอาร์เรย์ การเลือก ดัชนีแบบสุ่ม 3 ตำแหน่งก็ทำให้ได้เป้าหมายเดียวกัน
- อาร์เรย์ในหน่วยความจำเข้าถึงดัชนีเฉพาะได้ง่าย แต่การนับไปถึงไพ่ใบที่ 436,234 ในกองไพ่จริงนั้นใช้เวลานานในทางปฏิบัติ
ข้อจำกัดที่เกิดขึ้นในสตรีมที่ไม่รู้ขนาด
- หากดูไพ่ได้ครั้งละ 1 ใบ ถือไว้ได้พร้อมกันเพียง 1 ใบ และย้อนกลับไปยังไพ่ที่ผ่านไปแล้วไม่ได้ ก็ต้องเลือกไพ่สุดท้าย 1 ใบโดยไม่รู้จำนวนทั้งหมด
- บริการเก็บ log ก็เจอปัญหาในลักษณะคล้ายกัน
- รับข้อความ log จากบริการอื่นและจัดเก็บไว้ในที่เดียว
- หาก log หลั่งไหลเข้ามาเพราะ release ที่มีปัญหาหรือทราฟฟิกพุ่งสูง บริการเก็บ log อาจรับมือไม่ไหว
- บริการเก็บ log ในตัวอย่างมีค่า threshold ที่ประมวลผลได้ 5 log ต่อวินาที
- วิธีส่งเพียง 10% ของ log ช่วยไม่ให้เกิน threshold ในช่วงที่พุ่งสูง แต่ในช่วงเงียบก็ทิ้ง 90% ของ log โดยไม่จำเป็น
- พฤติกรรมที่ต้องการคือ ในช่วงเงียบให้ส่ง log ทั้งหมด และในช่วงที่พุ่งสูงให้ส่งได้สูงสุดเพียง 5 รายการต่อวินาที
- หากส่งเฉพาะ log 5 รายการแรกที่เห็นในแต่ละวินาที log ที่มาทีหลังจะไม่มีโอกาสถูกเลือก จึงไม่เป็นธรรม
Reservoir Sampling สำหรับรายการเดียว
- Reservoir Sampling รักษา ตัวอย่างที่เป็นธรรม จากรายการทั้งหมดที่เห็นมาแล้วได้ แม้ไม่รู้จำนวนทั้งหมด
- อาจเก็บทุกข้อความไว้ในหน่วยความจำแล้วค่อยเลือกภายหลังก็ได้ แต่หากไม่รู้ขนาดของ spike ก็ยากที่จะคาดการณ์ปริมาณหน่วยความจำที่ต้องใช้
- วิธีนี้แก้ปัญหาเดียวกันโดยไม่ใช้หน่วยความจำเกินจำนวนตัวอย่างที่ต้องการ
- กฎสำหรับเลือกไพ่ใบเดียวทำได้ง่าย
- ไพ่ใบแรกจะถูกเก็บไว้เสมอ
- ไพ่ใบใหม่ลำดับที่ n จะถูกเก็บด้วย ความน่าจะเป็น 1/n
- หากตัดสินใจเก็บไพ่ใบใหม่ ไพ่ที่เก็บอยู่เดิมจะถูกทิ้ง
- หากแทนที่ด้วยความน่าจะเป็น 50% ในทุกใบ ไพ่ท้าย ๆ จะได้เปรียบ จึงไม่เป็นธรรม
- ไพ่ใบแรกต้องรอดจากโอกาสถูกแทนที่หลายครั้งจึงจะยังอยู่หลังจากไพ่ใบที่ 10
- ไพ่ใบสุดท้ายแค่ถูกเลือกครั้งเดียวก็อาจเหลืออยู่ในมือได้
- กฎ 1/n ปรับให้สมดุลทั้งความน่าจะเป็นที่ไพ่ใบใหม่จะถูกเลือกและความน่าจะเป็นที่ไพ่เดิมจะอยู่รอด
- ไพ่ใบแรกถูกเก็บด้วยความน่าจะเป็น 1/1 หรือ 100%
- เมื่อถึงไพ่ใบที่สอง ไพ่ใบใหม่ถูกเลือกด้วยความน่าจะเป็น 1/2 และไพ่ใบแรกก็เหลืออยู่ด้วยความน่าจะเป็น 1/2
- เมื่อถึงไพ่ใบที่สาม ไพ่ใบใหม่ถูกเลือกด้วยความน่าจะเป็น 1/3 และไพ่ที่เก็บอยู่เดิมก็มีความน่าจะเป็น 50% × 2/3 จึงเท่ากับ 1/3
- โดยทั่วไป ในขั้นที่ n ความน่าจะเป็นที่ไพ่เดิมจะเหลืออยู่คือ
1/(n-1) * (1-(1/n))และเท่ากับความน่าจะเป็นที่ไพ่ใบใหม่จะถูกเลือกคือ1/n
การขยายไปสู่การเลือกหลายรายการ
- การเลือกรายการเดียวสามารถขยายเป็นการเลือกหลายรายการได้
- หากต้องการเลือกรายการ k รายการ จะมีกฎที่เปลี่ยนไปสองข้อ
- รายการใหม่จะถูกเลือกด้วย ความน่าจะเป็น k/n ไม่ใช่
1/n - หากจำเป็นต้องแทนที่ ให้สุ่มเลือกรายการหนึ่งจาก k รายการที่เก็บอยู่ในปัจจุบัน แล้วเปลี่ยนเป็นรายการใหม่
- รายการใหม่จะถูกเลือกด้วย ความน่าจะเป็น k/n ไม่ใช่
- ความน่าจะเป็นที่รายการเดิมถูกเลือกอยู่เขียนได้เป็น
k/(n-1)และเมื่อนำมาคูณกับความน่าจะเป็นที่จะไม่ถูกแทนที่ด้วยรายการใหม่ ก็ยังคงความเป็นธรรมไว้ได้ - เนื่องจากรายการที่เก็บอยู่ทั้งหมดมีความน่าจะเป็นเท่ากันที่จะถูกแทนที่ โอกาสที่แต่ละรายการจะยังคงอยู่ในแต่ละขั้นจึงเท่ากันด้วย
- การใช้งานจริงสรุปได้เป็นการใช้อาร์เรย์ขนาด k
- สร้างเลขสุ่มตั้งแต่ 0 ถึง n สำหรับรายการใหม่แต่ละรายการ
- หากเลขสุ่มน้อยกว่า k ให้แทนที่รายการในดัชนีนั้นด้วยรายการใหม่
- มิฉะนั้นให้ทิ้งรายการใหม่
การนำไปใช้กับบริการเก็บ log
- ในตัวอย่างบริการเก็บ log ตั้งค่า
k=5เพื่อเก็บข้อความ log ได้สูงสุดครั้งละ 5 รายการ - ทุกวินาทีจะส่ง log ที่ถูกเลือกไปยังบริการเก็บ log จากนั้นล้างอาร์เรย์ขนาด 5 แล้วเริ่มใหม่
- วิธีนี้สร้าง รูปแบบเป็นก้อน ที่ส่ง log เป็นชุดตามช่วงเวลา แทนที่จะเป็นสตรีม log แบบเรียลไทม์
- แต่จำนวน log ที่ส่งจะไม่เกิน threshold และในช่วงเงียบ จำนวน log ทั้งหมดกับจำนวน log ที่ส่งจะเคลื่อนไหวใกล้เคียงกัน
- ในช่วงเงียบจะไม่เสีย log ส่วนในช่วงที่พุ่งสูงจะไม่ส่ง log มากกว่า threshold ต่อวินาที และพื้นที่จัดเก็บก็ไม่เกิน log จำนวน
k=5รายการ
กรณีที่ต้องใช้ค่าน้ำหนัก
- log บางรายการอาจมีคุณค่ามากกว่า log รายการอื่น
- ตัวอย่างเช่น อาจต้องการเก็บ error log ทั้งหมด
- ในกรณีเช่นนี้ สามารถใช้รูปแบบดัดแปลงของ Reservoir Sampling แบบถ่วงน้ำหนัก ได้
- Reservoir Sampling คืออัลกอริทึมที่ช่วยแก้ปัญหาการสุ่มตัวอย่างจากสตรีม ซึ่งดูเหมือนเป็นไปไม่ได้ในตอนแรก ให้ทำได้ด้วยหน่วยความจำน้อย
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
ตอนเด็กผมอยู่ต่างจังหวัด และได้ยินมาว่าเพื่อนของพ่อคนหนึ่ง ด้วยหน้าที่การงานแล้วต้องขึ้นไปนับ จำนวนประชากรนกทาร์มิแกนหิน บนภูเขาทุกปี
เขาจะเดินไปตามเส้นทางที่กำหนดไว้ แล้วทำให้นกตกใจบินขึ้นเป็นช่วง ๆ ตามระยะที่กำหนด จากนั้นนับจำนวนและส่งยอดรวมให้หน่วยงานรัฐ เพื่อนำไปใช้ประเมินจำนวนประชากรทั้งหมด
ปีหนึ่งเขาต้องเดินทางไปต่างประเทศในช่วงสำรวจ จึงอธิบายวิธีทำอย่างละเอียดให้เพื่อนอีกคนและขอให้ทำแทน แต่เพื่อนคนนั้นลืมในวันจริง แถมรู้สึกว่ายุ่งยาก เลยส่งตัวเลขที่ดูพอสมเหตุสมผลไปแบบคร่าว ๆ
ปีถัดมา หนังสือพิมพ์ท้องถิ่นพาดหัวหน้าแรกว่า จำนวนประชากรนกทาร์มิแกนหินเพิ่มขึ้นเป็นประวัติการณ์ เพราะเพื่อนคนนั้นไม่ได้คิดว่าค่าประมาณดังกล่าวถูกใช้กำหนดโควตาอนุญาตล่าสัตว์ด้วย
https://en.wikipedia.org/wiki/Rock_ptarmigan
เมื่อก่อนผมเคยทำระบบจองให้สกีรีสอร์ตขนาดค่อนข้างใหญ่หลายแห่ง ระหว่างทำงานโต้รุ่งเพราะงานล่าช้า หนึ่งในสิ่งสุดท้ายที่ต้องปิดให้เสร็จคือรายงานสถิติทางการที่รัฐบาลประกาศ เช่น จำนวนผู้เข้าพัก
เอาเป็นว่าสถิติของปีนั้นแทบไม่เกี่ยวข้องกับความเป็นจริงเลย
ผมเป็นผู้เขียนบทความนี้เอง ถ้ามีคำถามก็ตอบได้ และยินดีรับฟีดแบ็ก
โค้ดของบทความทั้งหมดอยู่ที่ https://github.com/samwho/visualisations และใช้ MIT license จึงนำไปใช้ได้อย่างอิสระ
ถ้าขยาย reservoir sampling ให้น่าสนใจยิ่งขึ้น แทนที่จะสุ่มตัวเลขสำหรับแต่ละรายการเพื่อตัดสินว่าจะเปลี่ยนหรือไม่และจะเปลี่ยนตัวไหน สามารถสุ่มค่าจาก การแจกแจงเรขาคณิต เพื่อกำหนดจำนวนรายการที่ข้ามได้อย่างปลอดภัยก่อนการเปลี่ยนครั้งถัดไป
วิธีนี้มีประโยชน์เป็นพิเศษเมื่อสามารถข้ามรายการจำนวนมากได้ด้วยต้นทุนต่ำ เช่น กรณีที่เทปไดรฟ์สามารถกรอไปข้างหน้าได้เร็วแต่ไม่รู้ความยาวทั้งหมด หรือกรณีที่สามารถให้ระบบส่วนใหญ่เข้าสู่โหมดประหยัดพลังงานระหว่างที่ข้ามรายการ
เมื่อเลือก k รายการจาก n รายการ วิธีนี้จะทำการสุ่มตัวอย่างและข้ามประมาณ O(k * log (n/k)) ครั้ง
ในเชิงแนวคิด ผมชอบเวอร์ชันของ reservoir sampling ที่กำหนด priority แบบสุ่มคงที่ให้การ์ดแต่ละใบเมื่อมาถึง แล้วเก็บไว้เฉพาะ k ใบที่มี priority สูงสุดมากกว่า
ปัญหาที่ต่อเนื่องจากตรงนี้คือการเลือก k อันดับสูงสุดจากสตรีมที่ไม่รู้ความยาว ด้วยเวลา O(n) และพื้นที่ O(k) วิธีง่าย ๆ คือรักษา min heap ไว้ ซึ่งได้พื้นที่ O(k) แต่ใช้เวลา O(n log k)
แทนที่จะทำเช่นนั้น ให้มีบัฟเฟอร์แบบไม่เรียงลำดับที่จุได้สูงสุด 2k แล้วเพิ่มรายการเข้าไป พอเต็มก็ใช้ quickselect แบบสุ่มหรือ median-of-medians เพื่อเหลือไว้เฉพาะ k รายการอันดับสูงสุดในเวลา O(k) สำหรับ n รายการทั้งหมด จะทำงาน O(2k) ทุก ๆ k รายการ จึงได้เวลาในการรัน O(n)
หัวข้อที่เกี่ยวข้องอีกอย่างคือ rendezvous hashing: https://en.wikipedia.org/wiki/Rendezvous_hashing
นอกเรื่องเล็กน้อย ยังมีบทความดี ๆ เกี่ยวกับ alias method สำหรับการสุ่มตัวอย่างจากการแจกแจงความน่าจะเป็นแบบไม่ต่อเนื่อง: https://www.keithschwarz.com/darts-dice-coins/
แต่ตอนแรกพูดถึงการสุ่มเลือกการ์ด 3 ใบจากสำรับ 10 ใบหรือ 436,234 ใบ แล้วจู่ ๆ ก็เปลี่ยนไปเป็นเรื่องการเลือกการ์ดแค่ 1 ใบ เลยทำให้สับสนอยู่ครู่หนึ่ง
ถ้ามี หัวข้อย่อย ประมาณว่า “จากนี้จะเปลี่ยนไปใช้สมมติฐานที่ง่ายขึ้น คือถือการ์ดไว้เพียง 1 ใบ ไม่ใช่ 3 ใบ และไม่รู้ขนาดสำรับ” อยู่ก่อน “Now let me throw you a curveball...” น่าจะชัดเจนขึ้น
แต่ผมไม่แน่ใจว่าตัวเองเข้าใจ ความถูกต้องทางสถิติ ของแนวทางนี้ดีหรือไม่ ผมเข้าใจว่าทุก log ในช่วงเวลาหนึ่งมีโอกาสถูกใส่เข้ามาเท่ากัน แต่ถ้าอย่างนั้น log ที่เกิดขึ้นใน “ช่วงเวลาที่ช้า” จะถูกแสดงมากเกินไปในตัวชี้วัดรวมไม่ใช่หรือ?
ตัวอย่างเช่น ถ้าต้องการรู้ว่า endpoint ใดใช้เวลามากที่สุด เพื่อจะลดต้นทุนรวมของทั้ง fleet (เช่น CPU-วินาที) endpoint ที่มีทราฟฟิกเป็นช่วง ๆ อาจถูกแสดงน้อยกว่า endpoint ที่มีทราฟฟิกสม่ำเสมอ ทำให้วิธีนี้ดูไม่เหมาะสม
แบบนั้นเราอาจเสียเวลาไปปรับแต่ง endpoint ที่จริง ๆ แล้วมีทราฟฟิกไม่มาก
ในการวางแผน capacity แยกตามบริการ ผมก็สงสัยเหมือนกันว่าถูกต้องหรือไม่ที่บริการที่มีทราฟฟิกเป็นช่วง ๆ จะถูกแสดงน้อยกว่า
ผมอยากรู้ว่า reservoir sampling เหมาะกับ use case แบบไหน และสามารถทำการวิเคราะห์สถิติแบบใดได้จากข้อมูลที่ส่งกลับมา
บทความและคำอธิบายยอดเยี่ยม
จากมุมมองเชิงปฏิบัติ ผมยังคิดว่าวิธีนี้น่าจะเป็นตัวเลือกสุดท้ายสำหรับ การเก็บรวบรวมล็อก อยู่ดี เข้าใจว่าถ้าเกิดปริมาณพุ่งสูงก็ต้องทิ้งอะไรบางอย่าง แต่ประเด็นสำคัญคือควรทิ้งอะไร
การตัดสินใจว่าอะไรจะถูกทิ้งอย่าง “เป็นธรรม” ดูไม่ได้มีความหมายมากนัก
น่าจะดีกว่าถ้าทิ้งล็อกที่มีลำดับความสำคัญต่ำก่อน และถ้ามีระดับล็อกอย่าง debug/info/warning/error ก็ให้ความสำคัญกับเหตุการณ์ที่มีความรุนแรงสูง และทิ้งล็อก debug ที่ยืดยาวก่อน
อีกวิธีคือจัดกลุ่มลำดับล็อกให้เป็นส่วนหนึ่งของกิจกรรมเดียวกัน โดยสำหรับกิจกรรมที่สำเร็จให้บันทึกแค่จุดเริ่มต้นและจุดสิ้นสุด หรือการเปลี่ยนสถานะสำคัญ แล้วตัดล็อกระหว่างทางที่ซ้ำ ๆ ออก
เมื่อเกิดปริมาณพุ่งสูง แทนที่จะเก็บทุกบรรทัดของล็อก การ รวมยอด·สรุป ข้อความที่คล้ายกันหรือซ้ำกันจะช่วยลดปริมาณและทำให้เห็นแนวโน้มได้ชัดขึ้นด้วย
และยังต้องการจำกัดจำนวนบรรทัดล็อกทั้งหมดที่เก็บเข้ามาด้วยงบประมาณที่ใหญ่กว่า Reservoir sampling สามารถจัดการสิ่งเหล่านี้ได้ทั้งหมด
Reservoir sampling ที่เป็นธรรมก็สามารถทำให้ไม่เป็นธรรมอย่างควบคุมได้ เช่น เพิ่มความน่าจะเป็นในการเก็บรายการที่มีเนื้อหาน่าสนใจเป็นพิเศษ
ในฐานะทางเลือกสุดท้าย เทคนิคนี้แข่งขันกับการเลือกแบบสุ่มที่มีอคติและไม่ค่อยยึดหลักการ หรือแม้แต่อัลกอริทึมการเลือกที่ไม่สุ่มเลย
เป็นบทความที่เขียนดีและทำภาพอธิบายได้ดีมาก
ส่วนขยายขั้นสูงคือมีอัลกอริทึมที่คำนวณ จำนวนเรคอร์ดที่จะข้าม แทนที่จะทำการทดลองกับทุกเรคอร์ด บทความที่ดีเกี่ยวกับเรื่องนี้อยู่ที่นี่: https://richardstartin.github.io/posts/reservoir-sampling
รูปแบบหนึ่งของ weighted reservoir sampling ถูกใช้ใน ReSTIR (Spatiotemporal Reservoir Resampling สำหรับ ray tracing แบบเรียลไทม์) ซึ่งเป็น ตัวประมาณการส่งผ่านแสง แบบสุ่มที่มีการลดสัญญาณรบกวนเชิงปริภูมิ-เวลาในตัว
ตัวประมาณการส่งผ่านแสงพยายามคำนวณปริมาณแสงที่ผ่านฉาก (https://en.wikipedia.org/wiki/Radiance) เพื่อทำเช่นนั้น จำเป็นต้องอินทิเกรต radiance ของทุกเส้นทางที่แสงสามารถเดินทางได้ โดยยังคงรักษาการอนุรักษ์พลังงานไว้ (https://en.wikipedia.org/wiki/Rendering_equation)
ยกเว้นกรณีที่เรียบง่ายมาก อินทิกรัลนี้ของสมการเรนเดอร์ไม่มีคำตอบรูปแบบปิดที่จัดการได้ง่าย จึงต้องแก้ด้วยวิธีเชิงความน่าจะเป็น
แนวคิดพื้นฐานคือ วิธีมอนติคาร์โล (https://en.wikipedia.org/wiki/Monte_Carlo_method) โดยสุ่มสุ่มตัวอย่างเส้นทางที่เป็นไปได้จำนวนมากแล้วนำมาเฉลี่ย
ในช่วงหลายทศวรรษต่อมา กลยุทธ์ที่ซับซ้อนยิ่งขึ้นได้พัฒนาขึ้น เช่น importance sampling (IS), multiple importance sampling (MIS), sample importance resampling (SIR), resampling importance sampling (RIS), weighted reservoir sampling (WRS) และ ReSTIR ที่ผสาน RIS กับ WRS
บทความโดยละเอียดอยู่ที่นี่: https://agraphicsguynotes.com/posts/understanding_the_math_b...
เห็นเรื่องนี้แล้วทำให้อยากคิดต่อเกี่ยวกับอัลกอริทึมที่ฝ่ายสัมพันธมิตรใช้ หมายเลขซีเรียลในการประมาณจำนวนรถถังเยอรมัน
การประเมินภาคสนามสูงกว่าปริมาณการผลิตจริงประมาณ 5 เท่า แต่เทคนิคหมายเลขซีเรียลแม่นยำเกิน 90%
เป็นบทความที่ดีและอธิบายได้ยอดเยี่ยม เรื่องนี้ดูเหมือนจะพูดถึง Algorithm R ซึ่งน่าจะอธิบายครั้งแรกโดย Vitter: https://www.cs.umd.edu/~samir/498/vitter.pdf
บทความก่อนหน้าของ Vitter https://dl.acm.org/doi/10.1145/358105.893 อ้างถึง TAOCP เล่ม 2 ของ Knuth และใน Knuth ก็ไม่มีการอ้างอิงต่อเช่นกัน
จากมุมมองของวิทยาศาสตร์ข้อมูล ปริมาณข้อมูลเอง ก็มีข้อมูลสำคัญมาก ดังนั้นจึงควรบันทึกไว้ในล็อกด้วยว่าแต่ละ data point แทนจำนวนกี่รายการ
ตัวอย่างเช่น ถ้าอัตราการ sampling คือ 10% ก็ใส่ฟิลด์ที่มีค่า 10 ไว้ แล้วจะสามารถสร้างและประมาณค่าสถิติส่วนใหญ่ เช่น count, sum, average กลับขึ้นมาได้
โครงสร้างดีและอธิบายได้ชัดเจน ถ้าสนใจ เวอร์ชันแบบถ่วงน้ำหนัก ผมเคยอธิบายไว้เล็กน้อยที่นี่: https://gregable.com/2007/10/reservoir-sampling.html
ยังมีเวอร์ชันแบบกระจายที่ทำได้ง่ายด้วย MapReduce
อัลกอริทึมที่ง่ายมากอีกแบบคือสร้างคู่แบบสุ่มสำหรับแต่ละรายการในสตรีม แล้วคงรายการ N อันดับแรกตามค่าสุ่มนั้นไว้
อย่างแรก การทำแบบตรงไปตรงมาที่จัดอันดับด้วย
POW(RANDOM(), 1.0 / weight)แล้วเลือก N อันดับแรก จะมีปัญหาเรื่อง เสถียรภาพเชิงตัวเลข เมื่อ weight มีค่ามากหรือเล็กมากอย่างที่สอง ตัวอย่างผลลัพธ์จะไม่ได้มีการกระจายเหมือนประชากรต้นทาง แม้ในเชิงค่าคาดหมาย ยิ่งน้ำหนักรวมไปกระจุกอยู่ที่สมาชิกประชากรจำนวนน้อยก็ยิ่งเป็นเช่นนั้น แต่ในหลายกรณีก็เป็นการประมาณที่ใช้ได้
ปัญหาเหล่านี้มีพูดถึงเพิ่มเติมที่นี่: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
เป็นบทความที่ยอดเยี่ยม เข้าถึงง่าย และมีการแสดงภาพประกอบที่ดีมาก
ที่ $WORK เราใช้การดัดแปลงที่คล้ายกันเพื่อแก้ปัญหาที่เกี่ยวข้อง คือการประมาณ เปอร์เซ็นไทล์ บางค่าในสตรีมที่กำลังทำงานอยู่
เปอร์เซ็นไทล์ที่ต้องการเลือกจะเปลี่ยนเป็นครั้งคราว แต่โดยทั่วไปจะคงที่ตลอดการวนซ้ำมากกว่า 1 ล้านล้านครั้ง และมีข้อจำกัดว่าข้อมูลพื้นฐานมีลักษณะกึ่งคงที่
หากรองรับกระบวนการนี้ด้วย splay tree ก็จะทำการประมาณเปอร์เซ็นไทล์แบบ amortized O(1) ได้ เมื่อใช้ RAM เท่ากัน ขอบเขตความคลาดเคลื่อนจะกว้างกว่าเทคนิคอื่นหลายอย่าง แต่เร็วมาก
นอกจากนี้ยังสามารถปรับความน่าจะเป็นในการแทนที่ เพื่อกำหนด “ครึ่งชีวิตของข้อมูล” ตามเวลาหรือจำนวน และทำให้การประมาณเอนเอียงไปทางเหตุการณ์ล่าสุดได้ ซึ่งเหมาะกับปัญหาบางประเภทมากกว่า