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.  
  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
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 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