TDD-ähnlicher Ansatz für algorithmische Probleme

Ich habe bei einem algorithmischen Test mit Codility versagt, weil ich versucht habe, eine bessere Lösung zu finden, und am Ende hatte ich nichts.

Ich habe mir also überlegt, ob ich einen ähnlichen Ansatz wie TDD verwenden könnte. Dh wenn ich in der Regel schrittweise eine Lösung auf ähnliche Weise entwickeln kann?

Wenn ich einen Sortieralgorithmus schreiben würde, könnte ich von einem Standard-Bubblesort zu einem 2-Wege-Bubblesort wechseln, aber etwas Fortgeschritteneres wie Quicksort wäre ein "Quantensprung", aber zumindest hätte ich Testdaten, die ich leicht validieren kann.

Weitere Tipps für solche Tests? Eine Sache, die ich beim nächsten Mal tun würde, ist, mehr Methoden / Funktionen als innere Schleifen zu verwenden. Zum Beispiel benötigen Sie beim Sortieren häufig einen Tausch. Wenn es eine Methode wäre, müsste ich nur den aufrufenden Code ändern. Ich könnte sogar fortgeschrittenere Lösungen als abgeleitete Klassen haben.

Mit "Algorithmischen" und "normalen" Problemen meine ich Probleme, bei denen Zeitkomplexität wichtig ist. Anstatt mehr Tests wie in TDD zu bestehen, würden Sie dafür sorgen, dass es sich "besser verhält".

Mit "ähnlich wie TDD" meine ich:

1. Schreiben Sie einen relativ automatischen Test, um Zeit bei manuellen Tests zu sparen.
2. Inkrementelle Entwicklung.
3. Regressionstests, Fähigkeit zu erkennen, ob Code beschädigt ist oder zumindest, ob sich die Funktionalität zwischen Inkrementen ändert.

Ich denke, das sollte ziemlich leicht zu verstehen sein, wenn man es vergleicht

1. Eine Shell-Sortierung direkt schreiben
2. Springen von Bubblesort zu Quicksort (Total Rewrite)
3. Schrittweiser Übergang von einer Einweg-Blasensortierung zur Shell-Sortierung (falls möglich).

Siehe auch Ron Jeffries 'Versuch, einen Sudoku-Löser mit TDD zu erstellen , was leider nicht funktioniert hat.

Der Algorithmus erfordert ein umfassendes Verständnis der Prinzipien des Algorithmusdesigns. Mit diesen Prinzipien ist es tatsächlich möglich, schrittweise mit einem Plan fortzufahren, wie es Peter Norvig getan hat .

Bei Algorithmen, die nicht trivialen Entwurfsaufwand erfordern, ist der Aufwand fast immer inkrementeller Natur. Aber jedes "Inkrement", das in den Augen eines Algorithmus-Designers winzig ist , sieht für eine Person, die nicht über das gleiche Fachwissen oder Wissen mit dieser bestimmten Familie von Algorithmen verfügt , wie ein Quantensprung aus (um Ihre Phrase auszuleihen).

Aus diesem Grund ist eine Grundausbildung in CS-Theorie in Kombination mit viel Praxis der Algorithmusprogrammierung gleichermaßen wichtig. Zu wissen, dass eine bestimmte "Technik" (kleine Bausteine ​​von Algorithmen) existiert, ist ein langer Weg, um diese inkrementellen Quantensprünge zu erzielen.

Es gibt jedoch einige wichtige Unterschiede zwischen dem inkrementellen Fortschritt bei Algorithmen und TDD.

Einer des Unterschiedes wurde von erwähnten jeffo ein Test, der die Richtigkeit der Ausgabe bestätigt: Daten aus einem Test ist, der die behauptete Leistung zwischen unterschiedlicher Umsetzung des gleichen Algorithmus (der gleiche Lösung geben wetteifern oder verschiedenen Algorithmen).

In TDD fügt man eine neue Anforderung in Form eines Tests hinzu, und dieser Test darf zunächst nicht bestehen (rot). Dann ist die Anforderung erfüllt (grün). Schließlich wird der Code überarbeitet.

Bei der Algorithmusentwicklung ändert sich die Anforderung normalerweise nicht. Der Test zur Überprüfung der Korrektheit der Ergebnisse wird entweder zuerst oder kurz nach Abschluss einer Entwurfsimplementierung (sehr sicher, aber langsam) des Algorithmus geschrieben. Dieser Datenkorrektheitstest wird selten geändert. man ändert es nicht so, dass es als Teil des TDD-Ritus fehlschlägt (rot).

In diesem Aspekt unterscheidet sich die Datenanalyse jedoch deutlich von der Algorithmusentwicklung, da die Anforderungen an die Datenanalyse (sowohl die Eingabesätze als auch die erwarteten Ergebnisse) im menschlichen Verständnis nur lose definiert sind. Daher ändern sich die Anforderungen auf technischer Ebene häufig. Durch diese schnelle Änderung liegt die Datenanalyse irgendwo zwischen der Entwicklung von Algorithmen und der allgemeinen Entwicklung von Softwareanwendungen - obwohl sie immer noch algorithmisch sind, ändern sich die Anforderungen nach Geschmack eines jeden Programmierers "zu schnell".

Wenn sich die Anforderung ändert, wird normalerweise ein anderer Algorithmus benötigt.

Bei der Algorithmusentwicklung ist es dumm, den Leistungsvergleichstest so zu ändern (zu verschärfen), dass er fehlschlägt (rot). Sie erhalten keinen Einblick in mögliche Änderungen an Ihrem Algorithmus, die die Leistung verbessern würden.

Daher sind bei der Algorithmusentwicklung sowohl der Korrektheitstest als auch der Leistungstest keine TDD-Tests. Stattdessen handelt es sich bei beiden um Regressionstests . Insbesondere verhindert der Korrektheitstest, dass Sie Änderungen am Algorithmus vornehmen, die dessen Korrektheit beeinträchtigen. Der Leistungstest verhindert, dass Sie Änderungen am Algorithmus vornehmen, die ihn langsamer ausführen.

Sie können TDD weiterhin als persönlichen Arbeitsstil verwenden, mit der Ausnahme, dass das Ritual "Rot-Grün-Refaktor" für den Denkprozess der Algorithmusentwicklung weder unbedingt erforderlich noch besonders vorteilhaft ist .

Ich würde argumentieren, dass Algorithmusverbesserungen tatsächlich daraus resultieren, dass zufällige (nicht notwendigerweise korrekte) Permutationen zu den Datenflussdiagrammen des aktuellen Algorithmus vorgenommen oder zwischen zuvor bekannten Implementierungen gemischt und abgeglichen werden.

TDD wird verwendet, wenn mehrere Anforderungen vorhanden sind, die schrittweise zu Ihrem Testsatz hinzugefügt werden können .

Wenn Ihr Algorithmus datengesteuert ist, können alternativ alle Testdaten / Testfälle schrittweise hinzugefügt werden. TDD wäre auch nützlich. Aus diesem Grund funktioniert ein "TDD-ähnlicher" Ansatz von "Neue Testdaten hinzufügen - Code verbessern, damit diese Daten korrekt verarbeitet werden - Refactor" auch für offene Datenanalyse-Arbeiten, bei denen die Ziele von Algorithmen beim Menschen beschrieben werden -zentrische Wörter und ihr Erfolgsmaß werden ebenfalls in vom Menschen definierten Begriffen beurteilt.

Es soll einen Weg lehren, es weniger überwältigend zu machen, als zu versuchen, alle (Dutzende oder Hunderte) Anforderungen in einem einzigen Versuch zu erfüllen. Mit anderen Worten, TDD wird aktiviert, wenn Sie festlegen können, dass bestimmte Anforderungen oder Streckenziele vorübergehend ignoriert werden können, während Sie einige frühe Entwürfe Ihrer Lösung implementieren.

TDD ist kein Ersatz für Informatik. Es ist eine psychologische Krücke , die Programmierern hilft, den Schock zu überwinden, viele Anforderungen gleichzeitig erfüllen zu müssen.

Wenn Sie jedoch bereits eine Implementierung haben, die das richtige Ergebnis liefert, würde TDD das Ziel als erreicht und den Code als bereit zur Übergabe (an das Refactoring oder an einen anderen Programmierer-Benutzer) betrachten. In gewissem Sinne ermutigt es Sie, Ihren Code nicht vorzeitig zu optimieren, indem Sie objektiv signalisieren, dass der Code "gut genug" ist (um alle Korrektheitstests zu bestehen).

Bei TDD liegt der Schwerpunkt auch auf "Mikroanforderungen" (oder verborgenen Eigenschaften). Zum Beispiel Parameterüberprüfungen, Zusicherungen, Auslösen und Behandeln von Ausnahmen usw. TDD hilft dabei, die Richtigkeit von Ausführungspfaden sicherzustellen, die im normalen Verlauf der Softwareausführung nicht häufig ausgeführt werden.

Bestimmte Arten von Algorithmuscode enthalten auch diese Dinge; Diese sind für TDD zugänglich. Da der allgemeine Workflow des Algorithmus jedoch nicht TDD ist, werden solche Tests (zu Parameterüberprüfungen, Zusicherungen sowie zum Auslösen und Behandeln von Ausnahmen) in der Regel geschrieben, nachdem der Implementierungscode bereits (zumindest teilweise) geschrieben wurde.

Für Ihr Problem hätten Sie zwei Tests:

1. Ein Test, um sicherzustellen, dass der Algorithmus immer noch genau ist. zB Ist es richtig sortiert?
2. Leistungsvergleichstest - hat die Leistung verbessert. Dies kann schwierig werden. Daher ist es hilfreich, den Test auf demselben Computer und denselben Daten auszuführen und die Verwendung anderer Ressourcen einzuschränken. Eine dedizierte Maschine hilft.

Was zu testen ist oder welche Testabdeckung vollständig ist, ist umstritten, aber ich denke, dass die komplexen Teile Ihrer Anwendung, die verfeinert werden müssen (häufig geändert werden müssen), perfekte Kandidaten für automatisierte Tests sind. Diese Teile der Anwendung werden normalerweise sehr früh erkannt. Die Verwendung eines TDD-Ansatzes mit diesem Stück wäre sinnvoll.

Die Fähigkeit, komplexe Probleme zu lösen, sollte nicht durch die Zurückhaltung behindert werden, verschiedene Ansätze auszuprobieren. Ein automatisierter Test sollte in diesem Bereich hilfreich sein. Zumindest wirst du wissen, dass du es nicht noch schlimmer machst.

Anstatt mehr Tests wie in TDD zu bestehen, würden Sie dafür sorgen, dass es sich "besser verhält".

Art von.

Sie können die Laufzeit und Komplexität testen. Laufzeit-Tests müssen ein wenig nachsichtig sein, um Konflikte mit Systemressourcen zuzulassen. In vielen Sprachen können Sie jedoch auch Methoden überschreiben oder einfügen und tatsächliche Funktionsaufrufe zählen. Und wenn Sie Ihren aktuellen Algorithmus ist suboptimal sind zuversichtlich, können Sie einen Test vorstellen , dass lediglich verlangt , dass sort()invoke compare()weniger oft als die naive Umsetzung.

Sie können auch sort()zwei Sätze vergleichen und sicherstellen, dass sie bei compare()Anrufen nach Ihrer Zielkomplexität skaliert werden (oder ungefähr, wenn Sie eine gewisse Inkonsistenz erwarten).

Und wenn Sie können theoretisch beweisen , dass eine Reihe von Größe Nstreng nicht mehr als erfordern , soll N*log(N)Vergleiche, es könnte sinnvoll sein , Ihre beschränken bereits arbeit sort()zu N*log(N)Anrufungen von compare()...

Jedoch ...

Das Erfüllen einer Leistungs- oder Komplexitätsanforderung stellt nicht sicher, dass die zugrunde liegende Implementierung {AlgorithmX} ist . Und ich würde argumentieren, dass dies normalerweise in Ordnung ist. Es sollte keine Rolle spielen, welcher Algorithmus verwendet wird, vorausgesetzt, Sie treffen Ihre Implementierung und erfüllen Ihre Anforderungen, einschließlich aller wichtigen Komplexitäts-, Leistungs- oder Ressourcenanforderungen.

Wenn Sie jedoch sicherstellen möchten, dass ein bestimmter Algorithmus verwendet wird, müssen Sie langwieriger sein und viel tiefer gehen. Dinge wie..

• Stellen Sie sicher, dass genau die erwartete Anzahl von Anrufen bei compare()und swap()(oder was auch immer) getätigt wird
• Umschließen aller wichtigen Funktionen / Methoden und Sicherstellen, dass die Aufrufe mit einem vorhersehbaren Datensatz genau in der erwarteten Reihenfolge erfolgen
• Untersuchen des Arbeitszustands nach jedem der N Schritte, um sicherzustellen, dass er sich genau wie erwartet geändert hat

Wenn Sie jedoch sicherstellen möchten, dass insbesondere {AlgorithmX} verwendet wird, sind wahrscheinlich Funktionen von {AlgorithmX}, die Ihnen wichtig sind, wichtiger zu testen, als ob {AlgorithmX} am Ende tatsächlich verwendet wurde ...

Bedenken Sie auch, dass TDD die Notwendigkeit des Forschens, Denkens oder Planens in der Softwareentwicklung nicht negiert . Die Notwendigkeit von Brainstorming und Experimenten wird dadurch auch nicht zunichte gemacht, selbst wenn Sie in Ihrer automatisierten Testsuite nicht einfach behaupten können, dass Sie googeln und Whiteboarding betreiben .