VTK  9.2.6
vtkReservoirSampler.h
Go to the documentation of this file.
1/*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkReservoirSampler.h
5
6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 All rights reserved.
8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9
10 This software is distributed WITHOUT ANY WARRANTY; without even
11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12 PURPOSE. See the above copyright notice for more information.
13
14=========================================================================*/
30#ifndef vtkReservoirSampler_h
31#define vtkReservoirSampler_h
32
33#include "vtkAbstractArray.h"
34#include "vtkCommonMathModule.h"
35
36#include <algorithm>
37#include <cmath>
38#include <limits>
39#include <random>
40#include <stdexcept>
41
42class VTKCOMMONMATH_EXPORT vtkReservoirSamplerBase
43{
44protected:
45 using SeedType = typename std::random_device::result_type;
46
48};
49
50template <typename Integer, bool Monotonic = true>
52{
53public:
57 const std::vector<Integer>& operator()(Integer kk, Integer nn) const
58 {
59 VTK_THREAD_LOCAL static std::vector<Integer> data;
60 this->GenerateSample(kk, nn, data);
61 return data;
62 }
63
67 const std::vector<Integer>& operator()(Integer kk, vtkAbstractArray* array) const
68 {
69 VTK_THREAD_LOCAL static std::vector<Integer> data;
70 if (!array)
71 {
72 throw std::invalid_argument("Null arrays are disallowed.");
73 }
74 if (array->GetNumberOfTuples() > std::numeric_limits<Integer>::max())
75 {
76 throw std::invalid_argument("Array size would overflow integer type.");
77 }
78 this->GenerateSample(kk, array->GetNumberOfTuples(), data);
79 return data;
80 }
81
82protected:
83 void GenerateSample(Integer kk, Integer nn, std::vector<Integer>& data) const
84 {
85 if (nn < kk)
86 {
87 kk = nn;
88 }
89 if (kk < 0)
90 {
91 throw std::invalid_argument(
92 "You must choose a non-negative number of values from a proper sequence.");
93 }
94 data.resize(kk);
95 if (kk == 0)
96 {
97 return;
98 }
99 // I. Fill the output with the first kk values.
100 Integer ii;
101 for (ii = 0; ii < kk; ++ii)
102 {
103 data[ii] = ii;
104 }
105 if (kk == nn)
106 {
107 return;
108 }
109
110 std::mt19937 generator(vtkReservoirSampler::RandomSeed());
111 std::uniform_real_distribution<> unitUniform(0., 1.);
112 std::uniform_int_distribution<Integer> randomIndex(0, kk - 1);
113 double w = exp(log(unitUniform(generator)) / kk);
114
115 while (true)
116 {
117 Integer delta = static_cast<Integer>(floor(log(unitUniform(generator)) / log(1.0 - w)) + 1);
118 if (delta < 0)
119 {
120 // If delta overflows the size of the integer, we are done.
121 break;
122 }
123 // Be careful here since delta may be large and nn may be
124 // at or near numeric_limits<Integer>::max().
125 if (nn - ii > delta)
126 {
127 Integer jj = randomIndex(generator);
128#if 0
129 std::cout << " i " << ii << " δ " << delta << " w " << w << " → j " << jj << "\n";
130#endif
131 ii += delta;
132 data[jj] = ii;
133 w *= exp(log(unitUniform(generator)) / kk);
134 }
135 else
136 {
137 // Adding delta to ii would step beyond our sequence size,
138 // so we are done.
139 break;
140 }
141 }
142 if (Monotonic)
143 {
144 std::sort(data.begin(), data.end());
145 }
146 }
147};
148
149#endif // vtkReservoirSampler_h
150// VTK-HeaderTest-Exclude: vtkReservoirSampler.h
Abstract superclass for all arrays.
vtkIdType GetNumberOfTuples() const
Get the number of complete tuples (a component group) in the array.
static SeedType RandomSeed()
typename std::random_device::result_type SeedType
void GenerateSample(Integer kk, Integer nn, std::vector< Integer > &data) const
const std::vector< Integer > & operator()(Integer kk, Integer nn) const
Choose kk items from a sequence of (0, nn - 1).
const std::vector< Integer > & operator()(Integer kk, vtkAbstractArray *array) const
Choose kk items from a sequence of (0, array->GetNumberOfTuples() - 1).