Comment écrire des boucles correctes?

65

La plupart du temps, lors de l'écriture de boucles, j'écris généralement de mauvaises conditions aux limites (par exemple: résultat erroné) ou mes hypothèses sur les terminaisons de boucle sont erronées (par exemple: boucle tournant à l'infini). Bien que mes hypothèses soient correctes après quelques essais et erreurs, je me suis senti trop frustré à cause du manque de modèle informatique correct dans ma tête.

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

Les erreurs que j'ai commises initialement étaient:

  1. Au lieu de j> = 0, je l’ai gardé j> 0.
  2. Vous avez confondu si tableau [j + 1] = valeur ou tableau [j] = valeur.

Quels sont les outils / modèles mentaux pour éviter de telles erreurs?

CodeYogi
la source
6
Dans quelles circonstances croyez-vous que j >= 0c'est une erreur? Je serais plus méfiant du fait que vous y accédez array[j]et array[j + 1]sans le vérifier au préalable array.length > (j + 1).
Ben Cottrell
5
semblable à ce que @LightnessRacesinOrbit a dit, vous résolvez probablement des problèmes qui ont déjà été résolus. En règle générale, toute boucle que vous devez effectuer sur une structure de données existe déjà dans un module ou une classe de base ( Array.prototypedans l'exemple de JS). Cela vous évite de rencontrer des conditions de bord car quelque chose comme mapfonctionne sur tous les tableaux. Vous pouvez résoudre ce qui précède en utilisant slice et concat pour éviter de boucler tous ensemble: codepen.io/anon/pen/ZWovdg?editors=0012 Le moyen le plus correct d’écrire une boucle est de ne pas en écrire du tout.
Jed Schneider
13
En fait, allez-y et résolvez les problèmes résolus. C'est ce qu'on appelle la pratique. Ne vous souciez pas de les publier. Autrement dit, à moins que vous ne trouviez le moyen d’améliorer les solutions. Cela dit, réinventer la roue implique plus que la roue. Cela implique un système de contrôle qualité complet et un support client. Pourtant, les jantes personnalisées sont agréables.
candied_orange
53
Je crains que nous ne soyons dans la mauvaise direction ici. Donner des conneries à CodeYogi parce que son exemple fait partie d'un algorithme bien connu est plutôt sans fondement. Il n'a jamais prétendu avoir inventé quelque chose de nouveau. Il demande comment éviter certaines erreurs de limites très courantes lors de l'écriture d'une boucle. Les bibliothèques ont parcouru un long chemin, mais je vois toujours un avenir pour ceux qui savent écrire des boucles.
candied_orange
5
En général, lorsque vous utilisez des boucles et des index, vous devez apprendre que les index pointent entre des éléments et se familiarisent avec les intervalles semi-ouverts (en réalité, ils sont les deux côtés du même concept). Une fois que vous avez ces informations, la plupart des boucles / index grattent complètement.
Matteo Italia

Réponses:

208

Tester

Non, sérieusement, testez.

Je code depuis plus de 20 ans et je n’ai toujours pas confiance en moi pour écrire une boucle correctement la première fois. J'écris et exécute des tests qui prouvent que cela fonctionne avant que je suppose que cela fonctionne. Testez chaque côté de chaque condition limite. Par exemple, un rightIndex0 devrait faire quoi? Que diriez-vous de -1?

Rester simple

Si les autres ne peuvent pas voir ce que cela fait en un coup d'œil, vous le rendez trop difficile. N'hésitez pas à ignorer les performances si cela signifie que vous pouvez écrire quelque chose de facile à comprendre. Rendez-le seulement plus rapidement dans le cas peu probable où vous en auriez vraiment besoin. Et même alors seulement une fois que vous êtes absolument sûr de savoir exactement ce qui vous ralentit. Si vous pouvez obtenir une amélioration réelle de Big O , cette activité n’est peut-être pas vaine, mais même dans ce cas, rendez votre code aussi lisible que possible.

Par un

Connaissez la différence entre compter vos doigts et compter les espaces entre vos doigts. Parfois, les espaces sont ce qui est réellement important. Ne laissez pas vos doigts vous distraire. Savoir si votre pouce est un doigt. Sachez si l’écart entre votre petit doigt et votre pouce compte comme un espace.

commentaires

Avant de vous perdre dans le code, essayez de dire ce que vous voulez dire en anglais. Énoncez clairement vos attentes. N'expliquez pas comment fonctionne le code. Explique pourquoi tu le fais faire ce qu'il fait. Gardez les détails de mise en œuvre en dehors de cela. Il devrait être possible de refactoriser le code sans avoir à changer le commentaire.

Le meilleur commentaire est un bon nom.

Si vous pouvez dire tout ce que vous devez dire avec un bon nom, ne le répétez pas avec un commentaire.

Les abstractions

Les objets, les fonctions, les tableaux et les variables sont des abstractions qui ne valent que les noms qui leur sont donnés. Donnez-leur des noms qui garantissent que lorsque les gens regarderont à l'intérieur, ils ne seront pas surpris par ce qu'ils trouveront.

Noms courts

Utilisez des noms courts pour des choses de courte durée. iest un bon nom pour un index dans une belle boucle serrée dans une petite portée qui le rend évident. Si la ivie est suffisamment longue pour se disperser, ligne après ligne, avec d'autres idées et noms avec lesquels on peut confondre, iil est temps de donner iun beau nom explicatif.

Noms longs

Ne raccourcissez jamais un nom simplement pour des raisons de longueur de ligne. Trouvez un autre moyen de présenter votre code.

Espace blanc

Les défauts aiment se cacher dans un code illisible. Si votre langue vous permet de choisir votre style d'indentation, soyez au moins cohérent. Ne faites pas que votre code ressemble à un flot de bruit. Le code devrait ressembler à une marche en formation.

Constructions en boucle

Apprenez et passez en revue les structures de boucle dans votre langue. Regarder un débogueur mettre en évidence une for(;;)boucle peut être très instructif. Apprenez toutes les formes. while, do while, while(true), for each. Utilisez le plus simple possible. Regardez en amorçant la pompe . Apprenez quoi breaket continuefaites si vous en avez. Connaître la différence entre c++et ++c. N'ayez pas peur de rentrer tôt, à condition de toujours fermer tout ce qui doit être fermé. Enfin bloque ou de préférence quelque chose qui le marque pour la fermeture automatique lorsque vous l'ouvrez: Using statement / Try with Resources .

Boucles alternatives

Laissez quelque chose d'autre faire la boucle si vous le pouvez. C'est plus facile pour les yeux et déjà débogué. Ceux - ci se présentent sous plusieurs formes: collections ou cours d' eau qui permettent map(), reduce(), foreach(), et d' autres méthodes qui appliquent un lambda. Rechercher des fonctions spécialisées comme Arrays.fill(). Il y a aussi la récursivité, mais attendez-vous à ce que cela facilite les choses dans des cas particuliers. En règle générale, n'utilisez pas la récursivité jusqu'à ce que vous voyiez à quoi ressemblerait l'alternative.

Oh, et test.

Tester, tester, tester.

Ai-je mentionné le test?

Il y avait encore une chose. Je ne m'en souviens pas. Commencé avec un T ...

confits_orange
la source
36
Bonne réponse, mais peut-être devriez-vous mentionner le test. Comment traite-t-on la boucle infinie dans le test unitaire? Une telle boucle ne casse-t-elle pas les tests ???
GameAlchemist
139
@GameAlchemist C'est le test de la pizza. Si mon code n'arrête pas de fonctionner pendant le temps qu'il me faut pour faire une pizza, je commence à soupçonner que quelque chose ne va pas. Bien sûr, le problème qui se pose à Alan Turing n’est pas guéri, mais au moins, je fais sortir une pizza du marché.
candied_orange
12
@ CodeYogi - en fait, ça peut être très proche. Commencez avec un test qui fonctionne sur une seule valeur. Implémentez le code sans boucle. Ensuite, écrivez un test qui fonctionne sur deux valeurs. Implémenter la boucle. Il est très peu probable que vous obteniez une mauvaise condition limite sur la boucle si vous procédez ainsi, car dans presque toutes les circonstances, l’un ou l’autre de ces deux tests échouera si vous faites une telle erreur.
Jules
15
@CodeYogi Dude tous les crédits dus à TDD mais aux tests >> TDD. Afficher une valeur peut être un test, obtenir un deuxième regard sur votre code est un test (vous pouvez formaliser cela comme une révision de code, mais souvent je ne fais que prendre quelqu'un pour une conversation de 5 minutes). Un test est une chance que vous exprimiez votre intention d'échouer. Enfer, vous pouvez tester votre code en discutant d'une idée avec votre mère. J'ai trouvé des bugs dans mon code lorsque je regardais la tuile de la douche. Le TDD est une discipline formalisée efficace que l’on ne trouve pas dans tous les magasins. Je n'ai jamais codé une fois où les gens n'ont pas testé.
candied_orange
12
Je codais et testais des années et des années avant d'avoir entendu parler de TDD. C'est seulement maintenant que je réalise la corrélation de ces années avec les années passées à coder sans porter de pantalon.
candied_orange
72

Lors de la programmation, il est utile de penser à:

et en explorant un territoire inexploré (comme jongler avec des indices) , il peut être très, très , utile de ne pas penser à peu près , mais les rendre réellement les explicite dans le code avec des affirmations .

Prenons votre code original:

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

Et vérifiez ce que nous avons:

  • condition préalable: array[0..rightIndex]est trié
  • post-condition: array[0..rightIndex+1]est trié
  • invariant: 0 <= j <= rightIndexmais cela semble un peu redondant; ou @Jules noté dans les commentaires, à la fin d'un « rond », for n in [j, rightIndex+1] => array[j] > value.
  • invariant: à la fin d'un "round", array[0..rightIndex+1]est trié

Ainsi, vous pouvez d’abord écrire une is_sortedfonction ainsi qu’une minfonction travaillant sur une tranche de tableau, puis affirmer:

function insert(array, rightIndex, value) {
    assert(is_sorted(array[0..rightIndex]));

    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];

        assert(min(array[j..rightIndex+1]) > value);
        assert(is_sorted(array[0..rightIndex+1]));
    }   
    array[j + 1] = value; 

    assert(is_sorted(array[0..rightIndex+1]));
};

Il y a aussi le fait que votre condition de boucle est un peu compliquée; vous voudrez peut-être vous simplifier la tâche en séparant les choses:

function insert(array, rightIndex, value) {
    assert(is_sorted(array[0..rightIndex]));

    for (var j = rightIndex; j >= 0; j--) {
        if (array[j] <= value) { break; }

        array[j + 1] = array[j];

        assert(min(array[j..rightIndex+1]) > value);
        assert(is_sorted(array[0..rightIndex+1]));
    }   
    array[j + 1] = value; 

    assert(is_sorted(array[0..rightIndex+1]));
};

Maintenant, la boucle est simple ( jva de rightIndexà 0).

Enfin, cela doit maintenant être testé:

  • penser aux conditions aux limites ( rightIndex == 0, rightIndex == array.size - 2)
  • penser à valueêtre plus petit array[0]ou plus grand quearray[rightIndex]
  • penser à valueêtre égal à array[0], array[rightIndex]ou un indice moyen

Ne sous-estimez pas non plus le fuzzing . Vous avez des assertions en place pour détecter les erreurs, alors générez un tableau aléatoire et triez-le en utilisant votre méthode. Si une assertion est déclenchée, vous trouvez un bogue et pouvez étendre votre suite de tests.

Matthieu M.
la source
8
@CodeYogi: Avec ... des tests. Le problème, c’est qu’il peut être peu pratique de tout exprimer en assertions: si l’assertion ne fait que répéter le code, elle n’apporte rien de nouveau (la répétition n’aide pas à la qualité). C'est pourquoi ici je n'ai pas affirmé dans la boucle que 0 <= j <= rightIndexou array[j] <= value, cela ne ferait que répéter le code. D'autre part, is_sortedapporte une nouvelle garantie, donc c'est précieux. Ensuite, c’est à quoi servent les tests. Si vous appelez insert([0, 1, 2], 2, 3)votre fonction et que la sortie ne [0, 1, 2, 3]s'affiche pas, vous avez trouvé un bogue.
Matthieu M.
3
@MatthieuM. ne négligez pas la valeur d'une assertion simplement parce qu'elle duplique le code. Enfait, ces affirmations peuvent être très utiles si vous décidez de réécrire le code. Les tests ont parfaitement le droit de faire double emploi. Déterminez plutôt si l’assertion est tellement couplée à une implémentation de code unique que toute réécriture invaliderait l’assertion. C'est à ce moment-là que vous perdez votre temps. Bonne réponse au fait.
candied_orange
1
@CandiedOrange: En dupliquant le code, j'entends littéralement array[j+1] = array[j]; assert(array[j+1] == array[j]);. Dans ce cas, la valeur semble très très basse (c'est un copier / coller). Si vous dupliquez le sens mais exprimé d'une autre manière, alors il devient plus précieux.
Matthieu M.
10
Les règles de Hoare: aider à écrire des boucles correctes depuis 1969. "Pourtant, même si ces techniques sont connues depuis plus d'une décennie, la plupart des programmeurs n'en ont jamais entendu parler".
Joker_vD
1
@MatthieuM. Je conviens qu'il a très peu de valeur. Mais je ne pense pas que cela soit causé par un copier / coller. Supposons que je veuille refactoriser insert()pour que cela fonctionne en copiant un ancien tableau vers un nouveau tableau. Cela peut être fait sans casser les autres assert. Mais pas ce dernier. Cela montre simplement à quel point vos autres assertont été conçus.
candied_orange
29

Utiliser les tests unitaires / TDD

Si vous avez vraiment besoin d'accéder à des séquences via une forboucle, vous pouvez éviter les erreurs grâce aux tests unitaires , et plus particulièrement au développement piloté par les tests .

Imaginez que vous deviez implémenter une méthode prenant les valeurs supérieures à zéro, dans l'ordre inverse. À quels cas de test pouvez-vous penser?

  1. Une séquence contient une valeur supérieure à zéro.

    Actual: [5]. Attendu: [5].

    La mise en œuvre la plus simple qui satisfait aux exigences consiste à simplement renvoyer la séquence source à l'appelant.

  2. Une séquence contient deux valeurs, toutes deux supérieures à zéro.

    Actual: [5, 7]. Attendu: [7, 5].

    Maintenant, vous ne pouvez pas simplement renvoyer la séquence, mais vous devez l'inverser. Souhaitez-vous utiliser une for (;;)boucle, une autre construction de langage ou une méthode de bibliothèque n'a pas d'importance.

  3. Une séquence contient trois valeurs, l'une étant zéro.

    Actual: [5, 0, 7]. Attendu: [7, 5].

    Maintenant, vous devriez changer le code pour filtrer les valeurs. Là encore, cela pourrait être exprimé par un ifénoncé ou un appel à votre méthode de cadre préférée.

  4. En fonction de votre algorithme (puisqu'il s'agit de tests en boîte blanche, l'implémentation est importante), vous devrez peut-être gérer spécifiquement le [] → []cas de séquence vide , ou peut-être pas. Ou vous pouvez faire en sorte que le cas limite où toutes les valeurs sont négatives [-4, 0, -5, 0] → []est traitée correctement, ou même que les valeurs négatives aux limites sont: [6, 4, -1] → [4, 6]; [-1, 6, 4] → [4, 6]. Dans de nombreux cas, toutefois, vous ne subirez que les trois tests décrits ci-dessus: aucun test supplémentaire ne vous fera changer de code et ne serait donc pas pertinent.

Travailler à un niveau d'abstraction supérieur

Cependant, dans de nombreux cas, vous pouvez éviter la plupart de ces erreurs en travaillant à un niveau d'abstraction plus élevé, en utilisant des bibliothèques / frameworks existants. Ces bibliothèques / frameworks permettent de restaurer, trier, scinder et joindre les séquences, d’insérer ou de supprimer des valeurs dans des tableaux ou des listes à double liaison, etc.

Habituellement, foreachpeut être utilisé à la place de for, ce qui rend la vérification des conditions aux limites non pertinente: la langue le fait pour vous. Certaines langues, telles que Python, n'ont même pas la for (;;)construction, mais seulement for ... in ....

En C #, LINQ est particulièrement pratique lorsque vous travaillez avec des séquences.

var result = source.Skip(5).TakeWhile(c => c > 0);

est beaucoup plus lisible et moins sujet aux erreurs par rapport à sa forvariante:

for (int i = 5; i < source.Length; i++)
{
    var value = source[i];
    if (value <= 0)
    {
        break;
    }

    yield return value;
}
Arseni Mourzenko
la source
3
De votre question initiale, j’ai l’impression que le choix consiste d’une part à utiliser TDD et à trouver la bonne solution, et d’autre part à sauter la partie test et à obtenir les mauvaises conditions aux limites.
Arseni Mourzenko
18
Merci d’être celui qui a mentionné l’éléphant dans la pièce: ne pas utiliser de boucles du tout . Pourquoi les gens continuent de coder comme en 1985 (et je suis généreux) me dépasse. BOCTAOE.
Jared Smith
4
@ JaredSmith Une fois que l'ordinateur a exécuté ce code, combien voulez-vous parier qu'il n'y a pas d'instruction de saut? En utilisant LINQ, vous faites abstraction de la boucle, mais elle est toujours là. J'ai expliqué cela à des collègues qui n'avaient pas appris le dur travail du peintre Shlemiel . Faute de comprendre où les boucles se produisent, même si elles sont abstraites dans le code et que le code est beaucoup plus lisible, il en résulte presque invariablement des problèmes de performances qu'il est difficile d'expliquer, et encore moins de corriger.
un CVn
6
@ MichaelKjörling: lorsque vous utilisez LINQ, la boucle est là, mais une for(;;)construction ne serait pas très descriptive de cette boucle . Un aspect important est que LINQ (ainsi que les listes de compréhension en Python et les éléments similaires dans d'autres langues) rend les conditions aux limites généralement non pertinentes, du moins dans le cadre de la question initiale. Cependant, je suis tout à fait d'accord sur la nécessité de comprendre ce qui se passe sous le capot lors de l'utilisation de LINQ, en particulier en matière d'évaluation paresseuse.
Arseni Mourzenko
4
@ MichaelKjörling Je ne parlais pas nécessairement de LINQ et je ne vois pas très bien ce que vous voulez dire. forEach, map, LazyIterator, Etc. sont fournies par l'environnement du compilateur ou de l' exécution de la langue et sont sans doute moins susceptibles d'être marcher vers le seau de peinture à chaque itération. C’est cela, la lisibilité et les erreurs particulières, ce sont les deux raisons pour lesquelles ces fonctionnalités ont été ajoutées aux langues modernes.
Jared Smith
15

Je suis d'accord avec d'autres personnes qui disent tester votre code. Cependant, il est également bon de bien faire les choses en premier lieu. J'ai souvent tendance à me tromper sur les conditions aux limites et j'ai donc développé des astuces mentales pour prévenir de tels problèmes.

Avec un tableau indexé 0, vos conditions normales vont être:

for (int i = 0; i < length; i++)

ou

for (int i = length - 1; i >= 0; i--)

Ces modèles devraient devenir une seconde nature, vous ne devriez pas avoir à y penser du tout.

Mais tout ne suit pas exactement ce modèle. Donc, si vous n'êtes pas sûr d'avoir bien écrit, voici votre prochaine étape:

Branchez les valeurs et évaluez le code dans votre propre cerveau. Faites en sorte que la réflexion soit aussi simple que possible. Que se passe-t-il si les valeurs pertinentes sont des 0? Que se passe-t-il s'ils sont 1?

for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
    array[j + 1] = array[j];
}   
array[j + 1] = value;

Dans votre exemple, vous ne savez pas si cela devrait être [j] = valeur ou [j + 1] = valeur. Il est temps de commencer à l’évaluer manuellement:

Qu'advient-il si vous avez une longueur de tableau 0? La réponse devient évidente: rightIndex doit être (longueur - 1) == -1, donc j commence à -1, donc pour insérer à l’indice 0, vous devez ajouter 1.

Nous avons donc prouvé que la condition finale était correcte, mais pas à l’intérieur de la boucle.

Qu'advient-il si vous avez un tableau avec 1 élément, 10, et nous essayons d'insérer un 5? Avec un seul élément, rightIndex devrait commencer à 0. Donc, la première fois dans la boucle, j = 0, donc "0> = 0 && 10> 5". Puisque nous voulons insérer le 5 à l'index 0, le 10 doit être déplacé vers l'index 1, donc tableau [1] = tableau [0]. Comme cela se produit lorsque j est égal à 0, array [j + 1] = array [j + 0].

Si vous essayez d'imaginer un large réseau et ce qui se passe lors de l'insertion dans un emplacement arbitraire, votre cerveau sera probablement submergé. Mais si vous vous en tenez à des exemples simples de taille 0/1/2, il devrait être facile de faire un survol mental rapide et de voir où vos conditions aux limites se dégradent.

Imaginez que vous n’ayez jamais entendu parler du problème des poteaux de clôture et je vous dis que j’ai 100 poteaux de clôture en ligne droite, combien de segments les sépare. Si vous essayez d’imaginer 100 poteaux de clôture dans votre tête, vous allez être submergé. Alors, quel est le plus petit nombre de poteaux de clôture pour faire une clôture valide? Vous avez besoin de 2 pour faire une clôture, alors imaginez 2 poteaux, et l’image mentale d’un segment unique entre les poteaux le rend très clair. Vous n'êtes pas obligé de rester là à compter les posts et les segments car vous avez transformé le problème en quelque chose de intuitivement évident pour votre cerveau.

Une fois que vous pensez que c'est correct, il est bon de le tester et de vous assurer que l'ordinateur fait ce que vous pensez, mais ce devrait être une simple formalité.

Bryce Wagner
la source
4
J'aime vraiment for (int i = 0; i < length; i++). Une fois que j’ai pris cette habitude, j’ai arrêté de l’utiliser <=presque aussi souvent et j’ai eu l’impression que les boucles devenaient plus simples. Mais cela for (int i = length - 1; i >= 0; i--)semble trop compliqué comparé à: for (int i=length; i--; )(ce qui serait probablement encore plus judicieux d’écrire en tant que whileboucle à moins que je ne cherche à faire en isorte que la portée et la durée de vie soient plus petites). Le résultat continue à parcourir la boucle avec i == longueur-1 (initialement) à travers i == 0, la seule différence fonctionnelle étant que la while()version se termine par i == -1 après la boucle (si elle reste active), au lieu de i = = 0.
TOOGAM
2
@TOOGAM (int i = length; i--;;) fonctionne en C / C ++ car 0 est évalué comme faux, mais toutes les langues n'ont pas cette équivalence. Je suppose que vous pourriez dire que je--> 0.
Bryce Wagner
Naturellement, si vous utilisez une langue qui " > 0" requiert la fonctionnalité souhaitée, vous devez utiliser ces caractères, car ils sont requis par cette langue. Pourtant, même dans ces cas, en utilisant simplement le « > 0» est plus simple que de faire le processus en deux parties de première soustraction d' un, puis aussi en utilisant « >= 0». Une fois que j’ai appris que, grâce à un peu d’expérience, j’ai pris l’habitude de devoir utiliser le signe égal (par exemple, " >= 0") dans mes conditions de test de boucle beaucoup moins fréquemment, et le code résultant se sent généralement plus simple depuis.
TOOGAM
1
@BryceWagner si vous devez faire i-- > 0, pourquoi ne pas essayer la blague classique, i --> 0!
dimanche
3
@porglezomp Ah, oui, le va à l' opérateur . La plupart des langages de type C, y compris C, C ++, Java et C #, ont celui-là.
un CVn
11

Je suis trop frustré à cause du manque de modèle informatique correct dans ma tête.

Est un point très intéressant à cette question et il a généré ce commentaire: -

Il n'y a qu'un moyen: mieux comprendre votre problème. Mais c'est aussi général que votre question est. - Thomas Junk

... et Thomas a raison. Ne pas avoir l'intention claire d'une fonction devrait être un drapeau rouge - une indication claire que vous devez immédiatement ARRÊTER, saisir un crayon et du papier, vous éloigner de l'EDI et décomposer le problème correctement; ou du moins votre santé mentale - vérifiez ce que vous avez fait.

J'ai vu tellement de fonctions et de classes devenir un désordre complet parce que les auteurs ont tenté de définir l'implémentation avant d'avoir complètement défini le problème. Et c'est si facile à gérer.

Si vous ne comprenez pas bien le problème, il est également peu probable que vous codiez la solution optimale (en termes d'efficacité ou de clarté) et que vous ne pourrez pas créer de tests unitaires réellement utiles dans une méthodologie TDD.

Prenez votre code ici à titre d'exemple, il contient un certain nombre de défauts potentiels que vous n'avez pas encore pris en compte, par exemple: -

  • Et si rightIndex est trop bas? (indice: il va entraîner la perte de données)
  • Et si rightIndex est en dehors des limites du tableau? (obtiendrez-vous une exception, ou venez-vous de créer vous-même un buffer overflow?)

Il existe quelques autres problèmes liés aux performances et à la conception du code ...

  • Ce code devra-t-il être mis à l'échelle? Garder le tableau trié est-il la meilleure option, ou devriez-vous regarder d'autres options (comme une liste chaînée?)
  • pouvez-vous être sûr de vos hypothèses? (pouvez-vous garantir que le tableau sera trié, et si ce n'était pas le cas?)
  • réinventez-vous la roue? Les tableaux triés sont un problème bien connu, avez-vous étudié les solutions existantes? Existe-t-il une solution disponible dans votre langue (comme SortedList<t>en C #)?
  • Devriez-vous copier manuellement une entrée de tableau à la fois? ou votre langage fournit-il des fonctions communes comme celles de JScript Array.Insert(...)? ce code serait-il plus clair?

Ce code peut être amélioré de nombreuses façons, mais tant que vous n'avez pas correctement défini ce que vous avez besoin de faire, vous ne développez pas de code, vous le corrigez simplement dans l'espoir que cela fonctionnera. Investissez le temps dedans et votre vie deviendra plus facile.

James Snell
la source
2
Même si vous transmettez vos index à une fonction existante (telle que Array.Copy), il peut toujours être nécessaire de réfléchir pour obtenir les conditions liées correctes. Imaginer ce qui se passe dans les situations 0 longueur et 1 longueur et 2 longueur peut être le meilleur moyen de vous assurer que vous n'en copiez pas trop ou trop peu.
Bryce Wagner
@BryceWagner - Absolument vrai, mais sans une idée précise du problème, c'est que vous êtes en train de résoudre le problème, vous allez passer beaucoup de temps à se débattre dans le noir dans une stratégie de «succès et d'espoir» qui est de loin le PO plus gros problème à ce stade.
James Snell
2
@ CodeYogi - vous avez et comme d'autres l'ont souligné, vous avez assez mal divisé le problème en sous-problèmes, raison pour laquelle un certain nombre de réponses mentionnent votre approche de la résolution du problème comme moyen de l'éviter. Ce n'est pas quelque chose que vous devriez prendre personnellement, juste l'expérience de ceux d'entre nous qui y sommes allés.
James Snell
2
@ CodeYogi, je pense que vous avez peut-être confondu ce site avec Stack Overflow. Ce site est l’équivalent d’une session de questions-réponses sur un tableau blanc et non sur un terminal informatique. "Montre-moi le code" est une indication assez explicite que tu es sur le mauvais site.
Wildcard
2
@Wildcard +1: "Montre-moi le code" est, pour moi, un excellent indicateur de la raison pour laquelle cette réponse est correcte et que je dois peut-être trouver des moyens de mieux démontrer qu'il s'agit d'un problème de facteur humain / de conception qui ne peut que être modifié par le processus humain - aucune quantité de code ne peut l’enseigner.
James Snell
10

Les erreurs off-by-one sont l’une des erreurs de programmation les plus courantes. Même les développeurs expérimentés se trompent parfois. Les langages de niveau supérieur ont généralement des constructions d'itération similaires foreachou mapévitant toute indexation explicite. Mais parfois, vous avez besoin d'une indexation explicite, comme dans votre exemple.

Le défi est de savoir comment penser les plages de cellules d'un tableau. Sans modèle mental clair, il devient difficile de savoir quand inclure ou exclure les points finaux.

Lors de la description des plages d'un tableau, la convention est d' inclure la limite inférieure, exclure la limite supérieure . Par exemple, la plage 0..3 correspond aux cellules 0,1,2. Ces conventions sont utilisées dans des langues 0 indexées, par exemple la slice(start, end)méthode JavaScript renvoie le sous - tableau commençant par l' index startjusqu'à l' exclusion des index end.

Il est plus clair de penser que les index de plage décrivent les limites entre les cellules d’un tableau. L'illustration ci-dessous est un tableau de longueur 9, et les nombres situés sous les cellules sont alignés sur les bords et correspondent à la description des segments de tableau. Par exemple, il ressort clairement de l'illustration que la plage 2..5 correspond aux cellules 2,3,4.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │   -- cell indexes, e.g array[3]
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
0   1   2   3   4   5   6   7   8   9   -- segment bounds, e.g. slice(2,5) 
        └───────────┘ 
          range 2..5

Ce modèle est cohérent avec le fait que la longueur du tableau soit la limite supérieure d’un tableau. Un tableau de longueur 5 a les cellules 0..5, ce qui signifie qu'il y a les cinq cellules 0,1,2,3,4. Cela signifie également que la longueur d'un segment est la limite supérieure moins la limite inférieure, c'est-à-dire que le segment 2..5 a 5-2 = 3 cellules.

Avoir ce modèle à l'esprit lors d'une itération vers le haut ou vers le bas rend beaucoup plus clair le moment d'inclure ou d'exclure les points finaux. Lorsque vous effectuez une itération vers le haut, vous devez inclure le point de départ mais exclure le point de fin. Lorsque vous effectuez une itération vers le bas, vous devez exclure le point de départ (la limite supérieure) mais inclure le point final (la limite inférieure).

Puisque vous parcourez votre code itérativement, vous devez inclure la limite basse, 0, pour pouvoir itérer tout le temps j >= 0.

Compte tenu de cela, votre choix d'avoir l' rightIndexargument représentant le dernier index dans le sous-tableau rompt la convention. Cela signifie que vous devez inclure les deux points de terminaison (0 et rightIndex) dans l'itération. Cela rend également difficile la représentation du segment vide (dont vous avez besoin lorsque vous démarrez le tri). En réalité, vous devez utiliser -1 comme rightIndex lors de l'insertion de la première valeur. Cela semble assez peu naturel. Il semble plus naturel d’ rightIndexindiquer l’indice après le segment, donc 0 représente le segment vide.

Bien entendu, votre code est particulièrement déroutant, car il étend le sous-tableau trié avec un, en remplaçant l'élément immédiatement après le sous-tableau trié initialement. Donc, vous lisez à partir de l'indice j mais vous écrivez la valeur à j + 1. Ici, vous devez juste préciser que j est la position dans le sous-tableau initial, avant l’insertion. Lorsque les opérations sur les index deviennent trop difficiles, cela m'aide à les représenter sur un morceau de papier quadrillé.

JacquesB
la source
4
@ CodeYogi: Je dessinerais un petit tableau sous forme de grille sur un morceau de papier, puis effectuerais une itération de la boucle manuellement avec un crayon. Cela m'aide à clarifier ce qui se passe réellement, par exemple le fait qu'une plage de cellules est déplacée vers la droite et l'endroit où la nouvelle valeur est insérée.
JacquesB
3
"En informatique, il y a deux choses difficiles: l'invalidation de la mémoire cache, l'attribution de noms et les erreurs off-by-one."
Digital Trauma
1
@CodeYogi: Ajout d'un petit diagramme pour montrer de quoi je parle.
JacquesB
1
Une bonne perspicacité, spécialement les deux dernières parties méritant d'être lues, la confusion est également due à la nature de la boucle for, même si je trouve le bon index, la boucle décrémente j une fois avant la fin et me permet donc de faire un pas en arrière.
CodeYogi
1
Très. Excellent. Répondre. Et j'ajouterais que cette convention d'indexation inclusive / exclusive est également motivée par la valeur de myArray.Lengthor myList.Count- qui est toujours une valeur de plus que l'index "le plus à droite" basé sur zéro. ... La longueur de l'explication masque l'application pratique et simple de ces heuristiques de codage explicites. La foule TL; DR est en manque.
radarbob
5

L'introduction de votre question me fait penser que vous n'avez pas appris à coder correctement. Toute personne qui programme dans un langage impératif pendant plus de quelques semaines devrait vraiment avoir sa boucle de départ correctement dès la première fois dans plus de 90% des cas. Peut-être vous précipitez-vous pour commencer à coder avant d'avoir suffisamment réfléchi au problème.

Je vous suggère de corriger cette lacune en (ré) apprenant à écrire des boucles - et je recommanderais quelques heures de travail sur une gamme de boucles avec du papier et un crayon. Prenez un après-midi pour le faire. Ensuite, passez environ 45 minutes par jour à travailler sur le sujet jusqu'à ce que vous le compreniez vraiment.

C'est très bien de tester, mais vous devriez le faire dans l'espoir que vos limites de boucle (et le reste de votre code) soient correctes.

Marque de haute performance
la source
4
Je ne serais pas aussi affirmé sur les compétences de OP. Faire des erreurs de démarcation est facile, surtout dans un contexte stressant tel qu'un entretien d'embauche. Un développeur expérimenté pourrait également commettre ces erreurs, mais il est évident qu’un développeur expérimenté éviterait de telles erreurs en premier lieu par le biais de tests.
Arseni Mourzenko
3
@MainMa - Je pense que si Mark aurait pu être plus sensible, je pense qu'il a raison - Il y a un stress lié aux entretiens et il n'y a que du piratage de code ensemble sans qu'il soit dûment tenu compte du problème. La façon dont la question est formulée insiste beaucoup sur ce dernier point et c’est quelque chose qui peut être résolu au mieux à long terme en s’assurant que les bases sont solides, et non en piratant l’IDE
James Snell le
@JamesSnell Je pense que vous êtes trop confiant pour vous. Regardez le code et dites-moi ce qui vous fait penser que c'est sous-documenté? Si vous voyez clairement, il n'est mentionné nulle part que je ne pourrais pas résoudre le problème? Je voulais juste savoir comment éviter de répéter la même erreur. Je pense que vous obtenez tout votre programme correct en une seule fois.
CodeYogi
4
@CodeYogi Si vous devez faire des essais et des erreurs et que vous êtes frustré et que vous faites les mêmes erreurs avec votre codage, ce sont des signes que vous n'avez pas assez bien compris votre problème avant de commencer à écrire. . Personne ne dit que vous ne l'avez pas compris, mais que votre code aurait pu être mieux pensé et que ce sont des signes que vous avez du mal à choisir et que vous devez en tirer des leçons.
James Snell
2
@CodeYogi ... et puisque vous le demandez, je me trompe rarement en boucle, car je tiens à bien comprendre ce que je dois réaliser avant d'écrire du code, ce n'est pas difficile de faire quelque chose d'aussi simple classe de tableau. En tant que programmeur, l’une des choses les plus difficiles à faire est d’avouer que vous êtes le problème, mais tant que vous ne le ferez pas, vous ne commencerez pas à écrire un très bon code.
James Snell
3

Peut-être que je devrais mettre un peu de chair dans mon commentaire:

Il n'y a qu'un moyen: mieux comprendre votre problème. Mais c'est aussi général que votre question est

Votre point est

Bien que mes hypothèses soient correctes après quelques essais et erreurs, je me suis senti trop frustré à cause du manque de modèle informatique correct dans ma tête.

Quand je lis trial and error, mon réveil sonne. Bien sûr, beaucoup d’entre nous connaissent l’état d’esprit, quand on veut régler un petit problème et qu’il a cerné la tête à d’autres choses et commence à deviner d’une façon ou d’une autre, pour que le code soit conforme seemà ce qu’il est censé faire. Certaines solutions rigolotes en découlent - et certaines d’entre elles sont de pur génie . mais pour être honnête: la plupart ne le sont pas . Moi compris, connaissant cet état.

Indépendamment de votre problème concret, vous avez posé des questions sur la manière d'améliorer:

1) test

Cela a été dit par d'autres et je n'aurais rien de précieux à ajouter

2) Analyse du problème

Il est difficile de donner un conseil à cela. Je ne pourrais vous donner que deux astuces qui vous aideront probablement à améliorer vos compétences dans ce domaine:

  • le plus évident et le plus trivial est, à long terme, le plus efficace: résoudre de nombreux problèmes. Tout en pratiquant et en répétant, vous développez l’état d’esprit qui vous aide pour les tâches futures. La programmation est comme toute autre activité à améliorer par la pratique du travail acharné

Les Katas de code sont un moyen, ce qui pourrait aider un peu.

Comment pouvez-vous devenir un grand musicien? Il est utile de connaître la théorie et de comprendre les mécanismes de votre instrument. Cela aide d'avoir du talent. Mais finalement, la grandeur vient de la pratique; appliquer la théorie encore et encore, en utilisant les commentaires pour s'améliorer à chaque fois.

Code Kata

Un site que j'aime beaucoup: Code Wars

Atteindre la maîtrise grâce aux défis Améliorez vos compétences en vous entraînant avec d'autres sur de vrais défis de code

Ce sont des problèmes relativement petits qui vous aident à améliorer vos compétences en programmation. Et ce que j'aime le plus dans Code Wars , c'est que vous pouvez comparer votre solution à une autre .

Ou peut-être devriez-vous jeter un coup d’œil sur Exercism.io où vous obtenez les commentaires de la communauté.

  • L’autre conseil est presque aussi trivial: Apprenez à résoudre les problèmes Vous devez vous entraîner, décomposant les problèmes en problèmes vraiment mineurs. Si vous dites que vous avez des problèmes pour écrire des boucles , vous faites l'erreur de considérer la boucle dans son ensemble et de ne pas la déconstruire en morceaux. Si vous apprenez à démonter les choses étape par étape , vous apprendrez à éviter de telles erreurs.

Je sais - comme je l'ai dit plus haut que vous êtes parfois dans un tel état - qu'il est difficile de décomposer des "choses simples" en tâches plus "simples"; mais ça aide beaucoup.

Je me souviens que lorsque j’ai appris la programmation de façon professionnelle , j’avais de gros problèmes pour déboguer mon code. Quel était le problème? Hybris - L'erreur ne peut pas être dans telle ou telle région du code, car je sais qu'elle ne peut pas l'être. Et en conséquence? J'ai parcouru le code au lieu de l’analyser, mais j’ai dû apprendre, même si c’était fastidieux de décomposer mon code en instructions .

3) Développer une ceinture à outils

En plus de connaître votre langue et vos outils - je sais que ce sont les choses brillantes que les développeurs pensent en premier - apprendre les algorithmes (ou lecture).

Voici deux livres pour commencer:

C'est comme apprendre quelques recettes pour commencer à cuisiner. Au début, vous ne savez pas quoi faire, vous devez donc regarder ce que les chefs précédents ont cuisiné pour vous. La même chose vaut pour les algortihms. Les algorithmes ressemblent à des recettes de cuisine pour des repas courants (structures de données, tri, hachage, etc.). Si vous les connaissez (essayez au moins de le faire) par cœur, vous avez un bon point de départ.

3a) Connaître les constructions de programmation

Ce point est un dérivé - pour ainsi dire. Connaissez votre langue - et mieux: connaissez les constructions possibles dans votre langue.

Un point commun pour le code mauvais ou inefficent est parfois, que le programmeur ne connaît pas la différence entre les différents types de boucles ( for-, while-et do-loops). Ils sont tous interchangeables. mais dans certaines circonstances, choisir une autre construction en boucle conduit à un code plus élégant.

Et il y a l'appareil de Duff ...

PS:

sinon votre commentaire ne vaut rien que Donal Trump.

Oui, nous devrions rendre le codage génial!

Une nouvelle devise pour Stackoverflow.

Thomas Junk
la source
Ah, laissez-moi vous dire une chose très au sérieux. J'ai fait tout ce que vous avez mentionné et je peux même vous donner mon lien sur ces sites. Mais ce qui me frustre le plus, c'est que, au lieu d'obtenir la réponse à ma question, je reçois tous les conseils possibles en matière de programmation. Un seul gars a mentionné les pre-postconditions jusqu'à présent et je l'apprécie.
CodeYogi
D'après ce que vous dites, il est difficile d'imaginer où se situe votre problème. Peut-être une métaphore peut-elle m'aider: pour moi, c'est comme dire "comment puis-je voir" - la réponse évidente pour moi est "utilise tes yeux" car voir est si naturel pour moi, je ne peux pas imaginer, comment on ne peut pas voir. La même chose vaut pour votre question.
Thomas Junk
Entièrement d'accord avec les sonnettes d'alarme sur "essais et erreurs". Je pense que le meilleur moyen d'apprendre à mieux comprendre l'état d'esprit qui consiste à résoudre les problèmes consiste à exécuter des algorithmes et du code avec du papier et un crayon.
Wildcard
Euh ... pourquoi avez-vous un coup non grammaticalement pauvre envers un candidat politique cité sans contexte au milieu de votre réponse à propos de la programmation?
Wildcard
2

Si j'ai bien compris le problème, votre question est de savoir comment obtenir des boucles dès le premier essai, et non pas pour s'assurer que votre boucle est correcte (pour laquelle la réponse serait testée comme expliqué dans d'autres réponses).

Ce que je considère comme une bonne approche est d’écrire la première itération sans boucle. Une fois que vous avez fait cela, vous devriez remarquer ce qui devrait être changé entre les itérations.

Est-ce un nombre, comme un 0 ou un 1? Dans ce cas, vous avez probablement besoin d’un bingo, mais vous avez également votre point de départ i. Pensez alors combien de fois vous voulez exécuter la même chose, et vous aurez également votre condition finale.

Si vous ne savez pas EXACTEMENT le nombre de fois qu'il s'exécutera, vous n'avez pas besoin d'un, mais d'un temps ou d'un temps.

Techniquement, toute boucle peut être convertie en une autre boucle, mais le code est plus facile à lire si vous utilisez la bonne boucle. Voici donc quelques astuces:

  1. Si vous vous trouvez en train d'écrire un if () {...; break;} dans un for, vous avez besoin de temps et vous avez déjà la condition

  2. "While" est peut-être la boucle la plus utilisée dans toutes les langues, mais cela ne devrait pas être imo. Si vous vous trouvez en train d’écrire bool ok = True; while (check) {faire quelque chose et, espérons-le, changer à un moment donné}; alors vous n'avez pas besoin d'un certain temps, mais d'un peu, car cela signifie que vous avez tout ce dont vous avez besoin pour exécuter la première itération.

Maintenant un peu de contexte ... Quand j'ai appris à programmer (Pascal), je ne parlais pas anglais. Pour moi, "pour" et "tant que" n'avait pas beaucoup de sens, mais le mot clé "répéter" (faire en C) est presque identique dans ma langue maternelle, je l'utilisais donc pour tout. À mon avis, répéter (faire pendant) est la boucle la plus naturelle, car vous voulez presque toujours que quelque chose soit fait, puis vous voulez que ce soit refait, et encore, jusqu'à ce qu'un objectif soit atteint. "Pour" est juste un raccourci qui vous donne un itérateur et place étrangement la condition au début du code, même si, presque toujours, vous voulez que quelque chose soit fait jusqu'à ce que quelque chose se produise. En outre, while n'est qu'un raccourci pour if () {do while while ()}. Les raccourcis sont bien pour plus tard,

Andrei
la source
2

Je vais donner un exemple plus détaillé de la façon d'utiliser les conditions préalables / postérieures et les invariants pour développer une boucle correcte. Ensemble, ces affirmations sont appelées spécification ou contrat.

Je ne suggère pas que vous essayez de faire cela pour chaque boucle. Mais j'espère que vous trouverez utile de voir le processus de réflexion impliqué.

Pour ce faire, je vais traduire votre méthode dans un outil appelé Microsoft Dafny , conçu pour prouver l'exactitude de telles spécifications. Il vérifie également la terminaison de chaque boucle. Veuillez noter que Dafny n'a pas de forboucle, j'ai donc dû utiliser une whileboucle à la place.

Enfin, je montrerai comment vous pouvez utiliser ces spécifications pour concevoir une version légèrement plus simple de votre boucle. Cette version de boucle plus simple ne comporte pas la condition de boucle j > 0et l’affectation array[j] = value- comme ce fut votre intuition initiale.

Dafny prouvera pour nous que ces deux boucles sont correctes et font la même chose.

Je ferai ensuite une déclaration générale, basée sur mon expérience, sur la façon d’écrire une boucle en arrière correcte, qui vous aidera peut-être si vous faites face à cette situation à l’avenir.

Première partie - Rédaction d'une spécification pour la méthode

Le premier défi auquel nous sommes confrontés consiste à déterminer ce que la méthode est réellement censée faire. À cette fin, j'ai conçu des conditions pré et post spécifiant le comportement de la méthode. Pour rendre la spécification plus précise, j'ai amélioré la méthode afin qu'elle renvoie l'index où elle a valueété insérée.

method insert(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  // the method will modify the array
  modifies arr
  // the array will not be null
  requires arr != null
  // the right index is within the bounds of the array
  // but not the last item
  requires 0 <= rightIndex < arr.Length - 1
  // value will be inserted into the array at index
  ensures arr[index] == value 
  // index is within the bounds of the array
  ensures 0 <= index <= rightIndex + 1
  // the array to the left of index is not modified
  ensures arr[..index] == old(arr[..index])
  // the array to the right of index, up to right index is
  // shifted to the right by one place
  ensures arr[index+1..rightIndex+2] == old(arr[index..rightIndex+1])
  // the array to the right of rightIndex+1 is not modified
  ensures arr[rightIndex+2..] == old(arr[rightIndex+2..])

Cette spécification capture complètement le comportement de la méthode. Mon observation principale à propos de cette spécification est que cela serait simplifié si la procédure était passée à la valeur rightIndex+1plutôt qu'à rightIndex. Mais comme je ne vois pas d'où cette méthode est appelée, je ne sais pas quel effet ce changement aurait sur le reste du programme.

Deuxième partie - Déterminer un invariant de boucle

Maintenant que nous avons une spécification pour le comportement de la méthode, nous devons ajouter une spécification du comportement de la boucle qui convaincra Dafny que l’exécution de la boucle se terminera et aboutira à l’état final souhaité array.

Ce qui suit est votre boucle originale, traduite en syntaxe Dafny avec des invariants de boucle ajoutés. Je l'ai également changé pour retourner l'index où la valeur a été insérée.

{
    // take a copy of the initial array, so we can refer to it later
    // ghost variables do not affect program execution, they are just
    // for specification
    ghost var initialArr := arr[..];


    var j := rightIndex;
    while(j >= 0 && arr[j] > value)
       // the loop always decreases j, so it will terminate
       decreases j
       // j remains within the loop index off-by-one
       invariant -1 <= j < arr.Length
       // the right side of the array is not modified
       invariant arr[rightIndex+2..] == initialArr[rightIndex+2..]
       // the part of the array looked at by the loop so far is
       // shifted by one place to the right
       invariant arr[j+2..rightIndex+2] == initialArr[j+1..rightIndex+1]
       // the part of the array not looked at yet is not modified
       invariant arr[..j+1] == initialArr[..j+1] 
    {
        arr[j + 1] := arr[j];
        j := j-1;
    }   
    arr[j + 1] := value;
    return j+1; // return the position of the insert
}

Cela se vérifie chez Dafny. Vous pouvez le voir vous-même en suivant ce lien . Donc, votre boucle implémente correctement la spécification de méthode que j'ai écrite dans la première partie. Vous devrez décider si cette spécification de méthode correspond réellement au comportement souhaité.

Notez que Dafny produit ici une preuve d'exactitude. C'est une garantie d'exactitude bien plus forte que celle que l'on peut éventuellement obtenir en testant.

Troisième partie - une boucle plus simple

Maintenant que nous avons une spécification de méthode qui capture le comportement de la boucle. Nous pouvons modifier en toute sécurité l'implémentation de la boucle tout en gardant la certitude que nous n'avons pas changé le comportement de la boucle.

J'ai modifié la boucle afin qu'elle corresponde à vos intuitions d'origine concernant la condition de la boucle et la valeur finale de j. Je dirais que cette boucle est plus simple que celle que vous avez décrite dans votre question. Il est plus souvent capable d'utiliser jque de j+1.

  1. Commencez j à rightIndex+1

  2. Changez la condition de boucle en j > 0 && arr[j-1] > value

  3. Changer le devoir en arr[j] := value

  4. Décrémentez le compteur de boucle à la fin de la boucle plutôt qu'au début

Voici le code. Notez que les invariants de boucle sont aussi un peu plus faciles à écrire maintenant:

method insert2(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  modifies arr
  requires arr != null
  requires 0 <= rightIndex < arr.Length - 1
  ensures 0 <= index <= rightIndex + 1
  ensures arr[..index] == old(arr[..index])
  ensures arr[index] == value 
  ensures arr[index+1..rightIndex+2] == old(arr[index..rightIndex+1])
  ensures arr[rightIndex+2..] == old(arr[rightIndex+2..])
{
    ghost var initialArr := arr[..];
    var j := rightIndex+1;
    while(j > 0 && arr[j-1] > value)
       decreases j
       invariant 0 <= j <= arr.Length
       invariant arr[rightIndex+2..] == initialArr[rightIndex+2..]
       invariant arr[j+1..rightIndex+2] == initialArr[j..rightIndex+1]
       invariant arr[..j] == initialArr[..j] 
    {
        j := j-1;
        arr[j + 1] := arr[j];
    }   
    arr[j] := value;
    return j;
}

Quatrième partie - conseils sur le bouclage arrière

Après avoir écrit et prouvé correctement de nombreuses boucles sur plusieurs années, j’ai le conseil général suivant sur les boucles arrière.

Il est presque toujours plus facile de penser et d'écrire une boucle arrière (décrémentation) si la décrémentation est effectuée au début de la boucle plutôt qu'à la fin.

Malheureusement, la forconstruction de la boucle dans de nombreuses langues rend cela difficile.

Je soupçonne (mais ne peux pas prouver) que cette complexité est à l'origine de la différence d'intuition quant à ce que devrait être la boucle et ce qu'elle devait être en réalité. Vous êtes habitué à penser aux boucles en avant (incrémentation). Lorsque vous voulez écrire une boucle arrière (décrémentation), essayez de créer la boucle en essayant d'inverser l'ordre dans lequel les choses se passent dans une boucle avant (incrémentante). Mais en raison de la façon dont la forconstruction fonctionne, vous avez omis d'inverser l'ordre de l'affectation et de mettre à jour la variable de boucle - ce qui est nécessaire pour une véritable inversion de l'ordre des opérations entre une boucle en amont et en aval.

Cinquième partie - bonus

Juste pour compléter, voici le code que vous obtenez si vous passez rightIndex+1à la méthode plutôt que rightIndex. Cette modification élimine tous les +2décalages qui sont par ailleurs nécessaires pour penser à la correction de la boucle.

method insert3(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  modifies arr
  requires arr != null
  requires 1 <= rightIndex < arr.Length 
  ensures 0 <= index <= rightIndex
  ensures arr[..index] == old(arr[..index])
  ensures arr[index] == value 
  ensures arr[index+1..rightIndex+1] == old(arr[index..rightIndex])
  ensures arr[rightIndex+1..] == old(arr[rightIndex+1..])
{
    ghost var initialArr := arr[..];
    var j := rightIndex;
    while(j > 0 && arr[j-1] > value)
       decreases j
       invariant 0 <= j <= arr.Length
       invariant arr[rightIndex+1..] == initialArr[rightIndex+1..]
       invariant arr[j+1..rightIndex+1] == initialArr[j..rightIndex]
       invariant arr[..j] == initialArr[..j] 
    {
        j := j-1;
        arr[j + 1] := arr[j];
    }   
    arr[j] := value;
    return j;
}
flamingpenguin
la source
2
J'apprécierais vraiment un commentaire si vous
votiez vers le bas
2

Obtenir cela facilement et couramment est une question d'expérience. Bien que le langage ne vous permette pas de l'exprimer directement ou que vous utilisiez un cas plus complexe que ne le permet le système intégré simple, vous pensez qu'il s'agit d'un niveau supérieur tel que "visitez chaque élément une fois par ordre" et le codeur plus expérimenté traduit cela instantanément dans les détails appropriés, car il l'a déjà fait tant de fois.

Même dans ce cas, dans des cas plus complexes, il est facile de se tromper, car ce que vous écrivez n’est généralement pas ce qu’il faut de mieux . Avec des langages et des bibliothèques plus modernes, vous n'écrivez pas une chose facile, car il existe une construction prédéfinie. En C ++, le mantra moderne est "utiliser des algorithmes plutôt que d'écrire du code".

Donc, la meilleure façon de s’assurer que c’est bien, pour ce genre de chose en particulier, est d’examiner les conditions aux limites . Parcourez le code dans votre tête pour les quelques cas où les choses changent. Si le index == array-max, que se passe-t-il? Qu'en est- il max-1? Si le code tourne mal, ce sera à l'une de ces limites. Certaines boucles doivent s’inquiéter du premier ou du dernier élément, ainsi que de la construction en boucle qui établit les limites correctement; Par exemple, si vous vous référez a[I]et a[I-1]que se passe-t-il quand Iest la valeur minimale?

Aussi, regardez les cas où le nombre d'itérations (correctes) est extrême: si les limites se rencontrent et que vous aurez 0 itérations, cela fonctionnera-t-il sans cas particulier? Et qu’en est-il de la première itération, où la limite inférieure est également la limite supérieure en même temps?

L'examen des cas marginaux (des deux côtés de chaque bord) est ce que vous devez faire lorsque vous écrivez la boucle et ce que vous devez faire lors de la révision du code.

JDługosz
la source
1

J'essaierai déjà de rester à l'écart des sujets mentionnés à gogo.

Quels sont les outils / modèles mentaux pour éviter de telles erreurs?

Outils

Pour moi, le plus grand outil pour mieux écrire foret whileboucles est de ne pas écrire une forou des whileboucles du tout.

La plupart des langues modernes tentent de résoudre ce problème d’une manière ou d’une autre. Par exemple, Java, tout en ayant Iteratordès le début, ce qui était un peu maladroit à utiliser, a introduit une syntaxe raccourcie pour les utiliser plus facilement dans une version plus récente. C # les a aussi, etc.

Ma langue actuelle, Ruby, a adopté l’approche fonctionnelle ( .each, .mapetc.) à part entière. C'est très puissant. Je viens de faire un comptage rapide dans une base de code Ruby sur laquelle je travaille: dans environ 10 000 lignes de code, il y a zéro foret environ 5 while.

Si j'étais obligé de choisir une nouvelle langue, la recherche de boucles fonctionnelles / basées sur les données comme celle-ci serait très élevée dans la liste des priorités.

Modèles mentaux

Gardez à l'esprit que whilec'est le minimum d'abstraction que vous puissiez obtenir, juste un peu plus haut goto. À mon avis, la situation forest encore pire au lieu d’être meilleure car elle associe étroitement les trois parties de la boucle.

Donc, si je suis dans un environnement où forest utilisé, alors je m'assure que les 3 parties sont parfaitement simples et toujours les mêmes. Cela signifie que je vais écrire

limit = ...;
for (idx = 0; idx < limit; idx++) { 

Mais rien de plus complexe. J'aurai peut-être un compte à rebours de temps en temps, mais je ferai de mon mieux pour l'éviter.

Si whileje l' utilise , je reste à l'écart des manigances internes compliquées impliquant la condition de boucle. Le test à l'intérieur while(...)sera aussi simple que possible et j'éviterai breakde mon mieux. De plus, la boucle sera courte (lignes de code de comptage) et toutes les plus grandes quantités de code seront factorisées.

Surtout si la condition réelle tant que complexe est complexe, je vais utiliser une "variable de condition" qui est très facile à repérer, et ne place pas la condition dans la whiledéclaration elle-même:

repeat = true;
while (repeat) {
   repeat = false; 
   ...
   if (complex stuff...) {
      repeat = true;
      ... other complex stuff ...
   }
}

(Ou quelque chose comme ça, dans la bonne mesure, bien sûr.)

Cela vous donne un modèle mental très facile qui est "cette variable est exécutée de 0 à 10 monotone" ou "cette boucle est exécutée jusqu'à ce que cette variable soit false / true". La plupart des cerveaux semblent être capables de gérer parfaitement ce niveau d'abstraction.

J'espère que ça t'as aidé.

AnoE
la source
1

Les boucles inversées, en particulier, peuvent être difficiles à raisonner car bon nombre de nos langages de programmation sont orientés vers l'itération en aval, à la fois dans la syntaxe commune pour les boucles et par l'utilisation d'intervalles de demi-ouverture à base zéro. Je ne dis pas qu'il est faux que les langues fassent ces choix; Je dis simplement que ces choix compliquent la réflexion sur les boucles inverses.

En général, rappelez-vous qu'une boucle for est simplement un sucre syntaxique construit autour d'une boucle while:

// pseudo-code!
for (init; cond; step) { body; }

est équivalent à:

// pseudo-code!
init;
while (cond) {
  body;
  step;
}

(éventuellement avec une couche supplémentaire d'étendue pour conserver les variables déclarées dans l'étape d'init locale à la boucle).

Cela convient à de nombreux types de boucles, mais il est malaisé d’avoir le pas en dernier. Lorsque je travaille en arrière, je trouve qu'il est plus facile de démarrer l'index de boucle avec la valeur après celle que je veux et de déplacer la steppartie en haut de la boucle, comme ceci:

auto i = v.size();  // init
while (i > 0) {  // simpler condition because i is one after
    --i;  // step before the body
    body;  // in body, i means what you'd expect
}

ou, en tant que boucle for:

for (i = v.size(); i > 0; ) {
    --i;  // step
    body;
}

Cela peut sembler déroutant, car l'expression de l'étape est dans le corps plutôt que dans l'en-tête. C'est un effet secondaire regrettable de la syntaxe de boucle for for inhérente au biais direct. Pour cette raison, certains diront que vous faites plutôt ceci:

for (i = v.size() - 1; i >= 0; --i) {
    body;
}

Mais c'est un désastre si votre variable d'index est un type non signé (comme cela pourrait être en C ou C ++).

Gardant cela à l’esprit, écrivons votre fonction d’insertion.

  1. Puisque nous allons travailler en arrière, nous allons laisser l’index de boucle être l’entrée après le slot de tableau "courant". Je concevrais la fonction pour prendre la taille de l’entier plutôt que l’index du dernier élément car les plages semi-ouvertes sont le moyen naturel de représenter des plages dans la plupart des langages de programmation et parce qu’elles nous permettent de représenter un tableau vide sans avoir recours à à une valeur magique comme -1.

    function insert(array, size, value) {
      var j = size;
    
  2. Bien que la nouvelle valeur soit plus petite que l’ élément précédent , continuez à vous déplacer. Bien sûr, l'élément précédent peut être vérifié que s'il est un élément précédent, donc nous devons d' abord vérifier que nous ne sommes pas au début:

      while (j != 0 && value < array[j - 1]) {
        --j;  // now j become current
        array[j + 1] = array[j];
      }
    
  3. Cela laisse jlà où nous voulons la nouvelle valeur.

      array[j] = value; 
    };
    

Programmation Pearls de Jon Bentley donne une explication très claire du type d'insertion (et d'autres algorithmes), ce qui peut vous aider à construire vos modèles mentaux pour ce type de problèmes.

Adrian McCarthy
la source
0

Êtes-vous simplement confus sur ce que forfait réellement une boucle et sur les mécanismes de son fonctionnement?

for(initialization; condition; increment*)
{
    body
}
  1. Tout d'abord, l'initialisation est exécutée
  2. Ensuite, la condition est vérifiée
  3. Si la condition est vraie, le corps est exécuté une fois. Si non passez à # 6
  4. Le code d'incrément est exécuté
  5. Goto # 2
  6. Fin de boucle

Il pourrait être utile pour vous de réécrire ce code en utilisant une construction différente. Voici la même chose en utilisant une boucle while:

initialization
while(condition)
{
    body
    increment
}

Voici quelques autres suggestions:

  • Pouvez-vous utiliser une autre construction de langage comme une boucle foreach? Cela prend en charge la condition et l'étape d'incrément pour vous.
  • Pouvez-vous utiliser une fonction Carte ou Filtre? Certaines langues ont des fonctions avec ces noms qui parcourent en interne une collection pour vous. Vous venez de fournir la collection et le corps.
  • Vous devriez vraiment passer plus de temps à vous familiariser avec les forboucles. Vous les utiliserez tout le temps. Je vous suggère de parcourir une boucle for dans un débogueur pour voir comment il s'exécute.

* Notez que bien que j'utilise le terme "incrément", c'est juste du code qui se trouve après le corps et avant la vérification de la condition. Ce peut être un décrément ou rien du tout.

utilisateur2023861
la source
1
pourquoi le vote négatif?
user2023861
0

Tentative de compréhension supplémentaire

Pour les algorithmes non triviaux avec des boucles, vous pouvez essayer la méthode suivante:

  1. Créez un tableau fixe avec 4 positions et mettez quelques valeurs dans, pour simuler le problème;
  2. Ecrivez votre algorithme pour résoudre le problème donné , sans boucle et avec indexation codée en dur ;
  3. Après cela, substituez des indexations codées en dur dans votre code avec une variable iou j, et incrémentez / décrémentez ces variables si nécessaire (mais toujours sans aucune boucle);
  4. Réécrivez votre code et placez les blocs répétitifs dans une boucle , en remplissant les conditions de pré et post;
  5. [ facultatif ] réécrivez votre boucle afin qu'elle se présente sous la forme de votre choix (pour / while / do while);
  6. Le plus important est d'écrire votre algorithme correctement. après cela, vous refactorisez et optimisez votre code / boucles si nécessaire (mais cela pourrait rendre le code non trivial pour un lecteur)

Ton problème

//TODO: Insert the given value in proper position in the sorted subarray
function insert(array, rightIndex, value) { ... };

Écrire le corps de la boucle manuellement plusieurs fois

Utilisons un tableau fixe à 4 positions et essayons d'écrire l'algorithme manuellement, sans boucle:

           //0 1 2 3
var array = [2,5,9,1]; //array sorted from index 0 to 2
var leftIndex = 0;
var rightIndex = 2;
var value = array[3]; //placing the last value within the array in the proper position

//starting here as 2 == rightIndex

if (array[2] > value) {
    array[3] = array[2];
} else {
    array[3] = value;
    return; //found proper position, no need to proceed;
}

if (array[1] > value) {
    array[2] = array[1];
} else {
    array[2] = value;
    return; //found proper position, no need to proceed;
}

if (array[0] > value) {
    array[1] = array[0];
} else {
    array[1] = value;
    return; //found proper position, no need to proceed;
}

array[0] = value; //achieved beginning of the array

//stopping here because there 0 == leftIndex

Réécrire, en supprimant les valeurs codées en dur

//consider going from 2 to 0, going from "rightIndex" to "leftIndex"

var i = rightIndex //starting here as 2 == rightIndex

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

//stopping here because there 0 == leftIndex

Traduire en boucle

Avec while:

var i = rightIndex; //starting in rightIndex

while (true) {
    if (array[i] > value) { //refactor: this can go in the while clause
        array[i+1] = array[i];
    } else {
        array[i+1] = value;
        break; //found proper position, no need to proceed;
    }

    i--;
    if (i < leftIndex) { //refactor: this can go (inverted) in the while clause
        array[i+1] = value; //achieved beginning of the array
        break;
    }
}

Refactorisez / réécrivez / optimisez la boucle comme vous le souhaitez:

Avec while:

var i = rightIndex; //starting in rightIndex

while ((array[i] > value) && (i >= leftIndex)) {
    array[i+1] = array[i];
    i--;
}

array[i+1] = value; //found proper position, or achieved beginning of the array

avec for:

for (var i = rightIndex; (array[i] > value) && (i >= leftIndex); i--) {
    array[i+1] = array[i];
}

array[i+1] = value; //found proper position, or achieved beginning of the array

PS: le code suppose que l’entrée est valide et que ce tableau ne contient pas de répétitions;

Emerson Cardoso
la source
-1

C'est pourquoi j'éviterais d'écrire des boucles qui fonctionnent sur des indices bruts, en faveur d'opérations plus abstraites, dans la mesure du possible.

Dans ce cas, je ferais quelque chose comme ceci (en pseudo-code):

array = array[:(rightIndex - 1)] + value + array[rightIndex:]
Alexandre
la source
-3

Dans votre exemple, le corps de la boucle est assez évident. Et il est évident que certains éléments doivent être modifiés à la fin. Donc, vous écrivez le code, mais sans le début de la boucle, la condition de fin et l'affectation finale.

Ensuite, vous vous écartez du code et découvrez quel est le premier mouvement à effectuer. Vous changez le début de la boucle pour que le premier coup soit correct. Vous vous éloignez à nouveau du code et découvrez quel est le dernier mouvement à exécuter. Vous modifiez la condition de fin pour que le dernier mouvement soit correct. Et finalement, vous vous écartez de votre code, déterminez ce que doit être la dernière tâche et corrigez le code en conséquence.

gnasher729
la source
1
Pouvez-vous s'il vous plaît mettre en place un exemple?
CodeYogi
Le PO avait un exemple.
gnasher729
2
Que voulez-vous dire? Je suis l'OP.
CodeYogi