Está usando Random e OrderBy um bom algoritmo de shuffle?

Eu li um artigo sobre vários algoritmos de shuffle no Coding Horror . Eu vi que em algum lugar as pessoas fizeram isso para embaralhar uma lista:

var r = new Random(); var shuffled = ordered.OrderBy(x => r.Next()); 

Este é um bom algoritmo random? Como isso funciona exatamente? É uma maneira aceitável de fazer isso?

Não é uma maneira de embaralhar que eu gosto, principalmente com base no fato de que é O (n log n) sem um bom motivo quando é fácil implementar um O (n) shuffle. O código na pergunta “funciona” basicamente dando um número random (esperançosamente único!) Para cada elemento, depois ordenando os elementos de acordo com esse número.

Eu prefiro a variante de Durstenfield do shuffle de Fisher-Yates que troca elementos.

A implementação de um método de extensão de Shuffle simples consistiria basicamente em chamar ToList ou ToArray na input, usando uma implementação existente de Fisher-Yates. (Passe no Random como um parâmetro para tornar a vida geralmente mais agradável.) Há muitas implementações por aí … Eu provavelmente tenho uma em uma resposta em algum lugar.

A coisa boa sobre tal método de extensão é que então seria muito claro para o leitor o que você está realmente tentando fazer.

EDIT: Aqui está uma implementação simples (sem verificação de erros!):

 public static IEnumerable Shuffle(this IEnumerable source, Random rng) { T[] elements = source.ToArray(); // Note i > 0 to avoid final pointless iteration for (int i = elements.Length-1; i > 0; i--) { // Swap element "i" with a random earlier element it (or itself) int swapIndex = rng.Next(i + 1); T tmp = elements[i]; elements[i] = elements[swapIndex]; elements[swapIndex] = tmp; } // Lazily yield (avoiding aliasing issues etc) foreach (T element in elements) { yield return element; } } 

EDIT: comentários sobre o desempenho abaixo me lembrou que podemos realmente retornar os elementos à medida que os embaralharmos:

 public static IEnumerable Shuffle(this IEnumerable source, Random rng) {  T[] elements = source.ToArray();  for (int i = elements.Length - 1; i >= 0; i--)  {    // Swap element "i" with a random earlier element it (or itself) // ... except we don't really need to swap it fully, as we can // return it immediately, and afterwards it's irrelevant.    int swapIndex = rng.Next(i + 1); yield return elements[swapIndex];    elements[swapIndex] = elements[i];  } } 

Isso agora só fará o trabalho que for necessário.

Note que em ambos os casos, você precisa ter cuidado com a instância do Random você usa como:

  • Criar duas instâncias de Random ao mesmo tempo produzirá a mesma seqüência de números randoms (quando usados ​​da mesma maneira)
  • Random não é thread-safe.

Eu tenho um artigo sobre Random que entra em mais detalhes sobre essas questões e fornece soluções.

Isto é baseado na resposta de Jon Skeet.

Nessa resposta, a matriz é embaralhada e retornada usando o yield . O resultado líquido é que a matriz é mantida na memory durante a duração de foreach, assim como os objects necessários para a iteração, e ainda assim o custo é todo no início – o rendimento é basicamente um loop vazio.

Este algoritmo é muito usado em jogos, onde os três primeiros itens são escolhidos, e os outros só serão necessários mais tarde. Minha sugestão é yield os números assim que eles forem trocados. Isso reduzirá o custo inicial, mantendo o custo da iteração em O (1) (basicamente 5 operações por iteração). O custo total permaneceria o mesmo, mas o embaralhamento em si seria mais rápido. Nos casos em que isso é chamado de collection.Shuffle().ToArray() , teoricamente, não fará diferença, mas nos casos de uso acima mencionados, ele acelerará o start-up. Além disso, isso tornaria o algoritmo útil para casos em que você precisa apenas de alguns itens exclusivos. Por exemplo, se você precisar retirar três cartas de um baralho de 52, pode chamar o deck.Shuffle().Take(3) e somente três swaps ocorrerão (embora a matriz inteira tenha que ser copiada primeiro).

 public static IEnumerable Shuffle(this IEnumerable source, Random rng) { T[] elements = source.ToArray(); // Note i > 0 to avoid final pointless iteration for (int i = elements.Length - 1; i > 0; i--) { // Swap element "i" with a random earlier element it (or itself) int swapIndex = rng.Next(i + 1); yield return elements[swapIndex]; elements[swapIndex] = elements[i]; // we don't actually perform the swap, we can forget about the // swapped element because we already returned it. } // there is one item remaining that was not returned - we return it now yield return elements[0]; } 

A partir desta citação de Skeet:

Não é uma maneira de embaralhar que eu gosto, principalmente com base no fato de que é O (n log n) sem um bom motivo quando é fácil implementar um O (n) shuffle. O código na pergunta “funciona” basicamente dando um número random ( esperançosamente único! ) Para cada elemento, depois ordenando os elementos de acordo com esse número.

Eu vou explicar um pouco o motivo do esperançosamente único!

Agora, a partir do Enumerable.OrderBy :

Este método realiza uma sorting estável; isto é, se as chaves de dois elementos são iguais, a ordem dos elementos é preservada

Isto é muito importante! O que acontece se dois elementos “receberem” o mesmo número random? Acontece que eles permanecem na mesma ordem em que estão no array. Agora, qual é a possibilidade disso acontecer? É difícil calcular exatamente, mas há o problema do aniversário que é exatamente esse problema.

Agora é real? É verdade?

Como sempre, quando em dúvida, escreva algumas linhas de programa: http://pastebin.com/5CDnUxPG

Este pequeno bloco de código embaralha uma matriz de 3 elementos um certo número de vezes usando o algoritmo de Fisher-Yates feito para trás, o algoritmo de Fisher-Yates feito para frente (na página wiki há dois algoritmos de pseudocódigo … Eles produzem equivalentes resultados, mas um é feito do primeiro ao último elemento, enquanto o outro é feito do último ao primeiro elemento), o algoritmo errado ingênuo de http://blog.codinghorror.com/the-danger-of-naivete/ e usando o .OrderBy(x => r.Next()) e o .OrderBy(x => r.Next(someValue)) .

Agora, Random.Next is

Um inteiro assinado de 32 bits que é maior que ou igual a 0 e menor que MaxValue.

então é equivalente a

 OrderBy(x => r.Next(int.MaxValue)) 

Para testar se esse problema existe, podemos ampliar o array (algo muito lento) ou simplesmente reduzir o valor máximo do gerador de números randoms ( int.MaxValue não é um número “especial” … É simplesmente um número muito grande ). No final, se o algoritmo não for influenciado pela estabilidade do OrderBy , qualquer intervalo de valores deverá dar o mesmo resultado.

O programa então testa alguns valores, no intervalo 1 … 4096. Olhando para o resultado, fica claro que, para valores baixos (<128), o algoritmo é muito tendencioso (4-8%). Com 3 valores, você precisa de pelo menos r.Next(1024) . Se você tornar o array maior (4 ou 5), então mesmo r.Next(1024) não é suficiente. Eu não sou especialista em shuffling e em matemática, mas eu acho que para cada bit extra de comprimento do array, você precisa de 2 bits extras de valor máximo (porque o paradoxo de aniversário está conectado ao sqrt (numvalues)), então que se o valor máximo for 2 ^ 31, eu direi que você deve ser capaz de ordenar matrizes de até 2 ^ 12/2 ^ 13 bits (4096-8192 elementos)

É provavelmente ok para a maioria dos propósitos, e quase sempre gera uma distribuição verdadeiramente aleatória (exceto quando Random.Next () produz dois inteiros randoms idênticos).

Ele funciona atribuindo a cada elemento da série um inteiro random e, em seguida, ordenando a seqüência por esses números inteiros.

É totalmente aceitável para 99,9% dos aplicativos (a menos que você realmente precise lidar com o caso de borda acima). Além disso, a objeção do skeet ao seu tempo de execução é válida, portanto, se você estiver embaralhando uma lista longa, talvez não queira usá-la.

Parece um bom algoritmo de embaralhamento, se você não está muito preocupado com o desempenho. O único problema que eu diria é que seu comportamento não é controlável, então você pode ter dificuldade em testá-lo.

Uma opção possível é ter uma semente a ser passada como um parâmetro para o gerador de números randoms (ou o gerador random como um parâmetro), para que você possa ter mais controle e testá-lo mais facilmente.

Isso surgiu muitas vezes antes. Procure por Fisher-Yates no StackOverflow.

Aqui está uma amostra de código C # que escrevi para esse algoritmo. Você pode parametrizá-lo em outro tipo, se preferir.

 static public class FisherYates { // Based on Java code from wikipedia: // http://en.wikipedia.org/wiki/Fisher-Yates_shuffle static public void Shuffle(int[] deck) { Random r = new Random(); for (int n = deck.Length - 1; n > 0; --n) { int k = r.Next(n+1); int temp = deck[n]; deck[n] = deck[k]; deck[k] = temp; } } } 

Eu achei a resposta de Jon Skeet totalmente satisfatória, mas o robo-scanner do meu cliente reportará qualquer ocorrência da Random como uma falha de segurança. Então eu troquei para System.Security.Cryptography.RNGCryptoServiceProvider . Como um bônus, ele corrige esse problema de segurança de thread que foi mencionado. Por outro lado, RNGCryptoServiceProvider foi medido como 300x mais lento do que usando Random .

Uso:

 using (var rng = new RNGCryptoServiceProvider()) { var data = new byte[4]; yourCollection = yourCollection.Shuffle(rng, data); } 

Método:

 ///  /// Shuffles the elements of a sequence randomly. ///  /// A sequence of values to shuffle. /// An instance of a random number generator. /// A placeholder to generate random bytes into. /// A sequence whose elements are shuffled randomly. public static IEnumerable Shuffle(this IEnumerable source, RNGCryptoServiceProvider rng, byte[] data) { var elements = source.ToArray(); for (int i = elements.Length - 1; i >= 0; i--) { rng.GetBytes(data); var swapIndex = BitConverter.ToUInt32(data, 0) % (i + 1); yield return elements[swapIndex]; elements[swapIndex] = elements[i]; } } 

Ligeiramente não relacionado, mas aqui está um método interessante (que, embora seja realmente excessibe, foi REALMENTE implementado) para uma geração realmente aleatória de jogadas de dados!

Dado-O-Matic

A razão pela qual estou postando isso aqui é que ele faz alguns pontos interessantes sobre como seus usuários reagiram à idéia de usar algoritmos para baralhar, em vez de dados reais. É claro que, no mundo real, tal solução é apenas para os extremos realmente extremos do espectro, onde a aleatoriedade tem um impacto tão grande e talvez o impacto afete o dinheiro;).

Eu diria que muitas respostas aqui como “Esse algoritmo embaralha gerando um novo valor random para cada valor em uma lista e, em seguida, ordenando a lista por esses valores randoms” pode estar muito errado!

Eu acho que isso não atribui um valor random para cada elemento da coleção de origem. Em vez disso, pode haver um algoritmo de sorting em execução como o Quicksort, que chamaria uma function de comparação aproximadamente nn vezes n. Algum tipo de algoritmo realmente espera que esta function de comparação seja estável e sempre retorne o mesmo resultado!

Não poderia ser que o IEnumerableSorter chama uma function de comparação para cada etapa do algoritmo de, por exemplo, quicksort e cada vez chama a function x => r.Next() para ambos os parâmetros sem x => r.Next() los em cache!

Nesse caso, você pode realmente atrapalhar o algoritmo de sorting e torná-lo muito pior do que as expectativas sobre as quais o algoritmo é construído. É claro que eventualmente se tornará estável e retornará algo.

Eu poderia verificar isso mais tarde, colocando a saída de debugging dentro de uma nova function “Next” para ver o que acontece. No Reflector, não pude descobrir imediatamente como isso funciona.

Procurando por um algoritmo? Você pode usar minha class ShuffleList :

 class ShuffleList : List { public void Shuffle() { Random random = new Random(); for (int count = Count; count > 0; count--) { int i = random.Next(count); Add(this[i]); RemoveAt(i); } } } 

Então, use assim:

 ShuffleList list = new ShuffleList(); // Add elements to your list. list.Shuffle(); 

Como funciona?

Vamos dar uma lista ordenada inicial dos 5 primeiros inteiros: { 0, 1, 2, 3, 4 } .

O método começa contando o número de elementos e chama a count . Então, com a count decrescente em cada etapa, é preciso um número random entre 0 e count e move-o para o final da lista.

No seguinte exemplo passo a passo, os itens que podem ser movidos são itálico , o item selecionado está em negrito :

0 1 2 3 4
0 1 2 3 4
0 1 2 4 3
0 1 2 4 3
1 2 4 3 0
1 2 4 3 0
1 2 3 0 4
1 2 3 0 4
2 3 0 4 1
2 3 0 4 1
3 0 4 1 2

Esse algoritmo embaralha gerando um novo valor random para cada valor em uma lista e, em seguida, ordenando a lista por esses valores randoms. Pense nisso como adicionar uma nova coluna a uma tabela na memory, preenchê-la com GUIDs e, em seguida, classificar por essa coluna. Parece um caminho eficiente para mim (especialmente com o açúcar lambda!)

Tempo de boot para executar no código com todos os threads e cache de cada novo teste,

Primeiro código sem sucesso. Ele é executado no LINQPad. Se você seguir para testar este código.

 Stopwatch st = new Stopwatch(); st.Start(); var r = new Random(); List list = new List(); list.Add(new String[] {"1","X"}); list.Add(new String[] {"2","A"}); list.Add(new String[] {"3","B"}); list.Add(new String[] {"4","C"}); list.Add(new String[] {"5","D"}); list.Add(new String[] {"6","E"}); //list.OrderBy (l => r.Next()).Dump(); list.OrderBy (l => Guid.NewGuid()).Dump(); st.Stop(); Console.WriteLine(st.Elapsed.TotalMilliseconds); 

list.OrderBy (x => r.Next ()) usa 38,6528 ms

list.OrderBy (x => Guid.NewGuid ()) Usa 36.7634 ms (ele é recomendado do MSDN.)

a segunda vez que ambos usam no mesmo tempo.

EDIT: CÓDIGO DE TESTE no Intel Core i7 4 a 21GHz, RAM 8 GB DDR3 @ 1600, HDD SATA 5200 rpm com [dados: http://www.dropbox.com/s/pbtmh5s9lw285kp/data%5D

  usando o sistema;
 using System.Runtime;
 using System.Diagnostics;
 using System.IO;
 using System.Collections.Generic;
 usando System.Collections;
 using System.Linq;
 using System.Threading;

 Algoritmo de Namespace
 {
     Programa de aula
     {
         public static void Main (string [] args)
         {
             experimentar {
                 int i = 0;
                 int limite = 10;
                 var result = GetTestRandomSort (limite);
                 foreach (var element in result) {
                     Console.WriteLine ();
                     Console.WriteLine ("tempo {0}: {1} ms", ++ i, elemento);
                 }
             } catch (exceção e) {
                 Console.WriteLine (e.Message);
             } finalmente {
                 Console.Write ("Pressione qualquer tecla para continuar ...");
                 Console.ReadKey (true);
             }
         }

         public static IEnumerable  GetTestRandomSort (int limite)
         {
             para (int i = 0; i <5; i ++) {
                 caminho da string = nulo, temp = nulo;
                 Cronômetro st = nulo;
                 StreamReader sr = nulo;
                 int?  contagem = nulo;
                 Listar  lista = nulo;
                 Aleatório r = null;

                 GC.Collect ();
                 GC.WaitForPendingFinalizers ();
                 Thread.Sleep (5000);

                 st = Stopwatch.StartNew ();
                 #region Importar dados de input
                 path = Environment.CurrentDirectory + "\\ data";
                 list = new List  ();
                 sr = new StreamReader (caminho);
                 contagem = 0;
                 while (count  r.Next ()). ToList ();
 // #endregion

 // #region Classificar por Aleatório com OrderBy (Guid)
 // list = list.OrderBy (l => Guid.NewGuid ()). ToList ();
 // #endregion

 // #region Classificar por Aleatório com Parallel e OrderBy (random.Next ())
 // r = novo Random ();
 // list = list.AsParallel (). OrderBy (l => r.Next ()). ToList ();
 // #endregion

 // #region Classificar por Aleatório com Parallel OrderBy (Guid)
 // list = list.AsParallel (). OrderBy (l => Guid.NewGuid ()). ToList ();
 // #endregion

 // #region Classificar por random com o método de ordem aleatória definida pelo usuário
 // r = novo Random ();
 // list = list.Shuffle (r) .ToList ();
 // #endregion

 // #region Classificar por random com o método de ordem aleatória definida pelo usuário
 // r = novo Random ();
 // list = list.AsParallel (). Aleatório (r) .ToList ();
 // #endregion

                 // resultado
 //              
                 st.Stop ();
                 rendimento retorno st.Elapsed.TotalMilliseconds;
                 foreach (var element in list) {
                 Console.WriteLine (elemento);
             }
             }

         }
     }
 }

Descrição do resultado: http://sofpt.miximages.com/algorithm/ResultDescription.PNG
Status do resultado: http://sofpt.miximages.com/algorithm/ResultStat.PNG

Conclusão:
Suponha que: LINQ OrderBy (r.Next ()) e OrderBy (Guid.NewGuid ()) não são piores do que o método de ordem aleatória definido pelo usuário na primeira solução.

Resposta: Eles são contradição.