P4 Step4 Random Test

jaspar
Erstie
Erstie
Beiträge: 15
Registriert: 17. Jun 2009 11:36

P4 Step4 Random Test

Beitrag von jaspar »

Ich hänge einfach beim RandomTest.
Es werden 4000 erwartet und nur noch 37Knoten sind enthalten??
ich hab keine Ahnung mehr woran das nohc liegen könnte?
hat jemand ne idee?

hilfeschrei!

niewhner
Nichts ist wie es scheint
Beiträge: 23
Registriert: 17. Jun 2009 13:42

Re: P4 Step4 Random Test

Beitrag von niewhner »

jaspar hat geschrieben:Ich hänge einfach beim RandomTest.
Es werden 4000 erwartet und nur noch 37Knoten sind enthalten??
ich hab keine Ahnung mehr woran das nohc liegen könnte?
hat jemand ne idee?

hilfeschrei!
Genau das selbe Problem habe ich auch. Sogar der Balance Test von O_knut läuft durch.

Ich vermute dass der Fehler bei
if (node.left == null && node.right != null) bzw node.left != null && node.right == null liegt, sobald nur einer der Teilbäume leer ist. Im Grunde müsste man bei diesem Fall doch nur den nicht leeren Teilbaum als neuen Knoten setzen

VMann
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 16. Apr 2009 11:51

Re: P4 Step4 Random Test

Beitrag von VMann »

reduzieren auf 37 konnte ich auch ne Weile ^^

das passiert, wenn man beim Löschen durch den Knoten ersetzt, und zwar den Knoten so wie er gespeichert ist, mit Verweisen auf seine Nachfolger.
Ihr dürft nur die Inhalte des Knotens hochziehen, nicht einfach den ganzen Knoten, sonst nehmt ihr den kompletten Teilbaum mit (und verwerft dabei ne Menge Knoten).
Computer tun nicht das, was du von ihnen willst, sie tun das, was du ihnen sagst.

Benutzeravatar
Diablo
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 210
Registriert: 6. Sep 2008 17:43
Wohnort: Kreis Offenbach

Re: P4 Step4 Random Test

Beitrag von Diablo »

*G* toll bei mir löscht er zuwenig... hab noch immer 4974 Elemente ... alle Test laufen ausser halt Random ...
Ich gehe doch von gleichheit aus wenn:
node.interval.start == x.start && (node.agent.compareTo(agent) == 0)

ODER ???


.... nun bin ich auf 4001 runter...( nur bei Interval.start auf gleichheit geprüft und im rechten unterbaum den kleinsten hoch gezogen und natürlich dort gelöscht...) man ist das gemein *G*

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: P4 Step4 Random Test

Beitrag von Blub »

Diablo hat geschrieben: node.interval.start == x.start && (node.agent.compareTo(agent) == 0)
wieso vergleichst du nicht einfach den String per node.agent.equals(agent)? Wenns == 0 ist müsste es eigentlich auch gleich sein, aber imho etwas umständlich irgendwie ^^ erstmal die alphanumerische Größe zu bestimmen und davon dann auf gleichheit zu schliessen ^^
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

jaspar
Erstie
Erstie
Beiträge: 15
Registriert: 17. Jun 2009 11:36

Re: P4 Step4 Random Test

Beitrag von jaspar »

Die Lösung die du beschrieben hast VMann verstehe ich nicht so ganz... ich versuche mal den Ablauf meines Algos dazustellen.

Ich schau in remove() erstmal ähnlich wie in add() nach dem Interval.start Wert und sortiere danach..und steige entweder rechts oder links in den Baum ab. z.B. node.left = remove()
Stellt die Rekursion irgendwann identische Start Werte fest steige ich über den Vergleich mit agent.compareTo(node.agent) weiter ab in den Baum... bis start und agenten Gleicheit herrscht.
Dann springe ich in den Fall das das beide Unterbäume (node.left und && node.right) != null sind... das Löse ich ueber REkursion mit removeSmallest()...Diese Fälle klappen auch und werden in den ersten Test ja auch ueberprüft.

Falls dies nicht stimmt... wird auf node.left != null && node.right =null und analog das zu das Umgekehrte überprüft... und dort müsste der FEhler liegen das ich da falsch zusammenbaue.

Wäre froh wenn jemand mal sgen könnte wie das da vom genauen ablauf her geht.

danke.


[EDIT] Habe herausgefunden wenn ich die If abfrage mit node.left != null & node.right !=null herausnehme (in welcher removeSmallest augerufen wird) dann laufen alle Tests bis auf removeRoot und rano aber bei Random habe ich dann deutlich zu wenig gelöscht. 3696 sind dann noch enthalten...aber ich springe öfter in die ifabfragen die node.left != null node.right == null bzw umgekehrt abfangen....

zum verrückt werden.

VMann
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 16. Apr 2009 11:51

Re: P4 Step4 Random Test

Beitrag von VMann »

Deine Abfragen sind ein wenig umständlicher als nötig. Wenn du einen Knoten löschen willst und node.left oder node.right ist null, dann kannst du einfach den anderen nehmen um deinen gelöschten Knoten zu ersetzen. Wenn der auch null ist macht das nichts, muss also nicht extra abgefragt werden.
Dann noch updateHeight und UpdateBiggest nutzen und dein Teilbaum ist aktualisiert.
Dass einer (oder beide) der Nachfolger des zu löschenden Knotens null ist ist also der einfachere Fall.
jaspar hat geschrieben:[EDIT] Habe herausgefunden wenn ich die If abfrage mit node.left != null & node.right !=null herausnehme (in welcher removeSmallest augerufen wird) dann laufen alle Tests bis auf removeRoot und rano aber bei Random habe ich dann deutlich zu wenig gelöscht. 3696 sind dann noch enthalten...aber ich springe öfter in die ifabfragen die node.left != null node.right == null bzw umgekehrt abfangen....
Moment, wenn du noch 3696 übrig hast, dann hast du immernoch zuviel gelöscht, es müssten ja 4000 übrig bleiben.
Computer tun nicht das, was du von ihnen willst, sie tun das, was du ihnen sagst.

f_spitz
Erstie
Erstie
Beiträge: 15
Registriert: 31. Mai 2009 19:13

Re: P4 Step4 Random Test

Beitrag von f_spitz »

ich hab wohl ein ähnliches Problem: :(

ich bekomme die if(node.left != null) abfrage nicht richtig hin...
bisher rufe ich folgendes auf:
result=removeSmallest(node.left);
result.removed.right=node.right;
node=result.removed;

result habe ich mir vorher angelegt, um die ergebnisse des removeSmallest abzulegen.

es laufen alle tests bis auf den random durch... dort sind noch 1358 übrig. (statt 4000)

kann mir einer von euch weiterhelfen? was stimmt daran nicht?

Danke,
GRuß Flo

tanne
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 30. Sep 2008 16:05

Re: P4 Step4 Random Test

Beitrag von tanne »

f_spitz hat geschrieben:ich hab wohl ein ähnliches Problem: :(

ich bekomme die if(node.left != null) abfrage nicht richtig hin...
bisher rufe ich folgendes auf:
result=removeSmallest(node.left);
result.removed.right=node.right;
node=result.removed;

result habe ich mir vorher angelegt, um die ergebnisse des removeSmallest abzulegen.

es laufen alle tests bis auf den random durch... dort sind noch 1358 übrig. (statt 4000)

kann mir einer von euch weiterhelfen? was stimmt daran nicht?

Danke,
GRuß Flo
ok 1. du musst removeSmallest auf den rechten teilbaum aufrufen 2. musst du den .removed zum node machen un den result.node zum neuen rechten teilbaum un 3. verlierst du den linken teilbaum

eesti
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 116
Registriert: 6. Okt 2008 20:59
Wohnort: Darmstadt

Re: P4 Step4 Random Test

Beitrag von eesti »

ich hab acuh viel zu wenig, also 37 knoten.
Ich versteh nicht ganz was dieser hinweis beduetet, also wie ich nur die inhalte des knoten hochziehen kann. Und was passiert dabei mit den drunetrliegenden, denn die muss ich doch dann irgendwannnachziehen und darf die net vergessen????

VMann hat geschrieben: das passiert, wenn man beim Löschen durch den Knoten ersetzt, und zwar den Knoten so wie er gespeichert ist, mit Verweisen auf seine Nachfolger.
Ihr dürft nur die Inhalte des Knotens hochziehen, nicht einfach den ganzen Knoten, sonst nehmt ihr den kompletten Teilbaum mit (und verwerft dabei ne Menge Knoten).

k_b
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 213
Registriert: 15. Mär 2009 12:06

Re: P4 Step4 Random Test

Beitrag von k_b »

Mir gehts ganz genauso wie eesti, hat jemand nochmal einen Tipp??? Wenn die Befürchtung besteht, dass dann zu viel verraten ist kann mir ja auch ne private Nachricht schicken :P
eesti hat geschrieben:ich hab acuh viel zu wenig, also 37 knoten.
Ich versteh nicht ganz was dieser hinweis beduetet, also wie ich nur die inhalte des knoten hochziehen kann. Und was passiert dabei mit den drunetrliegenden, denn die muss ich doch dann irgendwannnachziehen und darf die net vergessen????


VMann hat geschrieben:
das passiert, wenn man beim Löschen durch den Knoten ersetzt, und zwar den Knoten so wie er gespeichert ist, mit Verweisen auf seine Nachfolger.
Ihr dürft nur die Inhalte des Knotens hochziehen, nicht einfach den ganzen Knoten, sonst nehmt ihr den kompletten Teilbaum mit (und verwerft dabei ne Menge Knoten).
GANZ GROßES DANKE SCHONMAL!!!!!!

tanne
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 30. Sep 2008 16:05

Re: P4 Step4 Random Test

Beitrag von tanne »

mal ganz allgemein , hoffe ist nicht zu viel verraten....
wenn der knoten den du löschen willst 2 kinder hat, "löscht" man ihn indem man ihn mit dem kleinsten konten aus dem rechten teilbaum (alternativ geht auch der größte aus dem linken) überschreibt. jetzt mus sman nur aufpassen dass man den baum auch wieder vervollständigt, also diesem "neuen" knoten die passenden söhne links un rechts anhängt

Benutzeravatar
Diablo
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 210
Registriert: 6. Sep 2008 17:43
Wohnort: Kreis Offenbach

Re: P4 Step4 Random Test

Beitrag von Diablo »

7
/ \
4 12
/ \ / \
2 6 8 15
\
10

Wenn nun die 7 gelöscht werden soll

Rechter unterbaum:

12
/ \
8 15
\
10

ist die 8 der kleinste nachfolger im linken baum

der neue Baum sieht dann so aus:


8
/ \
4 12
/ \ / \
2 6 10 15

f_spitz
Erstie
Erstie
Beiträge: 15
Registriert: 31. Mai 2009 19:13

Re: P4 Step4 Random Test

Beitrag von f_spitz »

viel Dank schon mal für die Erklärung....hat sehr geholfen
ich kann mir jedoch nicht erklären warum mein RandomTest einen StackOverflow liefert...(alle anderen laufen durch)

wenn mein node.left ungleich null ist sowie node.right !=null, dann mach ich folgendes:

-ich erstell mir eine tmp-tree mit node.left.
-dann führe ich removeSamallest auf den rechten Unterbaum aus und setzte node neu(das kleinste ausm rechten Unterbaum).
-mein neuer node.right ist dann das, was bei removeSmallest (out.node) rauskommt.
-und dann setzt ich noch mein node.left auf den tmp-tree von schritt 1...

also aufm papier muss das eigentlich stimmen...
der randomTest alledings liefert einen StackOverFlow at Step4Test.size...??!?!?!

so langsam reichts mir... ich sitze seit gefühlten 3 wochen an der Aufgabe... :twisted:

danke,
Gruß Flo

Benutzeravatar
anon
Neuling
Neuling
Beiträge: 10
Registriert: 16. Mai 2009 10:21

Re: P4 Step4 Random Test

Beitrag von anon »

f_spitz hat geschrieben:viel Dank schon mal für die Erklärung....hat sehr geholfen
ich kann mir jedoch nicht erklären warum mein RandomTest einen StackOverflow liefert...(alle anderen laufen durch)

wenn mein node.left ungleich null ist sowie node.right !=null, dann mach ich folgendes:

-ich erstell mir eine tmp-tree mit node.left.
-dann führe ich removeSamallest auf den rechten Unterbaum aus und setzte node neu(das kleinste ausm rechten Unterbaum).
-mein neuer node.right ist dann das, was bei removeSmallest (out.node) rauskommt.
-und dann setzt ich noch mein node.left auf den tmp-tree von schritt 1...

also aufm papier muss das eigentlich stimmen...
der randomTest alledings liefert einen StackOverFlow at Step4Test.size...??!?!?!

so langsam reichts mir... ich sitze seit gefühlten 3 wochen an der Aufgabe... :twisted:

danke,
Gruß Flo
also flo ne das stimmt so glaube ich nicht, guckst du:

.....L
.../....\.
..x......y
./....../
w......K
........\
.........z

L = zu löschendes Element
K = kleinstes Element aus rechtem Unterbaum

wenn du einfach removed.node als neuen rechten baum von node setzt, dann geht ja y verloren.
nach deinen vorgängen würde das ja danach so aussehen

.....K
.../....\.
..x......z
./.......
w.......
.........
(oder setzt du den rechten baum schon in removeSmallest irgendwie zusammen, so dass der schon komplett fertig bei out.node rauskommt? weil normal ist doch out.node einfach der rechte teil von removed, da links ja leer ist)

also ich hatte es jetzt mal so überlegt:

1. ich ersetze die inhalte von L einfach durch die inhalte von K (also agent und intervall)
2. ich ersetze out.removed (K) durch out.node (z)

dann müsste der baum so aussehen (und so sollte es ja richtig sein denke ich):

.....K
.../....\.
..x......y
./....../
w......z
.........
..........

hört sich gut an, funktioniert aber auch irgendwie nicht. entweder ich hab zu viele elemente gelöscht (60 übrig) oder wenn ich es so mache wie hier, dann noch 4964 übrig.
zeitweise hatte ich sogar 42 elemente übrig und dachte schon, ich hätte die frage nach dem leben, dem universum und allem programmiert.

kann jemand bestätigen dass man den baum so zusammensetzt?
wenn ja, dann liegt der fehler woanders in der rekursion oder so und ich kann woanders suchen :/

so langsam hab ich auch keine lust mehr :)

gruss,
a.

Antworten

Zurück zu „Archiv“