Elegir de forma eficiente n elementos aleatorios de la matriz de PHP (sin barajar)

Tengo el siguiente código para elegir $n elementos de una matriz array $array en PHP:

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

Dado un gran conjunto pero solo unos pocos elementos (por ejemplo, 5 cada 10000 ), esto es relativamente lento, por lo que me gustaría optimizarlo de manera que no se tengan que barajar todos los elementos. Los valores deben ser únicos

Estoy buscando la alternativa más eficiente. Podemos suponer que $array no tiene duplicados y está 0 indexado.

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

Esto proporcionará exactamente 5 elementos sin duplicados y muy rápidamente. Las llaves serán preservadas.

Nota: Debería asegurarse de que $ array tiene 5 o más elementos o agregar algún tipo de control para evitar un ciclo infinito.

Esta función realiza una reproducción aleatoria solo en $n elementos donde $n es la cantidad de elementos aleatorios que desea seleccionar. También funcionará en matrices asociativas y matrices dispersas. $array es la matriz para trabajar y $n es la cantidad de elementos aleatorios para recuperar.

Si definimos $max_index como count($array) - 1 - $iteration .

Funciona al generar un número aleatorio entre 0 y $max_index . Escogiendo la clave en ese índice, y reemplazando su índice con el valor en $max_index para que nunca pueda ser recogido nuevamente, ya que $max_index será uno menos en la próxima iteración e inalcanzable.

En resumen, esta es la mezcla de Fisher-Yates de Richard Durstenfeld pero opera solo en $n elementos en lugar de toda la matriz.

 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; } 

Esto solo mostrará ventajas para n pequeña en comparación con una combinación aleatoria de matriz, pero podría

  1. Elija un índice aleatorio r n veces, cada vez disminuyendo el límite en 1
  2. Ajustar para los índices usados ​​previamente
  3. Tomar valor
  4. Almacenar índice usado

Pseudocódigo

 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 

El truco es usar una variación de shuffle o, en otras palabras, un shuffle parcial.

el rendimiento no es el único criterio, la eficiencia estadística, es decir, el muestreo imparcial es tan importante (como la solución shuffle original)

 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; } 

TENGA EN CUENTA que el algoritmo es estrictamente O(n) tanto en tiempo como en espacio , produce selecciones no sesgadas (es una mezcla imparcial parcial ) y produce una salida que es la matriz adecuada con claves consecutivas (sin necesidad de array_values adicionales, etc.)

Use el ejemplo:

 $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)); 

Para obtener más variaciones y extensiones de mezcla para PHP:

  1. PHP: mezcla solo parte de una matriz
  2. PHP mezclar con semilla
  3. ¿Cómo puedo tomar n elementos al azar de una matriz de Perl?

Podría generar n veces un número aleatorio con mt_rand() y luego llenar estos valores en una nueva matriz. Para ir contra el caso en el que se devuelve el mismo índice dos veces, usamos el índice real devuelto para completar el nuevo conjunto y comprobamos siempre si el índice existe en el nuevo conjunto, si es así lo usamos para recorrerlo siempre que obtengamos un índice duplicado Al final usamos array_values() para obtener una matriz 0 indexada.

 $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);