O uso de Random e OrderBy é um bom algoritmo de reprodução aleatória?

164

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

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

Esse é um bom algoritmo de reprodução aleatória? Como isso funciona exatamente? É uma maneira aceitável de fazer isso?

Svish
fonte

Respostas:

205

Não é uma maneira de embaralhar que eu gosto, principalmente porque é O (n log n) sem um bom motivo, quando é fácil implementar um embaralhamento de O (n). O código da pergunta "funciona" basicamente atribuindo um número aleatório (espero que único!) A cada elemento e, em seguida, ordenando os elementos de acordo com esse número.

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

A implementação de um Shufflemétodo simples de extensão consistiria basicamente em chamarToList ou ToArrayna entrada e no uso de uma implementação existente do Fisher-Yates. (Passe Randomcomo um parâmetro para tornar a vida geralmente mais agradável.) Existem muitas implementações por aí ... Provavelmente, tenho uma resposta em algum lugar.

O lado bom desse método de extensão é que seria muito claro para o leitor o que você realmente está tentando fazer.

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

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> 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: Os comentários sobre o desempenho abaixo me lembraram que podemos realmente retornar os elementos à medida que os embaralhamos:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> 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];
    }
}

Agora, isso fará apenas o trabalho necessário.

Observe que nos dois casos, você precisa ter cuidado com a instância Randomque usa como:

  • Criar duas instâncias Randomaproximadamente ao mesmo tempo produzirá a mesma sequência de números aleatórios (quando usado da mesma maneira)
  • Random não é seguro para threads.

Eu tenho um artigoRandom que detalha essas questões e fornece soluções.

Jon Skeet
fonte
5
Bem, implementações para coisas pequenas, mas importantes, como esta, que eu diria que é sempre bom encontrar aqui no StackOverflow. Então, sim, por favor, se você quiser =)
Svish
9
Jon - sua explicação sobre Fisher-Yates é equivalente à implementação dada na pergunta (a versão ingênua). Durstenfeld / Knuth alcançam O (n) não por atribuição, mas por seleção de um conjunto decrescente e troca. Dessa forma, o número aleatório selecionado pode se repetir e o algoritmo leva apenas O (n).
Tvanfosson 17/08/09
8
Você provavelmente está ficando cansado de me ouvir sobre isso, mas tive um pequeno problema nos testes de unidade que você talvez queira conhecer. Há uma peculiaridade com o ElementAt que faz com que invoque a extensão a cada vez, fornecendo resultados não confiáveis. Nos meus testes, estou materializando o resultado antes de verificar para evitar isso.
Tvanfosson 17/08/09
3
@tvanfosson: Não estou doente :) Mas sim, os chamadores devem estar cientes de que é avaliado preguiçosamente.
21911 Jon Skeet
4
Um pouco tarde, mas observe source.ToArray();que você deve ter using System.Linq;o mesmo arquivo. Caso contrário, você receberá este erro:'System.Collections.Generic.IEnumerable<T>' does not contain a definition for 'ToArray' and no extension method 'ToArray' accepting a first argument of type 'System.Collections.Generic.IEnumerable<T>' could be found (are you missing a using directive or an assembly reference?)
Powerlord 22/10
70

Isso se baseia na resposta de Jon Skeet .

Nessa resposta, a matriz é embaralhada e retornada usando yield. O resultado líquido é que a matriz é mantida na memória durante a duração do foreach, além dos objetos necessários para a iteração, e ainda assim o custo está no início - o rendimento é basicamente um loop vazio.

Esse algoritmo é muito usado em jogos, onde os três primeiros itens são escolhidos e os outros só serão necessários mais tarde, se houver. Minha sugestão é para yieldos números assim que eles forem trocados. Isso reduzirá o custo de inicialização, mantendo o custo de iteração em O (1) (basicamente 5 operações por iteração). O custo total permaneceria o mesmo, mas o embaralhamento seria mais rápido. Nos casos em que isso é chamado, collection.Shuffle().ToArray()pois teoricamente não fará diferença, mas nos casos de uso acima mencionados, acelerará a inicialização. 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, poderá pagar deck.Shuffle().Take(3)e apenas três trocas ocorrerão (embora toda a matriz precise ser copiada primeiro).

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> 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]; 
}
configurador
fonte
Ai! Provavelmente, isso não retornará todos os itens da fonte. Você não pode confiar em um número aleatório exclusivo para N iterações.
P papai
2
Inteligente! (E eu odeio essa coisa de 15 caracteres ...)
Svish
@P Papai: Hein? Cuidado ao elaborar?
Svish
1
Ou você poderia substituir a> 0 com> = 0 e não ter que (embora, um hit RNG extra, mais uma atribuição redundante)
FryGuy
4
O custo de inicialização é O (N) como o custo de source.ToArray ();
quer
8

A partir desta citação de Skeet:

Não é uma maneira de embaralhar que eu gosto, principalmente porque é O (n log n) sem um bom motivo, quando é fácil implementar um embaralhamento de O (n). O código da pergunta "funciona" basicamente atribuindo um número aleatório ( espero que único! ) A cada elemento e, em seguida, ordenando os elementos de acordo com esse número.

Vou explicar um pouco o motivo do que se espera que seja único!

Agora, a partir do Enumerable.OrderBy :

Este método executa uma classificação 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 "recebem" o mesmo número aleatório? Acontece que eles permanecem na mesma ordem em que estão na matriz. Agora, qual é a possibilidade disso acontecer? É difícil calcular exatamente, mas existe o problema do aniversário que é exatamente esse problema.

Agora é real? É verdade?

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

Esse pequeno bloco de código embaralha uma matriz de 3 elementos um certo número de vezes, usando o algoritmo Fisher-Yates feito para trás, o algoritmo Fisher-Yates feito para frente (na página da wiki existem dois algoritmos de pseudo-código ... Eles produzem equivalentes resultados, mas um é feito do primeiro ao último elemento, enquanto o outro é feito do último ao primeiro elemento), o ingênuo algoritmo errado 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 é

Um inteiro assinado de 32 bits maior 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 aumentar a matriz (algo muito lento) ou simplesmente reduzir o valor máximo do gerador de números aleatórios ( int.MaxValuenã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 faixa de valores deverá fornecer o mesmo resultado.

O programa então testa alguns valores, no intervalo de 1 a 4096. Observando o resultado, é bastante claro que, para valores baixos (<128), o algoritmo é muito tendencioso (4-8%). Com 3 valores você precisa pelo menos r.Next(1024). Se você aumentar a matriz (4 ou 5), nem isso r.Next(1024)será suficiente. Eu não sou especialista em baralhar e em matemática, mas acho que para cada bit extra de comprimento da matriz, você precisa de 2 bits extras de valor máximo (porque o paradoxo do aniversário está conectado ao sqrt (numvalues)), então que, se o valor máximo for 2 ^ 31, direi que você poderá classificar matrizes de até 2 ^ 12/2 ^ 13 bits (4096-8192 elementos)

xanatos
fonte
Bem afirmado, e exibe perfeitamente um problema com a pergunta original. Isso deve ser mesclado com a resposta de Jon.
TheSoftwareJedi
6

Provavelmente está ok para a maioria dos propósitos, e quase sempre gera uma distribuição verdadeiramente aleatória (exceto quando Random.Next () produz dois números inteiros aleatórios idênticos).

Ele funciona atribuindo a cada elemento da série um número inteiro aleatório e ordenando a sequência por esses números inteiros.

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

ripper234
fonte
4

Isso já aconteceu várias vezes antes. Pesquise Fisher-Yates no StackOverflow.

Aqui está um exemplo de código C # que escrevi para esse algoritmo. Você pode parametrizar em algum 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;
                }
        }
}
hughdbrown
fonte
2
Você não deve usar Randomcomo uma variável estática como esta - Randomnão é seguro para threads. Veja csharpindepth.com/Articles/Chapter12/Random.aspx
Jon Skeet
@ Jon Skeet: claro, esse é um argumento legítimo. OTOH, o OP estava perguntando sobre um algoritmo totalmente errado, enquanto isso estava correto (exceto o caso de uso de embaralhamento de cartão multithreaded).
precisa saber é o seguinte
1
Isso significa apenas que isso é "menos errado" do que a abordagem do OP. Isso não significa que é um código que deve ser usado sem entender que não pode ser usado com segurança em um contexto multithread ... o que é algo que você não mencionou. Há uma expectativa razoável de que membros estáticos possam ser usados ​​com segurança a partir de vários threads.
Jon Skeet
@ Jon Skeet: Claro, eu posso mudar isso. Feito. Costumo pensar que voltando a uma pergunta respondida há três anos e meio e dizendo: "Está incorreto porque não lida com o caso de uso multithread" quando o OP nunca perguntou sobre nada além do algoritmo ser excessivo. Revise minhas respostas ao longo dos anos. Muitas vezes, eu respondi aos OPs que iam além dos requisitos declarados. Fui criticado por isso. Eu não esperaria que os OPs obtivessem respostas que se encaixassem em todos os usos possíveis.
precisa saber é o seguinte
Eu só visitei esta resposta porque alguém me apontou para ela no chat. Embora o OP não tenha mencionado especificamente a segmentação, acho que definitivamente vale a pena mencionar quando um método estático não é seguro para threads, pois é incomum e torna o código inadequado para muitas situações sem modificação. Seu novo código é seguro para threads - mas ainda não é o ideal, como se você o chamasse de vários threads "aproximadamente" ao mesmo tempo para embaralhar duas coleções do mesmo tamanho, as embaralhadas serão equivalentes. Basicamente, Randomé uma dor de usar, como observado no meu artigo.
Jon Skeet
3

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

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

Samuel Carrijo
fonte
3

Achei a resposta de Jon Skeet inteiramente satisfatória, mas o robo-scanner do meu cliente relatará qualquer instância Randomcomo uma falha de segurança. Então eu troquei por isso System.Security.Cryptography.RNGCryptoServiceProvider. Como bônus, ele corrige o problema de segurança do thread mencionado. Por outro lado, RNGCryptoServiceProviderfoi medido como 300x mais lento que o usoRandom .

Uso:

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

Método:

/// <summary>
/// Shuffles the elements of a sequence randomly.
/// </summary>
/// <param name="source">A sequence of values to shuffle.</param>
/// <param name="rng">An instance of a random number generator.</param>
/// <param name="data">A placeholder to generate random bytes into.</param>
/// <returns>A sequence whose elements are shuffled randomly.</returns>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> 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];
    }
}
frattaro
fonte
3

Procurando por um algoritmo? Você pode usar minha ShuffleListclasse:

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

Em seguida, use-o assim:

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

Como funciona?

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

O método começa contando o número de elementos e o chama count. Então, com a countdiminuição em cada etapa, é necessário um número aleatório entre 0ecount e move-lo para o final da lista.

No exemplo passo a passo a seguir, os itens que podem ser movidos estão em 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

SteeveDroz
fonte
Isso não é O (n). RemoveAt sozinho é O (n).
Paparazzo
Hmm, parece que você está certo, meu mal! Vou remover essa parte.
precisa saber é o seguinte
1

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

Dave Swersky
fonte
1

Um pouco sem relação, mas aqui está um método interessante (que mesmo sendo realmente excessivo, REALMENTE foi implementado) para a geração verdadeiramente aleatória de dados!

Dados-O-Matic

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

Irfy
fonte
1

Eu diria que muitas respostas aqui como "Esse algoritmo embaralha, gerando um novo valor aleatório para cada valor em uma lista e ordenando a lista por esses valores aleatórios" pode estar muito errado!

Eu acho que isso NÃO atribui um valor aleatório a cada elemento da coleção de origem. Em vez disso, pode haver um algoritmo de classificação em execução como o Quicksort que chamaria uma função de comparação aproximadamente n log n vezes. Algum tipo de algortihm realmente espera que esta função de comparação seja estável e sempre retorne o mesmo resultado!

Não seria possível que o IEnumerableSorter chame uma função de comparação para cada etapa do algoritmo, por exemplo, quicksort, e cada vez chame a função x => r.Next()para os dois parâmetros sem armazenar esses em cache!

Nesse caso, você pode realmente atrapalhar o algoritmo de classificação e torná-lo muito pior do que as expectativas em que o algoritmo se baseia. Obviamente, eventualmente se tornará estável e retornará algo.

Eu poderia checar mais tarde colocando a saída de depuração dentro de uma nova função "Next" para ver o que acontece. No Reflector, não consegui descobrir imediatamente como funciona.

cristão
fonte
1
Não é o caso: substituição interna void ComputeKeys (elementos TElement [], int count); Declarando Tipo: System.Linq.EnumerableSorter <TElement, TKey> Assembleia: System.Core, versão = 3.5.0.0 Esta função cria uma matriz em primeiro lugar com todas as chaves que consome memória, antes de quicksort os classifica
Christian
É bom saber - ainda assim, apenas um detalhe de implementação, que pode mudar em versões futuras!
Blorgbeard saiu em 10/10/12
-5

Hora de inicialização para executar no código, limpar todos os threads e armazenar em cache a cada novo teste,

Primeiro código malsucedido. É executado no LINQPad. Se você seguir para testar este código.

Stopwatch st = new Stopwatch();
st.Start();
var r = new Random();
List<string[]> list = new List<string[]>();
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 (recomendado do MSDN.)

depois da segunda vez, ambos usam ao mesmo tempo.

EDIT: CÓDIGO DE TESTE no Intel Core i7 [email protected], RAM 8 GB DDR3 @ 1600, HDD SATA 5200 rpm com [Dados: www.dropbox.com/s/pbtmh5s9lw285kp/data]

using System;
using System.Runtime;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Threading;

namespace Algorithm
{
    class Program
    {
        public static void Main(string[] args)
        {
            try {
                int i = 0;
                int limit = 10;
                var result = GetTestRandomSort(limit);
                foreach (var element in result) {
                    Console.WriteLine();
                    Console.WriteLine("time {0}: {1} ms", ++i, element);
                }
            } catch (Exception e) {
                Console.WriteLine(e.Message);
            } finally {
                Console.Write("Press any key to continue . . . ");
                Console.ReadKey(true);
            }
        }

        public static IEnumerable<double> GetTestRandomSort(int limit)
        {
            for (int i = 0; i < 5; i++) {
                string path = null, temp = null;
                Stopwatch st = null;
                StreamReader sr = null;
                int? count = null;
                List<string> list = null;
                Random r = null;

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

                st = Stopwatch.StartNew();
                #region Import Input Data
                path = Environment.CurrentDirectory + "\\data";
                list = new List<string>();
                sr = new StreamReader(path);
                count = 0;
                while (count < limit && (temp = sr.ReadLine()) != null) {
//                  Console.WriteLine(temp);
                    list.Add(temp);
                    count++;
                }
                sr.Close();
                #endregion

//              Console.WriteLine("--------------Random--------------");
//              #region Sort by Random with OrderBy(random.Next())
//              r = new Random();
//              list = list.OrderBy(l => r.Next()).ToList();
//              #endregion

//              #region Sort by Random with OrderBy(Guid)
//              list = list.OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion

//              #region Sort by Random with Parallel and OrderBy(random.Next())
//              r = new Random();
//              list = list.AsParallel().OrderBy(l => r.Next()).ToList();
//              #endregion

//              #region Sort by Random with Parallel OrderBy(Guid)
//              list = list.AsParallel().OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion

//              #region Sort by Random with User-Defined Shuffle Method
//              r = new Random();
//              list = list.Shuffle(r).ToList();
//              #endregion

//              #region Sort by Random with Parallel User-Defined Shuffle Method
//              r = new Random();
//              list = list.AsParallel().Shuffle(r).ToList();
//              #endregion

                // Result
//              
                st.Stop();
                yield return st.Elapsed.TotalMilliseconds;
                foreach (var element in list) {
                Console.WriteLine(element);
            }
            }

        }
    }
}

Descrição do resultado: https://www.dropbox.com/s/9dw9wl259dfs04g/ResultDescription.PNG
Estatística do resultado: https://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG

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

Resposta: Eles são contraditórios.

GMzo
fonte
1
A segunda opção não está correta e, portanto, seu desempenho é irrelevante . Isso também ainda não responde à questão de saber se a ordem por um número aleatório é aceitável, eficiente ou como funciona. A primeira solução também tem problemas de correção, mas eles não são tão importantes.
Servy
Desculpe, gostaria de saber qual o melhor tipo de parâmetro do Quicksort do Linq OrderBy? Eu preciso testar o desempenho. No entanto, acho que o tipo int só tem velocidade melhor que a sequência de Guid, mas não é. Eu entendi por que o MSDN recomendou. A primeira solução do desempenho editado é igual ao OrderBy com instância Random.
GMzo 26/02
Qual o sentido de medir o desempenho do código que não resolve o problema? O desempenho é apenas uma consideração a ser feita entre duas soluções que funcionam . Quando você tem soluções de trabalho, então você pode começar a compará-los.
Servy
Devo ter tempo para testar mais dados e, se terminar, prometo postar novamente. Suponha: eu acho que o Linq OrderBy não é pior que a primeira solução. Opinião: é fácil de usar e entender.
GMzo 27/02
É visivelmente menos eficiente do que algoritmos de embaralhamento simples e muito simples, mas mais uma vez, o desempenho é irrelevante . Eles não estão confundindo os dados de maneira confiável, além de terem menos desempenho.
Servy