การสุ่มตัวอย่างแบบ Reservoir Sampling

บทนำ

Reservoir Sampling เป็นอัลกอริทึมแบบสุ่ม (Randomized Algorithm) ในอัลกอริทึมนี้ เลือก k ไอเทมจากลิสต์ที่มี n ไอเทมที่แตกต่างกัน

เราสามารถแก้ได้โดยสร้างอาเรย์เป็น Reservoir ขนาด k แล้วสุ่มเลือกหนึ่งอิลิเมนต์จากลิสต์หลักและวางใน Reservoir List เมื่อไอเทมถูกเลือกครั้งหนึ่ง จะไม่ถูกเลือกอีกในครั้งต่อไป แต่วิธีนี้ไม่มีประสิทธิภาพ เราสามารถเพิ่มความซับซ้อนได้ด้วยวิธีนี้

ใน Reservoir List ให้คัดลอก k ไอเทมแรกจากลิสต์ ต่อไปทีละอันจาก (k+1)th ในลิสต์ ให้ไอเทมที่เลือกอยู่ที่ index i หา index แบบสุ่มจาก 0 ถึง i และเก็บไว้ใน j ถ้า j อยู่ในช่วง 0 ถึง k ให้ swap reservoir[j] กับ list[i]

อินพุตและเอาต์พุต

Input: ลิสต์จำนวนเต็ม: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, ค่า k = 6
Output: K-Selected items ในอาเรย์ที่กำหนด: 8 2 7 9 12 6

อัลกอริทึม

chooseKItems(array, n, k)
Input: อาเรย์, จำนวนอิลิเมนต์ในอาเรย์, จำนวนอิลิเมนต์ที่ต้องการเลือก
Output: เลือก k อิลิเมนต์แบบสุ่ม

Begin
    กำหนด output array ขนาด [k]
    คัดลอก k ไอเทมแรกจาก array ไป output
    while i < n, do
        j := สุ่มค่าหนึ่งจาก 0 ถึง i
        if j < k, then
            output[j] := array[i]
        เพิ่ม i ขึ้น 1
    done
    แสดง output array
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void display(int array[], int n) {
    for (int i = 0; i < n; i++)
        cout << array[i] << " ";
}

void chooseKItems(int array[], int n, int k) {
    // จะเลือก k ไอเทมจากอาเรย์
    int i;
    int output[k];
    for (i = 0; i < k; i++)
        output[i] = array[i];
    srand(time(NULL));  // ใช้ time function เพื่อได้ seed ค่าต่างกัน
    while (i < n) {
        int j = rand() % (i+1);  // random index จาก 0 ถึง i
        if (j < k)  // คัดลอก ith element ไป jth element ใน output array
            output[j] = array[i];
        i++;
    }
    cout << "K-Selected items in the given array: ";
    display(output, k);
}

int main() {
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int n = 12;
    int k = 6;
    chooseKItems(array, n, k);
}

ผลลัพธ์

K-Selected items in the given array: 8 2 7 9 12 6