假设我有一个数据列表:{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 其中 n = 10 个元素
我想从这个集合中随机选择 k 个元素来形成一个子列表,假设 k = 5。
在这种情况下,我可能会得到一个看起来像 {9, 3, 5, 2, 7} 的子列表
我可以通过以下方式完成此操作:
- 随机确定列表中的偏移量,介于 0 和列表的当前大小减 1 之间
- 将该元素附加到我的子列表
- 从原始列表中删除该元素
- 重复直到找到所需的大小
问题在于,随着原始列表的增长,偏移量和删除时间也会增长,对于任何非常大的列表(比如超过 1,000,000 个元素),执行此算法需要相当长的时间。
是否有更快的方法从给定数据列表生成随机序列?随机数生成器的实现应该放在一边,而不是关注随机数生成器的结果如何在所提出的算法中使用。
有什么想法吗?
现在我正在使用 C++ STL 列表
最佳答案
我会使用 random_shuffle
.您可以通过提供第三个参数来更改生成器。
它需要随机访问迭代器,因此您可以切换到 std::vector
(通常优于 std::list
,可以说是更糟糕的容器),或者只是对一些数组进行操作。我将同时演示:
int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::random_shuffle(data, data + 10);
// or
std::vector data; // populate it
std::random_shuffle(data.begin(), data.end());
现在一切都是随机的,只需将第一个 k
元素作为你的子集:
// now treat data[0] through data[k] as your random subset, or:
std::vector subset(data, data + k);
// or
data.resize(k); // shrink vector
请注意,在另一个问题中,Jerry shares an excellent way做你想做的事。
关于c++ - 从数据列表生成随机序列的最快方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3310928/