Elija eficientemente n elementos aleatorios de la matriz PHP(sin barajar)

arrays performance

Question

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

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

Dada una gran matriz, pero solo unos pocos elementos (por ejemplo, 5 cada 10000 ), esto es relativamente lento, por lo que me gustaría optimizarlo de modo 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 tiene un índice 0 .

Answer 1

El truco consiste en utilizar 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 lo es 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, 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;
}

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

Use 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 más variaciones y extensiones de barajar para PHP:

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

Answer 2

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

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

Funciona generando un número aleatorio entre 0 y $max_index . Elegir la clave en ese índice y reemplazar su índice con el valor en $max_index para que nunca se pueda volver a $max_index , ya que $max_index será uno menos en la próxima iteración e inalcanzable.

En resumen, este es el shuffle de Fisher-Yates de Richard Durstenfeld, pero opera solo con elementos $n 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;
}

Answer 3

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

1. Elija un índice aleatorio r n veces, cada vez disminuyendo el límite en 1
2. Ajustar para í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

Answer 4

Puede generar n veces un número aleatorio con mt_rand() y luego llenar estos valores en una nueva matriz. Para ir en contra del caso en el que se devuelve el mismo índice dos veces, usamos el índice devuelto real para llenar la nueva matriz y verificamos siempre si el índice existe en la nueva matriz, si es así, usamos while para recorrerlo siempre que obtengamos un índice duplicado Al final usamos array_values() para obtener una matriz indexada en 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);

Answer 5

$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: Tendrás que asegurarte de que $ array tenga 5 o más elementos o agregar algún tipo de verificación para evitar un bucle sin fin.