P9 - TestRehashing

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

P9 - TestRehashing

Beitrag von Christoph B »

Ahoi,

Testsuite: TestRehashing
Tests run: 2, Failures: 1, Errors: 0, Time elapsed: 0.054 sec

Testcase: testRehashing took 0.013 sec
FAILED
your rehashfunction does not work correctly. the position of an collidated element should have a new address.
junit.framework.AssertionFailedError: your rehashfunction does not work correctly. the position of an collidated element should have a new address.
at TestRehashing.testField(TestRehashing.java:176)
at TestRehashing.testRehashing(TestRehashing.java:76)

Testcase: testRemoveAndRehashing took 0.001 sec

Der Einzige test der bei mir noch fehlschlägt.
Könnts sein das Kettung / Verdrängung in dem Test nicht berücksichtigt wird?
Der einzige Fall in dem ich ein Element an die Adresse reinhaue, auf die es laut 1. Hash Funktion gehört, auch wenn der Platz bereits belegt ist nunmal wenn wenn das blockierende Element selbst durch Kollision dort gelandet ist.

Jemand vllt sogar ähnliche Probleme oder hat den Test bestanden (mit Kettung) ?

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

Beitrag von sonothar »

also ich hab nix mit Kettung gemacht. first come, first serve. wenn ein platzt schon belegt is, such ich halt mit der kollisionsfunktion den nächsten, bis ich einen freien gefunden hab
Bild

kechler
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 21. Nov 2004 22:33
Wohnort: Darmstadt

Beitrag von kechler »

Hallo,

ich habe leider genau dasselbe Problem! Die restlichen Tests laufen bei mir auch fehlerfrei durch...

Also beim Einfügen betrachte ich folgende Fälle:

1.) Der Platz in der Hashtabelle ist noch frei -> füge neues Element dort ein
2.) Wenn der Platz belegt ist:
a) wenn das Element an dieser Stelle als gelöscht markiert ist, füge das neue Element an diese Stelle ein
b) sonst suche mithilfe der Kollisionsfunktion den nächsten freien Platz

Macht ihrs genauso? Darf man vielleicht den Fall 2.a) nicht beachten und einfach das neue Element ans Ende der Kollisionskette einfügen??

Für Hilfe wäre ich ebenfalls sehr dankbar!

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Doch, 2a darf man tun, bin damit passed. Du musst aber halt aufpassen, dass du vorher weiter nach dem Element suchst, es könnte ja schon in der Map vorhanden sein.

7mSeni
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 185
Registriert: 4. Dez 2005 12:49

Beitrag von 7mSeni »

ich bekomme immer bei diesem Test ein timeout. Ich habe aber keine Ahnung wieso? Alle anderen Tests laufen.

Meine Vorgehenseise:

Jedesmal wenn ich ein element einfüge, dann berechne ich den belegungsfaktur, der sich aus #Elemente / Tabelengröße ergibt.
Wenn der wert > 0.75 ist, dann rufe ich eine Funkion rehash auf.

Die funktion rehash macht folgendes: Ich berechne die nächst größere primzahl mit dem sieb und speichere alle elemente der alten tabelle in einem vektor. dann erzeuge ich eine neue tabelle mit der neuen größe und füge alle elemente die ich zuvor gespeichert habe in die neue tabelle ein.

Dies funktioniert auch bei all meinen tests.

Mache ich da irgendwo ein denkfehler?

Oder wie geht ihr bei rehashing vor?

Wie gesagt bekomme ich immer ein timeout. Ich teste es bei mir lokal mit 400000 werten und ich brauche weniger als 10s.


Ich weiss nicht wo ich debuggen soll. Jemand ne idee?



Gruss

andreasfr
Neuling
Neuling
Beiträge: 6
Registriert: 2. Mai 2007 09:04

Beitrag von andreasfr »

das einfügen in den vector könnte relativ teuer sein, abder sollte eher nicht zu nem timeout führen. speicher doch einfach die referenz auf die alte tabelle irgendwie zwischen, leg ne neue an und schmeiß dann alles aus der alten in die neue. das erspaart dir ansich 1mal alles einfügen. vlt findest du dabei dann noch einen fehler, der zu nem timeout führen könnte..

7mSeni
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 185
Registriert: 4. Dez 2005 12:49

Beitrag von 7mSeni »

Hab den Fehler gefunden. Das Problem lag daran, dass ich die Kollisionsformel falsch geklammert hatte und dadurch bei der Einfüge operation in eine endlosschleife kam.

Jetzt gehts.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

also hat hier niemand kettung benutzt? ^^
miiist

kde
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Dez 2006 10:29
Kontaktdaten:

Beitrag von kde »

Hab Kettung benutzt und bin PASSED.
Hatte den Fehler am Anfang auch, weil ich vergessen hatte Elemente, die auf ihrer Hausposition stehen und einen Kettennachfolger haben durch eben diesen Kettennachfolger zu ersetzen. Allerdings kann dieser Fehler auch viele andere Ursachen haben.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

puh, thx, dann weiß ich das der Fehler bei mir liegt.
hm, dein Fehler klingt aber mehr nach nem Fehler der bei RemoveAndRehashing passieren könnte. (das mit dem ersetzen mach ich natürlich auch)
aber gut, nochmals thx ^^

Benutzeravatar
Maradatscha
Computerversteher
Computerversteher
Beiträge: 353
Registriert: 2. Okt 2006 18:53

Beitrag von Maradatscha »

ich hab keine kettung benutzt und hab nen timeout bei dem ersten rehashing test und dem ersten trickytest
meine kollisionsfunktion sieht ganz richtig aus glaub ich, ich teste auch mal so mit 300 000 elementen und das funktioniert auch ganz gut

Werwolf
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 10. Sep 2004 10:25

Beitrag von Werwolf »

Ich hab auch ein Problem mit dem "Re-Hashing".

Wenn ich rehashe, dann nehme ich die Elemente der Reihe nach aus der Hashtable und füge sie dann wieder neu ein.
Dabei kann es passieren, daß ein Element, das in der Original Tabelle durch eine Kollision auf eine Stelle gekommen ist, auch beim Re-Hashing wieder auf die selbe Stelle kommt.
Das wird vom TestSystem als Fehler angesehen.

Muß ich jetzt noch die Reihenfolge der Eingabe der Elemente beim Rehashing berücksichtigen ?

Ach so, ich benutzte beim Löschen die Version, daß ich das gelöschte Element nur als gelöscht makiere, und dann gegebenenfalls mit einem neuen Element überschreibe.

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

Beitrag von Edoat »

Das wird vom TestSystem als Fehler angesehen.
Welche Fehlermeldung kriegst du denn genau?

Ich rate jetzt mal paar Dinge, die man evtl. nicht beachtet haben könnte:
1. Neu gehashed wird nur wenn der Belegungsfaktor >75% ist, die Tabelle wird nie kleiner
2. Gelöscht markierte Elemente zählen für den Belegungsfaktor als tatsächlich gelöscht
3. Rehashen läuft grob gesehen folgendermaßen:
a) Hole alle nicht als gelöscht markierten Elemente aus der Hashtabelle und speichere sie zwischen
b) Erweitere deine Hashtabelle auf die neue Größe und setze alle Variablen, die du intern verwendest auf den Zustand, den sie in einer leeren Hashtabelle haben
c) Hashe alle zwischengespeicherten Elemente neu

Werwolf
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 10. Sep 2004 10:25

Beitrag von Werwolf »

z.B. Bekomme ich folgende Fehlermeldung :

your rehashfunction does not work correctly. the position of an collidated element should have a new address.
junit.framework.AssertionFailedError: your rehashfunction does not work correctly. the position of an collidated element should have a new address.


Weswegen ich annehme, daß nach dem Rehashing Werte die durch eine Kollision eine andere bekommen Stelle hatten nun diese Stelle nicht mehr haben dürfen.

@Edoat :
Ich habe alles Betrachtet, was du geschrieben hast, deswegen steh ich ja auch auf dem Schlauch.
Und es ist ja nur das Rehashing, was bei mir die Fehler hat. Alles andere funktioniert tadellos.

Ich habe sogar angefangen zu rehashen, wenn ein Element gelöscht wurde, das eine Kollision hervorgerufen hat.

Und das zwischen Speichern mach ich so :

T temphash = hashtabelle;
hashtabelle = new T[size];

Und danach gehe ich einfach 'temphash' durch, und füge jedes Element das nicht als gelöscht makiert ist, in 'hashtabelle' ein.

Bei meinem Test waren die Zahlen 42 auf 19, 7 auf 7 und 65 auf 14. Wobei 65 wegen einer Kollision mit 42 auf diesen Platz gekommen ist.

Nachdem ich 42 gelöscht habe und einen Rehasch gemacht habe, ist die 7 dann durch eine Kollision auf Platz 19 gekommen und als ich dann die 65 einfügen wollte gab es eine Kollision mit der 7 und sie kam wieder auf ihren Platz, den sie auch vor dem Rehashing hatte (14).

Deswegen verwundert es mich, daß das Testsystem, explizit sagt, daß Werte nach dem Rehashen eine andere Stelle haben müssen, falls sie ihre erste Position durch eine Kollision erhalten haben.

Benutzeravatar
R|ng0
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 24. Dez 2006 19:17

Beitrag von R|ng0 »

Werwolf hat geschrieben:z.B. Bekomme ich folgende Fehlermeldung :

your rehashfunction does not work correctly. the position of an collidated element should have a new address.
junit.framework.AssertionFailedError: your rehashfunction does not work correctly. the position of an collidated element should have a new address.
Hast du schon einmal daran gedacht, dass es nicht am rehashen der Tabelle liegt, sondern am rehashen der Element nach einer Kollision!?

Mal abgesehen davon, dass mir das Wort "collidated" nicht bekannt ist ;) , versuche ich den Satz mal frei zu übersetzen:
"Die Position eines kollidierten Elementes sollte eine neue Adresse haben."

Also meiner Meinung nach heißt das, dass deine Kollisionsbehandlung falsch ist oder genauer gesagt du gibst die Hausadresse zurück, aber auf diesem Feld dürfte schon ein Synonym (Eine Element mit dem gleichen Hashwert) stehen!?

Benutzt du die hi Funktion eigentlich? Du darfst keinen Bucket verwenden, der dir mehrere Elemente auf einer Position speichert!

Verwendest du Buckets, haben Synonyme die gleiche Position in der Tabelle und gerade die Kollisionsfunktion soll dir eine neue Adresse geben!?

oder ich kann mir noch vorstellen, dass deine getElementPosition nicht die eigentliche Adress zurück gibt, sondern du berechnest sie per h0, welches natürlich immer die gleiche gibt!?

Das wären meine Vorschläge. Hoffe es ist klar was ich meine und ich konnte helfen...

Antworten

Zurück zu „Archiv“