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

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个元素),执行此算法需要相当长的时间.

有没有更快的方法从给定数据列表生成随机序列？应该为这个问题留出随机数发生器的实现,而是关注如何在提出的算法中使用RNG结果.

有什么想法吗？

现在我正在使用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

请注意,在另一个问题中,杰瑞分享了一个做你想做的事情的好方法.