C ++随机选择std :: vector的非空元素 >

Question

给我一个大的向量，它本身包含特定数据类型的向量，例如std::vector<std::vector<double> > foo。我试图从foo中检索一个随机元素foo [idx]，使得foo[idx]非空或分别为foo[idx].empty() == false。

我天真的猜测是从foo中选择随机元素，直到我的约束foo[idx].empty() == false得到满足。

然而，很可能foo非常稀疏地填充非空向量。因此，我的方法很可能会非常缓慢。

是否有更好的方法或我应该考虑完全不同的数据结构？

Answer 1

使用非空元素的索引维护辅助向量，并从那里获取随机元素

Answer 2

您可以构建非空元素的索引：

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)];

Answer 3

您可以先提取非空的索引，然后选择一个：

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];

Answer 4

您可以构建非空向量的引用向量。

#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;
}

Answer 5

这里有几个问题：

1. 序数vector人口稀少
2. A vector of vectors is wateful

为了解决问题1，我建议使用map<size_t, vector<double>> foo这将允许你使用非线性指数，但它不需要干预空vectors的人口。这里选择一个随机填充元素只涉及推进迭代器以指向适当的元素。例如，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的解决方案会更精细，因为我建议一起放弃使用vectors以支持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);