I'm still using C++14. So std::sample is out of reach. Is there something equivalent in boost? I do not want to copy my std::multiset which isn't reorderable.
2 Answers
As far as I know, there is not such a thing in boost. But you may write a simple one, yourself:
template<typename T>
std::vector<T> sample_items(const std::multiset<T> & ms, int samples)
{
std::vector<T> ret_value;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, ms.size() - 1);
for (int i = 0; i < samples; i++)
{
auto first = std::begin(ms);
auto offset = dis(gen);
std::advance(first, offset);
ret_value.push_back(*first);
}
return ret_value;
}
I do not want to copy my std::multiset which isn't reorderable.
If still prefer not to send your multiset to a function, just change the function in order to work with iterators.
UPDATE
Added a sequential draw algorithm that doesn't require additional storage by dynamically adjusting the probability for selecting the next item in sequence order.
See sequential_sample below
random_sample
I think the semantics of random_sample should be that you don't pick the same sequence element twice.
With multiset you could get duplicate values. Just use set if you don't want that.
To avoid duplicate picks you can generate a set of unique indices until the size matches n and then project the results:
A problem that lurks here is that when doing it naively, you might always return the results in the input order, which is definitely not what you want.
So, you could do a hybrid approach where you keep track of already picked elements. In this implementation I do that, while
- optimizing the storage to avoid dynamic allocation (unless n is >10)
- optimize the storage for locality of reference (cache friendliness)
- also cache the iterators with the picked items, so that subsequent picks may optimize iterator traversal, instead always advancing from the start iterator
There are some more comments in the code, and I left in a few trace statements that may help in understanding how the algorithm and the optimizations operate.
#include <random>
#include <set>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <boost/container/flat_set.hpp>
#include <boost/container/small_vector.hpp>
namespace my {
static std::ostream trace(std::clog.rdbuf()/* or: nullptr*/);
template <typename It, typename Out, typename URBG>
Out random_sample(It f, It l, Out out, size_t n, URBG& urbg) {
size_t const size = std::distance(f,l);
// adjust n for size (matches std::sample)
n = std::min(size, n);
// bind distribution to the random bit generator
auto pick = [&urbg,dist=std::uniform_int_distribution<size_t>(0, size-1)]() mutable {
return dist(urbg);
};
// Optimized storage of indices: works best for small n, probably still
// better than `std::set` for large n.
// IDEA: For very large n, prefer just a vector, sort+unique until n
// reached
//
// The loc field is a cached (forward) iterator so we reduce repeated
// traversals.
// IDEA: when It is of random iterator category, specialize without loc
// cache
struct P {
size_t idx; It loc;
bool operator<(P const& rhs) const { return idx < rhs.idx; }
};
namespace bc = boost::container;
bc::flat_set<P, std::less<P>, bc::small_vector<P, 10> > picked;
// generate n unique picks
while (n-->0) {
auto entry = [&] {
while (true) {
auto insertion = picked.insert({pick(), f});
if (insertion.second)
return insertion.first;
}
}();
trace << "accept pick: " << entry->idx << "\n";
// traverse and cache loc
if (entry == begin(picked)) {
// advance from scratcj
entry->loc = std::next(f, entry->idx);
} else {
// minimum steps from prior cached loc
auto& prior = *std::prev(entry);
trace << "using prior reference: " << prior.idx << "\n";
entry->loc = std::next(prior.loc, entry->idx - prior.idx);
}
// output
*out++ = *entry->loc;
}
return out;
}
} // namespace my
int main() {
std::multiset const pool {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
80, 81, 82, 83, 84, 85, 86, 87, 88, 89,
90, 91, 92, 93, 94, 95, 96, 97, 98, 99,
};
std::mt19937 engine(std::random_device{}());
for (int i = 0; i<3; ++i) {
my::random_sample(
pool.begin(), pool.end(),
std::ostream_iterator<int>(std::cout << "-- random draw (n=3): ", " "),
3,
engine);
std::cout << "\n";
}
}
Prints, e.g.:
accept pick: 46
accept pick: 98
using prior reference: 46
accept pick: 55
using prior reference: 46
accept pick: 80
accept pick: 12
accept pick: 20
using prior reference: 12
accept pick: 63
accept pick: 80
using prior reference: 63
accept pick: 29
-- random draw (n=3): 46 98 55
-- random draw (n=3): 80 12 20
-- random draw (n=3): 63 80 29
sequential_sample
As announced at the top, if the results being in input-order is not an issue, you can be much more efficient and require no storage at all:
template <typename It, typename Out, typename URBG>
Out sequential_sample(It f, It l, Out out, size_t n, URBG&& urbg) {
using D = std::uniform_int_distribution<size_t>;
size_t size = std::distance(f, l);
n = std::min(n, size);
D dist;
for (; n != 0; ++f) {
if (dist(urbg, D::param_type{ 0, --size }) >= n)
continue;
*out++ = *f;
--n;
}
return out;
}
This program combines random_sample and sequential_sample and demonstrates the difference in results:
#include <random>
#include <algorithm>
namespace my {
template <typename It, typename Out, typename URBG>
Out sequential_sample(It f, It l, Out out, size_t n, URBG&& urbg) {
using D = std::uniform_int_distribution<size_t>;
size_t size = std::distance(f, l);
n = std::min(n, size);
D dist;
for (; n != 0; ++f) {
if (dist(urbg, D::param_type{ 0, --size }) >= n)
continue;
*out++ = *f;
--n;
}
return out;
}
}
#include <boost/container/flat_set.hpp>
#include <boost/container/small_vector.hpp>
namespace my {
template <typename It, typename Out, typename URBG>
Out random_sample(It f, It l, Out out, size_t n, URBG& urbg) {
using Dist = std::uniform_int_distribution<size_t>;
size_t const size = std::distance(f,l);
// adjust n for size (matches std::sample)
n = std::min(size, n);
// bind distribution to the random bit generator
auto pick = [&urbg,dist=Dist(0, size-1)]() mutable {
return dist(urbg);
};
// Optimized storage of indices: works best for small n, probably still
// better than `std::set` for large n.
// IDEA: For very large n, prefer just a vector, sort+unique until n
// reached
//
// The loc field is a cached (forward) iterator so we reduce repeated
// traversals.
// IDEA: when It is of random iterator category, specialize without loc
// cache
struct P {
size_t idx; It loc;
bool operator<(P const& rhs) const { return idx < rhs.idx; }
};
namespace bc = boost::container;
bc::flat_set<P, std::less<P>, bc::small_vector<P, 10> > picked;
// generate n unique picks
while (n-->0) {
auto entry = [&] {
while (true) {
auto insertion = picked.insert({pick(), f});
if (insertion.second)
return insertion.first;
}
}();
// traverse and cache loc
if (entry == begin(picked)) {
// advance from scratcj
entry->loc = std::next(f, entry->idx);
} else {
// minimum steps from prior cached loc
auto& prior = *std::prev(entry);
entry->loc = std::next(prior.loc, entry->idx - prior.idx);
}
// output
*out++ = *entry->loc;
}
return out;
}
} // namespace my
#include <set>
#include <iostream>
#include <iterator>
int main() {
std::multiset<int> const pool {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
80, 81, 82, 83, 84, 85, 86, 87, 88, 89,
90, 91, 92, 93, 94, 95, 96, 97, 98, 99,
};
std::mt19937 engine(std::random_device{}());
constexpr int N = 10;
for (int i = 0; i<N; ++i) {
my::sequential_sample(
pool.begin(), pool.end(),
std::ostream_iterator<int>(std::cout << "-- sequential draw (n=3): ", " "),
3,
engine);
std::cout << "\n";
}
for (int i = 0; i<N; ++i) {
my::random_sample(
pool.begin(), pool.end(),
std::ostream_iterator<int>(std::cout << "-- random draw (n=3): ", " "),
3,
engine);
std::cout << "\n";
}
}
Prints e.g.
-- sequential draw (n=3): 14 66 71
-- sequential draw (n=3): 24 26 30
-- sequential draw (n=3): 19 34 65
-- sequential draw (n=3): 16 41 49
-- sequential draw (n=3): 15 25 37
-- sequential draw (n=3): 15 49 84
-- sequential draw (n=3): 12 53 88
-- sequential draw (n=3): 46 70 94
-- sequential draw (n=3): 32 51 56
-- sequential draw (n=3): 32 37 95
-- random draw (n=3): 15 38 35
-- random draw (n=3): 61 64 58
-- random draw (n=3): 4 37 93
-- random draw (n=3): 0 43 84
-- random draw (n=3): 58 52 59
-- random draw (n=3): 81 43 3
-- random draw (n=3): 41 30 89
-- random draw (n=3): 58 9 84
-- random draw (n=3): 15 39 27
-- random draw (n=3): 74 27 9
Related