Różnice

Różnice między wybraną wersją a wersją aktualną.

--- random_sample_random_sample_n [2009/04/27 21:30]
pplonski
+++ random_sample_random_sample_n [2009/04/29 10:59] (aktualna)
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

zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Różnice

Narzędzia strony