4

请参阅有关 Boost Random 库的更通用使用的相关问题。

我的问题涉及从 a 中选择一个随机元素std::list，执行一些操作，这可能包括从列表中删除该元素，然后选择另一个随机元素，直到满足某个条件。

boost 代码和 for 循环大致如下所示：

// 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 是没有意义的，特别是如果我用 time(0) 播种它。

4

3 回答 3

2

我假设这MyClass & mc = myList.begin() + index;只是伪代码，因为 begin 返回一个迭代器，我不认为 list iterators (non-random-access) support operator+。

据我所知，在这种情况下，使用变量生成器您的三个基本选项是：

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

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

于 2010-05-20T13:54:58.520 回答
1

您可以创建自己的 uniform_contained_int 分发类，在其构造函数中接受一个容器，聚合一个 uniform_int，并在每次容器更改大小时重新创建 uniform_distribution。查看uniform_int 的描述，您需要实现哪些方法来创建您的分发。

于 2010-05-20T13:56:42.557 回答
0

我认为您需要更多地担心性能方面的问题。特别是这个：

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

不是获取index-th 元素的特别快速的方法。

我会将它转换成这样的东西（它应该对列表的随机子序列进行操作）：

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

前提是您不需要元素的随机排列。

于 2010-05-20T13:59:49.833 回答