00001 #ifndef __sampling_h
00002 #define __sampling_h
00003 #include <boost/dynamic_bitset.hpp>
00004 #include <vector>
00005
00006 #include "util/random.hh"
00007
00008
00009
00010
00011
00012 namespace Moses
00013 {
00014
00015
00016
00017 template<typename idx_t>
00018 void
00019 randomSample(std::vector<idx_t>& v, size_t s, size_t N)
00020 {
00021
00022
00023 s = std::min(s,N);
00024 v.resize(s);
00025
00026
00027
00028
00029
00030
00031 if (s*10<N) {
00032 boost::dynamic_bitset<uint64_t> check(N,0);
00033 for (size_t i = 0; i < v.size(); i++) {
00034 size_t x = util::rand_excl(N);
00035 while (check[x]) x = util::rand_excl(N);
00036 check[x]=true;
00037 v[i] = x;
00038 }
00039 } else {
00040 size_t m=0;
00041 for (size_t t = 0; m <= s && t < N; t++)
00042 if (s==N || util::rand_excl(N-t) < s-m) v[m++] = t;
00043 }
00044 }
00045
00046 };
00047
00048 #endif