Różnice między wybraną wersją a wersją aktualną.
Both sides previous revision Previous revision Next revision | Previous revision | ||
random_sample_random_sample_n [2009/04/27 21:30] pplonski |
random_sample_random_sample_n [2009/04/29 10:59] pplonski |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== random_sample ====== | + | ====== random_sample i random_sample_n ====== |
+ | |||
+ | Obie funkcje random_sample i random_sample_n pochodzą z rozszerzenia SGI i nie są częścią standardu C++. | ||
+ | |||
+ | Złożoność obu algorytmów jest liniowa. | ||
+ | |||
+ | Funkcje te kopiują elementy z losową kolejnością. | ||
+ | |||
+ | ===== random_sample ===== | ||
+ | |||
+ | random_sample przeładowywuje dwie funkcje: | ||
+ | |||
+ | template <class InputIterator, class RandomAccessIterator> | ||
+ | RandomAccessIterator random_sample(InputIterator first, InputIterator last,RandomAccessIterator ofirst, RandomAccessIterator olast) | ||
+ | |||
+ | template <class InputIterator, class RandomAccessIterator, class RandomNumberGenerator> | ||
+ | RandomAccessIterator random_sample(InputIterator first, InputIterator last,RandomAccessIterator ofirst, RandomAccessIterator olast, RandomNumberGenerator& rand) | ||
+ | |||
+ | |||
+ | == Opis działania == | ||
+ | Losowo kopiuje n elementów z zakresu [first, last) do zakresu [ofirst, olast), gdzie n = min(last-first, olast-ofirst). Każdy element ze zbioru wejściowego może pojawić się tylko raz w zbiorze wyjściowym, elementy są wybierane z jednakowym prawdopodobieństwem. **Elementy na wyjściu mogą pojawić się w dowolnej kolejności**. Pierwsza wersja random_sample korzysta z wewnętrznego generatora liczb losowych, druga wersja pobiera jako argument funktor(obiekt funkcję) zdefiniowanego przez użytkownika generatora. Elementem zwracanym przez random_sample jest element ofirst+n. | ||
+ | |||
+ | == Parametry == | ||
+ | * InputIterator - iterator który może być inkrementowany by uzyskać dostęp do następnego obiektu | ||
+ | * RandomAccessIterator - iterator który może być inkrementowany i dekrementownay (kroki mogą być różnej długości) | ||
+ | * RandomNumberGenerator - obiekt-funkcja, który pozwala na genrowanie liczb całkowitych z zakresu [0, N) np.: jeżeli f jest Random Number Generator to f(N) zwraca liczbę całkowitą mniejszą N i wiekszą lub równą zero | ||
+ | |||
+ | |||
+ | ===== random_sample_n ===== | ||
+ | |||
+ | random_sample_n przładowywuje dwie funkcje: | ||
+ | |||
+ | template <class ForwardIterator, class OutputIterator, class Distance> | ||
+ | OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last, OutputIterator out, Distance n) | ||
+ | |||
+ | template <class ForwardIterator, class OutputIterator, class Distance, class RandomNumberGenerator> | ||
+ | OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last, OutputIterator out, Distance n, RandomNumberGenerator& rand) | ||
+ | |||
+ | == Opis działania == | ||
+ | |||
+ | Losowo kopiuje m elementów z zakresu [first, last) do zakresu [out, out+m), gdzie m = min(last-first, n). Każdy element wejściowy może pojawić się na wyjściu dokładnie raz, elementy wybierane są z jednakowym prawdopodobieństwem. **Elementy na wyjściu są losowe ale zachowują porządek tak jak były ustawione na wejściu**. Pierwsza wersja random_sample_n korzysta z wewnętrznego generatora liczb losowych, druga wersja pobiera jako argument funktor(obiekt funkcję) zdefiniowanego przez użytkownika generatora. Funkcja zwraca element out+m. | ||
+ | |||
+ | == Parametry == | ||
+ | * ForwardIterator - iterator który pozwala tylko pobierać następne elementy | ||
+ | * OutputIterator - iterator w którym można zapisać wartość do wskazywanej pozycji i przesunąć się do wskazywania na następny element ale nie można odczytać wartości i cofnąć się | ||
+ | * Distance - wartość całkowita wyznaczająca liczbę elementów na wyjściu | ||
+ | * RandomNumberGenerator - funktor (zachowanie takie samo jak dal random_sample), wartość Distance jest jego argumentem | ||
+ | |||
+ | |||
+ | ===== Przykład ===== | ||
+ | <code cpp> | ||
+ | #include <iostream> | ||
+ | #include <ext/algorithm> | ||
+ | #include <time.h> | ||
+ | #include <vector> | ||
+ | #include <iterator> | ||
+ | |||
+ | using namespace std; | ||
+ | |||
+ | /* | ||
+ | Funktor - obiekt który może być wywołany tak jakby był funkcją. | ||
+ | Obiekt ten definiuje operator(). | ||
+ | */ | ||
+ | struct RandomNumberGenerator | ||
+ | { | ||
+ | int operator()(int r) | ||
+ | { | ||
+ | return rand()%r; | ||
+ | } | ||
+ | }; | ||
+ | |||
+ | int main () | ||
+ | { | ||
+ | // inicjacja zarodka generatora | ||
+ | srand(time(NULL)); | ||
+ | int i; | ||
+ | const int N = 10; | ||
+ | const int n = 6; | ||
+ | int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; | ||
+ | int B[n]; | ||
+ | |||
+ | /* random_sample */ | ||
+ | cout << "random_sample\n"; | ||
+ | int *ret_val; // wskaźnik na wartość zwracaną | ||
+ | ret_val = __gnu_cxx::random_sample(A, A+N, B, B+n); // przykład działania | ||
+ | cout << *(ret_val-1) << endl; // wartość zwrócona | ||
+ | for(i = 0; i < n; ++i) | ||
+ | cout << B[i] << " "; // wartości na wyjściu | ||
+ | cout << endl; | ||
+ | |||
+ | RandomNumberGenerator rng; // funktor | ||
+ | cout << rng(13) << endl; // przykład użycia funktora | ||
+ | __gnu_cxx::random_sample(A, A+N, B, B+n, rng); // wersja z genratorem zewnętrznym | ||
+ | copy(B, B + n, ostream_iterator<int>(cout, " ")); // wypisanie z użyciem operatora ostream_iterator | ||
+ | cout << endl; // i funkcji copy | ||
+ | |||
+ | /* random_sample_n */ | ||
+ | cout << "random_sample_n\n"; | ||
+ | vector<int> vec; // wektor do zapisu elementów wyjściowych | ||
+ | vector<int>::const_iterator it; | ||
+ | insert_iterator<vector<int> > ii(vec, vec.begin()); // insert_iterator do wstawiania elementów do wektora | ||
+ | __gnu_cxx::random_sample_n(A, A+N, ii, n); // przykład działania funkcji | ||
+ | for(it = vec.begin(); it != vec.end(); ++it) | ||
+ | cout << *it << " "; | ||
+ | cout << endl; | ||
+ | |||
+ | const int M = 6; | ||
+ | const int m = 3; | ||
+ | string AA[] = {"ola", "ala", "ela", "ele", "alo", "olo"}; // przykład działania funkcji na tablicy ze stringami | ||
+ | // funkcja z generatorem zewnetrznym i wynikiem działania przekazywanym od razu na standardowe wyjście | ||
+ | __gnu_cxx::random_sample_n(AA, AA+M, ostream_iterator<string>(cout ," "), m, rng); | ||
+ | cout << endl; | ||
+ | |||
+ | return 0; | ||
+ | } | ||
+ | </code> | ||
+ | |||
+ | ===== Linki ===== | ||
+ | - http://www.sgi.com/tech/stl/random_sample.html | ||
+ | - http://www.sgi.com/tech/stl/random_sample_n.html |