Testando para Random Value - Pensamentos sobre esta abordagem?

Question

OK, tenho vindo a trabalhar em um sistema aleatório seletor de imagem e fila (para que você não ver as mesmas imagens muitas vezes).

Tudo ia às mil maravilhas (tanto quanto o meu código de baixa qualidade faz) até cheguei ao pouco aleatório. Eu queria testá-lo, mas como você testar para ele? Não há Debug.Assert(i.IsRandom) (infelizmente): D

Então, eu tenho o meu cérebro nele após molhar-lo com um pouco de chá e veio com o seguinte, eu estava me perguntando se eu poderia ter os seus pensamentos?

• Basicamente, eu sabia que o aleatória pouco foi o problema, então eu arranquei isso a um delegado (que passaria então a ser passado para o construtor objetos).
• Eu, então, criou uma classe que praticamente executa a mesma lógica que o vivo código, mas lembra-se o valor selecionado em uma variável privada.
• Eu, então, jogou esse delegado para a classe ao vivo e testado contra que:

i.

Debug.Assert(myObj.RndVal == RndIntTester.ValuePassed);

Mas eu não pude deixar de pensar, eu estava perdendo meu tempo? eu corri que por muitas iterações para ver se ele caiu sobre a qualquer momento etc.

Você acha que eu estava perdendo meu tempo com isso? Ou eu poderia ter conseguido acabar com:

de GateKiller resposta me fez lembrar disso:

Atualização para esclarecer

• Devo acrescentar que eu basicamente nunca mais quero ver o mesmo resultado mais de um número X de vezes a partir de uma piscina de tamanho Y.
• A adição do recipiente de ensaio, basicamente permitiu-me ver se alguma das imagens previamente selecionados foram "aleatoriamente" selecionado.
• Eu acho que tecnicamente a coisa aqui está sendo testado em não o RNG (desde que eu nunca escreveu esse código), mas o fato de que eu estou esperando aleatória resultados de um conjunto limitado, e eu quero segui-los .

Answer 1

Test da obrigação: "para que você não ver as mesmas imagens muitas vezes"

Peça 100 imagens. Você viu uma imagem muitas vezes?

Answer 2

Há uma lista acessível de testes aleatoriedade estatística e pesquisa relacionada na Wikipedia. Note que você não vai saber com certeza que uma fonte é verdadeiramente aleatório com a maioria deles, você só descartou algumas maneiras em que ele pode ser facilmente previsível.

Answer 3

Se você tem um conjunto fixo de itens, e você não quer que eles se repetir muitas vezes, embaralhar a coleção aleatoriamente. Então você vai ter certeza de que você nunca vê a mesma imagem duas vezes seguidas, sinto que você está ouvindo Top 20 de rádio, etc. Você vai fazer uma passagem completa através da recolha antes de repetir.

Item[] foo = …
for (int idx = foo.size(); idx > 1; --idx) {
  /* Pick random number from half-open interval [0, idx) */
  int rnd = random(idx); 
  Item tmp = foo[idx - 1];
  foo[idx - 1] = foo[rnd];
  foo[rnd] = tmp;
}

Se você tem muitos itens para coletar e Shuffle todas de uma só vez (10s de milhares de imagens em um repositório), você pode adicionar um pouco de divisão e conquista para a mesma abordagem. Embaralhar grupos de imagens, e então embaralhar cada grupo.

Uma abordagem ligeiramente diferente que soa como ele poderia se aplicar ao seu problema declaração revista é ter sua implementação "seletor de imagem" manter sua história de seleção recente em uma fila de no máximo comprimento Y. Antes de retornar uma imagem, ela testa para ver se o seu nos tempos de fila X já, e se assim for, ele seleciona aleatoriamente outro, até que se encontre um que passa.

Se você está realmente perguntando sobre testar a qualidade do gerador de números aleatórios, eu vou ter que abrir o livro de estatísticas.

Answer 4

É impossível testar se um valor é verdadeiramente aleatório ou não. O melhor que você pode fazer é realizar o teste alguma grande número de vezes e teste que você tem uma distribuição adequada, mas se os resultados são verdadeiramente aleatório, mesmo isso tem um (muito pequena) chance de falhar.

Se você está fazendo teste de caixa branca, e você sabe que seu semente aleatória, então você pode realmente calcular o resultado esperado, mas você pode precisar de um teste separado para testar a aleatoriedade da sua RNG.

Answer 5

A geração de números aleatórios é demasiado importante para ser deixado ao acaso. - Robert R. Coveyou

Para resolver o problema psicológico:

Uma maneira decente para evitar repetições aparentes é selecionar alguns itens de forma aleatória do conjunto completo, descartando duplicatas. Jogar os, em seguida, selecione outro poucos. Quantos é "um pouco" depende de quão rápido você está jogando eles e quão grande é o conjunto completo é, mas por exemplo, evitando uma repetição dentro do maior dos "20", e "5 minutos" pode ser OK. Faça testes com usuários -. Como o programador que você vai ser tão doente de slideshows você não é um assunto bom teste

Para testar randomizar código, eu diria:

Passo 1: especifique como o código deve mapear os números aleatórios matérias para escolhas em seu domínio, e certifique-se de que seu código usa corretamente a saída do gerador de números aleatórios. Teste isso Mocking o gerador (ou semeando-a com um valor de teste conhecido, se é um PRNG).

Passo 2: Certifique-se o gerador é suficientemente aleatória para seus propósitos. Se você usou uma função de biblioteca, você faz isso através da leitura da documentação. Se você escreveu seu próprio país, por quê?

Passo 3 (estatísticos avançados apenas): executar alguns testes estatísticos para aleatoriedade na saída do gerador. Certifique-se de que você sabe qual é a probabilidade de um falso falha no teste.

Answer 6

Existem livros inteiros se pode escrever sobre aleatoriedade e avaliar se algo aparece ser aleatória, mas eu vou te salvar as páginas de matemática. Em suma, você pode usar um teste qui-quadrado como uma maneira de determinar quão bem um aparentemente "aleatórios" ataques de distribuição que você espera.

Se você estiver usando Perl, você pode usar o Estatísticas :: qui-quadrado módulo para fazer o trabalho duro para você.

No entanto, se você quiser ter certeza de que suas imagens são uniformemente distribuída , então você provavelmente não quer que eles sejam verdadeiramente aleatório. Em vez disso, eu sugiro que você tome a sua lista inteira de imagens, embaralhar essa lista, e em seguida, remover um item que sempre que você precisar de uma imagem "random". Quando a lista estiver vazia, você re-construir, re-shuffle, e repita.

Isto significa técnica que dado um conjunto de imagens, cada imagem individual não pode aparecer mais de uma vez a cada iteração através de sua lista. Suas imagens não posso deixar de estar uniformemente distribuída.

Todo o melhor,

Paul

Answer 7

O Aleatório e funções similares dar é, mas números pseudo-aleatórios, uma série de números produzidos através de uma função. Normalmente, você dá a essa função que o primeiro parâmetro de entrada (A.K.A. a "semente"), que é usado para produzir o primeiro número "aleatório". Depois disso, cada último valor é usado como o parâmetro de entrada para a próxima iteração do ciclo. Você pode verificar o artigo da Wikipedia sobre "Pseudorandom gerador de números", a explicação não é muito bom.

Todos estes algoritmos têm algo em comum: a série se repete depois de um número de iterações . Lembre-se, estes não são realmente números aleatórios, apenas séries de números que parecem aleatória. Para selecionar um gerador em detrimento de outro, você precisa perguntar a si mesmo:? O que você quer para ele

Como você testar a aleatoriedade? Na verdade você pode. Há uma abundância de testes para isso. O primeiro e mais simples é, naturalmente, executar o gerador de números pseudo-aleatórios um número enorme de vezes, e compilar o número de vezes que cada resultado aparece. No final, cada resultado deveria ter aparecido várias vezes muito perto (número de iterações) / (número de resultados possíveis). Quanto maior o desvio padrão deste, o pior seu gerador é.

O segundo é: quanto de números aleatórios que você está usando no momento? 2, 3? Leve-os em pares (ou tripplets) e repita o experimento anterior: após um longo número de iterações, cada resultado esperado deve ter aparecido pelo menos uma vez, e outra vez o número de vezes que cada resultado tem aparecido não deve ser muito longe o esperado. Há alguns geradores que funcionam muito bem para tirar um ou dois de cada vez, mas não espetacularmente quando você está tendo 3 ou mais (Randu alguém?).

Existem outros, exames mais complexos: alguns envolvem plotar os resultados em uma escala logarítmica, ou em um avião com um círculo no meio e, em seguida, contar o quanto das parcelas caiu dentro, outros ... Eu acredito que aqueles 2 acima deve ser suficiente na maioria das vezes (a menos que você é um matemático mimado).

Answer 8

Aleatório é aleatória. Mesmo se a mesma imagem aparece 4 vezes seguidas, ele ainda poderia ser considerado aleatório.

Answer 9

A minha opinião é que qualquer coisa aleatória não pode ser devidamente testado.

Claro que você pode tentar testá-lo, mas há tantas combinações para tentar que você é melhor fora apenas contando com a RNG e manchar a verificação de um punhado grande de casos.

Answer 10

Bem, o problema é que os números aleatórios, por definição, pode ter repetido (porque eles são ... esperar por ele: aleatória). Talvez o que você quer fazer é salvar o último número aleatório e comparar o calculado a isso, e se for igual basta calcular outra ... mas agora seus números são menos aleatório (eu sei que não há tal coisa como "mais ou menos" aleatoriedade, mas deixe-me usar o termo apenas desta vez), porque eles são a garantia de não repetição.

De qualquer forma, você nunca deve dar números aleatórios tanto pensamento. :)

Answer 11

Como os outros têm para fora pontas, é impossível para realmente teste de aleatoriedade. Você pode (e deve) ter a aleatoriedade contido a um método particular, e, em seguida, testes de unidade de gravação para todos os outros métodos. Dessa forma, você pode testar todas as outras funcionalidades, assumindo que você pode obter um número aleatório para fora daquela última parte.

Answer 12

armazenar os valores aleatórios e antes de usar o número aleatório seguinte gerado, cheque com o valor armazenado.

Answer 13

Qualquer bom pseudo-aleatórios gerador de números vai deixar você semear o gerador. Se você semear o gerador com o mesmo número, então o fluxo de números aleatórios gerados será o mesmo. Então por que não semear o gerador de números aleatórios e, em seguida, criar seus testes de unidade com base em que determinado fluxo de números?

Answer 14

Para obter uma série de não-repetição de números aleatórios:

1. Criar uma lista de números aleatórios.
2. Adicionar um número sequencial para cada número aleatório
3. Classificar a lista seqüenciado pelo número original aleatória
4. Use o seu número de seqüência como um novo número aleatório.

Answer 15

Do not testar a aleatoriedade, teste para ver se os resultados Sua obtenção são desejáveis ??(ou melhor, para tentar obter resultados indesejáveis ??algumas vezes antes de aceitar que os seus resultados são, provavelmente, vai ser desejável). Será impossível para garantir que você nunca vai conseguir um resultado indesejável se você está testando uma saída aleatória, mas pelo menos você pode aumentar as chances de que você vai perceber que isso aconteça.

Eu tomaria N piscinas de tamanho Y, a verificação de quaisquer resultados que aparecem mais de um número X de vezes, ou tomar uma piscina de tamanho N * Y, a verificação de cada grupo de tamanho Y para qualquer resultado que aparece mais de X vezes (1 a Y, Y + 2 a 1, 3 a Y + 2, etc). O que N é vai depender de como confiável você quer que o teste seja.

Answer 16

Os números aleatórios são gerados a partir de uma distribuição. Neste caso, cada valor deve ter o mesmo propability de aparecer. Se você calcular uma quantidade infinita de randoms, você começa a distribuição exata.

Na prática, chamar a função muitas vezes e verificar os resultados. Se você espera ter imagens N, calcule 100 * N randoms, em seguida, contar quantos de cada número esperado foram encontrados. A maioria deve aparecer 70-130 vezes. Re-executar o teste com diferentes aleatório-semente para ver se os resultados são diferentes.

Se você encontrar o gerador que você usar agora não é bom o suficiente, você pode facilmente encontrar algo. Google por "Mersenne Twister." - que é muito mais aleatória do que você jamais precisa

Para evitar imagens re-aparecer, você precisa de algo menos aleatório. Uma abordagem simples seria para verificar se os valores não permitidas, se o seu um desses, voltar a calcular.

Answer 17

Embora você não pode teste de aleatoriedade, você pode testar se para correlação, ou distribuição, de uma sequência de números.

Difícil objetivo de teste:. Cada vez que precisamos de uma imagem, selecione 1 de 4 imagens de forma aleatória

Fácil objetivo de teste:. Para cada 100 imagens que seleccionar, cada um dos 4 imagens deve aparecer pelo menos 20 vezes

Answer 18

Eu concordo com Adam Rosenfield. Para a situação que você está falando, a única coisa que você pode ser útil para teste é a distribuição em toda a gama.

A situação eu normalmente encontro é que eu estou gerar números pseudo-aleatórios com PRNG da minha linguagem favorita, e depois manipulá-los para o intervalo desejado. Para verificar se meus manipulações afetaram a distribuição, eu gerar um monte de números, manipulá-los e, em seguida, verificar a distribuição dos resultados.

Para obter um bom teste, você deve gerar pelo menos um par de ordens de magnitude mais números do que a sua gama detém. Os valores mais você usa, melhor o teste. Obviamente, se você tem realmente uma grande variedade, isso não vai funcionar, pois você terá que gerar demasiados números. Mas em sua situação ele deve funcionar bem.

Aqui está um exemplo em Perl que ilustra o que quero dizer:

for (my $i=0; $i<=100000; $i++) {
   my $r = rand;        # Get the random number
   $r = int($r * 1000); # Move it into the desired range
   $dist{$r} ++;        # Count the occurrences of each number
}

print "Min occurrences: ", (sort { $a <=> $b } values %dist)[1], "\n";
print "Max occurrences: ", (sort { $b <=> $a } values %dist)[1], "\n";

Se o spread entre os MIN e MAX ocorrências é pequeno, então a sua distribuição é bom. Se é grande, então a sua distribuição pode ser ruim. Você também pode usar essa abordagem para verificar se o seu alcance foi coberta e se quaisquer valores foram perdidas.

Mais uma vez, os mais números que você gerar, mais válidos os resultados. I tendem a começar pequeno e trabalhar-se a tudo o que a minha máquina irá tratar em uma quantidade razoável de tempo, por exemplo, cinco minutos.

Answer 19

Supondo que você está testando uma série de aleatoriedade dentro inteiros, uma maneira de verificar isso é criar um gajillion (bem, talvez 10.000 ou mais) números 'aleatória' e traçar a sua ocorrência em um histograma.

          ******    ******           ****
***********************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
         1         2         3         4         5
12345678901234567890123456789012345678901234567890

Os dados anteriores revelam um 'relativamente' distribuição normal.

se parecia mais distorcida, como esta:

          ******    ******           ****
    ************  ************  ************
    ************  ************  ***************
    ************  ************  ****************
    ************  ************  *****************
    ************  ************  *****************
   ***************************  ******************
   **************************** ******************
******************************* ******************
**************************************************
         1         2         3         4         5
12345678901234567890123456789012345678901234567890

Em seguida, você pode ver que há menos aleatoriedade. Como já foi mencionado, há a questão da repetição de lidar com tão bem.

Se você fosse escrever um arquivo binário de digamos 10.000 números aleatórios a partir do seu gerador usando, digamos, um número aleatório de 1 a 1024 e tenta comprimir o arquivo usando alguma compressão (zip, gzip, etc.), então você poderia comparar os dois tamanhos de arquivo. Se houver 'lotes' de compressão, então não é particularmente aleatória. Se não há muito de uma mudança no tamanho, então é 'bastante aleatória'.

por que isso funciona

Os algoritmos de compressão de procurar padrões (repetição e outros) e reduz que de alguma forma. Uma maneira de olhar um desses algoritmos de compressão é uma medida da quantidade de informação em um arquivo. Um arquivo altamente comprimido tem pouca informação (por exemplo aleatoriedade) e um arquivo compactado-pouco tem muita informação (aleatoriedade)