P9 - TestRehashing

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

Beitrag von Werwolf »

Ja, war alles klar ;).

Ich werde mal die Sachen überprüfen.

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Beitrag von Gnomix »

Ich habe mal eine Frage zu Rehashing, muss ein gerade einzuguegendes Element/Objekt auch mit in den Belegungsfaktor eingerechnet werden ?
Ich bekomme immmer den Fehler, dass ich zu spät rehashen wuerde.

Code: Alles auswählen

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

Testcase: testRehashing took 0.027 sec
	FAILED
you have forgotten to expand your hashtable. it's more than 75% inside.
	at TestRehashing.testRehashing(TestRehashing.java:61)

Testcase: testRemoveAndRehashing took 0.011 sec
	FAILED
you have forgotten to expand your hashtable. it's more than 75% inside.
	at TestRehashing.testRemoveAndRehashing(TestRehashing.java:139)

Aber ich rehashe sobald der Belegungsfaktor beim Einfügen eines neuen Elements überschritten ist, also ohne das neue.
Sprich, wenn ich eine Größe von 100 hätte rehashe ich erst, wenn ich das 77. Element einfuege, da dann erst die Belegung ueberschritten ist, bevor ich das Element einfuege.

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

Beitrag von HolgerF »

Du musst schon vorher vergrößern, also beim Einfügen des 76., sonst ist deine Belegung ja oberhalb der erlaubten Grenze.

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

Beitrag von Werwolf »

Einen Fehler hatte ich, und zwar habe ich bei der Kollisionsfunktion k/m-1 mod m anstatt k/m mod m-1 gemacht :oops: .

Aber die Fehlermeldung, daß das kollidierte Elemente nicht seine Position nach dem Rehashen gewechselt hat, bekomme ich immer noch.

Vielleicht liegt es daran, das ich erst einen Rehash durchführe, wenn ich das Elemente schon eingefügt habe ?

Falls ein Element den Belegungsfaktur über die Schwelle hebt, füge ich es erst ein, und dann führe ich den Rehash durch, oder führe ich erst den Rehash durch, und füge das Element dann erst ein ?

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

Beitrag von Christoph B »

also um das mal klarzustellen:

mir rehashen is afaik die Kollisionsbehandlung gemeint und nicht das ihr die Tabelle wachsen lässt weil Belegung >= 75%
Wie Ringo auch schon angemerkt hat.

Btw ich habs mit Kettung aufgegeben (laut Herrn Wach ist das Testsystem darauf noch nicht ausgelegt...daher kann man nu schlecht sagen obs wirklich eigener Fehler ist oder das Testsystem das vermurkst)
Macht einfach als gelöscht markieren - 5 minuten umschreiben un auf anhieb passed is weniger stress un man hat mehr zeit fürs lernen ^^

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Beitrag von Gnomix »

Die Position berechnet sich ja mit hi(key), wobei erstmal i=0 ist, und nur wenn der Platz besetzt ist, das nächste hi(key) berechnet wird.
Falls du durch das einfuegen eine Belegung erreichen wuerdest, die 75% uebersteigen wuerde, muss
1. Werte sichern
2. Tabelle vergrößern
3. Alle Werte die du zwischenspeicherst, wie Belegungsfaktor etc. zuruecksetzen.
4. Elemente der alten Tabelle neu eingefuegt werden
5. das neue Element eingefuegt werden.

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

Beitrag von Werwolf »

Danke für Antworten :) .

Habs jetzt (hoffentlich) verstanden.

Drudge
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 13. Apr 2004 20:17

Beitrag von Drudge »

@Christoph B: also ich habe die HT mit Kettung implementiert und bestanden.
ich will damit nur darauf hinweisen, dass man auch mit diesem ansatz zum ziel kommt und ggf nicht unbedingt sein konzept überarbeiten muss.

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

Beitrag von Christoph B »

Ich hätts auch durchgezogen wenn net TGDI2 Sem.Klausur un GDI2 Probe Klausur vor der Tür stehn würden.
Und zu behaupten evtl is das Testsystem schuld is wohl einfach nur der einfachste Weg mit seiner Niederlage gegenüber deepthought klar zu kommen xD

edit: dann aber mal so aus neugierde:
Du verdrängst auch nen Element anständig das selbst durch Kollision auf ner "Uradresse" gelandet ist?
Also so wies auch sein sollte un nich wirr verzweigt bzw wenn h0 belegt ist, wird einfach weiter gesucht - egal welcher wert auf h0 liegt?

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

Beitrag von R|ng0 »

Drudge hat geschrieben:@Christoph B: also ich habe die HT mit Kettung implementiert und bestanden.
ich will damit nur darauf hinweisen, dass man auch mit diesem ansatz zum ziel kommt und ggf nicht unbedingt sein konzept überarbeiten muss.
Ich habe es auch mit Kettung implementiert und habe auch mein passed, allerdings...
Christoph B hat geschrieben:dann aber mal so aus neugierde:
Du verdrängst auch nen Element anständig das selbst durch Kollision auf ner "Uradresse" gelandet ist?
Also so wies auch sein sollte un nich wirr verzweigt bzw wenn h0 belegt ist, wird einfach weiter gesucht - egal welcher wert auf h0 liegt?
(ja, ich verdränge ordentlich)
... sind unter anderem das die Gründe weswegen ich von der Kettung abrate!!!
Ich habe sicherlich wesentlich mehr Zeit investieren müssen, die ich eigentlich nicht hatte, wenn ich an die Probe- und Semestralklausur denke.

Drudge
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 13. Apr 2004 20:17

Beitrag von Drudge »

Verdrängen??? Äh, nö... ich verdränge eigentlich nix.
Jetzt wo ich drüber nachdenke... ich glaube ich muss da mal ein paar Tests in eigener Sache machen. (auch wenn das prog passed ist komme ich gerade ein wenig ins grübeln :P )

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

Beitrag von RomanSoldier »

Für alle, die beim erweitern ihre Hahsmap erneut von oben (letztes Element der alten Map) nach unten (erstes Element der alten Map) aufgebaut haben und den Test nicht bestehen, macht es andersherum. Dann bekommt ihr auch für den testRehashing ein PASSED, vorausgesetzt, alles andere ist richtig.

Meiner Meinung nach, ist das nicht in Ordnung, das Hashing so zu überprüfen, dass ein richtiges aufbauen der Map als falsch angesehen wird, vor allem, da es keinerlei Information über diesen Fall gibt! Das hat mir mal wieder 2 Tage Kopfzerbrechen bereitet, unnötigerweise!

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

Beitrag von HolgerF »

Das ist halt irgendwie so ein bisschen das Problem an der Methode, dass hier versucht wird, auch die interne Implementierung via automatischen Tests zu überprüfen. Die Position der Elemente in der Hashmap ist ein klares Interna der Implementation, das man normalerweise nie nach außen geben würde. Vor allem hängen sie eben auch stark von Implementierungsdetails ab, und wenn der Testcase da nicht alles berücksichtigt, weist er eigentlich gültige Lösungen zurück.

Entweder muss man die konkrete Implementierung stärker vorgeben, oder man muss auf solche Interna-Tests verzichten - die Überprüfung, dass man tatsächlich eine Hashmap entsprechend der Vorgabe gebaut hat und nicht irgendwas, obläge dann eben doch dem Tutor. Vielleicht so als Anregung an den Veranstalter fürs nächste Mal ;)

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

Beitrag von RomanSoldier »

Zum Glück habe ich den Fehler im Test gefunden, ansonsten hätte ich ohne Ende testen können, ohne einen Fehler zu entdecken (war das selbe im Prak 8 mit dem AllTheSame, auch dort war ein Fehler im Testfall - zumindest zur Aufgabenstellung, bisher habe ich keine offizielle Stellungnahme dazu erhalten. Der Ersteller des Praktikums hüllt sich in schweigen - oder ist abwesend).

Natürlich muss ich dir Holger Recht geben, die Implementierung zu prüfen ist eigentlich Aufgabe des Tutors, nur ich halte nicht einmal die Hälfte der Tutoren für fähig das zu tun - auch, wenn das wieder böse Kritik gegen mich gibt, das bin ich mittlerweile gewöhnt. Wenn ich sehe, dass sich der eine Tutor viel Mühe damit gibt, ein Testat abzunehmen und auch nach Implementierungen fragt, ohne dabei unfair zu sein, ein anderer einfach nur schnell ein PASSED oder FAILED verteilen will, kann es dabei auch nicht gerecht zu gehen. Ich finde es in Ordnung, wenn ein Tutor, der weiß, dass ein Student seine Praktika (das weiß man nach 2-3 gelösten) ordentlich löst, der braucht nicht jedes Detail durchzugehen, für jemanden, der potentiell unsicher ist, ist das bestimmt besser, auch die letzten Zweifel, wieso etwas funktioniert zu erklären. So versteht verstehen: 10 % von dem, was man ließt, behält man, aber 70% von dem, was man sagt und 90% von dem, was man tut.

In diesem Sinne!

Benutzeravatar
giftnudel
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 3. Mai 2005 11:26

Beitrag von giftnudel »

Warum machst du nicht einfach nächstes Jahr Tutor und dann schauen wir mal, was deine Studenten dann über dich sagen.

Ich glaube außerdem, dass deutlich mehr als die Hälfte der Tutoren zu so etwas fähig sind. Es mag den einen oder anderen geben, der das manchmal nicht so ernst nimmt. Meine Testate haben für 2 Praktika immer mindestens 20 Minuten gedauert....

Antworten

Zurück zu „Archiv“