Эффективно выбирать n случайных элементов из массива PHP (без перемешивания)

Эта функция выполняет перетасовку только для элементов $n, где $n - количество случайных элементов, которые вы хотите выбрать. Он также будет работать с ассоциативными массивами и разреженными массивами. $array - массив для работы, а $n - количество случайных элементов для извлечения.

Если мы определим $max_index как count($array) - 1 - $iteration.

Он работает, генерируя случайное число от 0 до $max_index. Выбор ключа по этому индексу и замена его индекса значением $max_index, чтобы он никогда не мог быть выбранным снова, так как $max_index будет на одну меньше на следующей итерации и недостижимым.

Вкратце это перетасовка Фишера-Йейтса Ричарда Дерстенфельда, но работающая только с элементами $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;
}

Хитрость заключается в том, чтобы использовать вариант перетасовки или, другими словами, частичную перетасовку.

Производительность не является единственным критерием, статистическая эффективность, т.Е. беспристрастная выборка так же важна (как и исходное решение 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. Как я могу взять n элементов случайным образом из массива Perl?

Это покажет преимущества только для небольших 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

Вы можете сгенерировать n-кратное случайное число с помощью mt_rand(), а затем заполнить эти значения в новом массиве. Чтобы пойти против случая, когда один и тот же индекс возвращается дважды, мы используем фактический возвращенный индекс для заполнения нового массива и всегда проверяем, существует ли индекс в новом массиве, если это так, мы используем 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);