p6 testRemove4

benrub
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 3. Dez 2006 01:26

p6 testRemove4

Beitrag von benrub »

Code: Alles auswählen

Testcase: testRemove4 took 0,007 sec
	Caused an ERROR
Key not in tree!
KeyNotInTreeException: Key not in tree!
	at AVLTree.getData(Unknown Source)
	at RemoveTest.testRemove4(RemoveTest.java:272)
bekomme ich, als einzige Fehlermeldung.
Na klar, denkt man sich, ich lösche einen Knoten den ich nicht löschen soll.
Meine Remove-Methode ist allerdings zemlich genau aus dem bestandenen P5 ersetzt, mit hinzugefügtem Balanceakt nach der Rekursion.

Hatte jemand denselben Fehler bzw. kann sich denken was das sein könnte? Finde auch keinen passenden Testcase...

Erebos
Mausschubser
Mausschubser
Beiträge: 47
Registriert: 27. Apr 2007 00:51

Beitrag von Erebos »

Ich hatte sowas ähnliches, vielleicht hast du irgendwo beim Rotieren eine Verknüpfung zu einem Sohn vergessen und diesen kann er dann nicht mehr erreichen.
Ich hatte zuletzt zum Testen das Beispiel aus dem Skript mit den Städten genommen und dann immer die Wurzel oder einen inneren Knoten nacheinander gelöscht bis der Baum leer war. Hab dadurch einige Fehler entdecken können

Pascha
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 6. Jun 2007 14:03

Beitrag von Pascha »

Code: Alles auswählen

Testcase: testRemove4 took 0.01 sec FAILED
Pre-Order stimmt nicht
junit.framework.AssertionFailedError: Pre-Order stimmt nicht
	at RemoveTest.testRemove4(RemoveTest.java:284)

Hallo, habe ebenfalls Probleme mit dem removeTest4. Bekomme nur an dieser einer Stelle die Meldung, dass PreOrder nicht stimmen würde, alle anderen Test laufen korrekt durch :/

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

Noch einmal für alle ....

Wenn nicht korrekt gelöscht wird, entsteht ein anderer Baum, der andere Traversierungsreihenfolgen hat. Da wir mit den Traversierungsmethoden entscheiden, ob der zugrundeliegende Baum korrekt ist, steht das im Test. Aber der Fehler liegt wo anders.

Diese Fehler lassen sich dadurch finden, dass man konsequent alle Möglichkeiten abtestet (so viele sinds nicht) und wirklich schaut ob da der richtige Baum rauskommt.

Wenn alle eigenen Tests funktionieren, fehlt ein Fall (sehr wahrscheinlich) oder die Tests sind die Bytes nicht wert, die sie belegen.

Ein Rumorakeln über "Xorder stimmt nicht" ist nicht zielführend.
Zuletzt geändert von wach am 6. Jun 2007 19:59, insgesamt 1-mal geändert.

Pascha
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 6. Jun 2007 14:03

Beitrag von Pascha »

mmh..

Nori
Erstie
Erstie
Beiträge: 22
Registriert: 15. Nov 2006 17:40
Kontaktdaten:

Beitrag von Nori »

Bei mir liefen bis vor 8 Minuten auch testRemove3 und 4 wegen falscher Preorder nicht durch. Bei mir lags daran, Dass z.B. bei diesem Baum

Code: Alles auswählen

   2                                  3
1   4     --2entfernen--> 1   4
    3 5                                   5
zwar der korrekte Baum entsteht, jedoch Höhe und Balance von Knoten3 nicht aktualisiert wurden. Der rekursive Aufbau, der die 3 gefunden hatte, war dafür zusatändig am Ende alle Knoten zu aktualisieren, aber der arbeitete natürlich noch mit der 2 Als Wurzel, weil die zu dem Zeitpunkt noch da stand. Kein rekursiver Aufruf kümmerte sich um die 3 an der neuen Stelle. Fieser Fehler, der in meinen Testfällen nicht auffiel und mich ca. 10 Stunden und einige Nerven gekostet hat.

sonothar
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 26. Okt 2005 00:15

Re: p6 testRemove4

Beitrag von sonothar »

benrub hat geschrieben:

Code: Alles auswählen

Testcase: testRemove4 took 0,007 sec
	Caused an ERROR
Key not in tree!
KeyNotInTreeException: Key not in tree!
	at AVLTree.getData(Unknown Source)
	at RemoveTest.testRemove4(RemoveTest.java:272)
ich geb die ma nen tipp: da steht "at AVLTree.getData(Unknown Source)"
das soll heißen deine getData hat die Exeption geworfen. also schau da mal nach!!!
Bild

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

<Edit: bitte keine PNs mehr an mich wegen dem Testcase... Herr Wach mag das nicht...>

Ich hab nen testcase erstellt, der zufällige bäume erzeugt und wieder löscht...

...mit ner eingebauten while (true) Schleife hatte ich dann am Ende auch tatsächlich noch einen sehr selten auftretenden Fehler gefunden der dann zum "failed" führte...

"Kleine Testbäume" zu nehmen ist auch nicht immer geeignet um alle Fehlerfälle durchzuspielen... einen Fehler hatte ich z.B. nicht finden können, als ich meinen Test 5 minuten lang Bäume mit 15 Knoten hab bauen lassen, aber fast auf anhib, als ich 50 Knoten benutzte.

Auf jeden Fall: wenn euer Baum einen 5-Minuten-Test mit 10000-Koten-Bäumen durchsteht ohne einen Fehler zu werfen, dann sollte er auch das Testat bestehen!

@Wach: Ist es eigentlich erlaubt Testcases direkt hier im Forum zu posten?
Zuletzt geändert von Antragon am 7. Jun 2007 13:11, insgesamt 1-mal geändert.

RomanSoldier
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 1. Dez 2005 20:32

Beitrag von RomanSoldier »

Bin zwar nicht Hr. Wach, aber
Tests
... Tauschen Sie Ihre Testcases auch nicht im Forum aus.
ich habe auch schon einen Rüffel dafür bekommen.

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

Antragon hat geschrieben: @Wach: Ist es eigentlich erlaubt Testcases direkt hier im Forum zu posten?
Nein. Auch das Anbieten über PN ist nicht ok.

Darüberhinaus ... wenn der Test wirklich prüft, ob korrekt gelöscht wurde MUSS da fast ne komplette Musterlösung drin sein.

Diese grossen Zufallsdaten können NUR helfen, evtl auftretende Exceptions im eigenen Code zu provozieren. Aussagen, ob da letzlich korrekt gearbeitet wurde, sind da nicht drin.

Pascha
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 6. Jun 2007 14:03

Beitrag von Pascha »

Also ich hab folgende Fälle geprüft, die laut meinen Tests auch korrektes Löschen hervorrufen:
- linkes Blatt löschen
- rechtes Blatt löschen
- linker Unterbaum vom gelöschten Knoten leer
- rechter Unterbaum vom gelöschten Knoten leer
- Lösche Wurzel/Knoten, größter Vorgänger hat linken Unterbaum bzw. kleinster Nachfolger hat rechten Unterbaum
- Beide Unterbäume nicht leer, linker Sohn ist größter Vorgänger bzw. rechter Sohn ist kleinster Nachfolger
- Alle Knoten löschen

Sonst fallen mir auch keine Fälle mehr ein, trotzdem ist laut removeTest4 ein Fehler in meiner Implementierung :/

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

:-(
...ok... dann halt keine Testcases hier im Forum/per PN...

@große Menge an Zufallszahlen:
...das ganze ist natürlich unter der Vorraussetzng zu sehen, dass der Programmschreiber sich an die Vorgaben gehalten hat, wie man zu löschen hat...
Diese Tests sind halt primär dazu gedacht zu überprüfen ob man Fehler bei verlinkungen gemacht hatte, da sich diese gerade bei großen Bäumen schnell zeigen.

Da das Praktikums-Testsystem ja nur sehr beschränkt Informationen zur Fehlerart zurückliefert, kann man mit solch einem Random-Test zumindest die meisten Fehlerquellen ausschließen, wenn es heist "falsche Preorder"...

Das der Test keine fehlerfreiheit garantiert ist sowieso klar... "Testing can show the presense of bugs, but not their absence."

X-Out
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 14. Mai 2007 19:06

Beitrag von X-Out »

@Pascha Läuft das jetz bei dir? Ich habe nämlich genau das gleiche Problem. Nur Removetest4 wo die PreOrder falsch ist - habe aber wirklich alles getestet (wie man eben so denkt das man alles getestet hat
:wink: )

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Beitrag von blowfish »

is nur n tipp, aber schau mal, ab wo du rekursiv anfängst deinen baum nach balance-fehlern durchzusuchen, wenn du einen knoten mit zwei nachfolgern löschst. denk daran, dass du ein blatt nach oben ziehst und das die balance deiner unteren knoten beeinflusst.
keine ahnung, ob dir das hilft, aber könnte ja sein....
Ein Hemd ist Einstellungssache!

Pascha
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 6. Jun 2007 14:03

Beitrag von Pascha »

@ X-Out.

ja es läuft bei mir. Habe doch ein Fall übersehen, dachte aber, dass ich ihn berücksichtigt hätte. Und zwar, den Fall, wenn der gelöschte Knoten beide Unterbäume besitzt und der größter Vorgänger / kleinster Nachfolger einer der Söhne vom gelöschten Knoten ist, wobei nach dem Löschen gleich an diesem Knoten eine Balance von +/- 2 entsteht. z.B.:
EDIT:

Code: Alles auswählen

              
                  4
        2                     7
  1                       6        8
                                           9

7 wird gelöscht

                  4
        2                     6
  1                                 8
                                           9

Zuletzt geändert von Pascha am 11. Jun 2007 10:46, insgesamt 1-mal geändert.

Antworten

Zurück zu „Archiv“