fork download 
  1. //
  2. //  main.cpp
  3. //  Reservoir Sampling
  4. //
  5. //  Created by Himanshu on 27/11/22.
  6. //
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. using namespace std;
  11.  
  12. void printReservoir (vector<int> reservoir) {
  13.     cout<<"Items in the reservoir:"<<endl;
  14.  
  15.     for (int item: reservoir) {
  16.         cout<<item<<" ";
  17.     }
  18.  
  19.     cout<<endl;
  20. }
  21.  
  22. bool checkItemPresent (vector<int> reservoir, int x) {
  23.     for (int item: reservoir) {
  24.         if (item == x) {
  25.             return true;
  26.         }
  27.     }
  28.  
  29.     return false;
  30. }
  31.  
  32. void selectReservoir (int stream[], int N, int k) {
  33.     int i; //current index of elements in stream[]
  34.  
  35.     // reservoir[] vector contain selected items.
  36.     // Initialise it with first k elements of stream[]
  37.     vector<int> reservoir;
  38.  
  39.     for (i = 0; i < k; i++) {
  40.         reservoir.push_back(stream[i]);
  41.     }
  42.  
  43.     printReservoir(reservoir);
  44.  
  45.     // N is the number of elements in the stream
  46.     while (i < N) {
  47.         if (!checkItemPresent(reservoir, stream[i])) {
  48.             int j = rand()%k;
  49.             reservoir[j] = stream[i];
  50.  
  51.             printReservoir(reservoir);
  52.         }
  53.  
  54.         i++;
  55.     }
  56.  
  57. }
  58.  
  59. void selectReservoirOptimized (int stream[], int N, int k) {
  60.     int i; //current index of elements in stream[]
  61.  
  62.     // reservoir[] vector contain selected items.
  63.     // Initialise it with first k elements of stream[]
  64.     vector<int> reservoir;
  65.  
  66.     for (i = 0; i < k; i++) {
  67.         reservoir.push_back(stream[i]);
  68.     }
  69.  
  70.     printReservoir(reservoir);
  71.  
  72.     // N is the number of elements in the stream
  73.     while (i < N) {
  74.         if (!checkItemPresent(reservoir, stream[i])) {
  75.             int r = rand()%(i+1);
  76.  
  77.             if (r < k) {
  78.                 reservoir[r] = stream[i];
  79.             }
  80.  
  81.             printReservoir(reservoir);
  82.         }
  83.  
  84.         i++;
  85.     }
  86.  
  87. }
  88.  
  89. void selectReservoirItem (int stream[], int N) {
  90.     int i=0; //current index of elements in stream[]
  91.     int x = stream[i];
  92.  
  93.     // N is the number of elements in the stream
  94.     while (i < N) {
  95.         int r = rand()%(i+1);
  96.  
  97.         if (r == i) {
  98.             x = stream[i];
  99.         }
  100.  
  101.         cout<<x<<endl;
  102.         i++;
  103.     }
  104.  
  105. }
  106.  
  107. int main () {
  108.     int stream[] = {1, 2, 5, 5, 3, 7, 8, 8, 8, 11, 12};
  109.  
  110.     int N = 11;
  111.     int k = 4;
  112.  
  113.     cout<<"Reservoir Sampling (Solution I)"<<endl;
  114.     selectReservoir(stream, N, k);
  115.  
  116.     cout<<endl<<"Reservoir Sampling Optimised (Solution II)"<<endl;
  117.     selectReservoirOptimized(stream, N, k);
  118.  
  119.     cout<<endl<<"Reservoir item (Solution III)"<<endl;
  120.     selectReservoirItem(stream, N);
  121.  
  122.     return 0;
  123. }
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin 
Standard input is empty
stdout 
Reservoir Sampling (Solution I)
Items in the reservoir:
1 2 5 5 
Items in the reservoir:
1 2 5 3 
Items in the reservoir:
1 2 7 3 
Items in the reservoir:
1 8 7 3 
Items in the reservoir:
1 8 7 11 
Items in the reservoir:
1 12 7 11 

Reservoir Sampling Optimised (Solution II)
Items in the reservoir:
1 2 5 5 
Items in the reservoir:
3 2 5 5 
Items in the reservoir:
3 2 5 5 
Items in the reservoir:
3 2 8 5 
Items in the reservoir:
3 2 8 5 
Items in the reservoir:
3 12 8 5 

Reservoir item (Solution III)
1
2
5
5
5
5
5
5
5
5
12
https://ideone.com/9tsniL
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!