Praktikum 5 - FAQ

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Praktikum 5 - FAQ

Beitrag von Demmi »

Da hier im Forum immer wieder die selben Fragen auftauchen, habe ich mir gestern in mehreren Mails an den Veranstalter konkrete Antworten beschafft, die ich keinem Vorenthalten möchte. Gerade bei der relativ unpräzisen Aufgabenstellung des 5. Praktikums finde ich solche Hinweise mehr als notwendig.
Vieles davon wurde bereits im Forum so gesagt, ich wollte es hier der Übersichtlichkeit nur noch einmal zusammenfassen. Los gehts:
  • 1. Für alle drei Hashfunktionen sollen jeweils nur die ersten 5 Zeichen in Ascii-Zahlen umgewandelt werden.
  • 2. Bei allen drei Hashfunktionen muss am Ende nochmal Modulo der Tabellengröße gerechnet werden.
  • 3. Beim Folding müssen die Zahlenwerte abwechselnd rückwärts und vorwärts addiert werden:
    Beispiel: Ascii=1234567890
    Adresslänge=2 -> Folding:09+78+65+34+21 = 207
    Adresslänge=3 -> Folding:098+567+432+001 = 1098
    Sollte der Ascii-Wert wegen seiner Länge nicht "faltbar" sein, wird am linken Ende (vorne dran) mit Nullen aufgefüllt.
  • 4. Beim Folding müssen die errechneten Hashes am linken Ende (vorne) abgeschnitten werden wenn sie eine größere Länge als die Adresslänge haben
    Beispiel:
    Adresslänge=2 - Hash=123 --> 23
    Adresslänge=3 - Hash=5678 --> 678
    Für den eigentlich unmöglichen Fall, dass der Hash die Länge 4 hat und die Adresslänge 2 ist, müssen 2 Stellen abgeschnitten werden, usw.
    Beispiel: Adresslänge=2 - Hash=1234 --> 34
  • 5.Beim Quadratic_Probing können negative Hashes errechnet werden. Die Java-eigene Modulofunktion errechnet mit negativen Werten erneut negative Werte. Dies ist (wenn ich mich nicht irre) entgegen der Definition von Prof. Buchmann / dem Cormen.
    Beispiel: (-12)%5 = -2
    Dieses Problem umgeht man, indem man im Falle eines negativen Hashwertes die Tabellengröße addiert, nachdem man Modulo gerechnet hat.
  • 6.Das Quadratic_Probing braucht keine Abbruchbedingung. Man geht davon aus, dass in endlicher Zeit ein freier Tabellenplatz gefunden wird.
  • 7.Einträge die als gelöscht markiert sind zählen noch zum Inhalt der Tabelle (Stichwort: Loadfaktor). Sie werden erst beim Rehash entfernt.
  • 8.Die Information zu den beim Probing durchlaufenen Slots eines Entries ("Homeadresse" - für die DOT-Ausgabe relevant) wird beim Rehash zurückgesetzt.
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

tmx-master
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 253
Registriert: 25. Okt 2006 17:44

Re: Praktikum 5 - FAQ

Beitrag von tmx-master »

Moment:

7.Einträge die als gelöscht markiert sind zählen noch zum Inhalt der Tabelle (Stichwort: Loadfaktor). Sie werden erst beim Rehash entfernt.

Das bedeutet also, dass nach einer Markierung eines Elementes als gelöscht nicht die Anzahl der Elemente in der HT um 1 verringert wird?
Gruß TM

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: Praktikum 5 - FAQ

Beitrag von Osterlaus »

Das wurde in diesem Beitrag und folgenden besprochen.

tmx-master
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 253
Registriert: 25. Okt 2006 17:44

Re: Praktikum 5 - FAQ

Beitrag von tmx-master »

Hmm,

ok, danke noch mal für den Hinweis. Wir haben jetzt die Zeile mit anzahlElem-- in delete auskommentiert.
Gruß TM

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Praktikum 5 - FAQ

Beitrag von Maeher »

Man sollte dann aber auch beachten, dass man die Anzahl der Elemente beim Insert nur dann erhöht, wenn man auf einen vorher leeren Platz schreibt. ;)

tmx-master
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 253
Registriert: 25. Okt 2006 17:44

Re: Praktikum 5 - FAQ

Beitrag von tmx-master »

Hmm,
ok, das ist natürlich richtig. Danke.
Gruß TM

Benutzeravatar
^Lara^
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 17. Jan 2005 12:57

Re: Praktikum 5 - FAQ

Beitrag von ^Lara^ »

Demmi hat geschrieben:
  • 1. Für alle drei Hashfunktionen sollen jeweils nur die ersten 5 Zeichen in Ascii-Zahlen umgewandelt werden.
Für folding braucht man doch die alle Zeichen, nicht nur die ersten 5, oder?
Sorry, will nur nochmal nachfragen, nicht dass ich irgendwas falsch verstehe..

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: Praktikum 5 - FAQ

Beitrag von Krümelmonster »

Nein, auch bei folding werden nur die ersten fünf Zeichen benutzt.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

Re: Praktikum 5 - FAQ

Beitrag von Wambolo »

6.Das Quadratic_Probing braucht keine Abbruchbedingung. Man geht davon aus, dass in endlicher Zeit ein freier Tabellenplatz gefunden wird
dabei kann aber durchaus rehashing erforderlich sein oder irre ich da.



achja, nochwas soll getTable auch die als gelöscht markierten Elemente enthalten? Macht ja meiner Meinung nach nicht so viel Sinn, aber man weiß ja nie.
Interpreter/Parser reported on Nov 12, 2008 8:30:04 PM:
Number too big (102 > 42).

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Praktikum 5 - FAQ

Beitrag von Maeher »

Nein. rehashing erfolgt dann ausschließlich wenn die tabelle zu voll ist. Wir sollen ja davon ausgehen, dass immer ein freier Platz gefunden wird, falls noch einer vorhanden ist.

die gelöschten sollen da wohl nicht drin sein. ist zumindest nicht angegeben, wie sie markiert sein sollten.

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

Re: Praktikum 5 - FAQ

Beitrag von Wambolo »

Maeher hat geschrieben:Nein. rehashing erfolgt dann ausschließlich wenn die tabelle zu voll ist. Wir sollen ja davon ausgehen, dass immer ein freier Platz gefunden wird, falls noch einer vorhanden ist.
ok, dann lassen sich aber doch leicht Endlosschleifen provozieren

(quadratic_probing)
z.B Ausgangsgröße der Tabelle ist 10
Füge, sagen wir mal, 10 Elemente ein, die alle den Basishashwert 3 besitzen.
Spätestens beim einfügen des 7ten Elements gehts nicht mehr weiter, obwohl die Anzahl der Elemente im Verhältnis zur Größe noch ok ist.
Interpreter/Parser reported on Nov 12, 2008 8:30:04 PM:
Number too big (102 > 42).

Benutzeravatar
^Lara^
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 17. Jan 2005 12:57

Re: Praktikum 5 - FAQ

Beitrag von ^Lara^ »

Man könnte ja auch sagen ab einer bestimmten Größe von i soll rehashed werden, damit könnte man dann endlosschleifen vermeiden... und sucht trotzem noch "lang" genug.

Schade das der Praktikums-Veranstalter hier keine Stellung nimmt... das war letztens Jahr mal was was besser war :P

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Praktikum 5 - FAQ

Beitrag von Mspringer »

^Lara^ hat geschrieben:Man könnte ja auch sagen ab einer bestimmten Größe von i soll rehashed werden, damit könnte man dann endlosschleifen vermeiden... und sucht trotzem noch "lang" genug.

Schade das der Praktikums-Veranstalter hier keine Stellung nimmt... das war letztens Jahr mal was was besser war :P
Da kann ich nur Zustimmen. Das hat Herr Wach wirklich wesentlich besser gemacht ;)

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: Praktikum 5 - FAQ

Beitrag von Demmi »

Wambolo hat geschrieben: (quadratic_probing)
z.B Ausgangsgröße der Tabelle ist 10
Füge, sagen wir mal, 10 Elemente ein, die alle den Basishashwert 3 besitzen.
Spätestens beim einfügen des 7ten Elements gehts nicht mehr weiter, obwohl die Anzahl der Elemente im Verhältnis zur Größe noch ok ist.
Das stimmt nicht ganz. Nach spätestens 92682 Interationen findet das Quadratic Probing den 8. verschiedenen Hash und somit noch einen freien Platz in der gegebenen Hashtabelle. Das ist zwar alles andere als effizient, aber funktioniert ohne Endlossschleife.

Hier eine kleine Übersicht
gefundener Hash = bei der i-ten Iteration zum ersten Mal gefunden
9=4
8=9
7=3
6=92682
5=92681
4=1
3=0
2=2

Mehr als 7 verschiedene Hashes braucht man eigentlich auch nicht, da vorher der Rehash gemacht wird.
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Praktikum 5 - FAQ

Beitrag von Maeher »

Nein demmi, das stimmt leider nicht. Der wird zwar tatsächlich gefunden, das liegt aber an nem integer-overflow^^

Es lassen sich tatsächlich Endlosschleifen produzieren, ja. Aber die Aussage des Veranstalters ist, dass wir davon ausgehen sollen, dass dem eben nicht so ist.

Und macht euch nicht so viele Gedanken, wenn mein Praktikums-Tutor bei testieren nichts falsch gemacht hat, dann gibt es keinerlei extra Testcases. . .

Antworten

Zurück zu „Archiv“