c++ - 从数据列表生成随机序列的最快方法是什么？

Question

假设我有一个数据列表:{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 列表

Answer 1

我会使用 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做你想做的事。