Como fazer TDD para algo com muitas permutações?

15

Ao criar um sistema como um AI, que pode levar muitos caminhos diferentes muito rapidamente, ou realmente qualquer algoritmo que tenha várias entradas diferentes, o conjunto de resultados possíveis pode conter um grande número de permutações.

Que abordagem devemos adotar para usar o TDD ao criar um sistema que produza muitas, muitas diferentes permutações de resultados?

    
por Nicole 21.10.2011 / 06:05
fonte

5 respostas

7

Adotando uma abordagem mais prática para resposta do pdr . O TDD tem tudo a ver com design de software em vez de teste. Você usa testes de unidade para verificar seu trabalho à medida que avança.

Portanto, em um nível de teste de unidade, você precisa projetar as unidades para que elas possam ser testadas de uma maneira completamente determinista. Você pode fazer isso pegando qualquer coisa que torne a unidade não-determinística (como um gerador de números aleatórios) e abstraia isso. Digamos que temos um exemplo ingênuo de um método que decide se um movimento é bom ou não:

class Decider {

  public boolean decide(float input, float risk) {

      float inputRand = Math.random();
      if (inputRand > input) {
         float riskRand = Math.random();
      }
      return false;

  }

}

// The usage:
Decider d = new Decider();
d.decide(0.1337f, 0.1337f);

Este método é muito difícil de testar e a única coisa que você realmente pode verificar em testes de unidade é o seu limite ... mas isso requer muitas tentativas para chegar aos limites. Então, vamos abstrair a parte aleatória criando uma interface e uma classe concreta que envolve a funcionalidade:

public interface IRandom {

   public float random();

}

public class ConcreteRandom implements IRandom {

   public float random() {
      return Math.random();
   }

}

A classe Decider agora precisa usar a classe concreta por meio de sua abstração, ou seja, a Interface. Essa maneira de fazer as coisas é chamada de injeção de dependência (o exemplo abaixo é um exemplo de injeção de construtor, mas você pode fazer isso com um setter também):

class Decider {

  IRandom irandom;

  public Decider(IRandom irandom) { // constructor injection
      this.irandom = irandom;
  }

  public boolean decide(float input, float risk) {

      float inputRand = irandom.random();
      if (inputRand > input) {
         float riskRand = irandom.random();
      }
      return false;

  }

}

// The usage:
Decider d = new Decider(new ConcreteRandom);
d.decide(0.1337f, 0.1337f);

Você pode se perguntar por que esse "código inchado" é necessário. Bem, para iniciantes, agora você pode simular o comportamento da parte aleatória do algoritmo porque o Decider agora tem uma dependência que segue o IRandom s "contrato". Você pode usar uma estrutura de simulação para isso, mas esse exemplo é simples o suficiente para se codificar:

class MockedRandom() implements IRandom {

    public List<Float> floats = new ArrayList<Float>();
    int pos;

   public void addFloat(float f) {
     floats.add(f);
   }

   public float random() {
      float out = floats.get(pos);
      if (pos != floats.size()) {
         pos++;
      }
      return out;
   }

}

A melhor parte é que isso pode substituir completamente a implementação concreta "real". O código fica fácil de testar assim:

@Before void setUp() {
  MockedRandom mRandom = new MockedRandom();

  Decider decider = new Decider(mRandom);
}

@Test
public void testDecisionWithLowInput_ShouldGiveFalse() {

  mRandom.addFloat(0f);

  assertFalse(decider.decide(0.1337f, 0.1337f));
}

@Test
public void testDecisionWithHighInputRandButLowRiskRand_ShouldGiveFalse() {

  mRandom.addFloat(1f);
  mRandom.addFloat(0f);

  assertFalse(decider.decide(0.1337f, 0.1337f));
}

@Test
public void testDecisionWithHighInputRandAndHighRiskRand_ShouldGiveTrue() {

  mRandom.addFloat(1f);
  mRandom.addFloat(1f);

  assertTrue(decider.decide(0.1337f, 0.1337f));
}

Espero que isso lhe dê ideias sobre como projetar seu aplicativo para que as permutações possam ser forçadas, para que você possa testar todos os casos de borda e outros enfeites.

    
por 21.10.2011 / 10:05
fonte
3

TDD rigoroso tende a quebrar um pouco para sistemas mais complexos, mas isso não importa muito em termos práticos - depois de conseguir isolar insumos individuais, basta escolher alguns casos de teste que forneçam uma cobertura razoável e use isso.

Isso requer algum conhecimento do que a implementação terá de fazer bem, mas isso é mais uma preocupação teórica - é altamente improvável que você esteja construindo uma AI especificada em detalhes por usuários não técnicos. Está na mesma categoria do que passar testes por codificação para os casos de teste - oficialmente o teste é a especificação e a implementação é a solução correta e a mais rápida possível, mas nunca acontece de fato.

    
por 21.10.2011 / 06:21
fonte
2

O TDD não é sobre testes, é sobre design.

Longe de desmoronar com a complexidade, ela se destaca nessas circunstâncias. Isso levará você a considerar o problema maior em peças menores, o que levará a um melhor design.

Não tente testar todas as permutações do seu algoritmo. Apenas construa teste após teste, escreva o código mais simples para fazer o teste funcionar, até que você tenha suas bases cobertas. Você deve ver o que eu quero dizer sobre quebrar o problema porque você será encorajado a falsificar partes do problema enquanto testa outras partes, para evitar ter que escrever 10 bilhões de testes para 10 bilhões de permutações.

Editar: eu queria adicionar um exemplo, mas não tive tempo antes.

Vamos considerar um algoritmo de classificação no local. Poderíamos ir em frente e escrever testes que cobrem a extremidade superior da matriz, a extremidade inferior da matriz e todos os tipos de combinações estranhas no meio. Para cada um, teríamos que construir uma matriz completa de algum tipo de objeto. Isso levaria tempo.

Ou poderíamos resolver o problema em quatro partes:

  1. Atravessar a matriz.
  2. Compare os itens selecionados.
  3. Trocar itens.
  4. Coordene os três acima.

A primeira é a única parte complicada do problema, mas abstraindo-a do resto, você tornou muito mais simples.

O segundo é quase certamente tratado pelo próprio objeto, pelo menos opcionalmente, em muitos frameworks com tipagem estática, haverá uma interface para mostrar se essa funcionalidade é implementada. Então você não precisa testar isso.

O terceiro é incrivelmente fácil de testar.

O quarto apenas manipula dois ponteiros, pede que a classe de percurso mova os ponteiros, solicita uma comparação e, com base no resultado dessa comparação, solicita que os itens sejam trocados. Se você falsificou os três primeiros problemas, pode testá-lo com muita facilidade.

Como nós levamos a um design melhor aqui? Digamos que você tenha simplificado e implementado um tipo de bolha. Funciona mas, quando você vai para produção e tem que lidar com um milhão de objetos, é muito lento. Tudo o que você precisa fazer é escrever uma nova funcionalidade de passagem e trocá-la. Você não precisa lidar com a complexidade de lidar com os outros três problemas.

Isso, você encontrará, é a diferença entre o teste de unidade e o TDD. O testador de unidade dirá que isso tornou seus testes frágeis, que se você testasse entradas e saídas simples, não precisaria escrever mais testes para sua nova funcionalidade. O TDDer dirá que eu separei as preocupações adequadamente para que cada classe que eu faça faça uma coisa e uma coisa bem.

    
por 21.10.2011 / 09:38
fonte
1

Não é possível testar todas as permutações de um cálculo com muitas variáveis. Mas isso não é novidade, sempre foi verdade em qualquer programa acima da complexidade dos brinquedos. O ponto de testes é verificar a propriedade do cálculo. Por exemplo, classificar uma lista com 1000 números exige algum esforço, mas qualquer solução individual pode ser verificada com muita facilidade. Agora, embora haja 1000! possível (classes de) entradas para esse programa e você não pode testá-los todos, é completamente suficiente para apenas gerar 1000 entradas aleatoriamente e verificar se a saída está, de fato, ordenada. Por quê? Porque é quase impossível escrever um programa que classifique 1000 vetores gerados aleatoriamente sem sendo também corretos em geral (a menos que você manipule deliberadamente para manipular certas entradas mágicas ...)

Agora, em geral, as coisas são um pouco mais complicadas. Realmente tem sido erros onde um mailer não entregaria e-mails para usuários se eles tivessem um 'f' em seu nome de usuário e o dia da semana fosse sexta-feira. Mas eu considero o esforço desperdiçado tentando antecipar essa estranheza. Sua suíte de testes deve fornecer a você uma confiança constante de que o sistema faz o que você espera nas entradas que você espera. Se fizer coisas funky em certos casos funky você notará logo depois de tentar o primeiro caso funky, e então você pode escrever um teste especificamente contra esse caso (que normalmente também cobrirá uma classe inteira de casos similares).

    
por 21.10.2011 / 08:26
fonte
0

Considere os casos de borda e alguma entrada aleatória.

Para pegar o exemplo de classificação:

  • Organize algumas listas aleatórias
  • Pegue uma lista que já esteja classificada
  • Pegue uma lista que esteja na ordem inversa
  • Veja uma lista que está quase classificada

Se funcionar rápido, você pode ter certeza de que funcionará para todas as entradas.

    
por 21.10.2011 / 09:36
fonte