É correto usar o método JavaScript Array.sort () para embaralhar?

126

Eu estava ajudando alguém com seu código JavaScript e meus olhos foram atraídos por uma seção que se parecia com isso:

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

Meu primeiro pensamento foi: ei, isso não pode funcionar! Mas então eu fiz algumas experiências e descobri que, de fato, pelo menos parece fornecer resultados bem aleatórios.

Depois, fiz uma pesquisa na web e, quase no topo, encontrei um artigo do qual esse código era mais copiado de maneira mais precisa. Parecia um site bastante respeitável e autor ...

Mas meu pressentimento me diz que isso deve estar errado. Especialmente porque o algoritmo de classificação não é especificado pelo padrão ECMA. Penso que diferentes algoritmos de classificação resultarão em diferentes embaralhamento não uniforme. Alguns algoritmos de classificação podem provavelmente até repetir infinitamente ...

Mas o que você acha?

E como outra pergunta ... como eu iria agora medir o quão aleatórios são os resultados dessa técnica de embaralhamento?

atualização: fiz algumas medições e publiquei os resultados abaixo como uma das respostas.

Rene Saarsoo
fonte
apenas para perceber que é inútil para arredondar o resultado somente a contagem de sinal
bormat
2
" Descobri que parece fornecer resultados bem aleatórios. " - REALMENTE ???
Bergi 21/10

Respostas:

109

Nunca foi minha maneira favorita de embaralhar, em parte porque é específica da implementação, como você diz. Em particular, pareço lembrar que a biblioteca padrão de classificação de Java ou .NET (não tenho certeza qual) pode frequentemente detectar se você acaba com uma comparação inconsistente entre alguns elementos (por exemplo, você primeiro declara A < Be B < C, mas depois C < A).

Também acaba como um shuffle mais complexo (em termos de tempo de execução) do que você realmente precisa.

Eu prefiro o algoritmo de reprodução aleatória que efetivamente particiona a coleção em "aleatório" (no início da coleção, inicialmente vazio) e "não embaralhado" (o restante da coleção). Em cada etapa do algoritmo, escolha um elemento aleatório não embaralhado (que poderia ser o primeiro) e troque-o pelo primeiro elemento não embaralhado - depois trate-o como embaralhado (ou seja, mova mentalmente a partição para incluí-lo).

Este é O (n) e requer apenas chamadas n-1 para o gerador de números aleatórios, o que é bom. Também produz um embaralhamento genuíno - qualquer elemento tem 1 / n de chance de terminar em cada espaço, independentemente da sua posição original (assumindo um RNG razoável). A versão classificada aproxima- se de uma distribuição uniforme (supondo que o gerador de números aleatórios não escolha o mesmo valor duas vezes, o que é altamente improvável se estiver retornando dobras aleatórias), mas acho mais fácil argumentar sobre a versão aleatória :)

Essa abordagem é chamada de embaralhamento de Fisher-Yates .

Considero uma boa prática codificar esse shuffle uma vez e reutilizá-lo em todos os lugares que você precisar para embaralhar itens. Então você não precisa se preocupar com implementações de classificação em termos de confiabilidade ou complexidade. São apenas algumas linhas de código (que não tentarei em JavaScript!)

O artigo da Wikipedia sobre embaralhamento (e em particular a seção de algoritmos de embaralhamento) fala sobre a classificação de uma projeção aleatória - vale a pena ler a seção sobre implementações ruins de embaralhamento em geral, para que você saiba o que evitar.

Jon Skeet
fonte
5
Raymond Chen vai em profundidade sobre a importância de que as funções de comparação tipo seguir as regras: blogs.msdn.com/oldnewthing/archive/2009/05/08/9595334.aspx
Jason Kresowaty
1
se meu raciocínio estiver correto, a versão classificada não produzirá uma reprodução aleatória 'genuína'!
7409 Christoph
@Christoph: Pensando nisso, até Fisher-Yates só dará uma distribuição "perfeita" se rand (x) estiver garantido exatamente igual ao seu alcance. Dado que geralmente existem 2 ^ x estados possíveis para o RNG para alguns x, não acho que seja exatamente igual para rand (3).
9139 Jon Skeet
@ Jon: mas Fisher-Yates criará 2^xestados para cada índice de matriz, ou seja, haverá 2 ^ (xn) de estados totais, que devem ser um pouco maiores que 2 ^ c - veja minha resposta editada para mais detalhes
Christoph
@Christoph: Talvez eu não tenha me explicado direito. Suponha que você tenha apenas 3 elementos. Você escolhe o primeiro elemento aleatoriamente, dentre todos os 3. Para obter uma distribuição completamente uniforme , você deve poder escolher um número aleatório no intervalo [0,3) de maneira totalmente uniforme - e se o PRNG tiver 2 ^ n possíveis estados, você não pode fazer isso - uma ou duas das possibilidades terão uma probabilidade um pouco maior de ocorrer.
Jon Skeet
118

Depois que Jon já cobriu a teoria , aqui está uma implementação:

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

O algoritmo é O(n), enquanto a classificação deve ser O(n log n). Dependendo da sobrecarga de execução do código JS em comparação com a sort()função nativa , isso pode levar a uma diferença notável no desempenho, que deve aumentar com o tamanho da matriz.


Nos comentários à resposta de bobobobo , afirmei que o algoritmo em questão pode não produzir probabilidades distribuídas uniformemente (dependendo da implementação de sort()).

Meu argumento segue estas linhas: Um algoritmo de classificação requer um certo número cde comparações, por exemplo, c = n(n-1)/2para Bubblesort. Nossa função de comparação aleatória torna o resultado de cada comparação igualmente provável, ou seja, há resultados 2^c igualmente prováveis . Agora, cada resultado deve corresponder a uma das n!permutações das entradas da matriz, o que impossibilita uma distribuição uniforme no caso geral. (Isso é uma simplificação, pois o número real de comparações necessárias depende da matriz de entrada, mas a asserção ainda deve ser mantida.)

Como Jon apontou, isso por si só não é motivo para preferir o uso de Fisher-Yates sort(), pois o gerador de números aleatórios também mapeará um número finito de valores pseudo-aleatórios para as n!permutações. Mas os resultados de Fisher-Yates ainda devem ser melhores:

Math.random()produz um número pseudo-aleatório no intervalo [0;1[. Como o JS usa valores de ponto flutuante de precisão dupla, isso corresponde aos 2^xvalores possíveis em que 52 ≤ x ≤ 63(estou com preguiça de encontrar o número real). Uma distribuição de probabilidade gerada usando Math.random()parará de se comportar bem se o número de eventos atômicos for da mesma ordem de magnitude.

Ao usar Fisher-Yates, o parâmetro relevante é o tamanho da matriz, que nunca deve ser abordada 2^52devido a limitações práticas.

Ao classificar com uma função de comparação aleatória, a função basicamente se importa apenas se o valor de retorno for positivo ou negativo, portanto isso nunca será um problema. Mas existe uma similar: como a função de comparação é bem comportada, os 2^cpossíveis resultados são, como afirmado, igualmente prováveis. Se c ~ n log nentão , 2^c ~ n^(a·n)onde a = const, o que torna pelo menos possível que 2^cseja da mesma magnitude que (ou até menor que) n!e, assim, leve a uma distribuição desigual, mesmo que o algoritmo de classificação seja mapeado uniformemente nas permutações. Se isso tem algum impacto prático está além de mim.

O verdadeiro problema é que não é garantido que os algoritmos de classificação sejam mapeados uniformemente nas permutações. É fácil ver que o Mergesort faz o que é simétrico, mas raciocinar sobre algo como Bubblesort ou, mais importante, Quicksort ou Heapsort, não é.


Conclusão: Enquanto sort()usar o Mergesort, você deverá estar razoavelmente seguro, exceto nos casos de canto (pelo menos, espero que 2^c ≤ n!seja um caso de canto), se não, todas as apostas serão desativadas.

Christoph
fonte
Obrigado pela implementação. É incrivelmente rápido! Especialmente em comparação com aquela porcaria lenta que escrevi sozinha enquanto isso.
Rene Saarsoo
1
Se você estiver usando a biblioteca underscore.js, aqui está como estendê-lo com o anterior método aleatório Fisher-Yates: github.com/ryantenney/underscore/commit/...
Steve
Muito obrigado por isso, a combinação da sua e da resposta de Johns me ajudou a resolver um problema no qual eu e um colega passamos quase 4 horas juntos! Originalmente, tínhamos um método semelhante ao OP, mas descobrimos que a randomização era muito esquisita. Por isso, pegamos o método e o modificamos um pouco para trabalhar com um pouco de jquery para criar uma lista de imagens (para um controle deslizante) para obter algumas randomização incrível.
Olá Mundo
16

Fiz algumas medições de quão aleatórios são os resultados desse tipo aleatório ...

Minha técnica era pegar uma pequena matriz [1,2,3,4] e criar todas (4! = 24) permutações dela. Então eu aplicaria a função de reprodução aleatória à matriz um grande número de vezes e contaria quantas vezes cada permutação é gerada. Um bom algoritmo de embaralhamento distribuiria os resultados de maneira uniforme em todas as permutações, enquanto um ruim não criaria esse resultado uniforme.

Usando o código abaixo, testei no Firefox, Opera, Chrome, IE6 / 7/8.

Surpreendentemente para mim, o tipo aleatório e o embaralhamento real criaram distribuições igualmente uniformes. Portanto, parece que (como muitos sugeriram) os principais navegadores estão usando a classificação por mesclagem. É claro que isso não significa que não pode haver um navegador por aí, isso é diferente, mas eu diria que significa que esse método de classificação aleatória é confiável o suficiente para ser usado na prática.

EDIT: Este teste realmente não mediu corretamente a aleatoriedade ou a falta dela. Veja a outra resposta que eu postei.

Mas no lado da performance, a função shuffle dada por Cristoph foi uma clara vencedora. Mesmo para pequenas matrizes de quatro elementos, o embaralhamento real era duas vezes mais rápido que o aleatório!

// A função shuffle postada por Cristoph.
var shuffle = função (matriz) {
    var tmp, atual, top = array.length;

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

    matriz de retorno;
};

// a função de classificação aleatória
var rnd = function () {
  retornar Math.round (Math.random ()) - 0,5;
};
var randSort = função (A) {
  retornar A.sort (rnd);
};

perm permations var = função (A) {
  if (A.length == 1) {
    retorno [A];
  }
  outro {
    var perms = [];
    for (var i = 0; i <comprimento A.; i ++) {
      var x = A. fatia (i, i + 1);
      var xs = A. slice (0, i) .concat (A. slice (i + 1));
      subperms var = permutações (xs);
      for (var j = 0; j <subperms.length; j ++) {
        perms.push (x.concat (subperms [j]));
      }
    }
    permanentes de retorno;
  }
};

var test = function (A, iterações, func) {
  // permutações init
  var stats = {};
  var perms = permutações (A);
  para (var i em permissões) {
    estatísticas ["" + permissões [i]] = 0;
  }

  // embaralhe várias vezes e colete estatísticas
  var start = new Date ();
  for (var i = 0; i <iterações; i ++) {
    var embaralhado = func (A);
    estatísticas ["" + embaralhado] ++;
  }
  var end = nova data ();

  // resultado do formato
  var arr = [];
  para (var i nas estatísticas) {
    arr.push (i + "" + estatísticas [i]);
  }
  retornar arr.join ("\ n") + "\ n \ nTempo gasto:" + ((fim de início) / 1000) + "segundos.";
};

alerta ("classificação aleatória:" + teste ([1,2,3,4], 100000, randSort));
alerta ("shuffle:" + teste ([1,2,3,4], 100000, shuffle));
Rene Saarsoo
fonte
11

Curiosamente, a Microsoft usou a mesma técnica em sua página de seleção aleatória do navegador.

Eles usaram uma função de comparação ligeiramente diferente:

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

Parece quase o mesmo para mim, mas acabou não sendo tão aleatório ...

Então, eu fiz alguns testes novamente com a mesma metodologia usada no artigo vinculado e, de fato - resultou que o método de classificação aleatória produziu resultados defeituosos. Novo código de teste aqui:

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
fonte
Não vejo por que tem que ser 0,5 - Math.random (), por que não apenas Math.random ()?
Alexander Mills
1
@AlexanderMills: A função comparadora passada para sort()deve retornar um número maior que, menor que ou igual a zero, dependendo da comparação de ae b. ( developer.mozilla.org/pt-BR/docs/Web/JavaScript/Reference/… )
LarsH
@LarsH sim que faz sentido
Alexander Mills
9

Coloquei uma página de teste simples no meu site, mostrando o viés do seu navegador atual em relação a outros navegadores populares, usando métodos diferentes para embaralhar. Ele mostra o terrível viés de apenas usar Math.random()-0.5, outro shuffle 'aleatório' que não é tendencioso e o método de Fisher-Yates mencionado acima.

Você pode ver que em alguns navegadores há uma chance de 50% de que certos elementos não mudem de lugar durante o 'shuffle'!

Nota: você pode tornar a implementação do shuffle Fisher-Yates por @Christoph um pouco mais rápida para o Safari alterando o código para:

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 do teste: http://jsperf.com/optimized-fisher-yates

Phrogz
fonte
5

Eu acho que é bom para casos em que você não é exigente quanto à distribuição e deseja que o código-fonte seja pequeno.

Em JavaScript (onde a fonte é transmitida constantemente), pequeno faz a diferença nos custos de largura de banda.

Nosredna
fonte
2
O fato é que você quase sempre é mais exigente quanto à distribuição do que pensa e, para o "código pequeno", sempre existe arr = arr.map(function(n){return [Math.random(),n]}).sort().map(function(n){return n[1]});, o que tem a vantagem de não demorar muito demais e ser realmente distribuído adequadamente. Também existem variantes de shuffle Knuth / FY muito compactadas.
Daniel Martin
@DanielMartin Essa frase deve ser uma resposta. Além disso, para evitar erros de análise, dois pontos e vírgula precisam ser adicionados para que ele se parece com isso: arr = arr.map(function(n){return [Math.random(),n];}).sort().map(function(n){return n[1];});.
Giacomo1968
2

É um truque, certamente. Na prática, um algoritmo de loop infinito não é provável. Se você estiver classificando objetos, poderá percorrer a matriz de cordas e fazer 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;
}

(e depois faça um loop neles novamente para remover o sortValue)

Ainda é um truque. Se você quiser fazê-lo bem, terá que fazê-lo da maneira mais difícil :)

Thorarin
fonte
2

Faz quatro anos, mas eu gostaria de salientar que o método comparador aleatório não será distribuído corretamente, independentemente do algoritmo de classificação que você usar.

Prova:

  1. Para uma matriz de nelementos, existem exatamente n!permutações (ou seja, possíveis embaralhamento).
  2. Toda comparação durante um shuffle é uma escolha entre dois conjuntos de permutações. Para um comparador aleatório, existe uma chance de 1/2 de escolher cada conjunto.
  3. Assim, para cada permutação p, a chance de terminar com permutação p é uma fração com denominador 2 ^ k (para alguns k), porque é uma soma dessas frações (por exemplo, 1/8 + 1/16 = 3/16 )
  4. Para n = 3, existem seis permutações igualmente prováveis. A chance de cada permutação, então, é 1/6. 1/6 não pode ser expresso como uma fração com uma potência de 2 como denominador.
  5. Portanto, o tipo de troca de moeda nunca resultará em uma distribuição justa de shuffles.

Os únicos tamanhos que poderiam ser corretamente distribuídos são n = 0,1,2.


Como exercício, tente desenhar a árvore de decisão de diferentes algoritmos de classificação para n = 3.


Há uma lacuna na prova: se um algoritmo de classificação depender da consistência do comparador e tiver um tempo de execução ilimitado com um comparador inconsistente, ele poderá ter uma soma infinita de probabilidades, que poderá adicionar até 1/6, mesmo que todo denominador na soma é uma potência de 2. Tente encontrar um.

Além disso, se um comparador tiver uma chance fixa de fornecer uma das respostas (por exemplo (Math.random() < P)*2 - 1, para constante P), a prova acima será válida. Se o comparador alterar suas chances com base nas respostas anteriores, talvez seja possível gerar resultados justos. Encontrar um comparador para um dado algoritmo de classificação pode ser um trabalho de pesquisa.

leewz
fonte
1

Se você estiver usando o D3, há uma função de reprodução aleatória incorporada (usando Fisher-Yates):

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

E aqui está Mike entrando em detalhes sobre isso:

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

Renaud
fonte
0

Aqui está uma abordagem que usa uma única matriz:

A lógica básica é:

  • Começando com uma matriz de n elementos
  • Remova um elemento aleatório da matriz e empurre-o para dentro da matriz
  • Remova um elemento aleatório dos primeiros n - 1 elementos da matriz e empurre-o para dentro da matriz
  • Remova um elemento aleatório dos primeiros n - 2 elementos da matriz e empurre-o para dentro da matriz
  • ...
  • Remova o primeiro elemento da matriz e empurre-o para dentro da matriz
  • Código:

    for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);
    ic3b3rg
    fonte
    Sua implementação tem um alto risco de deixar um número significativo de elementos intocados. Eles serão apenas deslocados em toda a matriz pela quantidade de elementos inferiores que foram empurrados para cima. Há um padrão desenhado nesse embaralhamento que o torna não confiável.
    Kir Kanos
    @KirKanos, não sei se entendi seu comentário. A solução que proponho é O (n). Definitivamente, vai "tocar" todos os elementos. Aqui está um violino para demonstrar.
    ic3b3rg 31/01
    0

    Você pode usar a Array.sort()função para embaralhar uma matriz - Sim.

    Os resultados são aleatórios o suficiente - Não.

    Considere o seguinte snippet 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(", ") + "]");
    })

    Saída de amostra:

    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, as contagens devem ser distribuídas uniformemente (para o exemplo acima, todas as contagens devem estar em torno de 20). Mas eles não são. Aparentemente, a distribuição depende de qual algoritmo de classificação é implementado pelo navegador e de como itera os itens da matriz para classificação.

    Mais informações são fornecidas neste artigo:
    Array.sort () não deve ser usado para embaralhar uma matriz

    Salman A
    fonte
    -3

    Não há nada de errado com isso.

    A função que você passa para .sort () geralmente se parece com

    função sortingFunc (primeiro, segundo)
    {
      // exemplo:
      retornar primeiro - segundo;
    }
    

    Seu trabalho no sortingFunc é retornar:

    • um número negativo se o primeiro for antes do segundo
    • um número positivo se o primeiro for depois do segundo
    • e 0 se forem completamente iguais

    A função de classificação acima coloca as coisas em ordem.

    Se você retornar + e + aleatoriamente como você tem, receberá uma ordem aleatória.

    Como no MySQL:

    SELECT * da tabela ORDER BY rand ()
    
    bobobobo
    fonte
    5
    é algo de errado com essa abordagem: dependendo do algoritmo de classificação em uso pela implementação JS, as probabilidades não serão igualmente distribuídos!
    7409 Christoph
    Isso é algo com o qual praticamente nos preocupamos?
    7119 bobobobo
    4
    @obobobo: dependendo da aplicação, sim, às vezes fazemos; Além disso, um corretamente trabalhando shuffle()só tem de ser escrito uma vez, por isso não é realmente um problema: basta colocar o trecho em seu cofre código e desenterrá-la sempre que precisar
    Christoph