¿Es correcto usar el método JavaScript Array.sort () para barajar?

126

Estaba ayudando a alguien con su código JavaScript y me llamó la atención una sección que se veía así:

function randOrd(){
  return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);

Mi primer pensamiento fue: ¡ oye, esto no puede funcionar! Pero luego experimenté un poco y descubrí que, de hecho, al menos parece proporcionar resultados muy aleatorios.

Luego realicé una búsqueda en la web y casi en la parte superior encontré un artículo del que este código se copió con mayor certeza. Parecía un sitio y autor bastante respetable ...

Pero mi instinto me dice que esto debe estar mal. Especialmente porque el algoritmo de clasificación no está especificado por el estándar ECMA. Creo que diferentes algoritmos de clasificación darán como resultado diferentes mezclas no uniformes. Algunos algoritmos de clasificación probablemente incluso se repitan infinitamente ...

Pero, ¿qué piensa usted?

Y como otra pregunta ... ¿cómo iría ahora y mediría cuán aleatorios son los resultados de esta técnica de barajado?

Actualización: hice algunas mediciones y publiqué los resultados a continuación como una de las respuestas.

Rene Saarsoo
fuente
solo para notar que es inútil redondear el resultado solo el recuento de signos
bormat
2
" Descubrí que parece proporcionar resultados muy aleatorizados " . ¿ REALMENTE?
Bergi

Respuestas:

109

Nunca ha sido mi forma favorita de barajar, en parte porque es específica de la implementación como usted dice. En particular, me parece recordar que la clasificación estándar de la biblioteca de Java o .NET (no estoy seguro de cuál) a menudo puede detectar si terminas con una comparación inconsistente entre algunos elementos (por ejemplo, primero reclamas A < By B < C, pero luego C < A).

También termina como una combinación más compleja (en términos de tiempo de ejecución) de lo que realmente necesita.

Prefiero el algoritmo aleatorio que divide efectivamente la colección en "barajada" (al comienzo de la colección, inicialmente vacía) y "no barajada" (el resto de la colección). En cada paso del algoritmo, elija un elemento aleatorio sin mezclar (que podría ser el primero) y cámbielo por el primer elemento sin mezclar, luego trátelo como barajado (es decir, mueva mentalmente la partición para incluirlo).

Esto es O (n) y solo requiere llamadas n-1 al generador de números aleatorios, lo cual es bueno. También produce una mezcla aleatoria genuina: cualquier elemento tiene una probabilidad de 1 n de terminar en cada espacio, independientemente de su posición original (suponiendo un RNG razonable). La versión ordenada se aproxima a una distribución par (suponiendo que el generador de números aleatorios no elige el mismo valor dos veces, lo que es muy poco probable si devuelve dobles aleatorios), pero me resulta más fácil razonar sobre la versión aleatoria :)

Este enfoque se llama barajar de Fisher-Yates .

Considero que es una buena práctica codificar esta combinación aleatoria una vez y reutilizarla en cualquier lugar donde necesite mezclar elementos. Entonces no necesita preocuparse por las implementaciones de clasificación en términos de confiabilidad o complejidad. Son solo unas pocas líneas de código (¡que no intentaré en JavaScript!)

El artículo de Wikipedia sobre barajar (y en particular la sección de algoritmos de barajar) habla de ordenar una proyección aleatoria: vale la pena leer la sección sobre implementaciones pobres de barajar en general, para que sepa qué evitar.

Jon Skeet
fuente
55
Raymond Chen profundiza en la importancia de que las funciones de comparación de clasificación sigan las reglas: blogs.msdn.com/oldnewthing/archive/2009/05/08/9595334.aspx
Jason Kresowaty
1
Si mi razonamiento es correcto, ¡la versión ordenada no produce una mezcla 'genuina'!
Christoph
@Christoph: Pensando en ello, incluso Fisher-Yates solo dará una distribución "perfecta" si se garantiza que rand (x) está exactamente por encima de su rango. Dado que generalmente hay 2 ^ x posibles estados para el RNG para algunas x, no creo que sea exactamente incluso para rand (3).
Jon Skeet
@ Jon: pero Fisher-Yates creará 2^xestados para cada índice de matriz, es decir, habrá un total de 2 ^ (xn) estados, que debería ser bastante mayor que 2 ^ c - vea mi respuesta editada para más detalles
Christoph
@ Christoph: Puede que no me haya explicado bien. Supongamos que tiene solo 3 elementos. Eliges el primer elemento al azar, de todos los 3. Para obtener una distribución completamente uniforme , deberías poder elegir un número aleatorio en el rango [0,3) de manera totalmente uniforme, y si el PRNG tiene 2 ^ n posibles estados, no puede hacer eso: una o dos de las posibilidades tendrán una probabilidad ligeramente mayor de ocurrir.
Jon Skeet
118

Después de que Jon ya haya cubierto la teoría , aquí hay una implementación:

function shuffle(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
}

El algoritmo es O(n), mientras que la ordenación debería ser O(n log n). Dependiendo de la sobrecarga de ejecutar código JS en comparación con la sort()función nativa , esto podría conducir a una diferencia notable en el rendimiento que debería aumentar con los tamaños de matriz.


En los comentarios a la respuesta de bobobobo , dije que el algoritmo en cuestión podría no producir probabilidades distribuidas uniformemente (dependiendo de la implementación de sort()).

Mi argumento sigue estas líneas: un algoritmo de clasificación requiere un cierto número cde comparaciones, por ejemplo, c = n(n-1)/2para Bubblesort. Nuestra función de comparación aleatoria hace que el resultado de cada comparación sea igualmente probable, es decir, hay resultados 2^c igualmente probables . Ahora, cada resultado debe corresponder a una de las n!permutaciones de las entradas de la matriz, lo que hace imposible una distribución uniforme en el caso general. (Esto es una simplificación, ya que el número real de comparaciones necesarias depende de la matriz de entrada, pero la afirmación aún debería mantenerse).

Como señaló Jon, esto por sí solo no es razón para preferir Fisher-Yates en lugar de usarlo sort(), ya que el generador de números aleatorios también asignará un número finito de valores pseudoaleatorios a las n!permutaciones. Pero los resultados de Fisher-Yates aún deberían ser mejores:

Math.random()produce un número pseudoaleatorio en el rango [0;1[. Como JS usa valores de coma flotante de doble precisión, esto corresponde a los 2^xposibles valores donde 52 ≤ x ≤ 63(soy demasiado vago para encontrar el número real). Una distribución de probabilidad generada usando Math.random()dejará de comportarse bien si el número de eventos atómicos es del mismo orden de magnitud.

Cuando se utiliza Fisher-Yates, el parámetro relevante es el tamaño de la matriz, que nunca debería acercarse 2^52debido a limitaciones prácticas.

Al ordenar con una función de comparación aleatoria, la función básicamente solo se preocupa si el valor de retorno es positivo o negativo, por lo que esto nunca será un problema. Pero hay una similar: debido a que la función de comparación se comporta bien, los 2^cposibles resultados son, como se dijo, igualmente probables. Si es c ~ n log nasí , 2^c ~ n^(a·n)dónde a = const, lo que hace al menos posible que 2^csea ​​de la misma magnitud que (o incluso menor que) n!y, por lo tanto, conduzca a una distribución desigual, incluso si el algoritmo de clasificación se asigna en las permutaciones de manera uniforme. Si esto tiene algún impacto práctico está más allá de mí.

El verdadero problema es que no se garantiza que los algoritmos de clasificación se asignen uniformemente a las permutaciones. Es fácil ver que Mergesort hace lo que es simétrico, pero el razonamiento sobre algo como Bubblesort o, lo que es más importante, Quicksort o Heapsort, no lo es.


El resultado final: siempre que sort()use Mergesort, debe estar razonablemente seguro, excepto en los casos de esquina (al menos espero que 2^c ≤ n!sea ​​un caso de esquina), si no, todas las apuestas están canceladas.

Christoph
fuente
Gracias por la implementación. ¡Es increíblemente rápido! Especialmente comparado con esa basura lenta que escribí yo solo mientras tanto.
Rene Saarsoo
1
Si está utilizando la biblioteca underscore.js, aquí le mostramos
Steve
Muchas gracias por esto, la combinación de su respuesta y la de Johns me ayudó a solucionar un problema en el que yo y un colega pasamos casi 4 horas combinadas. Originalmente teníamos un método similar al OP, pero descubrimos que la aleatorización era muy escasa, por lo que tomamos su método y lo cambiamos ligeramente para que funcione con un poco de jquery para mezclar una lista de imágenes (para un control deslizante) para obtener algo Aleatorización impresionante.
Hola Mundo
16

Hice algunas mediciones de cuán aleatorios son los resultados de este tipo aleatorio ...

Mi técnica consistía en tomar una pequeña matriz [1,2,3,4] y crear todas (4! = 24) permutaciones de la misma. Luego aplicaría la función de barajar a la matriz una gran cantidad de veces y contaría cuántas veces se genera cada permutación. Un buen algoritmo aleatorio distribuiría los resultados de manera bastante uniforme en todas las permutaciones, mientras que uno malo no crearía ese resultado uniforme.

Usando el siguiente código probé en Firefox, Opera, Chrome, IE6 / 7/8.

Sorprendentemente para mí, la ordenación aleatoria y la combinación aleatoria real crearon distribuciones igualmente uniformes. Por lo tanto, parece que (como muchos han sugerido) los principales navegadores están utilizando el tipo de fusión. Esto, por supuesto, no significa que no puede haber un navegador por ahí, eso es diferente, pero diría que significa que este método de clasificación aleatoria es lo suficientemente confiable como para usarlo en la práctica.

EDITAR: Esta prueba realmente no midió correctamente la aleatoriedad o la falta de ella. Vea la otra respuesta que publiqué.

Pero en el lado del rendimiento, la función aleatoria dada por Cristoph fue un claro ganador. ¡Incluso para pequeñas matrices de cuatro elementos, la combinación aleatoria real se realizó aproximadamente el doble de rápido que la clasificación aleatoria!

// La función aleatoria publicada por Cristoph.
var shuffle = function (array) {
    var tmp, current, top = array.length;

    if (arriba) while (- arriba) {
        current = Math.floor (Math.random () * (top + 1));
        tmp = array [actual];
        matriz [actual] = matriz [arriba];
        matriz [arriba] = tmp;
    }

    matriz de retorno;
};

// la función de ordenación aleatoria
var rnd = function () {
  return Math.round (Math.random ()) - 0.5;
};
var randSort = function (A) {
  devuelve A.sort (rnd);
};

permutaciones var = función (A) {
  if (A.length == 1) {
    volver [A];
  }
  más {
    perms var = [];
    para (var i = 0; i <A.length; i ++) {
      var x = A. corte (i, i + 1);
      var xs = A.slice (0, i) .concat (A.slice (i + 1));
      var subperms = permutaciones (xs);
      for (var j = 0; j <subperms.length; j ++) {
        perms.push (x.concat (subperms [j]));
      }
    }
    permisos de devolución;
  }
};

prueba var = función (A, iteraciones, func) {
  // permutaciones de inicio
  estadísticas de var = {};
  perms var = permutaciones (A);
  para (var i en perms) {
    stats ["" + permisos [i]] = 0;
  }

  // baraja muchas veces y reúne estadísticas
  inicio var = nueva fecha ();
  para (var i = 0; i <iteraciones; i ++) {
    var barajado = func (A);
    stats ["" + barajado] ++;
  }
  var end = nueva Fecha ();

  // resultado del formato
  var arr = [];
  para (var i en las estadísticas) {
    arr.push (i + "" + stats [i]);
  }
  return arr.join ("\ n") + "\ n \ nTiempo tomado:" + ((fin - inicio) / 1000) + "segundos".
};

alert ("ordenación aleatoria:" + prueba ([1,2,3,4], 100000, randSort));
alert ("shuffle:" + test ([1,2,3,4], 100000, shuffle));
Rene Saarsoo
fuente
11

Curiosamente, Microsoft utilizó la misma técnica en su página de selección aleatoria del navegador.

Utilizaron una función de comparación ligeramente diferente:

function RandomSort(a,b) {
    return (0.5 - Math.random());
}

Me parece casi igual, pero resultó no ser tan aleatorio ...

Así que hice algunas pruebas nuevamente con la misma metodología utilizada en el artículo vinculado y, de hecho, resultó que el método de clasificación aleatoria produjo resultados defectuosos. Nuevo código de prueba aquí:

function shuffle(arr) {
  arr.sort(function(a,b) {
    return (0.5 - Math.random());
  });
}

function shuffle2(arr) {
  arr.sort(function(a,b) {
    return (Math.round(Math.random())-0.5);
  });
}

function shuffle3(array) {
  var tmp, current, top = array.length;

  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }

  return array;
}

var counts = [
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
];

var arr;
for (var i=0; i<100000; i++) {
  arr = [0,1,2,3,4];
  shuffle3(arr);
  arr.forEach(function(x, i){ counts[x][i]++;});
}

alert(counts.map(function(a){return a.join(", ");}).join("\n"));
Rene Saarsoo
fuente
No veo por qué tiene que ser 0.5 - Math.random (), ¿por qué no solo Math.random ()?
Alexander Mills
1
@AlexanderMills: sort()se supone que la función de comparación pasada devuelve un número mayor que, menor que o igual a cero dependiendo de la comparación de ay b. ( developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… )
LarsH
@LarsH sí, eso tiene sentido
Alexander Mills
9

He colocado una página de prueba simple en mi sitio web que muestra el sesgo de su navegador actual en comparación con otros navegadores populares que utilizan diferentes métodos para barajar. Muestra el sesgo terrible de solo usarMath.random()-0.5 , otra mezcla aleatoria que no está sesgada, y el método Fisher-Yates mencionado anteriormente.

¡Puede ver que en algunos navegadores hay una probabilidad de hasta un 50% de que ciertos elementos no cambien de lugar durante el 'shuffle'!

Nota: puede hacer que la implementación de Fisher-Yates shuffle por @Christoph sea un poco más rápida para Safari cambiando el código a:

function shuffle(array) {
  for (var tmp, cur, top=array.length; top--;){
    cur = (Math.random() * (top + 1)) << 0;
    tmp = array[cur]; array[cur] = array[top]; array[top] = tmp;
  }
  return array;
}

Resultados de la prueba: http://jsperf.com/optimized-fisher-yates

Phrogz
fuente
5

Creo que está bien para casos en los que no eres exigente con la distribución y quieres que el código fuente sea pequeño.

En JavaScript (donde la fuente se transmite constantemente), pequeño hace la diferencia en los costos de ancho de banda.

Nosredna
fuente
2
La cuestión es que casi siempre eres más exigente con la distribución de lo que crees que eres, y para el "código pequeño", siempre hay arr = arr.map(function(n){return [Math.random(),n]}).sort().map(function(n){return n[1]});, lo que tiene la ventaja de no ser demasiado largo y distribuirse correctamente. También hay variantes de Shuffle Knuth / FY muy comprimidas.
Daniel Martin
@DanielMartin Esa frase debería ser una respuesta. Además, para evitar errores de análisis, dos puntos y comas se deben agregar por lo que se ve así: arr = arr.map(function(n){return [Math.random(),n];}).sort().map(function(n){return n[1];});.
Giacomo1968
2

Es un truco, sin duda. En la práctica, no es probable un algoritmo de bucle infinito. Si está ordenando objetos, puede recorrer la matriz de coords y hacer algo como:

for (var i = 0; i < coords.length; i++)
    coords[i].sortValue = Math.random();

coords.sort(useSortValue)

function useSortValue(a, b)
{
  return a.sortValue - b.sortValue;
}

(y luego vuelva a recorrerlos para eliminar sortValue)

Sin embargo, sigue siendo un truco. Si quieres hacerlo bien, tienes que hacerlo de la manera difícil :)

Thorarin
fuente
2

Han pasado cuatro años, pero me gustaría señalar que el método de comparación aleatorio no se distribuirá correctamente, sin importar el algoritmo de clasificación que utilice.

Prueba:

  1. Para una serie de nelementos, hay exactamente n!permutaciones (es decir, posibles mezclas).
  2. Cada comparación durante una combinación aleatoria es una elección entre dos conjuntos de permutaciones. Para un comparador aleatorio, hay una probabilidad de 1/2 de elegir cada conjunto.
  3. Por lo tanto, para cada permutación p, la posibilidad de terminar con la permutación p es una fracción con denominador 2 ^ k (para algunos k), porque es una suma de tales fracciones (por ejemplo, 1/8 + 1/16 = 3/16 )
  4. Para n = 3, hay seis permutaciones igualmente probables. La posibilidad de cada permutación, entonces, es 1/6. 1/6 no puede expresarse como una fracción con una potencia de 2 como denominador.
  5. Por lo tanto, el tipo de cambio de moneda nunca resultará en una distribución justa de barajas.

Los únicos tamaños que posiblemente podrían distribuirse correctamente son n = 0,1,2.


Como ejercicio, intente dibujar el árbol de decisión de diferentes algoritmos de clasificación para n = 3.


Hay una brecha en la prueba: si un algoritmo de clasificación depende de la consistencia del comparador y tiene un tiempo de ejecución ilimitado con un comparador inconsistente, puede tener una suma infinita de probabilidades, que puede sumar 1/6 incluso si cada denominador en la suma es una potencia de 2. Intenta encontrar uno.

Además, si un comparador tiene una probabilidad fija de dar cualquiera de las respuestas (por ejemplo (Math.random() < P)*2 - 1, para constante P), la prueba anterior se cumple. Si el comparador cambia sus probabilidades en función de las respuestas anteriores, es posible generar resultados justos. Encontrar un comparador para un algoritmo de clasificación dado podría ser un trabajo de investigación.

leewz
fuente
1

Si está usando D3, hay una función aleatoria incorporada (usando Fisher-Yates):

var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche'];
d3.shuffle(days);

Y aquí está Mike entrando en detalles al respecto:

http://bost.ocks.org/mike/shuffle/

Renaud
fuente
0

Aquí hay un enfoque que usa una sola matriz:

La lógica básica es:

  • Comenzando con una matriz de n elementos
  • Elimine un elemento aleatorio de la matriz y empújelo hacia la matriz.
  • Elimine un elemento aleatorio de los primeros n - 1 elementos del conjunto y empújelo hacia el conjunto
  • Elimine un elemento aleatorio de los primeros n - 2 elementos del conjunto y empújelo hacia el conjunto
  • ...
  • Retire el primer elemento de la matriz y empújelo sobre la matriz.
  • Código:

    for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);
    ic3b3rg
    fuente
    Su implementación tiene un alto riesgo de dejar una cantidad significativa de elementos intactos. Simplemente se desplazarán en toda la matriz por la cantidad de elementos inferiores que se hayan empujado hacia arriba. Hay un patrón dibujado en esa combinación que lo hace poco confiable.
    Kir Kanos
    @ KirKanos, no estoy seguro de entender tu comentario. La solución que propongo es O (n). Definitivamente va a "tocar" cada elemento. Aquí hay un violín para demostrar.
    ic3b3rg
    0

    ¿Se puede utilizar la Array.sort()función para barajar una matriz? Sí.

    ¿Son los resultados lo suficientemente aleatorios? No.

    Considere el siguiente fragmento de código:

    var array = ["a", "b", "c", "d", "e"];
    var stats = {};
    array.forEach(function(v) {
      stats[v] = Array(array.length).fill(0);
    });
    //stats = {
    //    a: [0, 0, 0, ...]
    //    b: [0, 0, 0, ...]
    //    c: [0, 0, 0, ...]
    //    ...
    //    ...
    //}
    var i, clone;
    for (i = 0; i < 100; i++) {
      clone = array.slice(0);
      clone.sort(function() {
        return Math.random() - 0.5;
      });
      clone.forEach(function(v, i) {
        stats[v][i]++;
      });
    }
    
    Object.keys(stats).forEach(function(v, i) {
      console.log(v + ": [" + stats[v].join(", ") + "]");
    })

    Salida de muestra:

    a [29, 38, 20,  6,  7]
    b [29, 33, 22, 11,  5]
    c [17, 14, 32, 17, 20]
    d [16,  9, 17, 35, 23]
    e [ 9,  6,  9, 31, 45]

    Idealmente, los recuentos deben estar distribuidos de manera uniforme (para el ejemplo anterior, todos los recuentos deben estar alrededor de 20). Pero no lo son. Aparentemente, la distribución depende de qué algoritmo de ordenación implementa el navegador y cómo itera los elementos de la matriz para la ordenación.

    Se proporciona más información en este artículo:
    Array.sort () no debe usarse para barajar una matriz

    Salman A
    fuente
    -3

    No tiene nada de malo.

    La función que pasa a .sort () generalmente se parece a

    función sortingFunc (primero, segundo)
    {
      // ejemplo:
      volver primero - segundo;
    }
    

    Su trabajo en sortingFunc es devolver:

    • un número negativo si el primero va antes que el segundo
    • un número positivo si el primero debe ir después del segundo
    • y 0 si son completamente iguales

    La función de clasificación anterior pone las cosas en orden.

    Si devuelve aleatoriamente + y + como lo que tiene, obtiene un pedido aleatorio.

    Como en MySQL:

    SELECCIONAR * de la tabla ORDER BY rand ()
    
    bobobobo
    fuente
    55
    no es algo malo en este enfoque: en función del algoritmo de ordenación en uso por la aplicación JS, las probabilidades no se distribuyen por igual!
    Christoph
    ¿Es eso algo de lo que prácticamente nos preocupamos?
    bobobobo
    44
    @bobobobo: dependiendo de la aplicación, sí, a veces lo hacemos; También, una de funcionar correctamente shuffle()sólo tiene que ser escrita una vez, así que no es realmente un problema: sólo hay que poner el fragmento de código en su bóveda y desvela que siempre que lo necesite
    Christoph