Wie identifizieren Sie Randfälle bei Algorithmen?

25

Wie können Sie herausfinden, welches Ihr schlechtester oder bester Fall sein könnte und welche anderen "Rand" -Fälle Sie haben könnten, bevor Sie sie haben, und wie bereiten Sie Ihren Code für sie vor?

Luis Armando
quelle
2
Alternative: Wenn möglich, bin ich ein großer Fan von Fuzzy-Tests. Es ist erstaunlich, wie die schiere Masse zufällig generierter Eingaben Fehler in einer Funktion aufspüren kann, die bei keiner Prüfung / Randprüfung aufgedeckt wurde. Die beiden arbeiten wirklich gut zusammen ... und sie werden offensichtlich durch die genaue Protokollierung von Fehlern ergänzt, wenn sie auf "wahren" Eingaben ausgeführt werden :)
Matthieu M.

Antworten:

28

Basierend auf dem Inhalt des Algorithmus können Sie identifizieren, welche Datenstrukturen / -typen / -konstrukte verwendet werden. Dann versuchen Sie, die (möglichen) Schwachstellen dieser zu verstehen und einen Ausführungsplan zu erstellen, der es in diesen Fällen zum Laufen bringt.

Der Algorithmus nimmt beispielsweise eine Zeichenfolge und eine Ganzzahl als Eingabe und sortiert die Zeichen der Zeichenfolge.

Hier haben wir:

Zeichenfolge mit einigen bekannten Sonderfällen:

  • Leerer String
  • Lange Schnur
  • Unicode-Zeichenfolge (Sonderzeichen)
  • Wenn es auf einen bestimmten Zeichensatz beschränkt ist, was passiert, wenn sich einige nicht im Bereich befinden?
  • Zeichenfolge mit ungerader / gerader Länge
  • Null (als Argument)
  • Nicht null beendet

Ganzzahl mit bekannten Sonderfällen:

  • 0
  • Min / MaxInt
  • Negativ positiv

Sortieralgorithmus , der in den folgenden Grenzfällen fehlschlagen kann:

  • Leere Eingabe
  • 1 Elementeingang
  • Sehr lange Eingabe (möglicherweise von maximaler Länge (für den Index verwendeter Datentyp))
  • Müll in der Sammlung, der sortiert wird
  • Null-Eingabe
  • Elemente duplizieren
  • Sammlung mit allen Elementen gleich
  • Eingabe ungerader / gerader Länge

Nehmen Sie dann all diese Fälle und erstellen Sie eine lange Liste, um zu verstehen, wie sie sich überschneiden. Ex:

  • Leerer String-Koffer deckt den leeren Sammelkoffer ab
  • Nullstring == Nullsammlung
  • etc.

Jetzt erstelle Testfälle für sie :)

Kurze Zusammenfassung : Teilen Sie den Algorithmus in Basisblöcke auf, für die Sie die Grenzfälle kennen, und setzen Sie sie dann wieder zusammen, um globale Grenzfälle zu erstellen

Victor Hurdugaci
quelle
5
Noch etwas hinzuzufügen. . . Analysieren Sie den Code und suchen Sie nach Sonderfällen im Code. Wenn der Entwickler 0 bis 13 anders als 14 und höher handhabt - möglicherweise verwendet der Entwickler aus Leistungsgründen unterschiedliche Algorithmen für kleine und große Werte -, haben Sie Randfälle bei 13 und 14. +1 für eine große Liste.
Ethel Evans
2

Ich glaube nicht, dass es irgendeinen Algorithmus gibt, um Kantenbedingungen zu bestimmen ... nur Erfahrung.

Beispiel: Für einen Byte-Parameter möchten Sie Zahlen wie 0, 127, 128, 255, 256, -1 testen, die Probleme verursachen können.

Steve Wellens
quelle
2

Eine "Kante" hat zwei Bedeutungen, und beide sind relevant, wenn es um Kantenfälle geht. Eine Kante ist entweder ein Bereich, in dem eine kleine Änderung der Eingabe zu einer großen Änderung der Ausgabe führt, oder das Ende eines Bereichs.

Um die Randfälle eines Algorithmus zu identifizieren, betrachte ich zunächst die Eingabedomäne. Seine Kantenwerte könnten zu Kantenfällen des Algorithmus führen.

Zweitens schaue ich auf die Ausgabedomäne und zurück auf die Eingabewerte, die sie erstellen könnten. Dies ist weniger häufig ein Problem bei Algorithmen, hilft jedoch bei der Suche nach Problemen bei Algorithmen, die zur Generierung von Ausgaben über eine bestimmte Ausgabedomäne entwickelt wurden. Beispielsweise sollte ein Zufallsgenerator in der Lage sein, alle beabsichtigten Ausgabewerte zu generieren.

Schließlich überprüfe ich den Algorithmus, um festzustellen, ob Eingabefälle ähnlich sind, die jedoch zu unterschiedlichen Ausgaben führen. Das Auffinden dieser Randfälle ist am schwierigsten, da sowohl Domänen als auch zwei Eingaben erforderlich sind.

MSalters
quelle
0

Das ist eine sehr allgemeine Frage, also kann ich nur ein paar allgemeine, vage Ideen rausschmeißen :)

-Prüfung Grenzfälle. Ex. Wenn Sie eine Zeichenfolge analysieren, was passiert, wenn die Zeichenfolge leer oder null ist? Wenn Sie von x nach y zählen, was passiert dann bei x und y?
-Code, der vereinfacht oder ausgetrocknet werden könnte. Jede nicht benötigte Komplexität kann zu Problemen führen.

seand
quelle
0

Ein Teil der Fähigkeit, Algorithmen zu verwenden, besteht darin, ihre Schwächen und pathologischen Fälle zu kennen. Victors Antwort gibt einige gute Tipps, aber im Allgemeinen würde ich raten, dass Sie sich mit dem Thema eingehender befassen müssen, um ein Gefühl dafür zu bekommen. Ich glaube nicht, dass Sie Faustregeln befolgen können, um diese Frage vollständig zu beantworten. ZB siehe Cormen oder Skiena (Skiena hat insbesondere einen sehr guten Abschnitt darüber, wo Algorithmen verwendet werden und was in bestimmten Fällen gut funktioniert, Cormen geht auf mehr Theorie ein, denke ich).

Steve
quelle