挑选从集合中的随机子集，最好的方法？ [英] best way to pick a random subset from a collection?

问题描述

我有一组在矢量对象从中我想选择一个随机子集（如100个项目回来，挑5随机）。在我第一次（非常草率）通过我做了一个非常简单的，也许过于聪明的解决方案：

I have a set of objects in a Vector from which I'd like to select a random subset (e.g. 100 items coming back; pick 5 randomly). In my first (very hasty) pass I did an extremely simple and perhaps overly clever solution:

Vector itemsVector = getItems();

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

虽然这具有很好的和简单的优点，我怀疑它不会规模非常好，即Collections.shuffle（）必须是O（n）的最少。我不太聪明的选择是

While this has the advantage of being nice and simple, I suspect it's not going to scale very well, i.e. Collections.shuffle() must be O(n) at least. My less clever alternative is

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())));
}

这是更好的方法有什么建议从集合中抽出一个随机子集？

Any suggestions on better ways to draw out a random subset from a Collection?

推荐答案

乔恩·宾利讨论这两种编程珠玑或更多的编程珍珠。你必须小心你的并购选择过程中N，但我想显示的code正常工作。而不是随机播放所有项目，你可以做随机洗牌洗牌只有第N个位置 - 这是一个有用的节省当N＆LT;＆LT;米

Jon Bentley discusses this in either 'Programming Pearls' or 'More Programming Pearls'. You need to be careful with your N of M selection process, but I think the code shown works correctly. Rather than randomly shuffle all the items, you can do the random shuffle only shuffling the first N positions - which is a useful saving when N << M.

高德纳还讨论了这些算法 - 我相信这将是第3卷排序和搜索，但我的集装未决房屋的举动，所以我不能正式检查

Knuth also discusses these algorithms - I believe that would be Vol 3 "Sorting and Searching", but my set is packed pending a move of house so I can't formally check that.

这篇关于挑选从集合中的随机子集，最好的方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！