Wie schreibe ich richtige Schleifen?

65

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?

CodeYogi
quelle
6
Unter welchen Umständen halten Sie das j >= 0für einen Fehler? Ich wäre vorsichtiger, wenn Sie darauf zugreifen array[j]und dies array[j + 1]nicht vorher überprüfen würden array.length > (j + 1).
Ben Cottrell
5
In Anlehnung an @LightnessRacesinOrbit lösen Sie wahrscheinlich Probleme, die bereits gelöst wurden. Im Allgemeinen ist eine Schleife, die Sie über eine Datenstruktur ausführen müssen, bereits in einem Kernmodul oder einer Klasse vorhanden (wie Array.prototypeim Beispiel von JS). Dies verhindert, dass Randbedingungen auftreten, da so etwas mapauf allen Arrays funktioniert. Sie können das oben beschriebene Problem mit slice und concat lösen, um ein gemeinsames Schleifen zu vermeiden: codepen.io/anon/pen/ZWovdg?editors=0012 Der korrekteste Weg, eine Schleife zu schreiben, besteht darin, überhaupt keine zu schreiben.
Jed Schneider
13
Tatsächlich gehen Sie voran und lösen Sie gelöste Probleme. Das nennt man Übung. Nur nicht die Mühe machen, sie zu veröffentlichen. Das heißt, es sei denn, Sie finden einen Weg, um die Lösungen zu verbessern. Das heißt, das Rad neu zu erfinden bedeutet mehr als das Rad. Es beinhaltet ein Qualitätskontrollsystem für ganze Räder und die Kundenbetreuung. Trotzdem sind Custom Felgen nett.
candied_orange
53
Ich fürchte, wir gehen hier in die falsche Richtung. CodeYogi Mist zu geben, weil sein Beispiel Teil eines bekannten Algorithmus ist, ist ziemlich unbegründet. Er hat nie behauptet, er hätte etwas Neues erfunden. Er fragt, wie man beim Schreiben einer Schleife einige sehr häufige Randfehler vermeidet. Bibliotheken haben einen langen Weg zurückgelegt, aber ich sehe immer noch eine Zukunft für Leute, die wissen, wie man Loops schreibt.
candied_orange
5
Im Allgemeinen sollten Sie beim Umgang mit Schleifen und Indizes lernen, dass Indizes auf Elemente verweisen, und sich mit halboffenen Intervallen vertraut machen (tatsächlich handelt es sich um zwei Seiten desselben Konzepts). Sobald Sie diese Fakten erhalten, verschwindet ein Großteil der Kopfkratzer in den Loops / Indizes vollständig.
Matteo Italia

Antworten:

208

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

kandierte_orange
quelle
36
Gute Antwort, aber vielleicht sollten Sie das Testen erwähnen. Wie geht man im Unit-Test mit Endlosschleifen um? Bricht eine solche Schleife die Tests nicht?
GameAlchemist
139
@ GameAlchemist Das ist der Pizzatest. Wenn mein Code in der Zeit, die ich für die Herstellung einer Pizza benötige, nicht mehr aufhört zu laufen, beginne ich zu vermuten, dass etwas nicht stimmt. Sicher, es ist kein Heilmittel für Alan Turings Stillstandsproblem, aber zumindest bekomme ich eine Pizza aus dem Deal.
candied_orange
12
@CodeYogi - eigentlich kann es sehr nahe kommen. Beginnen Sie mit einem Test, der mit einem einzelnen Wert arbeitet. Implementieren Sie den Code ohne eine Schleife. Schreiben Sie dann einen Test, der mit zwei Werten arbeitet. Implementieren Sie die Schleife. Es ist sehr unwahrscheinlich, dass Sie in der Schleife eine falsche Randbedingung erhalten, wenn Sie dies tun, da in fast allen Fällen der eine oder der andere dieser beiden Tests fehlschlägt, wenn Sie einen solchen Fehler machen.
Jules
15
@CodeYogi Geck alle Dank an TDD, aber Testen >> TDD. Das Ausgeben eines Werts kann ein Test sein, ein zweiter Blick auf Ihren Code ist ein Test (Sie können dies als Codeüberprüfung formalisieren, aber ich greife oft nur nach jemandem für ein 5-minütiges Gespräch). Ein Test ist jede Chance, die Sie geben, um Ihre Absicht zum Scheitern auszudrücken. Zur Hölle, Sie können Ihren Code testen, indem Sie mit Ihrer Mutter über eine Idee sprechen. Ich habe Fehler in meinem Code gefunden, als ich auf die Kacheln in der Dusche gestarrt habe. TDD ist eine effektive, formalisierte Disziplin, die Sie nicht in jedem Geschäft finden. Ich habe noch nie irgendwo codiert, wo die Leute nicht getestet haben.
candied_orange
12
Ich habe Jahr für Jahr programmiert und getestet, bevor ich jemals von TDD gehört hatte. Erst jetzt wird mir klar, dass diese Jahre mit den Jahren zu tun haben, in denen ich ohne Hose codiert habe.
candied_orange
72

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

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.

Matthieu M.
quelle
8
@ CodeYogi: Mit ... Tests. Die Sache ist, es kann unpraktisch sein, alles in Behauptungen auszudrücken : Wenn die Behauptung nur den Code wiederholt, bringt sie nichts Neues (Wiederholung hilft nicht bei der Qualität). Deshalb habe ich hier in der Schleife nicht behauptet, dass 0 <= j <= rightIndexoder array[j] <= value, es würde nur den Code wiederholen. Auf der anderen Seite is_sortedbringt eine neue Garantie, somit ist es wertvoll. Danach sind das Tests. Wenn Sie insert([0, 1, 2], 2, 3)Ihre Funktion aufrufen und die Ausgabe nicht erfolgt [0, 1, 2, 3], haben Sie einen Fehler gefunden.
Matthieu M.
3
@MatthieuM. Diskontieren Sie den Wert einer Behauptung nicht, nur weil sie den Code dupliziert. Tatsächlich können diese Aussagen sehr wertvoll sein, wenn Sie sich entscheiden, den Code neu zu schreiben. Das Testen hat das Recht, sich zu wiederholen. Überlegen Sie lieber, ob die Behauptung so an eine einzelne Codeimplementierung gekoppelt ist, dass ein erneutes Schreiben die Behauptung ungültig machen würde. Dann verschwenden Sie Ihre Zeit. Schöne Antwort übrigens.
candied_orange
1
@CandiedOrange: Mit dem Duplizieren des Codes meine ich wörtlich array[j+1] = array[j]; assert(array[j+1] == array[j]);. In diesem Fall scheint der Wert sehr, sehr niedrig zu sein (Kopieren / Einfügen). Wenn Sie die Bedeutung duplizieren, aber auf eine andere Weise ausdrücken, wird sie wertvoller.
Matthieu M.
10
Hoares Regeln: Helfen, korrekte Loops seit 1969 zu schreiben. "Obwohl diese Techniken seit mehr als einem Jahrzehnt bekannt sind, haben die meisten Programmierer noch nie von ihnen gehört."
Joker_vD
1
@MatthieuM. Ich stimme zu, dass es einen sehr geringen Wert hat. Aber ich denke nicht, dass es durch Kopieren / Einfügen verursacht wird. Angenommen, ich wollte eine Umgestaltung durchführen, insert()damit dies durch Kopieren von einem alten Array auf ein neues Array funktioniert. Das kann getan werden, ohne deine anderen zu zerbrechen assert. Aber nicht das letzte. Zeigt nur, wie gut Ihre anderen assertentworfen wurden.
candied_orange
29

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;
}
Arseni Mourzenko
quelle
3
Nun, aus Ihrer ursprünglichen Frage habe ich den Eindruck, dass die Wahl zum einen auf der Verwendung von TDD und der Erzielung der richtigen Lösung beruht und zum anderen das Testteil übersprungen wird und die Randbedingungen falsch sind.
Arseni Mourzenko
18
Vielen Dank für Ihren derjenige , den die Elefanten im Raum zu erwähnen: nicht mit Schleifen überhaupt . Warum die Leute immer noch wie 1985 programmieren (und ich bin großzügig), ist mir ein Rätsel. BOCTAOE.
Jared Smith
4
@JaredSmith Wenn der Computer diesen Code tatsächlich ausführt, wie viel möchten Sie wetten, dass dort keine Sprunganweisung enthalten ist? Mit LINQ abstrahieren Sie die Schleife, aber sie ist immer noch da. Ich habe das Mitarbeitern erklärt, die nichts über die harte Arbeit von Shlemiel, dem Maler, gelernt haben . Wenn man nicht versteht, wo Schleifen auftreten, selbst wenn sie nicht im Code enthalten sind und der Code dadurch deutlich besser lesbar ist, führt dies fast immer zu Leistungsproblemen, die man nicht erklären kann, geschweige denn beheben kann.
ein CVn
6
@ MichaelKjörling: Wenn Sie LINQ verwenden, ist die Schleife vorhanden, aber ein for(;;)Konstrukt würde diese Schleife nicht sehr beschreiben . Ein wichtiger Aspekt ist, dass LINQ (sowie Listenverständnisse in Python und ähnliche Elemente in anderen Sprachen) die Randbedingungen zumindest im Rahmen der ursprünglichen Frage zumeist irrelevant macht. Über die Notwendigkeit, zu verstehen, was unter der Haube passiert, wenn LINQ verwendet wird, kann ich mich jedoch nicht mehr einigen, insbesondere wenn es um verzögerte Evaluierung geht.
Arseni Mourzenko
4
@ MichaelKjörling Ich habe nicht unbedingt über LINQ gesprochen und irgendwie verstehe ich deinen Standpunkt nicht. forEach, map, LazyIteratorEtc. wird durch die Sprache der Compiler oder Laufzeitumgebung zur Verfügung gestellt und sind wohl weniger wahrscheinlich bei jeder Iteration zurück in die Farbeimer zu Fuß. Das, die Lesbarkeit und Fehler, die bei jedem einzelnen auftreten, sind die beiden Gründe, warum diese Funktionen modernen Sprachen hinzugefügt wurden.
Jared Smith
15

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.

Bryce Wagner
quelle
4
Ich mag es wirklich for (int i = 0; i < length; i++). Sobald ich mich an diese Gewohnheit gewöhnt hatte, hörte ich <=fast genauso oft auf zu benutzen und fühlte, dass die Schleifen einfacher wurden. Aber for (int i = length - 1; i >= 0; i--)scheint zu kompliziert, im Vergleich zu: for (int i=length; i--; )(was wahrscheinlich noch sinnvoll wäre , als zu schreiben , whileSchleife , wenn ich versuchte zu machen ihaben einen geringeren Umfang / Leben). Das Ergebnis durchläuft die Schleife weiterhin mit i == Länge-1 (anfangs) bis i == 0, wobei der einzige funktionale Unterschied darin besteht, dass die while()Version nach der Schleife mit i == -1 endet (falls sie weiterlebt), anstatt mit i = = 0.
TOOGAM
2
@TOOGAM (int i = length; i--;) funktioniert in C / C ++, da 0 als falsch ausgewertet wird, aber nicht alle Sprachen diese Entsprechung haben. Ich denke, Sie könnten sagen, ich ...> 0.
Bryce Wagner
Wenn Sie eine Sprache verwenden, die die " > 0" gewünschte Funktionalität erfordert, sollten Sie natürlich solche Zeichen verwenden, da diese für diese Sprache erforderlich sind. Doch auch in diesen Fällen nur mit dem „ > 0“ ist einfacher als von dem zweiteiligen Prozess zu tun zuerst , eines Subtrahieren und dann auch mit „ >= 0“. Nachdem ich das durch ein wenig Erfahrung gelernt hatte, musste ich das Gleichheitszeichen (z. B. " >= 0") in meinen Schleifentestbedingungen viel seltener verwenden, und der resultierende Code hat sich seitdem im Allgemeinen einfacher angefühlt.
TOOGAM
1
@BryceWagner Wenn Sie etwas tun müssen i-- > 0, probieren Sie doch den klassischen Witz aus i --> 0!
Porglezomp
3
@porglezomp Ah ja das geht an Betreiber . Die meisten C-ähnlichen Sprachen, einschließlich C, C ++, Java und C #, haben diese.
ein CVn
11

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.

James Snell
quelle
2
Auch wenn Sie Ihre Indizes an eine vorhandene Funktion (z. B. Array.Copy) übergeben, müssen Sie möglicherweise nachdenken, um die richtigen Bindungsbedingungen zu erhalten. Stellen Sie sich vor, was in Situationen mit Länge 0 und Länge 1 und Länge 2 passiert, um sicherzustellen, dass Sie nicht zu wenig oder zu viele kopieren.
Bryce Wagner
@BryceWagner - Auf jeden Fall wahr, aber ohne eine klare Vorstellung davon, welches Problem Sie tatsächlich lösen, werden Sie viel Zeit damit verbringen, sich in der Dunkelheit in einer Strategie zu schlagen, die bei weitem das OP ist größtes Problem an dieser Stelle.
James Snell
2
@CodeYogi - Sie haben das Problem in Teilprobleme unterteilt, und wie andere darauf hingewiesen haben, haben Sie es eher in Teilprobleme unterteilt. Aus diesem Grund wird in einer Reihe von Antworten Ihr Lösungsansatz genannt, um dieses Problem zu vermeiden. Es ist nichts, was Sie persönlich nehmen sollten, sondern nur Erfahrung von denen von uns, die dort waren.
James Snell
2
@CodeYogi, ich denke, Sie haben diese Site möglicherweise mit Stack Overflow verwechselt. Diese Site entspricht einer Q & A-Sitzung an einem Whiteboard , nicht an einem Computerterminal. "Zeigen Sie mir den Code" ist ein ziemlich eindeutiger Hinweis darauf, dass Sie sich auf der falschen Seite befinden.
Wildcard
2
@Wildcard +1: "Zeigen Sie mir den Code" ist für mich ein ausgezeichneter Indikator dafür, warum diese Antwort richtig ist und dass ich möglicherweise an Möglichkeiten arbeiten muss, um besser zu demonstrieren, dass es sich um ein Problem mit dem Faktor Mensch / Design handelt, das nur möglich ist durch Veränderungen im menschlichen Prozess angesprochen werden - keine Menge Code könnte es lehren.
James Snell
10

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.

JacquesB
quelle
4
@CodeYogi: Ich würde ein kleines Array als Raster auf ein Blatt Papier zeichnen und dann manuell mit einem Bleistift durch eine Iteration der Schleife gehen. Dies hilft mir zu klären, was tatsächlich passiert, z. B. dass ein Zellbereich nach rechts verschoben wird und wo der neue Wert eingefügt wird.
JacquesB
3
"In der Informatik gibt es zwei schwierige Dinge: die Ungültigmachung des Cache, die Benennung von Dingen und einzelne Fehler."
Digital Trauma
1
@CodeYogi: Ein kleines Diagramm wurde hinzugefügt, um zu zeigen, wovon ich spreche.
JacquesB
1
Großartiger Einblick, besonders wenn Sie die letzten beiden Pars lesen sollten, liegt die Verwirrung auch an der Art der for-Schleife, selbst wenn ich den richtigen Index finde, dekrementiert sich die Schleife einmal vor der Beendigung und bringt mich damit einen Schritt zurück.
CodeYogi
1
Sehr. Ausgezeichnet. Antworten. Und ich möchte hinzufügen, dass diese inklusive / exklusive Indexkonvention auch durch den Wert von myArray.Lengthoder motiviert myList.Countist, der immer um eins höher ist als der auf Null basierende Index ganz rechts. ... Die Länge der Erklärung widerspricht der praktischen und einfachen Anwendung dieser expliziten Codierungsheuristiken. Die TL; DR-Menge fehlt.
Radarbob
5

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.

High Performance Mark
quelle
4
Ich wäre nicht so selbstsicher in Bezug auf die Fähigkeiten von OP. Vor allem in einem stressigen Umfeld wie einem Einstellungsgespräch ist es einfach, Grenzfehler zu machen. Ein erfahrener Entwickler könnte diese Fehler ebenfalls machen, aber natürlich würde ein erfahrener Entwickler solche Fehler durch Testen zunächst vermeiden.
Arseni Mourzenko
3
@MainMa - Ich denke, Mark hätte sensibler sein können, aber ich denke, er hat Recht - Es gibt Interviewstress und es gibt nur das Zusammenhacken von Code, ohne die Definition des Problems zu berücksichtigen. Die Art und Weise, wie die Frage formuliert ist, weist sehr stark auf Letzteres hin, und dies lässt sich langfristig am besten lösen, indem Sie sicherstellen, dass Sie eine solide Grundlage haben, und nicht indem Sie sich von der IDE abkoppeln
James Snell,
@JamesSnell Ich denke, Sie sind zuversichtlich über sich selbst hinweg. Schauen Sie sich den Code an und sagen Sie mir, warum Sie denken, dass er nicht dokumentiert ist. Wenn Sie klar sehen, wird nirgends erwähnt, dass ich das Problem nicht lösen konnte? Ich wollte nur wissen, wie ich vermeiden kann, denselben Fehler zu wiederholen. Ich denke, Sie bekommen Ihr gesamtes Programm auf einmal richtig.
CodeYogi
4
@CodeYogi Wenn Sie "Versuch und Irrtum" machen müssen und "frustriert" sind und "dieselben Fehler machen", dann sind dies Anzeichen dafür, dass Sie Ihr Problem nicht gut genug verstanden haben, bevor Sie mit dem Schreiben begonnen haben . Niemand sagt, Sie hätten es nicht verstanden, aber Ihr Code hätte besser durchdacht sein können, und es sind Anzeichen dafür, dass Sie Probleme haben, auf die Sie zurückgreifen und von denen Sie lernen können oder nicht.
James Snell
2
@CodeYogi ... und da Sie mich fragen, verstehe ich meine Schleifen und Verzweigungen nur selten falsch, weil ich genau weiß, was ich erreichen muss, bevor ich Code schreibe Array-Klasse. Als Programmierer ist es am schwierigsten, zuzugeben, dass Sie das Problem sind, aber solange Sie dies nicht tun, werden Sie keinen wirklich guten Code schreiben.
James Snell
3

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:

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.

Thomas Junk
quelle
Ah, lassen Sie mich Ihnen eine Sache sehr ernsthaft sagen. Ich habe alles getan, was Sie erwähnt haben, und ich kann Ihnen sogar meinen Link auf diesen Seiten geben. Aber das, was mich frustriert, ist, dass ich nicht die Antwort auf meine Frage bekomme, sondern alle möglichen Ratschläge zur Programmierung. Nur ein Typ hat die pre-postBedingungen bis jetzt erwähnt und ich schätze es.
CodeYogi
Nach dem, was Sie sagen, ist es schwierig, sich vorzustellen, wo Ihr Problem liegt. Vielleicht hilft eine Metapher: Für mich ist es so, als würde man sagen "wie kann ich sehen" - die naheliegende Antwort für mich ist "benutze deine Augen", weil das Sehen für mich so natürlich ist, dass ich mir nicht vorstellen kann, wie man nicht sehen kann. Gleiches gilt für Ihre Frage.
Thomas Junk
Stimmen Sie mit den Alarmglocken für "Versuch und Irrtum" völlig überein. Ich denke, der beste Weg, die Denkweise zur Problemlösung vollständig zu erlernen, besteht darin, Algorithmen und Code mit Papier und Bleistift auszuführen.
Wildcard
Ähm ... warum hast du einen grammatikalisch schlechten Stich in einen politischen Kandidaten, der ohne Kontext in der Mitte deiner Antwort über das Programmieren zitiert wird?
Wildcard
2

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,

Andrei
quelle
2

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;
}
flamingpenguin
quelle
2
Würde mich sehr über einen Kommentar freuen, wenn Du
flamingpenguin 19.04.16
2

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.

JDługosz
quelle
1

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.

AnoE
quelle
1

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.

Adrian McCarthy
quelle
0

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.

user2023861
quelle
1
Warum die Gegenstimme?
user2023861
0

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.

Emerson Cardoso
quelle
-1

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:]
Alexander
quelle
-3

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.

gnasher729
quelle
1
Können Sie bitte ein Beispiel nennen?
CodeYogi
Das OP hatte ein Beispiel.
gnasher729
2
Was meinst du? Ich bin der OP.
CodeYogi