从PHP数组中高效地选择n个随机元素（不使用shuffle）

Question

从PHP数组中高效地选择n个随机元素（不使用shuffle）

14

我有以下代码在PHP中从数组$array中选择$n个元素：

shuffle($array);
$result = array_splice($array, 0, $n);

当有一个大数组，但只有很少的元素（例如10000中的5个）时，这会相对较慢，因此我希望优化它，使得不必对所有元素进行洗牌。值必须是唯一的。

我正在寻找最高效的替代方案。我们可以假设$array没有重复，并且索引从0开始。

- Fabian Schmengler

1

请参见：http://php.net/manual/zh/function.array-rand.php#93834 - Rizier123

我也看过那个，但是我有点担心 array_flip 在大数组上的性能。 - Fabian Schmengler

@FabianSchmengler 感谢您的博客文章和基准测试。我认为您应该编辑您的问题，简要解释哪种解决方案（在两种争议中）最适合未来读者使用哪种情况。哦！还有，放一个链接到您的博客文章，其中包含所有细节。该页面已经存档在Internet Archive上。 - Fr0zenFyr

6个回答

4

此函数仅对$n个元素执行洗牌操作，其中$n是要选择的随机元素数量。它还适用于关联数组和稀疏数组。$array是要处理的数组，$n是要检索的随机元素数量。

如果我们将$max_index定义为count($array) - 1 - $iteration。

它通过生成0到$max_index之间的随机数来工作。选择该索引处的键，并将其索引替换为$max_index处的值，以便不能再次选择，因为在下一次迭代时$max_index将减少一个并且无法访问。总之，这是Richard Durstenfeld的Fisher-Yates shuffle，但仅对$n个元素进行操作，而不是整个数组。

function rand_pluck($array, $n) {
    $array_keys = array_keys($array);
    $array_length = count($array_keys);
    $max_index = $array_length -1;
    $iterations = min($n, $array_length);
    $random_array = array();
    while($iterations--) {
        $index = mt_rand(0, $max_index);
        $value = $array_keys[$index];
        $array_keys[$index] = $array_keys[$max_index];
        array_push($random_array, $array[$value]);
        $max_index--;
    }
    return $random_array;
}

- George Reith

是的，对于洗牌算法的变体是最好的（类似于我的答案），无论是在性能上还是在统计上，即无偏采样，+1。 - Nikos M.

严格来说，这个解决方案并不是 O(n)，而是 O(N)，因为必须使用 array_keys 等等。当然，它比原始的 shuffle 解决方案更快，而且是无偏的（因为它是 shuffle 的一个变体）。我的解决方案严格是 O(n)，但存在其他一些问题... - Nikos M.

@NikosM。确实，但实际上，在大规模数组（数十万个元素）上，“array_keys”非常快。重要的是区分时间复杂度和实际时间。虽然我不怀疑你的方法可能更快，但我决定在任何数组上工作的额外奖励比每100k元素可能产生的10毫秒惩罚更重要。 - George Reith

是的，看起来我们在这里需要权衡一下。我正在考虑如何通过另一种变化来优化我的回答，否则你的回答似乎应该是最佳解决方案。 - Nikos M.

3

关键是使用洗牌的变体，换句话说，是部分洗牌。

性能不是唯一的标准，统计效率，即无偏采样与原始shuffle解决方案同样重要。

function random_pick( $a, $n ) 
{
  $N = count($a);
  $n = min($n, $N);
  $picked = array_fill(0, $n, 0); $backup = array_fill(0, $n, 0);
  // partially shuffle the array, and generate unbiased selection simultaneously
  // this is a variation on fisher-yates-knuth shuffle
  for ($i=0; $i<$n; $i++) // O(n) times
  { 
    $selected = mt_rand( 0, --$N ); // unbiased sampling N * N-1 * N-2 * .. * N-n+1
    $value = $a[ $selected ];
    $a[ $selected ] = $a[ $N ];
    $a[ $N ] = $value;
    $backup[ $i ] = $selected;
    $picked[ $i ] = $value;
  }
  // restore partially shuffled input array from backup
  // optional step, if needed it can be ignored, e.g $a is passed by value, hence copied
  for ($i=$n-1; $i>=0; $i--) // O(n) times
  { 
    $selected = $backup[ $i ];
    $value = $a[ $N ];
    $a[ $N ] = $a[ $selected ];
    $a[ $selected ] = $value;
    $N++;
  }
  return $picked;
}

注意，该算法在时间和空间上严格为O(n)，产生无偏选择（是部分无偏洗牌），并产生具有连续键的适当数组输出（不需要额外的array_values等）。

使用示例：

$randomly_picked = random_pick($my_array, 5);
// or if an associative array is used
$randomly_picked_keys = random_pick(array_keys($my_array), 5);
$randomly_picked = array_intersect_key($my_array, array_flip($randomly_picked_keys));

针对PHP的洗牌算法，还有更多的变体和扩展：

- Nikos M.

看起来我们发布了同一算法的不同变体。对于你在我的答案中提到的原因，我给你点赞。 - George Reith

1

就像我下面所说的那样，我的算法快了很多。这个大约慢了25倍，而且不再随机：http://sandbox.onlinephpfunctions.com/code/68a415bbe48b07a9af10bdf8fecf4cf5e616a3ef - Devon

1

@Devon，玩弄测试用例，你会感到惊讶，这样做：注释掉我的代码的可选部分（涉及备份），并使用值为10、100、1000的测试用例，特别是对于10，你会非常惊讶，而且我的代码在所有情况下都具有统一的性能；这些情况和是无偏的（产生真正的组合）http://sandbox.onlinephpfunctions.com/code/7d63e32356902c1bd49dc1dd91ad44acd2ff38a6 - Nikos M.

再次感谢您的回答。不幸的是，在PHP中处理数组会有很大的开销，但对于PHP 7和HHVM而言，这是目前为止最好的通用解决方案（请参见http://www.schmengler-se.de/en/2015/09/efficiently-draw-random-elements-from-large-php-array/）。尽管如此，我还是接受了@Devons的答案，因为在我的用例中，它在所有平台上都有最好的结果。 - Fabian Schmengler

@fschmengler，好的，我也评论了Devon的答案，但请注意，这个算法在所有情况下都具有均匀的性能（由于常数因素可能在某些情况下较慢，但是均匀），因为例如绝对没有碰撞（不像其他情况）。干杯 - Nikos M.

显示剩余5条评论

2

我想知道为什么这里的每个人都把它搞得那么复杂？

以下是最快最简单的方法：

$randomArray = array_rand(array_flip($array), $n);

- hekag71341

2

您可以使用mt_rand()生成n个随机数，并将这些值填充到一个新数组中。为了避免返回相同的索引，我们使用实际返回的索引来填充新数组，并且始终检查索引是否存在于新数组中，如果是，则使用while循环遍历它，直到获取重复的索引。最后，我们使用array_values()获取一个从0开始的数组。

$count = count($array) - 1;
$new_array = array();
for($i = 0; $i < $n; $i++) {
    $index = mt_rand(0, $count);
    while(isset($new_array[$index])) {
        $index = mt_rand(0, $count);
    }

    $new_array[$index] = $array[$index];
}
$new_array = array_values($new_array);

- Charlotte Dunois

2

如果 mt_rand 两次返回相同的索引怎么办？ - Endijs

@Endijs 在范围为10000的情况下，这种可能性非常小，但是我们可以检查它是否已经被返回，如果是，则重新生成。 - Charlotte Dunois

在阅读代码后，我发现之前被踩的帖子是错误的。如果进行一些小的编辑以解锁投票，则可以重新点赞该帖子。 - Nikos M.

@NikosM。这是给你的。 - Charlotte Dunois

2

这将只对小的n显示出与数组洗牌相比的好处，但您可以：

选择一个随机索引r n次，每次将限制减少1
调整先前使用的索引
取值
存储已使用的索引

伪代码

arr = []
used = []
for i = 0..n-1:
    r = rand 0..len-i
    d = 0
    for j = 0..used.length-1:
        if r >= used[j]:
            d += 1
    arr.append($array[r + d])
    used.append(r)
return arr

- Paul S.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Devon · Accepted Answer

12

$randomArray = [];
while (count($randomArray) < 5) {
  $randomKey = mt_rand(0, count($array)-1);
  $randomArray[$randomKey] = $array[$randomKey];
}

这将快速提供恰好 5 个不重复的元素。键将被保留。

注意：您需要确保 $array 中有 5 个或更多的元素，或添加某种检查以防止无限循环。

- Devon

1

随着 n 逐渐接近数组长度，我会担心这将花费很长时间......选中它们后是否有快速的重新索引的方法？ - Paul S.

1

@PaulS。这完全取决于数组的大小。如果n接近数组长度，则shuffle()或其他类似的解决方案会更好。 - Devon

如果效率真的是一个问题，你也可以缓存$array的长度（在while之外计算），而不是每次调用mt_rand函数时都重新计算。 - Marten Koetsier

@NikosM. 和 Devon，感谢你们的有趣讨论。我进行了一些基准测试，并编写了一个非正式证明，证明这个算法实际上是无偏的。如果你们对结果感兴趣，请查看以下链接：http://www.schmengler-se.de/en/2015/09/efficiently-draw-random-elements-from-large-php-array/#more-1112 - Fabian Schmengler

@fschmengler，是的，关于无偏的观点并不正确（至少不完全正确），因为我之后看到了它（并发表了额外的评论），但无偏的部分仍然成立，因为为了产生与原始的shuffle-splice解决方案相同的结果，在最终选择中还需要一个额外的shuffle（以及array_values）。关于这个问题的好文章，如果对你的情况有效，那就没问题，干杯！ - Nikos M.

显示剩余17条评论