从集合中随机选择一个子集的最佳方法是什么？

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

有没有更好的方法从一个集合中随机选择一个子集？

- Tom

---

严格来说，您的代码假定您正在处理一个列表/向量。如果您处理的是任意集合，则首先必须将其所有项提取到一个列表/向量/数组中，这可能非常昂贵。这是因为通常的洗牌算法仅适用于列表/数组。 - Alexander

我发现 Floyd 算法可以在所有子集上提供可证明的均匀分布，因此我强烈推荐 Eyal Schneider 的答案，其中链接到了一篇详细介绍该算法的文章，包括证明和实现。 - Jean-Philippe Pellet

itemsVector.remove的时间复杂度为O(n) http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html#remove(int)。我认为可以实现O(k)的运行时间。 - Kunukn

Answer 1

Jon Bentley在《编程珠玑》或《更多编程珠玑》中讨论了这个问题。在选择N和M时需要小心，但我认为所展示的代码是正确的。不要随机打乱所有项目，而是只对前N个位置进行随机打乱-当N << M 时，这是一个有用的节省。

Knuth也讨论了这些算法 - 我相信那应该是第3卷“排序和搜索”，但我的书集已经装箱等待搬家，所以我不能正式检查。

- Jonathan Leffler

---

+1 真是厉害，你比我更快地回答了问题。我也在写关于执行前五步随机洗牌的内容：从1到M选择一个随机数，将第一个元素与该索引处的元素进行交换，然后从2到M选择一个随机数，交换第二个元素，依此类推。 - Alexander

感谢大家提供的所有信息。虽然他们都有很好的补充，但我选择这个方案，因为这可能是我重构代码的方式：

• 将 i 设为 0
• 从 i 到 n 中获取随机元素 r
• 交换元素 @ i 和元素 @ r
• i++
• 重复直到获得所需的元素

- Tom

Answer 2

@Jonathan，

我相信这就是你所说的解决方案：

void genknuth(int m, int n)
{    for (int i = 0; i < n; i++)
         /* select m of remaining n-i */
         if ((bigrand() % (n-i)) < m) {
             cout << i << "\n";
             m--;
         }
}

这段内容出自Jon Bentley的《编程珠玑》第127页，基于Knuth的实现。

编辑：我刚在第129页看到了进一步的修改：

void genshuf(int m, int n)
{    int i,j;
     int *x = new int[n];
     for (i = 0; i < n; i++)
         x[i] = i;
     for (i = 0; i < m; i++) {
         j = randint(i, n-1);
         int t = x[i]; x[i] = x[j]; x[j] = t;
     }
     sort(x, x+m);
     for (i = 0; i< m; i++)
         cout << x[i] << "\n";
}

基于这个想法，我们只需要对数组的前m个元素进行洗牌操作即可。

- daniel

Answer 3

如果你想从一个包含n个元素的列表中选择k个不同的元素，使用上面提到的方法将会是O(n)或O(kn)，因为从向量中移除一个元素会导致数组复制，将所有元素向下移动。

既然你在寻找最佳方法，这取决于你可以对输入列表做什么。如果可以修改输入列表，就像你的例子一样，你只需要把k个随机元素交换到列表的开头，并在O(k)时间内返回它们，方法如下：

public static <T> List<T> getRandomSubList(List<T> input, int subsetSize)
{
    Random r = new Random();
    int inputSize = input.size();
    for (int i = 0; i < subsetSize; i++)
    {
        int indexToSwap = i + r.nextInt(inputSize - i);
        T temp = input.get(i);
        input.set(i, input.get(indexToSwap));
        input.set(indexToSwap, temp);
    }
    return input.subList(0, subsetSize);
}

如果列表必须以与开始时相同的状态结束，您可以跟踪您交换的位置，然后在复制所选子列表后将列表返回到其原始状态。这仍然是一种O（k）的解决方案。

但是，如果您不能修改输入列表，并且k远小于n（例如从100个中选择5个），则最好不要每次删除所选元素，而只需选择每个元素，如果您得到重复的元素，请将其丢弃并重新选择。这将为您提供O（kn /（n-k）），当n支配k时，它仍接近于O（k）。 （例如，如果k小于n / 2，则减少为O（k））。

如果k没有被n支配，并且您不能修改列表，则最好复制您的原始列表，并使用第一个解决方案，因为O（n）和O（k）一样好。

正如其他人所指出的那样，如果您依赖于每个子列表都是可能的强随机性（和无偏见），则绝对需要比java.util.Random更强大的内容。请参阅java.security.SecureRandom。

- Dave L.

Answer 4

我几周前写了一个高效的实现，链接在这里：http://gregbeech.com/blog/shuffle-and-takerandom-extension-methods-for-ienumerable-t。它是用C#编写的，但将其转换成Java非常简单（基本上是相同的代码）。优点是它也完全不偏向任何一种结果（而某些现有答案则存在偏差），测试方法在这里：http://gregbeech.com/blog/determining-the-bias-of-a-shuffle-algorithm。它是基于Fisher-Yates shuffle的Durstenfeld实现。

- Greg Beech

---

很棒的文章。我认为可以从中得出一个结论，即在原始问题的代码中，交换元素而不是删除它们可以改进代码。这样可以避免在删除元素时需要折叠列表所带来的性能损失。 - qualidafial

这个回答几乎只有链接，能否请有关人员更新一下相关代码？ - Russia Must Remove Putin

链接已损坏。 - Antoine

由于WaybackMachine的强大功能，您可以在此处找到一份副本（https://web.archive.org/web/20111016031646/http://gregbeech.com:80/blog/shuffle-and-takerandom-extension-methods-for-ienumerable-t）。 - Jayrassic

Answer 5

您使用随机数来选择元素的第二种解决方案似乎很可靠，但是：

• 根据您的数据敏感程度而定，我建议使用某种哈希方法来混淆随机数生成器的种子。有一个好的案例研究，请参见我们如何学会在网上扑克中作弊(但是截至2015年12月18日，此链接已失效)。一些备用网址可通过在双引号中搜索文章标题在谷歌上找到，包括:

  • 我们如何学会在网上扑克中作弊 ——显然是最初的出版商。
  • 我们如何学会在网上扑克中作弊
  • 我们如何学会在网上扑克中作弊
     

• Vector是同步的。如果可能的话，使用ArrayList可以提高性能。

- qualidafial

---

感谢您提供更好的种子使用提示；我会查看您发布的链接。完全同意使用ArrayList而不是Vector；但是，这是一个第三方库返回的Vector，我无法控制返回的数据类型。谢谢！ - Tom

哈哈，我现在需要修复我的洗牌代码了...我之前使用的是System.nanoTime()作为我的种子！感谢您的精彩文章。 - Pyrolistical

这样做是可行的，但不是最佳方式。它比必要的速度慢。 - Dave L.

Answer 6

这里有一个在stackoverflow上非常相似的问题。

总结一下我最喜欢的答案（第一个来自用户Kyle）：

• O(n) 解法：遍历列表，并以概率（#needed / #remaining）复制一个元素（或其引用）。例如：如果 k = 5，n = 100，则您使用概率 5/100 获取第一个元素。如果您复制了它，则选择下一个元素的概率为 4/99；但是如果您没有选择第一个元素，则概率为 5/99。
• O(k log k) 或 O(k²)：通过随机选择小于 n 的数字，然后随机选择小于 n-1 的数字等，构建一个 k 个索引（数字在 {0, 1, ..., n-1} 中）的排序列表。在每个步骤中，您需要重新校准您的选择，以避免碰撞并保持概率均匀。例如，如果 k=5，n=100，您的第一个选择是 43，则您的下一个选择在 [0, 98] 范围内，如果它大于等于 43，则将其加 1。因此，如果您的第二个选择是 50，则将其加 1，您就会得到 {43, 51}。如果您的下一个选择是 51，则将其加 2，以获得 {43, 51, 53}。

这里有一些伪Python代码 -

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s 

我是说时间复杂度是O(k²) 或者 O(k log k)，这取决于你能多快地在容器中搜索和插入s。如果s是一个普通的列表，其中一个操作是线性的，那么你将得到k²。然而，如果你愿意把s建成平衡二叉树，你可以在O(k log k)的时间内完成。

- Tyler

---

这些方法还不错，但并非最佳方式。可以用O(k)的时间复杂度完成。 - Dave L.

这些不会影响原始数组。我还没有看到任何解决方案在不操纵原始数组的情况下也能做到这一点。 - Tyler

我已经在上面添加了这样的解决方案。只要k远小于n，你最好只是从列表中选择随机元素，并且排除重复项，直到你得到k个为止。 - Dave L.

这是一个非常实用的算法，特别是如果您使用哈希集来快速检查冲突。但从理论分析来看，最坏情况实际上是O（无穷大），因为您没有保证冲突数量的限制；非哈希版本每个冲突检查仍需要O（log k）= k log k总计。 - Tyler

确实，你应该使用一个哈希集来检查冲突。由于我们处理的是随机算法，因此重要的是分析输入的最坏情况复杂度，而不是随机值的预期情况。 - Dave L.

Answer 7

我认为这里有两个解决方案没有出现 - 对应的内容相当长，并包含一些链接，但我不认为所有帖子都涉及从N个元素的集合中选择K个元素的问题。[通过“集合”，我指的是数学术语，即所有元素仅出现一次，顺序不重要]。

解决方案1：

//Assume the set is given as an array:
Object[] set ....;
for(int i=0;i<K; i++){
randomNumber = random() % N;
    print set[randomNumber];
    //swap the chosen element with the last place
    temp = set[randomName];
    set[randomName] = set[N-1];
    set[N-1] = temp;
    //decrease N
    N--;
}

这看起来与丹尼尔给出的答案相似，但实际上非常不同。它的运行时间为O(k)。

另一个解决方案是使用一些数学： 将数组索引视为Z_n，因此我们可以随机选择2个数字，x是与n互质的，即选择gcd(x，n)=1，另一个是“起始点”a，然后序列：a％n，a+x％n，a+2*x％n，... a+(k-1)*x％n是一系列不同的数字（只要k≤n）。

- user967710

Answer 8

我个人会选择您的初始实现：非常简洁。性能测试将展示其可扩展性。我已经在一个相当频繁使用的方法中实现了非常相似的代码块，并且它具有足够的扩展性。特别的代码依赖于包含超过10,000个项目的数组。

- daniel

Answer 9

删除的成本是多少？因为如果需要将数组重写到新的内存块中，那么在第二个版本中，您已经执行了O(5n)次操作，而不是之前想要的O(n)。

您可以创建一个布尔数组并将其设置为false，然后：

for (int i = 0; i < 5; i++){
   int r = rand.nextInt(itemsVector.size());
   while (boolArray[r]){
       r = rand.nextInt(itemsVector.size());
   }
   subsetList.add(itemsVector[r]);
   boolArray[r] = true;
}

如果您的子集比总大小小很多，则此方法有效。当这些大小接近（即，大小为1/4或其他值）时，您会在随机数生成器上遇到更多的冲突。在这种情况下，我会制作一个整数列表，其大小与您的大型数组相同，然后对该整数列表进行洗牌，并从中取出第一个元素以获取您的（无冲突的）索引。这样，您需要花费O(n)来构建整数数组以及另外O(n)进行洗牌，但是没有内部while检查器的冲突，并且少于remove可能会产生的潜在O(5n)成本。

- mmr

---

O(5N) === O(N); 这就是大O符号的关键点。但是，当你有两个方法，都是O(N)时，常数乘数和常数加法项变得显著（以及任何相关的次线性项）。 - Jonathan Leffler

Answer 10

Set<Integer> s = new HashSet<Integer>()
// add random indexes to s
while(s.size() < 5)
{
    s.add(rand.nextInt(itemsVector.size()))
}
// iterate over s and put the items in the list
for(Integer i : s)
{
    out.add(itemsVector.get(i));
}

- Wesley Tarle

---

如果它没有概率运行时间，那就太好了，当n接近集合的大小时，运行时间会大大增加... - Jean-Philippe Pellet