Modultests für Algorithmen

[1UnitedPower]

Meine Herren!

Ich stehe vor der Aufgabe Modul-Tests für die Klasse der Sortieralgorithmen zu entwickeln. Es reicht nicht aus zu testen, ob ein Algorithmus eine Eingabe korrekt sortiert, es muss sehr genau differenziert werden. Ein Modul-Test für Bubblesort darf beispielsweise keinen Quicksort passieren lassen. Ein Modul-Test für Heapsort soll nur Heapsort akzeptieren, keinen BinaryTree-Sort. Bei Quicksort ist die Reihenfolge der Vergleiche und Vertauschungen nicht eindeutig, sie ist zum Beispiel abhängig von der Wahl des Pivot-Elements. Unabhängig davon müssen alle gültigen Implementationen  von Quicksort den Test erfüllen. Jetzt bin ich auf der Suche nach geeigneten Charaktermerkmalen, die ich für die Tests benutzen kann. Vorschläge? Anhaltspunkte? Lektüre?

[1UnitedPower]

Meine Herren!

PS: Es ist nicht nur Ein- und Ausgabe der Algorithmen bekannt, sondern jeder Zwischenschritt (Vergleich, Tausch, Manipulation) ist über ein Sortierprotokoll nachvollziehbar.

Das Protokoll kann für Bubblesort etwa so aussehen:

Eingabe: cba
Vergleiche: c mit b
Tausche: c mit b
Zwischenschritt: bca
Vergleiche: c mit a
Tausche: c mit a
Zwischenschritt: bac
Vergleiche: b mit a
Tausche: b mit a
Zwischenschritt: abc
Ausgabe: abc

[Rouven]

Hello,

Es reicht nicht aus zu testen, ob ein Algorithmus eine Eingabe korrekt sortiert, es muss sehr genau differenziert werden. Ein Modul-Test für Bubblesort darf beispielsweise keinen Quicksort passieren lassen. Ein Modul-Test für Heapsort soll nur Heapsort akzeptieren, keinen BinaryTree-Sort. Bei Quicksort ist die Reihenfolge der Vergleiche und Vertauschungen nicht eindeutig, sie ist zum Beispiel abhängig von der Wahl des Pivot-Elements.

wow, das klingt nach einer Herausforderung. Damit scheiden ja traditionelle Unit-Test Verfahren schon fast aus, weil zu sehr Blackbox. Welche Anhaltspunkte stehen dir denn technisch zur Verfügung, darfst du die Implementierung manipulieren, per Code Injection, per direkter Source Manipulation, ...? Du wirst es ja schließlich nur dann schaffen, wenn du automatisiert das Verhalten des Algorithmus überwachen und damit bei Zwischenschritten bereits kontrollieren kannst. Das ganze klingt schon fast nach einer Erkennung des Algorithmusses und damit gar nicht mal leicht. Ist die Menge der Kandidaten bekannt, sprich weißt du auf welche/wieviele Sortierverfahren du prüfst?

MfG
Rouven

[1UnitedPower]

Meine Herren!

wow, das klingt nach einer Herausforderung. Damit scheiden ja traditionelle Unit-Test Verfahren schon fast aus, weil zu sehr Blackbox.

Die Modul-Tests dürfen auch gerne White-Box-Verfahren einschließen. Das ist keine Limitation.

Welche Anhaltspunkte stehen dir denn technisch zur Verfügung, darfst du die Implementierung manipulieren, per Code Injection, per direkter Source Manipulation, ...?

Die Algorithmen sind als Generatoren implementiert. Mir steht es frei so viele Zwischenrufe (yield / emit) einzufügen, wie ich möchte. Die Zwischenrufe dürfen dabei nicht manipulativ sein, sondern müssen die internen Daten unberührt lassen.

Du wirst es ja schließlich nur dann schaffen, wenn du automatisiert das Verhalten des Algorithmus überwachen und damit bei Zwischenschritten bereits kontrollieren kannst.

Ja die Zwischenschritte kann ich genauestens überwachen, das hatte ich in der urprünglichen Fragestellung vergessen. Es gibt ein Sortierprotokoll, das alle Zwischenschrite akribisch genau auflistet und das ich bei Bedarf erweitern kann.

Das ganze klingt schon fast nach einer Erkennung des Algorithmusses und damit gar nicht mal leicht. Ist die Menge der Kandidaten bekannt, sprich weißt du auf welche/wieviele Sortierverfahren du prüfst?

Ja die Kandidaten sind:

Bubblesort
Gnomesort
Selectionsort
Quicksort
Swapsort
Shakesort
Combsort
Stoogesort
Heapsort
Mergesort
Insertionsort
Slowsort