Meistens schreibe ich beim Schreiben von Schleifen falsche Randbedingungen (z. B. falsches Ergebnis) oder meine Annahmen über das Beenden von Schleifen sind falsch (z. B. Endlosschleifen). Obwohl ich meine Vermutungen nach einigem Ausprobieren richtig gemacht habe, war ich zu frustriert, weil ich kein korrektes Rechenmodell in meinem Kopf hatte.

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

Die Fehler, die ich anfangs gemacht habe, waren:

1. Anstelle von j> = 0 habe ich es j> 0 gehalten.
2. Wurde verwirrt, ob Array [j + 1] = Wert oder Array [j] = Wert.

Was sind Werkzeuge / mentale Modelle, um solche Fehler zu vermeiden?

Prüfung

Nein, im Ernst, testen.

Ich programmiere seit über 20 Jahren und traue mich immer noch nicht, beim ersten Mal eine Schleife richtig zu schreiben. Ich schreibe und führe Tests durch, die beweisen, dass es funktioniert, bevor ich vermute, dass es funktioniert. Testen Sie jede Seite jeder Randbedingung. Zum Beispiel sollte eine rightIndexvon 0 was tun? Wie wäre es mit -1?

Halte es einfach

Wenn andere nicht sehen können, was es auf einen Blick tut, machen Sie es zu schwer. Sie können die Leistung jederzeit ignorieren, wenn dies bedeutet, dass Sie etwas leicht verständliches schreiben können. Machen Sie es nur in dem unwahrscheinlichen Fall, dass Sie es wirklich brauchen, schneller. Und selbst dann nur, wenn Sie absolut sicher sind, dass Sie genau wissen, was Sie bremst. Wenn Sie eine tatsächliche Verbesserung von Big O erzielen können, ist diese Aktivität möglicherweise nicht sinnlos. Machen Sie Ihren Code jedoch so lesbar wie möglich.

Aus um eins

Kennen Sie den Unterschied zwischen dem Zählen Ihrer Finger und dem Zählen der Abstände zwischen Ihren Fingern. Manchmal sind die Räume das, was wirklich wichtig ist. Lass dich nicht von deinen Fingern ablenken. Wissen Sie, ob Ihr Daumen ein Finger ist. Wissen Sie, ob die Lücke zwischen Ihrem kleinen Finger und dem Daumen als Leerzeichen gilt.

Bemerkungen

Bevor Sie sich im Code verirren, versuchen Sie zu sagen, was Sie auf Englisch meinen. Geben Sie Ihre Erwartungen klar an. Erkläre nicht, wie der Code funktioniert. Erklären Sie, warum Sie es tun lassen, was es tut. Halten Sie Implementierungsdetails davon fern. Es sollte möglich sein, den Code umzugestalten, ohne den Kommentar ändern zu müssen.

Der beste Kommentar ist ein guter Name.

Wenn Sie alles, was Sie zu sagen haben, mit einem guten Namen sagen können, sagen Sie es NICHT noch einmal mit einem Kommentar.

Abstraktionen

Objekte, Funktionen, Arrays und Variablen sind alle Abstraktionen, die nur so gut sind wie die Namen, die ihnen gegeben wurden. Geben Sie ihnen Namen, die sicherstellen, dass Menschen, die in sie hineinschauen, nicht von dem überrascht werden, was sie finden.

Kurznamen

Verwenden Sie kurze Namen für kurzlebige Dinge. iist ein feiner Name für einen Index in einer schönen engen Schleife in einem kleinen Bereich, der seine Bedeutung deutlich macht. Wenn das iLeben lang genug ist, um sich mit anderen Ideen und Namen, die verwechselt werden können, über mehrere Zeilen zu verbreiten, iist es Zeit, ieinen schönen, langen, erklärenden Namen zu vergeben.

Lange Namen

Kürzen Sie einen Namen niemals einfach aus Gründen der Zeilenlänge. Finden Sie einen anderen Weg, um Ihren Code zu gestalten.

Leerzeichen

Defekte lieben es, sich in unlesbarem Code zu verstecken. Wenn Sie in Ihrer Sprache einen Einrückungsstil auswählen können, müssen Sie mindestens konsistent sein. Lassen Sie Ihren Code nicht wie einen Strom von Rauschen aussehen. Der Code sollte so aussehen, als würde er in Formation marschieren.

Schleifenkonstrukte

Lernen und überprüfen Sie die Schleifenstrukturen in Ihrer Sprache. Das Hervorheben einer for(;;)Schleife durch einen Debugger kann sehr lehrreich sein. Lerne alle Formen. while, do while, while(true), for each. Verwenden Sie das einfachste, mit dem Sie davonkommen können. Schauen Sie nach, wie Sie die Pumpe vorfüllen . Erfahren Sie, was breakund continuetun Sie, wenn Sie sie haben. Kennen Sie den Unterschied zwischen c++und ++c. Haben Sie keine Angst, vorzeitig zurückzukehren, solange Sie immer alles schließen, was geschlossen werden muss. Schließlich blockiert oder markiert es vorzugsweise zum automatischen Schließen, wenn Sie es öffnen: Using statement / Try with Resources .

Loop-Alternativen

Lassen Sie etwas anderes die Schleife machen, wenn Sie können. Es ist augenschonender und bereits getestet. Diese kommen in vielen Formen: Sammlungen oder Ströme , die erlauben map(), reduce(), foreach()und andere solche Verfahren , die eine Lambda - Anwendung. Suchen Sie nach Spezialfunktionen wie Arrays.fill(). Es gibt auch Rekursionen, von denen man aber nur erwartet, dass sie die Sache in besonderen Fällen erleichtern. Verwenden Sie im Allgemeinen keine Rekursion, bis Sie sehen, wie die Alternative aussehen würde.

Oh, und teste.

Test, Test, Test.

Habe ich das Testen erwähnt?

Es gab noch eine Sache. Ich kann mich nicht erinnern. Begonnen mit einem T ...

Bei der Programmierung ist es nützlich, an Folgendes zu denken:

• Voraussetzungen
• Nachbedingungen
• Varianten
• und Invarianten (von Schleifen oder Typen )

und wenn man Neuland erkundet (z. B. mit Indizes jongliert), kann es sehr, sehr nützlich sein, nicht nur an diese zu denken, sondern sie tatsächlich im Code mit Behauptungen explizit zu machen .

Nehmen wir Ihren Originalcode:

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

Und überprüfen Sie, was wir haben:

• Voraussetzung: array[0..rightIndex]ist sortiert
• Nachbedingung: array[0..rightIndex+1]ist sortiert
• invariant: 0 <= j <= rightIndexaber es scheint ein bisschen überflüssig; oder als @Jules bemerkte in den Kommentaren am Ende eines „runden“, for n in [j, rightIndex+1] => array[j] > value.
• Invariante: am Ende einer "Runde" array[0..rightIndex+1]wird sortiert

Sie können also zunächst eine is_sortedFunktion sowie eine minFunktion schreiben, die an einem Array-Slice arbeitet, und dann Folgendes bestätigen:

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]));
};

Es gibt auch die Tatsache, dass Ihre Schleifenbedingung etwas kompliziert ist; Vielleicht möchten Sie es sich leichter machen, indem Sie die Dinge aufteilen:

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]));
};

Jetzt ist die Schleife einfach ( jgeht von rightIndexbis 0).

Zum Schluss muss dies noch getestet werden:

• denke an Randbedingungen ( rightIndex == 0, rightIndex == array.size - 2)
• Denken Sie valuedaran, kleiner array[0]oder größer zu sein alsarray[rightIndex]
• denken valuegleich sein array[0], array[rightIndex]oder einem mittleren Index

Unterschätzen Sie auch nicht das Fuzzing . Sie haben Behauptungen, mit denen Sie Fehler auffangen können. Generieren Sie also ein zufälliges Array und sortieren Sie es nach Ihrer Methode. Wenn eine Behauptung ausgelöst wird, haben Sie einen Fehler gefunden und können Ihre Testsuite erweitern.

Verwenden Sie Unit Testing / TDD

Wenn Sie wirklich über eine forSchleife auf Sequenzen zugreifen müssen , können Sie die Fehler durch Komponententests und insbesondere durch testgetriebene Entwicklung vermeiden .

Stellen Sie sich vor, Sie müssen eine Methode implementieren, die die Werte, die über Null liegen, in umgekehrter Reihenfolge verwendet. Welche Testfälle könnten Sie sich vorstellen?

1. Eine Sequenz enthält einen Wert, der größer als Null ist.

   Aktuell: [5]. Erwartet: [5].

   Die einfachste Implementierung, die die Anforderungen erfüllt, besteht darin, die Quellsequenz einfach an den Aufrufer zurückzugeben.

2. Eine Sequenz enthält zwei Werte, die beide über Null liegen.

   Aktuell: [5, 7]. Erwartet: [7, 5].

   Jetzt können Sie die Sequenz nicht nur zurückgeben, sondern sollten sie auch umkehren. Würden Sie eine for (;;)Schleife, ein anderes Sprachkonstrukt oder eine Bibliotheksmethode verwenden, spielt das keine Rolle.

3. Eine Sequenz enthält drei Werte, von denen einer Null ist.

   Aktuell: [5, 0, 7]. Erwartet: [7, 5].

   Jetzt sollten Sie den Code ändern, um die Werte zu filtern. Dies könnte wiederum durch eine ifAnweisung oder einen Aufruf Ihrer bevorzugten Framework-Methode ausgedrückt werden.

4. Abhängig von Ihrem Algorithmus (da dies ein White-Box-Test ist, ist die Implementierung von Bedeutung) müssen Sie möglicherweise speziell den leeren Sequenzfall behandeln [] → [], oder vielleicht auch nicht. Oder Sie können dafür sorgen , dass der Rand Fall , in dem alle Werte negativ sind [-4, 0, -5, 0] → []korrekt gehandhabt, oder sogar , dass Grenze negative Werte sind: [6, 4, -1] → [4, 6]; [-1, 6, 4] → [4, 6]. In vielen Fällen haben Sie jedoch nur die drei oben beschriebenen Tests: Ein zusätzlicher Test führt nicht zu einer Änderung Ihres Codes und ist daher irrelevant.

Arbeiten Sie auf einer höheren Abstraktionsebene

In vielen Fällen können Sie jedoch die meisten dieser Fehler vermeiden, indem Sie auf einer höheren Abstraktionsebene mit vorhandenen Bibliotheken / Frameworks arbeiten. Diese Bibliotheken / Frameworks ermöglichen das Zurücksetzen, Sortieren, Teilen und Verbinden der Sequenzen, das Einfügen oder Entfernen von Werten in Arrays oder doppelt verknüpften Listen usw.

Normalerweise foreachkann verwendet werden , statt for, so dass Randbedingungen Prüfung irrelevant: die Sprache macht es für Sie. Einige Sprachen, wie Python, haben nicht einmal das for (;;)Konstrukt, sondern nur for ... in ....

In C # ist LINQ besonders praktisch, wenn Sie mit Sequenzen arbeiten.

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

ist viel lesbarer und weniger fehleranfällig im Vergleich zu seiner forVariante:

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

    yield return value;
}

Ich stimme anderen Leuten zu, die sagen, testen Sie Ihren Code. Es ist aber auch schön, es überhaupt richtig zu machen. In vielen Fällen neige ich dazu, die Randbedingungen falsch zu verstehen, daher habe ich mentale Tricks entwickelt, um solche Probleme zu vermeiden.

Bei einem 0-indizierten Array sind Ihre normalen Bedingungen:

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

oder

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

Diese Muster sollten zur Selbstverständlichkeit werden, darüber sollte man überhaupt nicht nachdenken müssen.

Aber nicht alles folgt genau diesem Muster. Wenn Sie sich nicht sicher sind, ob Sie es richtig geschrieben haben, ist hier Ihr nächster Schritt:

Stecke Werte ein und bewerte den Code in deinem eigenen Gehirn. Machen Sie es sich so einfach wie möglich, darüber nachzudenken. Was passiert, wenn die relevanten Werte 0 sind? Was passiert, wenn sie 1 sind?

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

In Ihrem Beispiel sind Sie sich nicht sicher, ob es [j] = Wert oder [j + 1] = Wert sein soll. Zeit, es manuell auszuwerten:

Was passiert, wenn Sie eine Array-Länge von 0 haben? Die Antwort wird offensichtlich: rightIndex muss (Länge - 1) == -1 sein, also beginnt j bei -1. Um also bei Index 0 einzufügen, müssen Sie 1 hinzufügen.

Wir haben also bewiesen, dass die endgültige Bedingung korrekt ist, aber nicht das Innere der Schleife.

Was passiert, wenn Sie ein Array mit 1 Element und 10 haben und wir versuchen, eine 5 einzufügen? Bei einem einzelnen Element sollte rightIndex bei 0 beginnen. Beim ersten Durchlaufen der Schleife ist j = 0, also "0> = 0 && 10> 5". Da wir die 5 bei Index 0 einfügen möchten, sollte die 10 zu Index 1 verschoben werden, also ist Array [1] = Array [0]. Da dies geschieht, wenn j 0 ist, ist Array [j + 1] = Array [j + 0].

Wenn Sie versuchen, sich ein großes Array vorzustellen und was passiert, wenn Sie es an einer beliebigen Stelle einfügen, wird Ihr Gehirn wahrscheinlich überfordert sein. Wenn Sie sich jedoch an einfache Größenbeispiele für 0/1/2 halten, sollte es einfach sein, einen kurzen mentalen Durchlauf zu machen und zu sehen, wo Ihre Randbedingungen zusammenbrechen.

Stellen Sie sich vor, Sie haben noch nie von dem Zaunpfostenproblem gehört und ich sage Ihnen, ich habe 100 Zaunpfosten in einer geraden Linie, wie viele Segmente zwischen ihnen. Wenn Sie versuchen, sich 100 Zaunpfähle in Ihrem Kopf vorzustellen, werden Sie einfach überwältigt sein. Also, was sind die wenigsten Zaunpfosten, um einen gültigen Zaun zu bauen? Sie brauchen 2, um einen Zaun zu bauen. Stellen Sie sich also 2 Pfosten vor, und das mentale Bild eines einzelnen Segments zwischen den Pfosten macht dies sehr deutlich. Sie müssen nicht dort sitzen, um Beiträge und Segmente zu zählen, weil Sie das Problem für Ihr Gehirn intuitiv offensichtlich gemacht haben.

Sobald Sie glauben, dass es korrekt ist, sollten Sie einen Test durchführen und sicherstellen, dass der Computer das tut, was Sie für richtig halten. An diesem Punkt sollte es sich jedoch nur um eine Formalität handeln.

Ich war zu frustriert, weil ich kein korrektes Computermodell im Kopf hatte.

Ist ein sehr interessanter Punkt zu dieser Frage und es generiert diesen Kommentar: -

Es gibt nur einen Weg: Verstehe dein Problem besser. Aber das ist so allgemein wie Ihre Frage. - Thomas Junk

... und Thomas hat recht. Keine klare Absicht für eine Funktion zu haben, sollte eine rote Fahne sein - ein klares Zeichen dafür, dass Sie sofort STOPPEN, einen Stift und ein Papier nehmen, sich von der IDE entfernen und das Problem ordnungsgemäß auflösen sollten. oder zumindest überprüfen Sie, was Sie getan haben.

Ich habe so viele Funktionen und Klassen gesehen, die zu einem völligen Durcheinander geworden sind, weil die Autoren versucht haben, die Implementierung zu definieren, bevor sie das Problem vollständig definiert haben. Und es ist so einfach damit umzugehen.

Wenn Sie das Problem nicht vollständig verstehen, ist es auch unwahrscheinlich, dass Sie die optimale Lösung codieren (entweder in Bezug auf Effizienz oder Klarheit), und Sie werden auch nicht in der Lage sein, wirklich nützliche Komponententests in einer TDD-Methodik zu erstellen.

Nehmen Sie Ihren Code als Beispiel, er enthält eine Reihe potenzieller Fehler, die Sie zum Beispiel noch nicht berücksichtigt haben:

• was ist, wenn rightIndex zu niedrig ist? (Hinweis: es wird Datenverlust beinhalten)
• Was ist, wenn RightIndex außerhalb der Array-Grenzen liegt? (Bekommst du eine Ausnahme oder hast du dir nur einen Pufferüberlauf gemacht?)

Es gibt ein paar andere Probleme im Zusammenhang mit der Leistung und dem Design des Codes ...

• Muss dieser Code skaliert werden? Ist es die beste Option, das Array sortiert zu lassen, oder sollten Sie sich andere Optionen (wie eine verknüpfte Liste) ansehen?
• Können Sie sich Ihrer Annahmen sicher sein? (Können Sie garantieren, dass das Array sortiert wird, und was ist, wenn dies nicht der Fall ist?)
• erfindest du das Rad neu? Sortierte Arrays sind ein bekanntes Problem. Haben Sie die vorhandenen Lösungen untersucht? Gibt es bereits eine Lösung in Ihrer Sprache (z. B. SortedList<t>in C #)?
• sollten Sie jeweils einen Array-Eintrag manuell kopieren? oder bietet Ihre Sprache allgemeine Funktionen wie JScript Array.Insert(...)? Wäre dieser Code klarer?

Es gibt viele Möglichkeiten, diesen Code zu verbessern, aber solange Sie nicht genau definiert haben, wozu dieser Code benötigt wird, entwickeln Sie keinen Code, sondern hacken ihn einfach zusammen in der Hoffnung, dass er funktioniert. Investiere die Zeit in sie und dein Leben wird einfacher.

Off-by-One-Fehler gehören zu den häufigsten Programmierfehlern. Sogar erfahrene Entwickler verstehen das manchmal falsch. Höhere Sprachen haben normalerweise Iterationskonstrukte wie foreachoder mapdie eine explizite Indizierung ganz vermeiden. Manchmal ist jedoch eine explizite Indizierung erforderlich, wie in Ihrem Beispiel.

Die Herausforderung besteht darin, wie man sich Bereiche von Array-Zellen vorstellt. Ohne ein klares mentales Modell wird es verwirrend, wann die Endpunkte ein- oder ausgeschlossen werden sollen.

Bei der Beschreibung von Array-Bereichen gilt die Konvention, die Untergrenze und die Obergrenze auszuschließen . Zum Beispiel ist der Bereich 0..3 die Zellen 0,1,2. Diese Konvention wird in allen 0-indizierten Sprachen verwendet. Beispielsweise gibt die slice(start, end)Methode in JavaScript das Subarray zurück, das mit Index beginnt start, aber keinen Index enthält end.

Es ist klarer, wenn Sie sich Bereichsindizes als Beschreibung der Kanten zwischen Array-Zellen vorstellen. Die folgende Abbildung zeigt ein Array der Länge 9, und die Zahlen unter den Zellen sind an den Rändern ausgerichtet. Sie werden zur Beschreibung von Arraysegmenten verwendet. ZB ist aus der Abbildung ersichtlich, dass der Bereich 2..5 die Zellen 2,3,4 ist.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 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

Dieses Modell ist konsistent damit, dass die Arraylänge die Obergrenze eines Arrays ist. Ein Array mit der Länge 5 hat Zellen 0..5, dh es gibt die fünf Zellen 0,1,2,3,4. Dies bedeutet auch, dass die Länge eines Segments die Obergrenze minus die Untergrenze ist, dh das Segment 2..5 hat 5-2 = 3 Zellen.

Wenn Sie dieses Modell berücksichtigen, wenn Sie nach oben oder unten iterieren, ist es viel klarer, wann Sie die Endpunkte ein- oder ausschließen müssen. Wenn Sie nach oben iterieren, müssen Sie den Startpunkt einschließen, aber den Endpunkt ausschließen. Wenn Sie abwärts iterieren, müssen Sie den Startpunkt (die obere Grenze) ausschließen, aber den Endpunkt (die untere Grenze) einschließen.

Da Sie in Ihrem Code nach unten iterieren, müssen Sie die Untergrenze 0 einschließen, damit Sie währenddessen iterieren j >= 0.

In Anbetracht dessen rightIndexverstößt die Auswahl, dass das Argument den letzten Index im Subarray darstellt, gegen die Konvention. Dies bedeutet, dass Sie beide Endpunkte (0 und rightIndex) in die Iteration einbeziehen müssen. Außerdem ist es schwierig, das leere Segment darzustellen (das Sie benötigen, wenn Sie die Sortierung starten). Tatsächlich müssen Sie -1 als rightIndex verwenden, wenn Sie den ersten Wert einfügen. Das scheint ziemlich unnatürlich. Es erscheint natürlicher, rightIndexden Index nach dem Segment anzugeben, daher steht 0 für das leere Segment.

Natürlich ist Ihr Code besonders verwirrend, da er das sortierte Unterfeld um eins erweitert und das Element unmittelbar nach dem anfänglich sortierten Unterfeld überschreibt. Sie lesen also aus dem Index j, schreiben aber den Wert auf j + 1. Hier sollte nur klar sein, dass j die Position in der anfänglichen Unteranordnung vor dem Einfügen ist. Wenn Indexoperationen zu knifflig werden, kann ich sie auf einem Blatt Rasterpapier darstellen.

Die Einleitung zu Ihrer Frage lässt mich denken, dass Sie nicht richtig gelernt haben, zu programmieren. Wer länger als ein paar Wochen in einer imperativen Sprache programmiert, sollte in mehr als 90% der Fälle seine Loop-Grenzen gleich beim ersten Mal richtig einstellen. Vielleicht beeilen Sie sich, mit dem Codieren zu beginnen, bevor Sie das Problem ausreichend durchdacht haben.

Ich schlage vor, Sie korrigieren diesen Mangel, indem Sie (erneut) lernen, wie man Schleifen schreibt - und ich würde empfehlen, einige Stunden mit Papier und Bleistift durch eine Reihe von Schleifen zu arbeiten. Nehmen Sie sich einen Nachmittag frei, um dies zu tun. Nehmen Sie sich dann etwa 45 Minuten Zeit, um sich mit dem Thema zu befassen, bis Sie es wirklich verstanden haben.

Es ist alles sehr gut zu testen, aber Sie sollten in der Erwartung testen, dass Sie im Allgemeinen Ihre Schleifengrenzen (und den Rest Ihres Codes) richtig hinbekommen.

Vielleicht sollte ich meinem Kommentar etwas Fleisch hinzufügen:

Es gibt nur einen Weg: Verstehe dein Problem besser. Aber das ist so allgemein wie Ihre Frage

Ihr Punkt ist

Obwohl ich meine Vermutungen nach einigem Ausprobieren richtig gemacht habe, war ich zu frustriert, weil ich kein korrektes Rechenmodell in meinem Kopf hatte.

Wenn ich lese trial and error, läuten meine Alarmglocken. Natürlich kennen viele von uns den Geisteszustand, wenn man ein kleines Problem beheben möchte und seinen Kopf um andere Dinge gewickelt hat und anfängt, auf die eine oder andere Weise zu raten, um den Code seemzu machen, was zu tun ist. Einige hackische Lösungen ergeben sich daraus - und einige von ihnen sind reine Genies ; aber um ehrlich zu sein: die meisten sind es nicht . Ich eingeschlossen, diesen Zustand kennend.

Unabhängig von Ihrem konkreten Problem stellten Sie Fragen, wie Sie sich verbessern können:

1) Test

Das haben andere gesagt, und ich hätte nichts Wertvolles hinzuzufügen

2) Problemanalyse

Es ist schwer, dazu einen Rat zu geben. Ich kann Ihnen nur zwei Tipps geben, die Ihnen wahrscheinlich dabei helfen, Ihre Kenntnisse zu diesem Thema zu verbessern:

• Das Offensichtliche und Trivialste ist auf lange Sicht das Effektivste: Viele Probleme lösen. Während Sie üben und wiederholen, entwickeln Sie die Denkweise, die Ihnen bei zukünftigen Aufgaben hilft. Das Programmieren ist wie jede andere Aktivität, die durch hartes Üben verbessert werden soll

Code Katas sind ein Weg, der ein bisschen helfen könnte.

Wie kommst du dazu, ein großartiger Musiker zu sein? Es hilft, die Theorie zu kennen und die Mechanik Ihres Instruments zu verstehen. Es hilft, Talent zu haben. Aber letztendlich kommt Größe aus dem Üben. Die Theorie immer wieder anwenden und Feedback verwenden, um jedes Mal besser zu werden.

Code Kata

Eine Seite, die ich sehr mag: Code Wars

Beherrschung durch Herausforderung erreichen Verbessern Sie Ihre Fähigkeiten, indem Sie mit anderen in echten Code-Herausforderungen trainieren

Dies sind relativ kleine Probleme, die Ihnen helfen, Ihre Programmierkenntnisse zu verbessern. Und was mir an Code Wars am besten gefällt, ist, dass Sie Ihre Lösung mit einer anderen vergleichen können .

Oder vielleicht sollten Sie einen Blick auf Exercism.io werfen, wo Sie Feedback von der Community erhalten.

• Der andere Rat ist beinahe ebenso trivial: Probleme auflösen lernen Sie müssen sich selbst trainieren und Probleme in wirklich kleine Probleme auflösen. Wenn Sie sagen, dass Sie Probleme beim Schreiben von Schleifen haben , machen Sie den Fehler, dass Sie die Schleife als Ganzes sehen und nicht in Teile zerlegen. Wenn Sie lernen, die Dinge Schritt für Schritt auseinander zu nehmen , lernen Sie, solche Fehler zu vermeiden.

Ich weiß - wie ich oben schon sagte -, dass es manchmal schwierig ist, "einfache" Dinge in "einfachere" Aufgaben zu unterteilen. aber es hilft sehr.

Ich erinnere mich, als ich das erste Mal professionell programmieren lernte , hatte ich große Probleme beim Debuggen meines Codes. Was war das Problem? Hybris - Der Fehler kann nicht in so oder so einer Region des Codes sein, weil ich weiß, dass es nicht sein kann. Und in der Folge? Ich überflog den Code, anstatt ihn zu analysieren, und musste lernen - auch wenn es mühsam war, Anweisungen für Anweisungen in meinen Code zu zerlegen .

3) Entwickeln Sie einen Toolbelt

Abgesehen davon, dass Sie Ihre Sprache und Ihre Werkzeuge kennen - ich weiß, dass dies die glänzenden Dinge sind, an die Entwickler zuerst denken - lernen Sie Algorithmen (auch bekannt als Lesen).

Hier sind zwei Bücher zu Beginn:

• Einführung in die Algortihms

• Algorithmen

Dies ist wie das Erlernen einiger Rezepte, um mit dem Kochen zu beginnen. Zuerst wissen Sie nicht, was Sie tun sollen, also müssen Sie schauen, welche früheren Köche für Sie gekocht haben. Das gleiche gilt für Algortihms. Algorithmen sind wie Kochrezepte für gemeinsame Mahlzeiten (Datenstrukturen, Sortieren, Haschieren usw.). Wenn Sie sie auswendig kennen (zumindest versuchen), haben Sie einen guten Ausgangspunkt.

3a) Programmierkonstrukte kennen

Dieser Punkt ist sozusagen eine Ableitung. Kennen Sie Ihre Sprache - und besser: wissen Sie, welche Konstrukte in Ihrer Sprache möglich sind .

Ein gemeinsamer Punkt für schlecht oder ineffizienten Code ist manchmal, dass der Programmierer nicht den Unterschied zwischen dem verschiedenen Arten von Schleifen weiß ( for-, while-und do-loops). Sie sind irgendwie alle austauschbar; Unter bestimmten Umständen führt die Auswahl eines anderen Schleifenkonstrukts jedoch zu eleganterem Code.

Und da ist Duffs Gerät ...

PS:

Ansonsten ist Ihr Kommentar nicht gut als Donal Trump.

Ja, wir sollten das Programmieren wieder großartig machen!

Ein neues Motto für Stackoverflow.

Wenn ich das Problem richtig verstanden habe, lautet Ihre Frage, wie Sie vom ersten Versuch an richtig denken, um Schleifen zu erhalten, und nicht, wie Sie sicherstellen, dass Ihre Schleife richtig ist (für die die Antwort wie in den anderen Antworten erläutert getestet wird).

Was ich für einen guten Ansatz halte, ist das Schreiben der ersten Iteration ohne Schleife. Nachdem Sie dies getan haben, sollten Sie feststellen, was zwischen den Iterationen geändert werden sollte.

Ist es eine Zahl wie eine 0 oder eine 1? Dann brauchen Sie höchstwahrscheinlich ein für und Bingo, Sie haben auch Ihr Start-i. Überlegen Sie dann, wie oft Sie dasselbe ausführen möchten, und Sie haben auch Ihre Endbedingung.

Wenn Sie nicht genau wissen, wie oft es ausgeführt wird, brauchen Sie kein for, sondern eine Weile oder eine do while.

Technisch gesehen kann jede Schleife in eine andere übersetzt werden. Der Code ist jedoch einfacher zu lesen, wenn Sie die richtige Schleife verwenden. Hier einige Tipps:

1. Wenn Sie feststellen, dass Sie ein if () {...; break;} in ein for schreiben, brauchen Sie eine Weile, und Sie haben bereits die Bedingung

2. "While" ist vielleicht die am häufigsten verwendete Schleife in jeder Sprache, sollte aber nicht imo sein. Wenn Sie feststellen, dass Sie bool ok = True schreiben; while (check) {mach etwas und ändere hoffentlich irgendwann ok}; Dann brauchen Sie nicht eine Weile, sondern eine Pause, denn das bedeutet, dass Sie alles haben, was Sie brauchen, um die erste Iteration auszuführen.

Nun ein bisschen Kontext ... Als ich zum ersten Mal Programmieren lernte (Pascal), sprach ich kein Englisch. Für mich war "for" und "while" nicht sehr sinnvoll, aber das Schlüsselwort "repeat" (do while in C) ist in meiner Muttersprache fast dasselbe, daher würde ich es für alles verwenden. Wiederholen (do while) ist meiner Meinung nach die natürlichste Schleife, denn fast immer möchten Sie, dass etwas getan wird, und dann möchten Sie, dass es immer wieder getan wird, bis ein Ziel erreicht ist. "For" ist nur eine Abkürzung, die Ihnen einen Iterator gibt und die Bedingung seltsamerweise an den Anfang des Codes setzt, obwohl Sie fast immer möchten, dass etwas getan wird, bis etwas passiert. While ist nur eine Abkürzung für if () {do while ()}. Verknüpfungen sind nett für später,

Ich werde ein detaillierteres Beispiel geben, wie man Pre / Post-Bedingungen und Invarianten verwendet, um eine korrekte Schleife zu entwickeln. Zusammen werden solche Behauptungen als Spezifikation oder Vertrag bezeichnet.

Ich schlage nicht vor, dass Sie versuchen, dies für jede Schleife zu tun. Aber ich hoffe, dass Sie es nützlich finden, den beteiligten Denkprozess zu sehen.

Zu diesem Zweck übersetze ich Ihre Methode in ein Tool namens Microsoft Dafny , mit dem die Richtigkeit solcher Spezifikationen nachgewiesen werden soll. Es prüft auch die Beendigung jeder Schleife. Bitte beachten Sie, dass Dafny keine forSchleife hat und ich whilestattdessen eine Schleife verwenden musste.

Abschließend werde ich zeigen, wie Sie solche Spezifikationen verwenden können, um eine wohl etwas einfachere Version Ihrer Schleife zu entwerfen. Diese einfachere Loop-Version hat tatsächlich die Loop-Bedingung j > 0und die Zuweisung array[j] = value- so wie es Ihre anfängliche Intuition war.

Dafny wird uns beweisen, dass beide Schleifen korrekt sind und dasselbe tun.

Ich werde dann, basierend auf meinen Erfahrungen, einen allgemeinen Anspruch darauf erheben, wie man eine korrekte Rückwärtsschleife schreibt, der Ihnen vielleicht helfen wird, wenn Sie in Zukunft mit dieser Situation konfrontiert werden.

Erster Teil - Schreiben einer Spezifikation für die Methode

Die erste Herausforderung besteht darin, festzustellen, was die Methode tatsächlich leisten soll. Zu diesem Zweck habe ich Vor- und Nachbedingungen entworfen, die das Verhalten der Methode festlegen. Um die Spezifikation genauer zu machen, habe ich die Methode dahingehend erweitert, dass sie den Index zurückgibt, an dem sie valueeingefügt wurde.

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..])

Diese Spezifikation erfasst das Verhalten der Methode vollständig. Meine Hauptbemerkung zu dieser Spezifikation ist, dass es vereinfacht würde, wenn der Prozedur der Wert übergeben würde, rightIndex+1anstatt rightIndex. Da ich jedoch nicht sehen kann, woher diese Methode stammt, weiß ich nicht, welche Auswirkungen diese Änderung auf den Rest des Programms haben würde.

Zweiter Teil - Bestimmung einer Schleifeninvariante

Jetzt haben wir eine Spezifikation für das Verhalten der Methode. Wir müssen eine Spezifikation für das Schleifenverhalten hinzufügen, die Dafny davon überzeugt, dass die Ausführung der Schleife beendet wird und zum gewünschten Endzustand von führt array.

Das Folgende ist Ihre ursprüngliche Schleife, übersetzt in Dafny-Syntax mit hinzugefügten Schleifeninvarianten. Ich habe es auch geändert, um den Index zurückzugeben, in dem Wert eingefügt wurde.

{
    // 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
}

Dies wird in Dafny bestätigt. Sie können es selbst sehen, indem Sie diesem Link folgen . Ihre Schleife implementiert also die Methodenspezifikation, die ich in Teil 1 geschrieben habe, korrekt. Sie müssen entscheiden, ob diese Methodenspezifikation wirklich das gewünschte Verhalten ist.

Beachten Sie, dass Dafny hier einen Beweis für die Richtigkeit vorlegt. Dies ist eine weitaus stärkere Garantie für die Richtigkeit, als dies durch Tests möglich ist.

Dritter Teil - eine einfachere Schleife

Jetzt haben wir eine Methodenspezifikation, die das Verhalten der Schleife erfasst. Wir können die Implementierung der Schleife sicher ändern, ohne jedoch die Gewissheit zu verlieren, dass wir das Verhalten der Schleife nicht geändert haben.

Ich habe die Schleife so modifiziert, dass sie Ihren ursprünglichen Vorstellungen über den Schleifenzustand und den Endwert von entspricht j. Ich würde argumentieren, dass diese Schleife einfacher ist als die Schleife, die Sie in Ihrer Frage beschrieben haben. Es ist häufiger in der Lage, jals zu verwenden j+1.

1. Beginne j um rightIndex+1

2. Ändern Sie die Schleifenbedingung in j > 0 && arr[j-1] > value

3. Ändern Sie die Zuordnung zu arr[j] := value

4. Dekrementieren Sie den Schleifenzähler am Ende der Schleife und nicht am Anfang

Hier ist der Code. Beachten Sie, dass die Schleifeninvarianten jetzt auch etwas einfacher zu schreiben sind:

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

Vierter Teil - Hinweise zum Rückwärtsschleifen

Nachdem ich über einige Jahre viele Schleifen geschrieben und als richtig erwiesen habe, habe ich den folgenden allgemeinen Ratschlag zum Zurückschleifen.

Es ist fast immer einfacher, über eine Rückwärtsschleife (Dekrementierungsschleife) nachzudenken und diese zu schreiben, wenn die Dekrementierung am Anfang der Schleife und nicht am Ende durchgeführt wird.

Leider macht das forSchleifenkonstrukt in vielen Sprachen dies schwierig.

Ich vermute (kann aber nicht beweisen), dass diese Komplexität den Unterschied in Ihrer Intuition darüber verursacht hat, was die Schleife sein sollte und was sie eigentlich sein musste. Sie sind es gewohnt, über vorwärts gerichtete (inkrementelle) Schleifen nachzudenken. Wenn Sie eine Rückwärtsschleife (Dekrementierungsschleife) schreiben möchten, versuchen Sie, die Schleife zu erstellen, indem Sie versuchen, die Reihenfolge umzukehren, in der die Vorwärtsschleife (Inkrementierungsschleife) ausgeführt wird. Aufgrund der Funktionsweise des forKonstrukts haben Sie jedoch versäumt, die Reihenfolge der Zuweisung und die Aktualisierung der Schleifenvariablen umzukehren. Dies ist für eine echte Umkehrung der Reihenfolge der Operationen zwischen einer Rückwärts- und einer Vorwärtsschleife erforderlich.

Fünfter Teil - Bonus

Der Vollständigkeit halber sehen Sie hier den Code, den Sie erhalten, wenn Sie rightIndex+1die Methode anstelle von übergeben rightIndex. Diese Änderung beseitigt alle +2Offsets, die ansonsten erforderlich sind, um über die Richtigkeit der Schleife nachzudenken.

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

Es ist eine Frage der Erfahrung, wie einfach und flüssig dies funktioniert . Auch wenn die Sprache es Ihnen nicht erlaubt, es direkt auszudrücken, oder wenn Sie einen komplexeren Fall verwenden, als es mit dem einfachen eingebauten Ding möglich ist, ist Ihrer Meinung nach eine höhere Ebene wie "jedes Element einmal in der Reihenfolge der Ehrerbietung besuchen" und Der erfahrene Coder setzt das sofort in die richtigen Details um, weil er es so oft getan hat.

Selbst dann ist es in komplexeren Fällen leicht, sich zu irren, weil das, was Sie schreiben, in der Regel nicht das ist, was in Dosen vorkommt. Mit moderneren Sprachen und Bibliotheken schreiben Sie nicht die einfache Sache, weil es ein festes Konstrukt oder einen Aufruf dafür gibt. In C ++ lautet das moderne Mantra "Algorithmen verwenden, anstatt Code zu schreiben".

Der Weg, um sicherzustellen, dass es richtig ist, für diese Art von Dingen im Besonderen, besteht darin, die Randbedingungen zu betrachten . Durchsuche den Code in deinem Kopf nach den wenigen Fällen an den Rändern, an denen sich die Dinge ändern. Wenn index == array-maxja, was passiert dann? Was ist max-1? Wenn der Code falsch abbiegt, befindet er sich an einer dieser Grenzen. Einige Schleifen müssen sich darum kümmern, dass das erste oder letzte Element sowie das Schleifenkonstrukt die Grenzen richtig setzen. zB wenn Sie sich beziehen a[I]und a[I-1]was passiert, wenn Ider Minimalwert ist?

Schauen Sie sich auch Fälle an, in denen die Anzahl der (korrekten) Iterationen extrem ist: Wenn die Grenzen erfüllt sind und Sie 0 Iterationen haben, funktioniert das dann nur ohne einen Sonderfall? Und was ist mit nur einer Iteration, bei der die unterste Grenze gleichzeitig auch die höchste Grenze ist?

Das Untersuchen der Kantenfälle (beide Seiten jeder Kante) ist das, was Sie beim Schreiben der Schleife tun sollten und was Sie bei Codeüberprüfungen tun sollten.

Ich werde versuchen, mich von den genannten Themen bereits in Hülle und Fülle fernzuhalten.

Was sind Werkzeuge / mentale Modelle, um solche Fehler zu vermeiden?

Werkzeuge

Für mich ist das größte Werkzeug, um besser zu schreiben forund whileSchleifen zu erstellen, keine foroder gar keine whileSchleifen zu schreiben .

Die meisten modernen Sprachen versuchen, dieses Problem auf die eine oder andere Weise anzugehen. Zum Beispiel hat Java, obwohl es Iteratorvon Anfang an etwas umständlich zu bedienen war, eine Abkürzungssyntax eingeführt, um die Verwendung in einer neueren Version zu erleichtern. C # hat sie auch usw.

Meine derzeit favorisierte Sprache, Ruby, hat auf dem funktionalen Ansatz ( .each, .mapetc.) Full-Front. Das ist sehr mächtig. Ich habe gerade eine schnelle Zählung in einer Ruby-Codebasis durchgeführt, an der ich arbeite: In ungefähr 10.000 Codezeilen gibt es null forund ungefähr fünf while.

Wenn ich gezwungen wäre, eine neue Sprache zu wählen, würde die Suche nach solchen funktionalen / datenbasierten Schleifen ganz oben auf der Prioritätenliste stehen.

Mentale Modelle

Denken Sie daran, dass dies whiledas Minimum an Abstraktion ist, das Sie nur einen Schritt weiter oben erhalten können goto. Meiner Meinung nach formacht es noch schlimmer als besser, da es alle drei Teile der Schleife eng zusammenbricht.

Also, wenn ich in einer Umgebung bin, in der fores benutzt wird, dann stelle ich verdammt sicher, dass alle 3 Teile absolut einfach und immer gleich sind. Das heißt, ich werde schreiben

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

Aber nichts sehr komplexes. Vielleicht, vielleicht habe ich manchmal einen Countdown, aber ich werde mein Bestes tun, um das zu vermeiden.

Bei der Verwendung whilehalte ich mich von verworrenen inneren Shenannigans fern, die die Schleifenbedingung betreffen. Der Test im Innern while(...)wird so einfach wie möglich sein und ich werde vermeiden, breakso gut ich kann. Außerdem ist die Schleife kurz (Zählen von Codezeilen) und größere Codemengen werden herausgerechnet.

Insbesondere wenn die aktuelle while-Bedingung komplex ist, verwende ich eine "Bedingungsvariable", die sehr leicht zu erkennen ist und die Bedingung nicht in die whileAnweisung selbst einfügt :

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

(Oder so ähnlich, natürlich im richtigen Maße.)

Dies gibt Ihnen ein sehr einfaches mentales Modell: "Diese Variable läuft monoton von 0 bis 10" oder "Diese Schleife läuft, bis diese Variable falsch / wahr ist". Die meisten Gehirne scheinen in der Lage zu sein, mit dieser Abstraktionsebene zurechtzukommen.

Ich hoffe, das hilft.

Insbesondere Reverse-Loops sind schwer zu überlegen, da viele unserer Programmiersprachen sowohl in der üblichen for-Loop-Syntax als auch durch die Verwendung von nullbasierten halboffenen Intervallen auf Vorwärtsiteration ausgerichtet sind. Ich sage nicht, dass es falsch ist, dass die Sprachen diese Entscheidungen getroffen haben; Ich sage nur, dass diese Entscheidungen das Denken über umgekehrte Schleifen erschweren.

Denken Sie im Allgemeinen daran, dass eine for-Schleife nur syntaktischer Zucker ist, der um eine while-Schleife herum aufgebaut ist:

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

ist äquivalent zu:

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

(Möglicherweise mit einer zusätzlichen Ebene für den Gültigkeitsbereich, um die im Init-Schritt deklarierten Variablen lokal für die Schleife zu halten.)

Dies ist für viele Arten von Schleifen in Ordnung, aber wenn Sie rückwärts gehen, ist es schwierig, den letzten Schritt zu machen. Wenn Sie rückwärts arbeiten, ist es einfacher, den Schleifenindex mit dem Wert nach dem gewünschten Wert zu beginnen und den stepTeil wie folgt an den oberen Rand der Schleife zu verschieben:

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
}

oder als for-Schleife:

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

Dies kann nervig erscheinen, da sich der Schrittausdruck im Hauptteil und nicht in der Kopfzeile befindet. Dies ist ein bedauerlicher Nebeneffekt der inhärenten Vorwärtsneigung für die Schleifensyntax. Aus diesem Grund werden einige argumentieren, dass Sie dies stattdessen tun:

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

Dies ist jedoch eine Katastrophe, wenn Ihre Indexvariable vom Typ ohne Vorzeichen ist (wie in C oder C ++).

In diesem Sinne schreiben wir Ihre Einfügefunktion.

1. Da wir rückwärts arbeiten, wird der Schleifenindex der Eintrag nach dem "aktuellen" Array-Slot sein. Ich würde die Funktion so entwerfen, dass sie die Größe der Ganzzahl und nicht den Index bis zum letzten Element annimmt, da halboffene Bereiche in den meisten Programmiersprachen die natürliche Art der Darstellung von Bereichen sind und uns die Möglichkeit gibt, ein leeres Array ohne Umsortierung darzustellen auf einen magischen Wert wie -1.

   function insert(array, size, value) {
     var j = size;
   

2. Während der neue Wert kleiner als das vorherige Element ist, verschieben Sie ihn weiter. Natürlich kann das vorherige Element nur geprüft werden , ob es ist ein vorhergehendes Element, so dass wir zuerst überprüfen müssen , dass wir nicht gleich am Anfang sind:

     while (j != 0 && value < array[j - 1]) {
       --j;  // now j become current
       array[j + 1] = array[j];
     }
   

3. Dies lässt jgenau dort, wo wir den neuen Wert wollen.

     array[j] = value; 
   };
   

Das Programmieren von Pearls von Jon Bentley bietet eine sehr klare Erklärung der Einfügesortierung (und anderer Algorithmen), mit deren Hilfe Sie Ihre mentalen Modelle für diese Art von Problemen erstellen können.

Sind Sie einfach verwirrt darüber, was eine forSchleife tatsächlich tut und wie sie funktioniert?

for(initialization; condition; increment*)
{
    body
}

1. Zunächst wird die Initialisierung ausgeführt
2. Dann wird der Zustand geprüft
3. Wenn die Bedingung erfüllt ist, wird der Körper einmal ausgeführt. Wenn nicht, gehe zu # 6
4. Der Inkrementcode wird ausgeführt
5. Springe zu # 2
6. Ende der Schleife

Es kann nützlich sein, diesen Code mit einem anderen Konstrukt umzuschreiben. Hier ist dasselbe mit einer while-Schleife:

initialization
while(condition)
{
    body
    increment
}

Hier sind einige andere Vorschläge:

• Können Sie ein anderes Sprachkonstrukt wie eine foreach-Schleife verwenden? Dies erledigt die Bedingung und den Inkrementierungsschritt für Sie.
• Können Sie eine Karten- oder Filterfunktion verwenden? Einige Sprachen haben Funktionen mit diesen Namen, die eine Sammlung intern für Sie durchlaufen. Sie liefern nur die Sammlung und den Körper.
• Sie sollten wirklich mehr Zeit damit verbringen, sich mit forSchleifen vertraut zu machen . Sie werden sie die ganze Zeit benutzen. Ich schlage vor, dass Sie eine for-Schleife in einem Debugger durchlaufen, um zu sehen, wie sie ausgeführt wird.

* Beachten Sie, dass ich zwar den Begriff "Inkrement" verwende, es sich jedoch nur um einen Code handelt, der sich hinter dem Textkörper und vor der Zustandsprüfung befindet. Es kann ein Dekrement oder gar nichts sein.

Versuch zusätzlicher Einsichten

Für nicht triviale Algorithmen mit Schleifen können Sie die folgende Methode verwenden:

1. Erstellen Sie ein festes Array mit 4 Positionen und geben Sie einige Werte ein, um das Problem zu simulieren .
2. Schreiben Sie Ihren Algorithmus auf das gegebene Problem zu lösen , ohne Schleife und mit hartcodierte Indizierungen ;
3. Danach werden hartcodierte Indexierungen substituieren im Code mit einigen variable ioder jund Inkrement / Dekrement diese Variablen wie erforderlich (aber immer noch ohne jede Schleife);
4. Schreiben Sie Ihren Code um und fügen Sie die sich wiederholenden Blöcke in eine Schleife ein , um die Vor- und Nachbedingungen zu erfüllen.
5. [ optional ] Schreiben Sie Ihre Schleife so, dass sie die gewünschte Form hat (für / while / do while).
6. Das Wichtigste ist, dass Sie Ihren Algorithmus richtig schreiben. Danach überarbeiten und optimieren Sie gegebenenfalls Ihren Code / Ihre Schleifen (was den Code für einen Leser jedoch möglicherweise nicht mehr trivial macht).

Ihr Problem

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

Schreiben Sie den Körper der Schleife mehrmals manuell

Verwenden wir ein festes Array mit 4 Positionen und versuchen Sie, den Algorithmus manuell ohne Schleifen zu schreiben:

           //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

Schreiben Sie neu und entfernen Sie fest codierte Werte

//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

In eine Schleife übersetzen

Mit 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;
    }
}

Refactor / rewrite / optimiere die Schleife wie du willst:

Mit 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

mit 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: Der Code setzt voraus, dass die Eingabe gültig ist und dass das Array keine Wiederholungen enthält.

Aus diesem Grund würde ich es nach Möglichkeit vermeiden, Schleifen zu schreiben, die auf Rohindizes basieren, und zwar zugunsten von abstrakteren Operationen.

In diesem Fall würde ich so etwas tun (in Pseudocode):

array = array[:(rightIndex - 1)] + value + array[rightIndex:]

In Ihrem Beispiel ist der Körper der Schleife ziemlich offensichtlich. Und es liegt auf der Hand, dass am Ende ein Element geändert werden muss. Sie schreiben also den Code, jedoch ohne den Beginn der Schleife, die Endebedingung und die endgültige Zuweisung.

Dann entfernen Sie sich vom Code und finden heraus, welcher Zug zuerst ausgeführt werden muss. Sie ändern den Anfang der Schleife so, dass der erste Zug korrekt ist. Sie verlassen den Code erneut und finden heraus, welcher Zug als letzter ausgeführt werden muss. Sie ändern die Endebedingung so, dass der letzte Zug korrekt ist. Und schließlich lösen Sie sich von Ihrem Code und finden heraus, wie die endgültige Zuweisung lauten muss, und korrigieren den Code entsprechend.