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

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?

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.

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

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)

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.

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

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.

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

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

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

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

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.

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.