java - 从集合中选择随机子集的最佳方法？

Question

我在 Vector 中有一组对象，我想从中选择一个随机子集(例如，返回 100 个项目；随机选择 5 个)。在我的第一次(非常仓促的)传球中，我做了一个非常简单但可能过于聪明的解决方案:

Vector itemsVector = getItems();

Collections.shuffle(itemsVector);
itemsVector.setSize(5);

虽然这具有美观和简单的优点，但我怀疑它不会很好地扩展，即 Collections.shuffle() 必须至少为 O(n)。我不太聪明的选择是

Vector itemsVector = getItems();

Random rand = new Random(System.currentTimeMillis()); // would make this static to the class    

List subsetList = new ArrayList(5);
for (int i = 0; i < 5; i++) {
     // be sure to use Vector.remove() or you may get the same item twice
     subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size())));
}

关于从集合中抽取随机子集的更好方法有什么建议吗？

Answer 1

Jon Bentley 在“Programming Pearls”或“More Programming Pearls”中讨论了这一点。您需要小心您的 N of M 选择过程，但我认为显示的代码可以正常工作。与其随机打乱所有项目，不如随机打乱只打乱前 N 个位置 - 当 N << M.

时，这是一个有用的节省

Knuth 还讨论了这些算法 - 我相信这将是第 3 卷“排序和搜索”，但我的集合已打包等待搬家，因此我无法正式检查。