给我一个大的向量,它本身包含特定数据类型的向量,例如std::vector<std::vector<double> > foo
。我试图从foo中检索一个随机元素foo [idx],使得foo[idx]
非空或分别为foo[idx].empty() == false
。
我天真的猜测是从foo
中选择随机元素,直到我的约束foo[idx].empty() == false
得到满足。
然而,很可能foo
非常稀疏地填充非空向量。因此,我的方法很可能会非常缓慢。
是否有更好的方法或我应该考虑完全不同的数据结构?
使用非空元素的索引维护辅助向量,并从那里获取随机元素
您可以构建非空元素的索引:
std::vector<std::vector<double> > foo;
std::vector<decltype (foo)::iterator> nonempty;
for (auto it = foo.begin(); it != foo.end; ++it)
{
if (! it->empty())
{
nonempty.push_back(it);
}
}
std::random_device rd;
// random-number engine used (Mersenne-Twister in this case)
std::mt19937 rng(rd());
// create a guaranteed unbiased index (unlike using modulo on rand)
std::uniform_int_distribution<size_t> uni_idx_dist(0,nonempty.size() - 1);
auto &random_nonempty = *nonempty[uni_idx_dist(rng)];
您可以先提取非空的索引,然后选择一个:
std::vector<int> ind;
for (int i = 0; i < foo.size(); i++){
if (! foo[i].empty()) {
ind.push_back(i);
}
}
int i = rand() % int.size();
return int[i];
您可以构建非空向量的引用向量。
#include <algorithm>
#include <functional>
#include <iterator>
#include <random>
#include <vector>
#include <iostream>
int main() {
using int_vec_t = std::vector<int>;
std::vector<int_vec_t> v = {
{0, 1, 2}, {}, {}, {3, 4, 5},
{}, {6, 7, 8}, {}, {}, {9}, {10, 11}
};
// You can't put reference direcly, so use reference_wrapper instead
std::vector<std::reference_wrapper<int_vec_t> > nonempty;
nonempty.reserve(v.size());
// "copy" non empty vectors. (Doesn't do copy, actually)
std::copy_if(v.begin(), v.end(), std::back_inserter(nonempty), [](const int_vec_t& v) { return !v.empty();});
if (nonempty.empty())
return 0;
// pick an element
static std::random_device rd;
static std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, nonempty.size() - 1);
const int_vec_t& result = nonempty[dis(gen)];
// dump result
std::copy(result.begin(), result.end(), std::ostream_iterator<int>(std::cout, ", "));
return 0;
}
这里有几个问题:
vector
人口稀少vector
of vector
s is wateful为了解决问题1,我建议使用map<size_t, vector<double>> foo
这将允许你使用非线性指数,但它不需要干预空vector
s的人口。这里选择一个随机填充元素只涉及推进迭代器以指向适当的元素。例如,result
将是pair
中随机键值foo
的常量:
const auto idx = foo.empty() ? 0U : std::mt19937{std::random_device{}()}() % size(foo);
const auto result = next(cbegin(foo), idx);
1和2的解决方案会更精细,因为我建议一起放弃使用vector
s以支持multimap<size_t, double> foo
这包含map
解决方案的所有好处,但权衡是必须使用迭代来重复密钥upper_bound
。此外,因为multimap
不存储密钥计数,所以size_t keyCount
需要与multimap
一起维护。或者假设它是一个临时初始化为0U
,它可能在需要时浪费地发现:for(auto it = cbegin(foo); it != cend(foo); it = foo.upper_bound(it->first)) ++keyCount;
使用keyCount
我们可以再次找到result
,这里将是与随机密钥匹配的第一个元素的常量迭代器:
int idx = keyCount == 0U ? 0 : std::mt19937{std::random_device{}()}() % keyCount;
auto result = cbegin(foo);
while(idx-- > 0) result = foo.upper_bound(result->first);