使用boost ::随机从std ::列表中选择要删除元素的列表

Question

看到这个 相关问题 关于Boost随机库的更多通用使用。

我的问题涉及从一个随机元素中选择 std::list, ，进行一些操作，可以很好地包括从列表中删除元素，然后选择另一个随机元素，直到满足某些条件为止。

增强代码和循环看起来大致相似：

// create and insert elements into list
std::list<MyClass> myList;
//[...]

// select uniformly from list indices
boost::uniform_int<> indices( 0, myList.size()-1 );    
boost::variate_generator< boost::mt19937, boost::uniform_int<> > 
  selectIndex(boost::mt19937(), indices);

for( int i = 0; i <= maxOperations; ++i ) {
    int index = selectIndex();
    MyClass & mc = myList.begin() + index;

    // do operations with mc, potentially removing it from myList
    //[...]
}

我的问题是，只要在元素上执行的操作在删除元素时，variate_generator就有可能在列表中选择无效索引。我认为每次完全重新创建variate_generator是没有意义的，尤其是在时间（0）播种时。

Answer 1

我认为 MyClass & mc = myList.begin() + index; 只是伪代码，因为开始返回迭代器，我认为列表迭代器（非随机访问）支持 operator+.

据我所知，在这种情况下，使用Variate Generator，您的三个基本选项是：

• 删除项目时，重新创建发电机。
• 在生成的索引上进行过滤，如果是> =列表的当前大小，请重试，直到获得有效的索引。请注意，如果您删除了很多索引，这也可能会变得非常效率。
• 将节点留在列表中，但标记为无效，因此，如果您尝试在该索引上操作，则可以安全地进行无操作。这只是第二个选项的不同版本。

或者，您可以设计一种能够适应容器更换大小的不同索引生成算法。

Answer 2

您可以创建自己的Uniform_contained_int分发类，该类别在其构造函数中接受一个容器，汇总一个Uniform_int，并每次容器更改大小时都会重新创建Uniform_distribution。看着那（这 制服的描述 您需要实现哪些方法来创建分布。

Answer 3

我认为您还有更多需要担心性能。特别是这样：

std::list<MyClass> myList;
myList.begin() + index;

不是一种特别快的方法 index- 元素。

我会将其转换为这样的东西（应该在列表的随机子序列上运行）：

X_i ~ U(0, 1) for all i
left <- max_ops
N <- list size
for each element
  if X_i < left/N
    process element
    left--
  N--

只要您不需要元素的随机排列。