std::ranges::sample
Von cppreference.com
| Definiert in Header <algorithm> |
||
| Aufruf-Signatur |
||
| template< std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O, class Gen > |
(1) | (seit C++20) |
| template< ranges::input_range R, std::weakly_incrementable O, class Gen > requires (ranges::forward_range<R> || std::random_access_iterator<O>) && |
(2) | (seit C++20) |
1) Wählt M = min(n, last - first) Elemente aus der Sequenz
[first, last) (ohne Zurücklegen) aus, so dass jede mögliche Stichprobe die gleiche Wahrscheinlichkeit hat zu erscheinen, und schreibt diese ausgewählten Elemente in den Bereich, der bei out beginnt. Der Algorithmus ist stabil (bewahrt die relative Reihenfolge der ausgewählten Elemente), nur wenn
I std::forward_iterator modelliert. Das Verhalten ist undefiniert, wenn out sich in
[first, last) befindet.2) Dasselbe wie (1), verwendet aber r als Quellbereich, als ob ranges::begin(r) als first und ranges::end(r) als last verwendet würden.
Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als niebloids bekannt), d.h.
- Können explizite Template-Argumentlisten bei keinem von ihnen angegeben werden.
- Keiner von ihnen ist für Argument-abhängige Suche sichtbar.
- Wenn einer von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die Argument-abhängige Suche unterdrückt.
Inhalt |
[bearbeiten] Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den Bereich von Elementen definiert, aus denen die Stichprobe entnommen wird (die Population) |
| r | - | der Bereich, aus dem die Stichprobe entnommen wird (die Population) |
| out | - | der Ausgabiterator, in den die Stichproben geschrieben werden |
| n | - | Anzahl der zu entnehmenden Stichproben |
| gen | - | der Zufallszahlengenerator, der als Quelle der Zufälligkeit verwendet wird |
[bearbeiten] Rückgabewert
Ein Iterator, der gleich out + M ist, also das Ende des resultierenden Stichprobenbereichs.
[bearbeiten] Komplexität
Linear: 𝓞(last - first).
[bearbeiten] Hinweise
Diese Funktion kann Auswahl-Sampling oder Reservoir-Sampling implementieren.
[bearbeiten] Mögliche Implementierung
struct sample_fn { template<std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O, class Gen> requires (std::forward_iterator<I> or std::random_access_iterator<O>) && std::indirectly_copyable<I, O> && std::uniform_random_bit_generator<std::remove_reference_t<Gen>> O operator()(I first, S last, O out, std::iter_difference_t<I> n, Gen&& gen) const { using diff_t = std::iter_difference_t<I>; using distrib_t = std::uniform_int_distribution<diff_t>; using param_t = typename distrib_t::param_type; distrib_t D{}; if constexpr (std::forward_iterator<I>) { // this branch preserves "stability" of the sample elements auto rest{ranges::distance(first, last)}; for (n = ranges::min(n, rest); n != 0; ++first) if (D(gen, param_t(0, --rest)) < n) { *out++ = *first; --n; } return out; } else { // O is a random_access_iterator diff_t sample_size{}; // copy [first, first + M) elements to "random access" output for (; first != last && sample_size != n; ++first) out[sample_size++] = *first; // overwrite some of the copied elements with randomly selected ones for (auto pop_size{sample_size}; first != last; ++first, ++pop_size) { const auto i{D(gen, param_t{0, pop_size})}; if (i < n) out[i] = *first; } return out + sample_size; } } template<ranges::input_range R, std::weakly_incrementable O, class Gen> requires (ranges::forward_range<R> or std::random_access_iterator<O>) && std::indirectly_copyable<ranges::iterator_t<R>, O> && std::uniform_random_bit_generator<std::remove_reference_t<Gen>> O operator()(R&& r, O out, ranges::range_difference_t<R> n, Gen&& gen) const { return (*this)(ranges::begin(r), ranges::end(r), std::move(out), n, std::forward<Gen>(gen)); } }; inline constexpr sample_fn sample {}; |
[bearbeiten] Beispiel
Führen Sie diesen Code aus
#include <algorithm> #include <iomanip> #include <iostream> #include <iterator> #include <random> #include <vector> void print(auto const& rem, auto const& v) { std::cout << rem << " = [" << std::size(v) << "] { "; for (auto const& e : v) std::cout << e << ' '; std::cout << "}\n"; } int main() { const auto in = {1, 2, 3, 4, 5, 6}; print("in", in); std::vector<int> out; const int max = in.size() + 2; auto gen = std::mt19937{std::random_device{}()}; for (int n{}; n != max; ++n) { out.clear(); std::ranges::sample(in, std::back_inserter(out), n, gen); std::cout << "n = " << n; print(", out", out); } }
Mögliche Ausgabe
in = [6] { 1 2 3 4 5 6 }
n = 0, out = [0] { }
n = 1, out = [1] { 5 }
n = 2, out = [2] { 4 5 }
n = 3, out = [3] { 2 3 5 }
n = 4, out = [4] { 2 4 5 6 }
n = 5, out = [5] { 1 2 3 5 6 }
n = 6, out = [6] { 1 2 3 4 5 6 }
n = 7, out = [6] { 1 2 3 4 5 6 }[bearbeiten] Siehe auch
| (C++20) |
Ordnet Elemente in einem Bereich zufällig neu an (Algorithmus-Funktionsobjekt) |
| (C++17) |
Wählt N zufällige Elemente aus einer Sequenz aus (Funktionstemplate) |
