高效地从 PHP 数组中选取 n 个随机元素（无需随机播放）

问题描述 投票：0回答：7

我有以下代码在 PHP 中从数组 

$n
中选取 
$array
元素：

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

给定一个大数组但只有几个元素（例如 

5
中的 
10000
），这相对较慢，所以我想对其进行优化，以便不必对所有元素进行混洗。这些值必须是唯一的。

我正在寻找性能最佳的替代方案。我们可以假设 

$array
没有重复项并且是 
0
索引的。

php arrays performance random shuffle
7个回答
12
投票
$randomArray = [];
while (count($randomArray) < 5) {
  $randomKey = mt_rand(0, count($array)-1);
  $randomArray[$randomKey] = $array[$randomKey];
}

这将非常快地提供恰好 5 个没有重复的元素。 密钥将被保留。

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

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;
}
3
投票

技巧是使用 shuffle 的变体，或者换句话说，部分随机播放。

性能不是唯一的标准，统计效率，即无偏采样同样重要（与原始

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 洗牌的进一步变化和扩展：

  1. PHP - 仅打乱数组的一部分
  2. PHP 用种子洗牌
  3. 如何从 Perl 数组中随机取出 n 个元素？
2
投票

与数组洗牌相比，这只会显示小

n
的好处，但你可以

  1. 选择随机索引 
    r
    n
    次，每次将限制减少 
    1
  2. 调整之前使用的索引
  3. 获取价值
  4. 存储使用过的索引

伪代码

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
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);
2
投票

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

这是最快最简单的方法：

$randomArray = array_rand(array_flip($array), $n);
0
投票

array_rand
当它只从数组中选取一个随机键时，速度非常快，因为它不会进行数组操作。

您会看到的一个常见现象是在此函数中使用 

array_flip
来实际返回值而不是键。但是，您不需要这样做，而且 
array_flip
功能比 
array_rand

慢

如果您只需要一个元素，只需执行以下操作：

$element = $array[array_rand($array)];

如果您需要多个随机元素，实际上在循环中多次调用

array_rand
（num = 1）比构建一个键数组（num > 1）并循环遍历它要好。

这是一个基准测试脚本和一些相关结果：

数组随机一次：0.69403910636902秒
数组 Rand 多次：0.021188974380493 秒
随机播放和选择：16.576865911484 秒
阵列翻转和兰德：8.9312789440155 秒

<?php

function array_rand_multiple_times($array, $num) {
    $result = [];
    for ($i = 0; $i < $num; $i++) {
        $result[] = $array[array_rand($array)];
    }
    return $result;
}

function shuffle_and_pick($array, $num) {
    shuffle($array);
    return array_slice($array, 0, $num);
}

function array_rand_once($array, $num) {
    $keys = array_rand($array, $num);
    $result = [];
    foreach ($keys as $key) {
        $result[] = $array[$key];
    }
    return $result;
}

function array_flip_and_rand($array, $num) {
    return array_rand(array_flip($array), $num);
}

// Benchmark function
function benchmark($name, $function, $array, $num, $iterations) {
    $start = microtime(true);
    for ($i = 0; $i < $iterations; $i++) {
        $testArray = $array; // Ensure we work with a fresh copy of the array each time
        call_user_func($function, $testArray, $num);
    }
    $end = microtime(true);
    $time = $end - $start;
    echo "{$name}: {$time} seconds\n";
}

$array = range(1, 100000);
$num = 100;
$iterations = 10000;

benchmark('Array Rand Once', 'array_rand_once', $array, $num, $iterations);
benchmark('Array Rand Multiple Times', 'array_rand_multiple_times', $array, $num, $iterations);
benchmark('Shuffle and Pick', 'shuffle_and_pick', $array, $num, $iterations);
benchmark('Array Flip and Rand', 'array_flip_and_rand', $array, $num, $iterations);
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.