Na maioria das vezes, durante a gravação de loops, geralmente escrevo condições de contorno erradas (por exemplo: resultado errado) ou minhas suposições sobre terminações de loop estão erradas (por exemplo: loop em execução infinita). Embora eu tenha acertado minhas suposições após algumas tentativas e erros, fiquei muito frustrado por causa da falta de um modelo de computação correto na minha cabeça.
/**
* Inserts the given value in proper position in the sorted subarray i.e.
* array[0...rightIndex] is the sorted subarray, on inserting a new value
* our new sorted subarray becomes array[0...rightIndex+1].
* @param array The whole array whose initial elements [0...rightIndex] are
* sorted.
* @param rightIndex The index till which sub array is sorted.
* @param value The value to be inserted into sorted sub array.
*/
function insert(array, rightIndex, value) {
for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
array[j + 1] = array[j];
}
array[j + 1] = value;
};
Os erros que cometi inicialmente foram:
- Em vez de j> = 0, eu o mantive j> 0.
- Fiquei confuso se array [j + 1] = valor ou array [j] = valor.
O que são ferramentas / modelos mentais para evitar esses erros?
programming-practices
loops
CodeYogi
fonte
fonte
j >= 0
é um erro? Eu ficaria mais cauteloso com o fato de você estar acessandoarray[j]
earray[j + 1]
sem primeiro verificar issoarray.length > (j + 1)
.Array.prototype
exemplo de JS). Isso evita que você encontre condições de borda, pois algo comomap
funciona em todas as matrizes. Você pode resolver o problema acima usando slice e concat para evitar o loop completo : codepen.io/anon/pen/ZWovdg?editors=0012 A maneira mais correta de escrever um loop é não escrever um.Respostas:
Teste
Não, sério, teste.
Estou codificando há mais de 20 anos e ainda não confio em mim para escrever um loop corretamente na primeira vez. Escrevo e executo testes que provam que funciona antes que eu suspeite. Teste cada lado de cada condição de contorno. Por exemplo, um
rightIndex
de 0 deve fazer o que? Que tal -1?Mantenha simples
Se os outros não conseguem ver o que ele faz de relance, você está dificultando demais. Fique à vontade para ignorar o desempenho, se isso significa que você pode escrever algo fácil de entender. Apenas a torne mais rápida no caso improvável de que você realmente precisa. E mesmo assim, apenas quando você tiver certeza absoluta de que sabe exatamente o que está atrasando você. Se você pode obter uma melhoria real do Big O , essa atividade pode não ser inútil, mas mesmo assim, torne seu código o mais legível possível.
Desligado por um
Saiba a diferença entre contar os dedos e contar os espaços entre os dedos. Às vezes, os espaços são o que é realmente importante. Não deixe seus dedos te distraírem. Saiba se o seu polegar é um dedo. Saiba se a diferença entre o dedo mindinho e o polegar conta como um espaço.
Comentários
Antes de se perder no código, tente dizer o que você quer dizer em inglês. Afirme suas expectativas claramente. Não explique como o código funciona. Explique por que você está fazendo o que faz. Mantenha os detalhes da implementação fora disso. Deve ser possível refatorar o código sem precisar alterar o comentário.
O melhor comentário é um bom nome.
Se você pode dizer tudo o que precisa dizer com um bom nome, NÃO o diga novamente com um comentário.
Abstrações
Objetos, funções, matrizes e variáveis são todas abstrações que são tão boas quanto os nomes que recebem. Dê a eles nomes que garantam que, quando as pessoas olham dentro delas, não serão surpreendidas pelo que encontrarem.
Nomes curtos
Use nomes curtos para coisas de vida curta.
i
é um nome fino para um índice em um loop apertado agradável em um escopo pequeno que torna seu significado óbvio. Se ai
vida é longa o suficiente para se espalhar, linha após linha, com outras idéias e nomes que podem ser confundidosi
, é hora de dari
um bom e longo nome explicativo.Nomes longos
Nunca encurte um nome simplesmente devido a considerações sobre o comprimento da linha. Encontre outra maneira de definir seu código.
Espaço em branco
Os defeitos adoram se esconder em códigos ilegíveis. Se o seu idioma permitir que você escolha seu estilo de indentação, pelo menos seja consistente. Não faça seu código parecer um fluxo de ruído. O código deve parecer que está em formação.
Construções de loop
Aprenda e revise as estruturas de loop no seu idioma. Observar um depurador destacar um
for(;;)
loop pode ser muito instrutivo. Aprenda todas as formas.while
,do while
,while(true)
,for each
. Use o mais simples que você pode se safar. Procure preparar a bomba . Aprenda o quebreak
econtinue
faça se você os tiver. Saiba a diferença entrec++
e++c
. Não tenha medo de voltar mais cedo, desde que sempre feche tudo o que precisa ser fechado. Por fim, bloqueia ou preferencialmente algo que o marca para fechamento automático quando você o abre: Using statement / Try with Resources .Alternativas de loop
Deixe outra coisa fazer o loop, se puder. É mais fácil para os olhos e já está depurado. Estes vêm em muitas formas: coleções ou riachos que permitem
map()
,reduce()
,foreach()
, e outros tais métodos que se aplicam a lambda. Procure funções especiais comoArrays.fill()
. Também há recursão, mas apenas esperamos que isso facilite as coisas em casos especiais. Geralmente, não use recursão até ver como seria a alternativa.Ah, e teste.
Teste, teste, teste.
Eu mencionei o teste?
Havia mais uma coisa. Não me lembro. Começou com um T ...
fonte
Ao programar, é útil pensar em:
e ao explorar um território desconhecido (como fazer malabarismos com índices), pode ser muito, muito útil não apenas pensar neles, mas torná-los explícitos no código com asserções .
Vamos pegar seu código original:
E verifique o que temos:
array[0..rightIndex]
é classificadaarray[0..rightIndex+1]
é classificado0 <= j <= rightIndex
mas parece um pouco redundante; ou como @Jules observou nos comentários, no final de uma "rodada"for n in [j, rightIndex+1] => array[j] > value
,.array[0..rightIndex+1]
é classificadoAssim, você pode primeiro escrever uma
is_sorted
função, bem como umamin
função que trabalha em uma fatia da matriz, e depois afirmar:Há também o fato de que sua condição de loop é um pouco complicada; convém facilitar as coisas dividindo as coisas:
Agora, o loop é direto (
j
passa derightIndex
para0
).Finalmente, agora isso precisa ser testado:
rightIndex == 0
,rightIndex == array.size - 2
)value
ser menorarray[0]
ou maior quearray[rightIndex]
value
ser igual aarray[0]
,array[rightIndex]
ou algum índice do meioAlém disso, não subestime a difusão . Você possui asserções para detectar erros; portanto, gere uma matriz aleatória e classifique-a usando seu método. Se uma afirmação for acionada, você encontrou um erro e pode estender seu conjunto de testes.
fonte
0 <= j <= rightIndex
ouarray[j] <= value
, apenas repetiria o código. Por outro lado,is_sorted
traz uma nova garantia, portanto é valiosa. Depois, é para isso que servem os testes. Se você chamarinsert([0, 1, 2], 2, 3)
sua função e a saída não for,[0, 1, 2, 3]
então você encontrou um erro.array[j+1] = array[j]; assert(array[j+1] == array[j]);
. Nesse caso, o valor parece muito baixo (é uma cópia / pasta). Se você duplicar o significado, mas expresso de outra maneira, ele se tornará mais valioso.insert()
para que funcionasse copiando de uma matriz antiga para uma nova. Isso pode ser feito sem quebrar os outrosassert
. Mas não este último. Apenas mostra o quão bem os seus outrosassert
foram projetados.Usar teste de unidade / TDD
Se você realmente precisar acessar seqüências através de um
for
loop, poderá evitar os erros através de testes de unidade e, principalmente , de desenvolvimento orientado a testes .Imagine que você precise implementar um método que aceite valores superiores a zero, na ordem inversa. Em quais casos de teste você pôde pensar?
Uma sequência contém um valor que é superior a zero.
Actual:
[5]
. Espera:[5]
.A implementação mais direta que satisfaz os requisitos consiste em simplesmente retornar a sequência de origem ao chamador.
Uma sequência contém dois valores, ambos superiores a zero.
Actual:
[5, 7]
. Espera:[7, 5]
.Agora, você não pode simplesmente retornar a sequência, mas deve revertê-la. Você usaria um
for (;;)
loop, outra construção de linguagem ou um método de biblioteca não importa.Uma sequência contém três valores, um sendo zero.
Actual:
[5, 0, 7]
. Espera:[7, 5]
.Agora você deve alterar o código para filtrar os valores. Novamente, isso pode ser expresso por meio de uma
if
declaração ou de uma chamada para seu método de estrutura favorito.Dependendo do seu algoritmo (como esse é um teste de caixa branca, a implementação é importante), pode ser necessário lidar especificamente com o
[] → []
caso de sequência vazio , ou talvez não. Ou você pode garantir que o caso extremo em que todos os valores são negativos[-4, 0, -5, 0] → []
é tratado corretamente, ou mesmo que os valores negativos de fronteira são:[6, 4, -1] → [4, 6]; [-1, 6, 4] → [4, 6]
. Em muitos casos, no entanto, você terá apenas os três testes descritos acima: qualquer teste adicional não fará com que você altere seu código e, portanto, seria irrelevante.Trabalhe em um nível mais alto de abstração
No entanto, em muitos casos, você pode evitar a maioria desses erros trabalhando em um nível de abstração mais alto, usando bibliotecas / estruturas existentes. Essas bibliotecas / estruturas permitem reverter, classificar, dividir e unir as seqüências, inserir ou remover valores em matrizes ou listas duplamente vinculadas, etc.
Geralmente,
foreach
pode ser usado em vez defor
, tornando irrelevantes as condições de contorno: o idioma faz isso por você. Algumas linguagens, como Python, nem sequer têm afor (;;)
construção, mas apenasfor ... in ...
.Em C #, o LINQ é particularmente conveniente ao trabalhar com sequências.
é muito mais legível e menos propenso a erros em comparação com sua
for
variante:fonte
for(;;)
construção não seria muito descritiva desse loop . Um aspecto importante é que o LINQ (assim como a compreensão de listas em Python e elementos semelhantes em outras linguagens) torna as condições de contorno praticamente irrelevantes, pelo menos no escopo da pergunta original. No entanto, não posso concordar mais sobre a necessidade de entender o que acontece ocultamente ao usar o LINQ, especialmente quando se trata de uma avaliação lenta.forEach
,map
,LazyIterator
, Etc. são fornecidos pelo compilador ou tempo de execução ambiente da linguagem e são, indiscutivelmente, menos provável que seja andando de volta para o balde de tinta em cada iteração. Que, legibilidade e erros pontuais são os dois motivos pelos quais esses recursos foram adicionados às linguagens modernas.Concordo com outras pessoas que dizem testar seu código. No entanto, também é bom acertar em primeiro lugar. Eu tenho uma tendência a errar nas condições de contorno em muitos casos, então desenvolvi truques mentais para evitar esses problemas.
Com uma matriz indexada 0, suas condições normais serão:
ou
Esses padrões devem se tornar uma segunda natureza, você não precisa pensar neles.
Mas nem tudo segue esse padrão exato. Portanto, se você não tiver certeza se escreveu corretamente, aqui está o próximo passo:
Conecte valores e avalie o código em seu próprio cérebro. Torne o pensamento mais simples possível. O que acontece se os valores relevantes forem 0s? O que acontece se eles são 1s?
No seu exemplo, você não tem certeza se deve ser [j] = valor ou [j + 1] = valor. Hora de começar a avaliar manualmente:
O que acontece se você tiver um comprimento de matriz 0? A resposta se torna óbvia: rightIndex deve ser (length - 1) == -1, para que j comece em -1, para inserir no índice 0, é necessário adicionar 1.
Portanto, provamos que a condição final está correta, mas não o interior do loop.
O que acontece se você tiver uma matriz com 1 elemento, 10 e tentarmos inserir um 5? Com um único elemento, rightIndex deve começar em 0. Portanto, na primeira vez no loop, j = 0, então "0> = 0 && 10> 5". Como queremos inserir o 5 no índice 0, os 10 devem ser movidos para o índice 1, então array [1] = array [0]. Como isso acontece quando j é 0, matriz [j + 1] = matriz [j + 0].
Se você tentar imaginar uma grande variedade e o que acontece inserindo-se em algum local arbitrário, seu cérebro provavelmente ficará sobrecarregado. Mas se você se ater a exemplos simples de tamanho 0/1/2, deve ser fácil fazer uma rápida corrida mental e ver onde suas condições de contorno se deterioram.
Imagine que você nunca ouviu falar do problema do poste antes e eu lhe digo que tenho 100 postes em uma linha reta, quantos segmentos entre eles. Se você tentar imaginar 100 postes na sua cabeça, ficará impressionado. Então, qual é o menor número de postes para fazer uma cerca válida? Você precisa de 2 para fazer uma cerca, então imagine 2 postagens, e a imagem mental de um único segmento entre as postagens deixa muito claro. Você não precisa ficar sentado contando mensagens e segmentos porque transformou o problema em algo intuitivamente óbvio para o seu cérebro.
Depois que você achar que está correto, é bom executá-lo através de um teste e garantir que o computador faça o que você acha que deveria, mas nesse momento deve ser apenas uma formalidade.
fonte
for (int i = 0; i < length; i++)
. Quando entrei nesse hábito, parei de usar<=
quase sempre e senti que os loops ficaram mais simples. Masfor (int i = length - 1; i >= 0; i--)
parece excessivamente complicado, comparado com:for (int i=length; i--; )
(o que provavelmente seria ainda mais sensato escrever como umwhile
loop, a menos que eu estivesse tentando fazeri
com um escopo / vida menor). O resultado ainda é executado através do loop com i == length-1 (inicialmente) através de i == 0, com apenas diferença funcional sendo que awhile()
versão termina com i == -1 após o loop (se estiver ativo), em vez de i = = 0.> 0
" requer a funcionalidade desejada, esses caracteres devem ser usados porque são requeridos por esse idioma. Ainda assim, mesmo nesses casos, usar apenas o "> 0
" é mais simples do que executar o processo de duas partes, primeiro subtraindo um e depois também usando ">= 0
". Depois que aprendi que, com um pouco de experiência, adquiri o hábito de precisar usar o sinal de igual (por exemplo, ">= 0
") em minhas condições de teste de loop com muito menos frequência, e o código resultante geralmente parecia mais simples desde então.i-- > 0
, por que não experimentar a piada clássicai --> 0
!É um ponto muito interessante para esta pergunta e gerou este comentário: -
... e Thomas está certo. Não ter uma intenção clara de uma função deve ser uma bandeira vermelha - uma indicação clara de que você deve PARAR imediatamente, pegar um lápis e papel, se afastar do IDE e resolver o problema adequadamente; ou pelo menos sanidade - verifique o que você fez.
Eu já vi tantas funções e classes que se tornaram uma bagunça completa porque os autores tentaram definir a implementação antes de definirem o problema completamente. E é tão fácil de lidar.
Se você não entender completamente o problema, também é improvável que você esteja codificando a solução ideal (em termos de eficiência ou clareza), nem poderá criar testes de unidade genuinamente úteis em uma metodologia TDD.
Tome seu código aqui como exemplo, ele contém várias falhas em potencial que você ainda não considerou, por exemplo: -
Existem alguns outros problemas relacionados ao desempenho e design do código ...
SortedList<t>
em C #)?Array.Insert(...)
? esse código seria mais claro?Existem várias maneiras de melhorar esse código, mas até que você tenha definido corretamente o que você precisa fazer, você não estará desenvolvendo o código, apenas o cortando na esperança de que funcione. Invista o tempo e sua vida ficará mais fácil.
fonte
Erros de um por um são um dos erros de programação mais comuns. Até desenvolvedores experientes entendem isso errado algumas vezes. Linguagens de nível superior geralmente têm construções de iteração como
foreach
oumap
que evitam a indexação explícita por completo. Mas, às vezes, você precisa de uma indexação explícita, como no seu exemplo.O desafio é como pensar em intervalos de células da matriz. Sem um modelo mental claro, torna-se confuso quando incluir ou excluir os pontos finais.
Ao descrever intervalos de matriz, a convenção é incluir o limite inferior, excluir o limite superior . Por exemplo, o intervalo 0..3 são as células 0,1,2. Essas convenções são usadas em idiomas indexados a 0, por exemplo, o
slice(start, end)
método em JavaScript retorna a sub-matriz que começa com índicestart
até, mas não inclui, o índiceend
.É mais claro quando você pensa nos índices de intervalo como descrevendo as bordas entre as células da matriz. A ilustração abaixo é uma matriz de comprimento 9, e os números abaixo das células são alinhados às bordas e é o que é usado para descrever os segmentos da matriz. Por exemplo, é claro na ilustração que o intervalo 2..5 é as células 2,3,4.
Esse modelo é consistente em ter o comprimento da matriz como o limite superior de uma matriz. Uma matriz com comprimento 5 possui células 0..5, o que significa que existem as cinco células 0,1,2,3,4. Isso também significa que o comprimento de um segmento é o limite superior menos o limite inferior, ou seja, o segmento 2..5 possui 5-2 = 3 células.
Ter esse modelo em mente ao iterar para cima ou para baixo torna muito mais claro quando incluir ou excluir os pontos finais. Ao iterar para cima, você precisa incluir o ponto inicial, mas excluir o ponto final. Ao iterar para baixo, você precisa excluir o ponto inicial (o limite superior), mas incluir o ponto final (o limite inferior).
Como você está iterando para baixo no seu código, você precisa incluir o limite inferior, 0, para iterar enquanto
j >= 0
.Dado isso, sua escolha de ter o
rightIndex
argumento representa o último índice no subarray quebra a convenção. Isso significa que você precisa incluir os dois pontos de extremidade (0 e rightIndex) na iteração. Também dificulta a representação do segmento vazio (que você precisa quando inicia a classificação). Você realmente precisa usar -1 como rightIndex ao inserir o primeiro valor. Isso parece bastante antinatural. Parece mais natural terrightIndex
indicado o índice após o segmento, então 0 representa o segmento vazio.É claro que seu código é extremamente confuso porque expande a sub-matriz classificada com uma, substituindo o item imediatamente após a sub-matriz inicialmente classificada. Então você lê o índice j, mas escreve o valor em j + 1. Aqui você deve deixar claro que j é a posição no sub-arranjo inicial, antes da inserção. Quando as operações de índice ficam complicadas, isso me ajuda a fazer um diagrama em um pedaço de papel quadriculado.
fonte
myArray.Length
oumyList.Count
- que é sempre um a mais que o índice "mais à direita" baseado em zero. ... O comprimento da explicação esconde a aplicação prática e simples dessas heurísticas de codificação explícita. A multidão TL; DR está perdendo.A introdução à sua pergunta me faz pensar que você não aprendeu a codificar corretamente. Qualquer pessoa que esteja programando em uma linguagem imperativa por mais de algumas semanas deve realmente estar acertando seus limites de loop pela primeira vez em mais de 90% dos casos. Talvez você esteja se apressando para começar a codificar antes de pensar o suficiente sobre o problema.
Sugiro que você corrija essa deficiência (re) aprendendo a escrever loops - e recomendo algumas horas trabalhando em vários loops com papel e lápis. Tire uma tarde de folga para fazer isso. Depois, gaste 45 minutos ou mais por dia trabalhando no tópico até você realmente entender.
Está tudo muito bem testando, mas você deve estar testando na expectativa de que você geralmente acerte seus limites de loop (e o resto do seu código).
fonte
Talvez eu deva colocar um pouco de carne no meu comentário:
Seu ponto é
Quando eu leio
trial and error
, meus sinos de alarme começam a tocar. É claro que muitos de nós conhecemos o estado de espírito, quando se deseja resolver um pequeno problema e envolveu outras coisas e começou a adivinhar, de uma ou de outra maneira, que o códigoseem
deveria fazer o que deveria fazer. Algumas soluções hackish surgem disso - e algumas são pura genialidade ; mas para ser honesto: a maioria deles não é . Eu inclusive, conhecendo esse estado.Independentemente do seu problema concreto, você fez perguntas sobre como melhorar:
1) Teste
Isso foi dito por outros e eu não teria nada valioso a acrescentar
2) Análise de Problemas
É difícil dar alguns conselhos para isso. Há apenas duas dicas que eu poderia lhe dar, o que provavelmente o ajudará a melhorar suas habilidades nesse tópico:
O Code Katas é uma maneira, o que pode ajudar um pouco.
Code Kata
Um site que eu gosto muito: Code Wars
São problemas relativamente pequenos, que ajudam a aprimorar suas habilidades de programação. E o que eu mais gosto no Code Wars é que você pode comparar sua solução com uma das outras .
Ou talvez, você deve dar uma olhada no Exercism.io, onde obtém feedback da comunidade.
Eu sei - como eu disse acima, às vezes você está em tal estado - que é difícil dividir coisas "simples" em tarefas mais "simples"; mas ajuda muito.
Lembro que, quando aprendi a programar profissionalmente , tive grandes problemas com a depuração do meu código. Qual era o problema? Hybris - O erro não pode estar nessa e em tal região do código, porque eu sei que não pode estar. E em conseqüência? Eu vasculhei o código em vez de analisá-lo e tive que aprender - mesmo que fosse tedioso quebrar meu código para obter instruções .
3) Desenvolver um cinto de ferramentas
Além de conhecer sua linguagem e suas ferramentas - eu sei que essas são as coisas brilhantes sobre as quais os desenvolvedores pensam primeiro - aprendem algoritmos (também conhecidos como leitura).
Aqui estão dois livros para começar:
Introdução aos algortihms
Algoritmos
É como aprender algumas receitas para começar a cozinhar. No começo, você não sabe o que fazer, então precisa procurar o que os chefs anteriores prepararam para você. O mesmo vale para algortihms. Os algoritmos são como cozinhar receitas para refeições comuns (estruturas de dados, classificação, hash etc.) Se você os conhece (pelo menos tente) de cor, você tem um bom ponto de partida.
3a) Conheça construções de programação
Este ponto é um derivado - por assim dizer. Conheça o seu idioma - e melhor: saiba quais construções são possíveis no seu idioma.
Às vezes, um ponto comum para código ruim ou ineficiente é que o programador não sabe a diferença entre os diferentes tipos de loops (
for-
,while-
edo
-loops). Eles são de alguma maneira todos intercambiáveis e utilizáveis; mas, em algumas circunstâncias, escolher outra construção em loop leva a um código mais elegante.E existe o dispositivo de Duff ...
PS:
Sim, devemos tornar a codificação excelente novamente!
Um novo lema para Stackoverflow.
fonte
pre-post
condições até agora e eu aprecio isso.Se eu entendi o problema corretamente, sua pergunta é como pensar em obter loops desde a primeira tentativa, não como garantir que seu loop esteja correto (para o qual a resposta seria testada conforme explicado em outras respostas).
O que considero uma boa abordagem é escrever a primeira iteração sem nenhum loop. Depois de fazer isso, observe o que deve ser alterado entre as iterações.
É um número, como um 0 ou um 1? Então você provavelmente precisará de um para, e bingo, você também terá o seu i. Em seguida, pense quantas vezes você deseja executar a mesma coisa e também terá sua condição final.
Se você não sabe EXATAMENTE quantas vezes ele será executado, não precisará de um tempo, mas de um tempo ou de um tempo.
Tecnicamente, qualquer loop pode ser traduzido para qualquer outro loop, mas o código é mais fácil de ler se você usar o loop correto, então aqui estão algumas dicas:
Se você está escrevendo um if () {...; break;} dentro de um for, precisa de um tempo e já tem a condição
"While" é talvez o loop mais usado em qualquer idioma, mas não deve ser imo. Se você estiver escrevendo bool ok = True; enquanto (marque) {faça alguma coisa e espero que mude ok em algum momento}; então você não precisa de um tempo, mas de um tempo, porque significa que você tem tudo o que precisa para executar a primeira iteração.
Agora um pouco de contexto ... Quando aprendi a programar (Pascal), não falava inglês. Para mim, "for" e "while" não fazia muito sentido, mas a palavra-chave "repeat" (faça enquanto em C) é quase a mesma na minha língua materna, então eu a usaria para tudo. Na minha opinião, a repetição (do while) é o loop mais natural, porque quase sempre você quer que algo seja feito e, em seguida, deseja que seja feito novamente e novamente, até que um objetivo seja alcançado. "For" é apenas um atalho que fornece um iterador e coloca estranhamente a condição no início do código, mesmo que, quase sempre, você queira que algo seja feito até que algo aconteça. Além disso, while é apenas um atalho para if () {do while ()}. Atalhos são bons para mais tarde,
fonte
Vou dar um exemplo mais detalhado de como usar condições pré / pós e invariantes para desenvolver um loop correto. Juntas, essas afirmações são chamadas de especificação ou contrato.
Não estou sugerindo que você tente fazer isso para cada loop. Mas espero que você ache útil ver o processo de pensamento envolvido.
Para isso, traduzirei seu método em uma ferramenta chamada Microsoft Dafny , projetada para provar a exatidão de tais especificações. Ele também verifica o término de cada loop. Observe que o Dafny não possui um
for
loop, então tive que usar umwhile
loop.Por fim, mostrarei como você pode usar essas especificações para projetar uma versão, indiscutivelmente, um pouco mais simples do seu loop. Esta versão mais simples do loop, de fato, tem a condição do loop
j > 0
e a atribuiçãoarray[j] = value
- como foi sua intuição inicial.Dafny nos provará que esses dois loops estão corretos e fazem a mesma coisa.
Farei então uma afirmação geral, com base na minha experiência, sobre como escrever um loop reverso correto, que talvez o ajude a enfrentar essa situação no futuro.
Parte Um - Escrevendo uma Especificação para o Método
O primeiro desafio que enfrentamos é determinar o que o método realmente deve fazer. Para esse fim, projetei condições pré e pós que especificam o comportamento do método. Para tornar a especificação mais exata, aprimorei o método para fazê-lo retornar o índice onde
value
foi inserido.Esta especificação captura totalmente o comportamento do método. Minha principal observação sobre essa especificação é que seria simplificado se o procedimento passasse o valor em
rightIndex+1
vez derightIndex
. Mas como não consigo ver de onde esse método é chamado, não sei que efeito essa mudança teria no restante do programa.Parte Dois - determinando um loop invariável
Agora temos uma especificação para o comportamento do método, temos que adicionar uma especificação do comportamento do loop que convencerá Dafny de que a execução do loop será encerrada e resultará no estado final desejado de
array
.O seguinte é o seu loop original, traduzido para a sintaxe do Dafny, com os invariantes do loop adicionados. Também mudei para retornar o índice onde o valor foi inserido.
Isso verifica em Dafny. Você pode vê-lo seguindo este link . Portanto, seu loop implementa corretamente a especificação de método que escrevi na parte um. Você precisará decidir se essa especificação de método é realmente o comportamento que você deseja.
Observe que Dafny está produzindo uma prova de correção aqui. Essa é uma garantia de correção muito mais forte do que a que pode ser obtida pelo teste.
Parte três - um loop mais simples
Agora que temos uma especificação de método que captura o comportamento do loop. Podemos modificar com segurança a implementação do loop, mantendo a confiança de que não alteramos o comportamento do loop.
Modifiquei o loop para que ele corresponda às suas intuições originais sobre a condição do loop e o valor final de
j
. Eu argumentaria que esse loop é mais simples que o loop que você descreveu na sua pergunta. É mais frequentemente capaz de usarj
do quej+1
.Comece j em
rightIndex+1
Altere a condição do loop para
j > 0 && arr[j-1] > value
Altere a atribuição para
arr[j] := value
Reduza o contador do loop no final do loop em vez do início
Aqui está o código. Observe que os invariantes de loop também são um pouco mais fáceis de escrever agora:
Parte Quatro - conselhos sobre loop reverso
Depois de ter escrito e provado que estava correto em muitos ciclos ao longo de alguns anos, tenho o seguinte conselho geral sobre fazer um loop para trás.
É quase sempre mais fácil pensar e escrever um loop para trás (decrescente) se o decremento for realizado no início do loop e não no final.
Infelizmente, a
for
construção do loop em muitos idiomas dificulta isso.Suspeito (mas não posso provar) que essa complexidade foi o que causou a diferença na sua intuição sobre o que o loop deveria ser e o que realmente precisava ser. Você está acostumado a pensar em loops avançados (incrementais). Quando você deseja escrever um loop para trás (decrescente), tenta criar o loop, tentando reverter a ordem em que as coisas acontecem em um loop para frente (incrementando). Mas, devido à maneira como a
for
construção funciona, você negligenciou para reverter a ordem da atribuição e atualização da variável de loop - o que é necessário para uma verdadeira reversão da ordem das operações entre um loop para trás e para frente.Parte Cinco - bônus
Apenas para completar, eis o código que você obtém se passar
rightIndex+1
para o método em vez derightIndex
. Essa alteração elimina todos os+2
deslocamentos necessários para pensar sobre a correção do loop.fonte
Fazer isso com facilidade e fluência é uma questão de experiência. Mesmo que o idioma não permita que você o expresse diretamente, ou você esteja usando um caso mais complexo do que o simples item interno pode suportar, o que você acha que é um nível mais alto como "visite cada elemento uma vez em ordem de reverência" e o codificador mais experiente traduz isso nos detalhes certos instantaneamente, porque ele fez isso tantas vezes.
Mesmo assim, em casos mais complexos, é fácil errar, porque o que você está escrevendo normalmente não é o comum. Com linguagens e bibliotecas mais modernas, você não escreve a coisa mais fácil porque existe uma construção enlatada ou exige isso. Em C ++, o mantra moderno é "use algoritmos em vez de escrever código".
Portanto, a maneira de garantir que esteja certo, para esse tipo de coisa em particular, é observar as condições de contorno . Rastrear o código em sua cabeça para os poucos casos nas bordas de onde as coisas mudam. Se o
index == array-max
que acontece? Que talmax-1
? Se o código fizer uma curva errada, ele estará em um desses limites. Alguns loops precisam se preocupar com o primeiro ou o último elemento, bem como com a construção de loop, acertando os limites; por exemplo, se você se referea[I]
e oa[I-1]
que acontece quandoI
é o valor mínimo?Além disso, observe os casos em que o número de iterações (corretas) é extremo: se os limites forem atingidos e você tiver 0 iterações, será que isso funcionará sem um caso especial? E quanto a apenas uma iteração, em que o limite mais baixo também é o mais alto ao mesmo tempo?
Examinar os casos de borda (ambos os lados de cada borda) é o que você deve fazer ao escrever o loop e o que deve fazer nas revisões de código.
fonte
Vou tentar ficar longe dos tópicos mencionados em abundância.
Ferramentas
Para mim, a maior ferramenta para escrever melhor
for
e fazerwhile
loops não é escrever nenhumfor
ou fazerwhile
loops.A maioria das linguagens modernas tenta direcionar esse problema de uma maneira ou de outra. Por exemplo, Java, apesar de ter
Iterator
desde o início, que costumava ser um pouco desajeitado de usar, introduziu uma sintaxe de atalho para usá-los mais facilmente em uma versão mais recente. O C # também os possui, etc.Minha linguagem atualmente favorita, Ruby, adotou a abordagem funcional (
.each
,.map
etc.) de frente para frente. Isso é muito poderoso. Acabei de fazer uma contagem rápida em algumas bases de código do Ruby em que estou trabalhando: em cerca de 10.000 linhas de código, existem zerofor
e cerca de 5while
.Se eu fosse forçado a escolher um novo idioma, procurar loops funcionais / baseados em dados como esse seria muito alto na lista de prioridades.
Modelos mentais
Lembre-se de que
while
é o mínimo mínimo de abstração possível, apenas um passo acimagoto
. Na minha opinião,for
piora ainda mais, em vez de melhorar, pois divide as três partes do loop firmemente.Portanto, se estou em um ambiente em que
for
é usado, garanto que todas as três partes sejam simples e sempre iguais. Isso significa que eu vou escreverMas nada muito mais complexo. Talvez, talvez eu tenha uma contagem regressiva às vezes, mas farei o possível para evitá-la.
Se estiver usando
while
, evito travessuras internas complicadas que envolvam a condição do loop. O teste dentro do testewhile(...)
será o mais simples possível, e evitareibreak
o melhor que puder. Além disso, o loop será curto (contando linhas de código) e qualquer quantidade maior de código será fatorada.Especialmente se a condição while for complexa, usarei uma "variável de condição" que é muito fácil de detectar e não colocarei a condição na
while
própria declaração:(Ou algo assim, na medida correta, é claro.)
Isso fornece um modelo mental muito fácil, que é "essa variável está executando de 0 a 10 monotonamente" ou "esse loop é executado até que a variável seja falsa / verdadeira". A maioria dos cérebros parece capaz de lidar com esse nível de abstração muito bem.
Espero que ajude.
fonte
Loops reversos, em particular, podem ser difíceis de raciocinar, porque muitas de nossas linguagens de programação são direcionadas para a iteração direta, tanto na sintaxe comum do loop for quanto pelo uso de intervalos semiabertos baseados em zero. Não estou dizendo que é errado que os idiomas tenham feito essas escolhas; Só estou dizendo que essas escolhas complicam o pensamento sobre loops reversos.
Em geral, lembre-se de que um loop for é apenas açúcar sintático construído em torno de um loop while:
é equivalente a:
(possivelmente com uma camada extra de escopo para manter as variáveis declaradas na etapa init local ao loop).
Isso é bom para muitos tipos de loops, mas a última etapa é desajeitada quando você está andando para trás. Ao trabalhar para trás, acho mais fácil iniciar o índice do loop com o valor após o desejado e mover a
step
parte para o topo do loop, assim:ou, como um loop for:
Isso pode parecer irritante, pois a expressão da etapa está no corpo e não no cabeçalho. Esse é um efeito colateral lamentável da polarização direta inerente na sintaxe do loop for. Por isso, alguns argumentam que você faz o seguinte:
Mas isso é um desastre se sua variável de índice for um tipo não assinado (como pode ser em C ou C ++).
Com isso em mente, vamos escrever sua função de inserção.
Como trabalharemos para trás, deixaremos o índice de loop ser a entrada após o slot de matriz "atual". Eu projetaria a função para levar o tamanho do número inteiro ao invés de um índice para o último elemento, porque os intervalos semi-abertos são a maneira natural de representar os intervalos na maioria das linguagens de programação e porque nos oferece uma maneira de representar um array vazio sem recorrer para um valor mágico como -1.
Enquanto o novo valor for menor que o elemento anterior , continue mudando. Claro, o elemento anterior pode ser verificado somente se não é um elemento anterior, para que primeiro tem que verificar que não estamos bem no começo:
Isso deixa
j
exatamente onde queremos o novo valor.A programação de pérolas de Jon Bentley fornece uma explicação muito clara sobre o tipo de inserção (e outros algoritmos), o que pode ajudar a criar seus modelos mentais para esses tipos de problemas.
fonte
Você está simplesmente confuso sobre o que um
for
loop realmente faz e a mecânica de como ele funciona?Pode ser útil reescrever esse código usando uma construção diferente. Aqui está o mesmo usando um loop while:
Aqui estão algumas outras sugestões:
for
loops. Você os usará o tempo todo. Sugiro que você percorra um loop for em um depurador para ver como ele é executado.* Observe que, enquanto eu uso o termo "incremento", são apenas alguns códigos que estão depois do corpo e antes da verificação da condição. Pode ser um decréscimo ou nada.
fonte
Tentativa de insight adicional
Para algoritmos não triviais com loops, você pode tentar o seguinte método:
i
ouj
, e aumente / diminua essas variáveis conforme necessário (mas ainda sem nenhum loop);Seu problema
Escreva o corpo do loop manualmente várias vezes
Vamos usar uma matriz fixa com 4 posições e tentar escrever o algoritmo manualmente, sem loops:
Reescreva, removendo valores codificados
Traduzir para um loop
Com
while
:Refatore / reescreva / otimize o loop da maneira que desejar:
Com
while
:com
for
:PS: o código assume que a entrada é válida e esse array não contém repetições;
fonte
É por isso que eu evitaria escrever loops que operam em índices brutos, em favor de operações mais abstratas, sempre que possível.
Nesse caso, eu faria algo assim (em pseudo código):
fonte
No seu exemplo, o corpo do loop é bastante óbvio. E é óbvio que algum elemento precisa ser alterado no final. Então você escreve o código, mas sem o início do loop, a condição final e a atribuição final.
Então você se afasta do código e descobre qual é a primeira jogada que precisa ser executada. Você altera o início do loop para que o primeiro movimento seja correto. Você se afasta do código novamente e descobre qual é a última jogada que precisa ser executada. Você altera a condição final para que o último movimento esteja correto. E, finalmente, você se afasta do seu código e descobre qual deve ser a atribuição final e corrige o código de acordo.
fonte