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

การสุ่มตัวอย่างอ่างเก็บน้ำเป็นอัลกอริธึมแบบสุ่ม ในอัลกอริธึมนี้ k รายการจะถูกเลือกจากรายการที่มี n รายการที่แตกต่างกัน

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

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

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

Input:
The list of integers: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, The value of k = 6
Output:
K-Selected items in the given array: 8 2 7 9 12 6

อัลกอริทึม

chooseKItems(array, n, k)

ป้อนข้อมูล: อาร์เรย์ จำนวนองค์ประกอบในอาร์เรย์ จำนวนองค์ประกอบที่เลือก

ผลลัพธ์: เลือก k องค์ประกอบแบบสุ่ม

Begin
   define output array of size [k]
   copy k first items from array to output

   while i < n, do
      j := randomly choose one value from 0 to i
      if j < k, then
         output[j] := array[i]
      increase i by 1
   done
   display output array
End

ตัวอย่าง

#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) {        //it will choose k items from the array
   int i;
   int output[k];
   for (i = 0; i < k; i++)
      output[i] = array[i];

   srand(time(NULL));        //use time function to get different seed value

   while(i < n) {
      int j = rand() % (i+1);         //random index from 0 to i

      if (j < k)          //copy ith element to jth element in the 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