Abordagem TDD para problemas algorítmicos

Eu falhei em um teste algorítmico com o Codility porque tentei encontrar uma solução melhor e, no final, não tinha nada.

Então isso me fez pensar se eu poderia usar uma abordagem semelhante ao TDD? Ou seja, se eu normalmente consigo desenvolver uma solução gradualmente de maneira semelhante?

Se eu estivesse escrevendo um algoritmo de classificação, poderia passar de um Bubblesort padrão para um de bolhas bidirecional, mas algo mais avançado como o Quicksort seria um "salto quântico", mas pelo menos eu teria dados de teste que posso validar facilmente.

Outras dicas para esses testes? Uma coisa que eu faria na próxima vez é usar mais métodos / funções do que loops internos. Por exemplo, na classificação, você geralmente precisa de uma troca. Se fosse um método, eu precisaria apenas modificar o código de chamada. Eu poderia até ter soluções mais avançadas como classes derivadas.

Com problemas "Algorítmicos" vs "normais", quero dizer problemas em que a complexidade do tempo é importante. Então, em vez de passar em mais testes como no TDD, você faria "se comportar melhor".

Com "semelhante ao TDD", quero dizer:

1. Escreva um teste relativamente automático para economizar tempo em testes manuais por incremento.
2. Desenvolvimento incremental.
3. Teste de regressão, capacidade de detectar se o código quebra ou pelo menos se a funcionalidade muda entre incrementos.

Eu acho que isso deve ser bem fácil de entender se você comparar

1. Escrevendo uma classificação de shell diretamente
2. Saltar de bubblesort para quicksort (reescrita total)
3. Movendo de forma incremental de uma classificação de bolha unidirecional para classificação de shell (se possível).

Veja também a tentativa de Ron Jeffries de criar um solucionador de Sudoku com TDD , que infelizmente não funcionou.

O algoritmo requer uma compreensão significativa dos princípios de design do algoritmo. Com esses princípios, é realmente possível proceder de forma incremental, com um plano, como Peter Norvig fez .

De fato, para algoritmos que exigem esforço de design não trivial, é quase sempre que o esforço é de natureza incremental. Mas cada "incremento", que é minúsculo aos olhos de um projetista de algoritmos, parece um salto quântico (emprestando sua frase) para uma pessoa que não teve o mesmo conhecimento ou experiência com essa família de algoritmos em particular.

É por isso que uma educação básica em teoria de CS combinada com muita prática de programação de algoritmos é igualmente importante. Saber que uma "técnica" específica (pequenos blocos de construção de algoritmos) existe é um longo caminho para dar esses saltos quânticos incrementais.

Existem algumas diferenças importantes entre o progresso incremental nos algoritmos e no TDD.

Uma das diferenças foi mencionada por JeffO : Um teste que verifica a exatidão dos dados de saída é separado de um teste que afirma o desempenho entre diferentes implementações do mesmo algoritmo (ou diferentes algoritmos que tentam fornecer a mesma solução).

No TDD, adiciona-se um novo requisito na forma de um teste, e esse teste inicialmente não deve passar (vermelho). Então o requisito é satisfeito (verde). Finalmente, o código é refatorado.

No desenvolvimento de algoritmos, o requisito geralmente não muda. O teste de verificação da correção dos resultados é gravado primeiro ou logo após a conclusão de uma implementação preliminar (altamente confiável, mas lenta) do algoritmo. Esse teste de correção de dados raramente é alterado; não se muda para falhar (vermelho) como parte do ritual TDD.

Entretanto, nesse aspecto, a análise de dados é distintamente diferente do desenvolvimento de algoritmos, porque os requisitos de análise de dados (os conjuntos de entradas e os resultados esperados) são definidos apenas de maneira vaga na compreensão humana. Assim, os requisitos mudam frequentemente em nível técnico. Essa mudança rápida coloca a análise de dados em algum lugar entre o desenvolvimento de algoritmos e o desenvolvimento geral de aplicativos de software - embora ainda sejam pesados, os requisitos também estão mudando "muito rápido" ao gosto de qualquer programador.

Se o requisito for alterado, normalmente será necessário um algoritmo diferente.

No desenvolvimento de algoritmos, alterar (restringir) o teste de comparação de desempenho para falhar (vermelho) é tolo - ele não fornece nenhuma visão sobre possíveis alterações em seu algoritmo que melhorariam o desempenho.

Portanto, no desenvolvimento de algoritmos, o teste de correção e o desempenho não são testes de TDD. Em vez disso, ambos são testes de regressão . Especificamente, o teste de regressão da correção impede que você faça alterações no algoritmo que quebrará sua correção; o teste de desempenho impede que você faça alterações no algoritmo que o tornará mais lento.

Você ainda pode incorporar o TDD como um estilo de trabalho pessoal, exceto que o ritual "vermelho - verde - refator" não é estritamente necessário nem particularmente benéfico ao processo de pensamento do desenvolvimento de algoritmos.

Eu argumentaria que as melhorias do algoritmo realmente resultam em fazer permutações aleatórias (não necessárias) para os diagramas de fluxo de dados do algoritmo atual, ou misturá-las e combiná-las entre implementações conhecidas anteriormente.

O TDD é usado quando há vários requisitos que podem ser adicionados gradualmente ao seu conjunto de testes.

Como alternativa, se seu algoritmo for orientado por dados, cada parte dos dados / caso de teste poderá ser adicionada de forma incremental. TDD também seria útil. Por esse motivo, uma abordagem "do tipo TDD" de "adicionar novos dados de teste - melhorar o código para manipulá-los corretamente - refatorar" também funcionará no trabalho de análise de dados em aberto, no qual os objetivos dos algoritmos são descritos em humanos. palavras centradas e sua medida de sucesso também julgadas em termos humanos definidos.

Pretende ensinar uma maneira de torná-lo menos irresistível do que tentar satisfazer todos (dezenas ou centenas) de requisitos em uma única tentativa. Em outras palavras, o TDD é ativado quando você pode determinar que determinados requisitos ou metas de expansão podem ser temporariamente ignorados enquanto você implementa alguns rascunhos iniciais da sua solução.

TDD não é um substituto para a ciência da computação. É uma muleta psicológica que ajuda os programadores a superar o choque de ter que atender a muitos requisitos ao mesmo tempo.

Mas se você já possui uma implementação que fornece o resultado correto, o TDD consideraria seu objetivo cumprido e o código pronto para ser entregue (para refatoração ou para outro usuário-programador). Em certo sentido, incentiva você a não otimizar prematuramente seu código, objetivamente, sinalizando que o código é "bom o suficiente" (para passar em todos os testes de correção).

No TDD, há um foco em "micro-requisitos" (ou qualidades ocultas) também. Por exemplo, validações de parâmetros, asserções, lançamento e manipulação de exceções, etc. O TDD ajuda a garantir a correção dos caminhos de execução que não são freqüentemente exercidos no curso normal da execução do software.

Certos tipos de código de algoritmo também contêm essas coisas; estes são passíveis de TDD. Mas como o fluxo de trabalho geral do algoritmo não é TDD, esses testes (em validações de parâmetros, asserções e lançamento e manipulação de exceções) tendem a ser gravados depois que o código de implementação já foi (pelo menos parcialmente) gravado.

Para o seu problema, você teria dois testes:

1. Um teste para garantir que o algoritmo ainda seja preciso. por exemplo, está classificado corretamente?
2. Teste de comparação de desempenho - o desempenho foi aprimorado. Isso pode ser complicado, portanto, ajuda a executar o teste na mesma máquina, nos mesmos dados e limita o uso de outros recursos. Uma máquina dedicada ajuda.

O que testar ou a cobertura completa do teste é discutível, mas acho que as partes complexas do seu aplicativo que precisam ser ajustadas (são muito alteradas) são candidatas perfeitas para testes automatizados. Essas partes do aplicativo geralmente são identificadas muito cedo. Usar uma abordagem TDD com esta peça faria sentido.

Ser capaz de resolver problemas complexos não deve ser prejudicado por uma relutância em tentar várias abordagens. Ter um teste automatizado deve ajudar nessa área. Pelo menos você saberá que não está piorando.

Então, em vez de passar em mais testes como no TDD, você faria "se comportar melhor".

Tipo de.

Você pode testar o tempo de execução e a complexidade. Os testes de tempo de execução precisarão ser um pouco tolerantes para permitir a contenção nos recursos do sistema. Mas, em muitos idiomas, você também pode substituir ou injetar métodos e contar chamadas de funções reais. E, se você estiver confiante de que seu algoritmo atual é subótimo, poderá introduzir um teste que simplesmente exija que sort()invoque compare()menos vezes do que a implementação ingênua.

Ou, você pode comparar sort()em dois conjuntos e garantir que eles sejam escalados nas compare()chamadas de acordo com a complexidade do seu destino (ou mais adiante, se você espera alguma inconsistência).

E, se você puder provar, teoricamente, que um conjunto de tamanho não Ndeve exigir mais do que N*log(N)comparações, pode ser razoável restringir o que você já trabalha sort()a N*log(N)invocações de compare()...

Contudo ...

Atender a um requisito de desempenho ou complexidade não garante que a implementação subjacente seja {AlgorithmX} . E eu diria que isso normalmente é bom. Não importa qual algoritmo é usado, desde que você atinja sua implementação atenda aos seus requisitos, incluindo requisitos importantes de complexidade, desempenho ou recursos.

Mas, se você quiser garantir que um algoritmo específico seja usado, precisará ser mais tedioso e aprofundar muito mais. Coisas como..

• Garantir que exatamente o número esperado de chamadas compare()e swap()(ou o que seja) seja feito
• Agrupar todas as principais funções / métodos e garantir, com um conjunto de dados previsível, que as chamadas ocorram exatamente na ordem esperada
• Examinar o estado de funcionamento após cada uma das N etapas para garantir que ele seja alterado exatamente como esperado

Mas, novamente, se você está tentando garantir que o {AlgorithmX} seja usado em particular, provavelmente existem recursos do {AlgorithmX} com os quais você se importa que são mais importantes para testar do que se o {AlgorithmX} foi realmente usado no final ...

Também lembre-se, o TDD não nega a necessidade de pesquisar, pensar ou planejar no desenvolvimento de software. Ele também não nega a necessidade de brainstorming e experimentação, mesmo que você não possa afirmar com facilidade no Google e no whiteboard no seu conjunto de testes automatizado.