fork download
copy 
  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.  
  75.         int r = rand()%(i+1);
  76.  
  77.         if (r < k) {
  78.             reservoir[r] = stream[i];
  79.         }
  80.  
  81.         printReservoir(reservoir);
  82.  
  83.         i++;
  84.     }
  85.  
  86. }
  87.  
  88. void selectReservoirItem (int stream[], int N) {
  89.     int i=0; //current index of elements in stream[]
  90.     int x = stream[i];
  91.  
  92.     // N is the number of elements in the stream
  93.     while (i < N) {
  94.         int r = rand()%(i+1);
  95.  
  96.         if (r == i) {
  97.             x = stream[i];
  98.         }
  99.  
  100.         cout<<x<<endl;
  101.         i++;
  102.     }
  103.  
  104. }
  105.  
  106. int main () {
  107.     int stream[] = {1, 2, 5, 5, 3, 7, 8, 8, 8, 11, 12};
  108.  
  109.     int N = 11;
  110.     int k = 4;
  111.  
  112.     cout<<"Reservoir Sampling (Solution I)"<<endl;
  113.     selectReservoir(stream, N, k);
  114.  
  115.     cout<<endl<<"Reservoir Sampling Optimised (Solution II)"<<endl;
  116.     selectReservoirOptimized(stream, N, k);
  117.  
  118.     cout<<endl<<"Reservoir item (Solution III)"<<endl;
  119.     selectReservoirItem(stream, N);
  120.  
  121.     return 0;
  122. }
  123.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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 8 8 5 
Items in the reservoir:
3 8 8 5 
Items in the reservoir:
3 8 11 5 
Items in the reservoir:
3 8 11 5 

Reservoir item (Solution III)
1
2
5
5
5
5
5
5
8
8
8
https://ideone.com/Jm3Bkj
language:
C++ 4.3.2 (gcc-4.3.2)
created:
300 days 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!