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

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.

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.

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.

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

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

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

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.

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 :)

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.

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/

Aquí hay un enfoque que usa una sola matriz:

La lógica básica es:

Código:

for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[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

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 ()