У меня есть следующий код для выбора $n элементов массива $array в PHP:
shuffle($array); $result = array_splice($array, 0, $n);
Учитывая большой массив, но только несколько элементов (например, 5 из 10000 ), это относительно медленно, поэтому я хотел бы оптимизировать его таким образом, чтобы не все элементы были перетасованы. Значения должны быть уникальными.
Я ищу наиболее эффективную альтернативу. Мы можем предположить, что $array не имеет дубликатов и 0 индексирован.
$randomArray = []; while (count($randomArray) < 5)) { $randomKey = mt_rand(0, count($array)-1); $randomArray[$randomKey] = $array[$randomKey]; }
Это обеспечит ровно 5 элементов без дубликатов и очень быстро. Клавиши будут сохранены.
Примечание. Вам нужно убедиться, что массив $ array имеет 5 или более элементов или добавляет некоторую проверку, чтобы предотвратить бесконечный цикл.
Эта функция выполняет перетасовку только на $n элементах, где $n – количество случайных элементов, которые вы хотите выбрать. Он также будет работать на ассоциативных массивах и разреженных массивах. $array – это массив для работы, а $n – количество случайных элементов для извлечения.
Если мы определяем $max_index как count($array) - 1 - $iteration .
Он работает, создавая случайное число от 0 до $max_index . Выбор ключа в этом индексе и замена его индекса на значение $max_index чтобы он никогда не мог быть выбран снова, поскольку $max_index будет меньше на следующей итерации и недостижимой.
Таким образом, это Shuffle от Fisher-Yates Ричарда Дурстенфельда, но работает только на $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; }
Это будет показывать только преимущества для небольших n по сравнению с массивом shuffle, но вы можете
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
Хитрость заключается в использовании вариации тасования или, другими словами, частичного перетасовки.
производительность – не единственный критерий, статистическая эффективность, то есть несмещенная выборка важна (как и исходное решение для 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, eg $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:
Вы можете генерировать n-раз случайное число с помощью mt_rand() и затем заполнять эти значения в новом массиве. Чтобы пойти против случая, когда один и тот же индекс возвращается дважды, мы используем фактический возвращенный индекс для заполнения нового массива и всегда проверяем, существует ли индекс в новом массиве, если мы используем его для циклического прохождения, пока мы получаем дублирующий индекс. В конце мы используем 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);