70

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

有关从集合中提取随机子集的更好方法的任何建议？

4

10 回答 10

12

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

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

于 2008-09-25T22:35:59.303 回答
9

@乔纳森，

我相信这是您正在谈论的解决方案：

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 的 Programming Pearls 第 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个元素......”的想法。

于 2008-09-25T22:57:39.093 回答
5

如果你试图从 n 的列表中选择 k 个不同的元素，你上面给出的方法将是 O(n) 或 O(kn)，因为从 Vector 中删除一个元素会导致 arraycopy 将所有元素向下移动.

由于您要求最好的方法，这取决于您可以使用输入列表做什么。

如果可以接受修改输入列表，如您的示例中所示，那么您可以简单地将 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 / (nk)) 当 n 支配 k 时仍然接近 O(k)。（例如，如果 k 小于 n / 2，则它减少到 O(k)）。

如果 k 不以 n 为主，并且您无法修改列表，则不妨复制原始列表，并使用您的第一个解决方案，因为 O(n) 将与 O(k) 一样好。

正如其他人所指出的那样，如果您依赖于每个子列表都可能（且无偏见）的强随机性，那么您肯定需要比java.util.Random. 见java.security.SecureRandom。

于 2008-09-25T23:26:39.493 回答
4

几周前我写了一个有效的实现。它在 C# 中，但翻译成 Java 很简单（基本上是相同的代码）。好的一面是它也是完全公正的（一些现有的答案不是） -一种测试方法在这里。

它基于 Fisher-Yates shuffle 的 Durstenfeld 实现。

于 2008-09-25T23:06:37.107 回答
2

但是，您使用 Random 选择元素的第二种解决方案似乎很合理：

于 2008-09-25T22:10:18.630 回答
1

这是关于stackoverflow的一个非常相似的问题。

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

  • O(n) 解决方案：遍历您的列表，并以概率 (#needed / #remaining) 复制出一个元素（或对其的引用）。示例：如果 k = 5 且 n = 100，那么您采用概率为 5/100 的第一个元素。如果你复制那个，那么你选择下一个概率为 4/99；但如果你没有拿第一个，概率是 5/99。
  • O(k log k) 或 O(k 2 )：通过随机选择一个 < n 的数字，然后随机选择一个数字，构建 k 个索引（{0, 1, ..., n-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 2 )或O(k log k)，因为它取决于您搜索 s 并将其插入容器的速度。如果 s 是一个普通列表，那么其中一个操作是线性的，你得到 k^2。但是，如果您愿意将 s 构建为平衡二叉树，则可以节省 O(k log k) 时间。

于 2008-09-26T01:26:30.813 回答
0

移除费用是多少？因为如果需要将数组重写到新的内存块，那么您在第二个版本中完成了 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)，在 shuffle 中花费了另一个 O(n)，但是没有来自内部 while 检查器的冲突，并且可能花费的成本低于潜在的 O(5n)。

于 2008-09-25T22:17:25.307 回答
0

我个人会选择您的初始实施：非常简洁。性能测试将显示它的可扩展性。我已经以一种被滥用的方法实现了一个非常相似的代码块，并且它的扩展性足够大。特定代码也依赖于包含超过 10,000 个项目的数组。

于 2008-09-25T22:18:16.053 回答
0 
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));
}
于 2008-09-25T23:05:15.520 回答
0

我认为这里不会出现两个解决方案 - 对应的内容很长，并且包含一些链接，但是，我认为并非所有帖子都与从一组 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 互质，即 chhose gcd(x,n)=1，另一个是 a，即“起点” - 然后是系列： a % n,a+x % n, a+2*x % n,...a+(k-1)*x%n 是不同数字的序列（只要k<=n)。

于 2012-03-03T22:09:43.057 回答