Algorithmen[Prog 2]

[Joey]

Ich wollte mal fragen, ob schon wer angefangen hat die Aufgabe zu lösen, um mich mal ein bisschen an den Laufzeiten und erreichten epsilon orientieren zu können bzw inwieweit ich damit Wettbewerbsfähig bin

Also mit dem gleichen Prozessor, welcher auf dem Übungsblatt steht.

bei Fixed Epsilon: wenns gut läuft um die 500 ms +- 50
bei FixedSize: Rekord liegt bei 0.0188

Edit: nun nachdem ich die "Bedingungen" (konstanter zusätzlicher Speicherbedarf in den Buckets) noch eingehauen musste, ist nun alles langsamer wesentlich geworden....
bei Fixed Epsilon: wenns gut läuft um die 900 ms +- 50

[Tankwart]

bei Fixed Epsilon: 1048576 Elemente / 1,5s / alle Durchläufe erfolgreich
bei FixedSize: Rekord liegt bei 0.0194

[grovieman]

Hi,
hab bei Fixed Epsilon: 2^20: 1,9s
und bei Fixed Size hab ichs einmal bis 0,0188 geschafft, die Regel ist allerdings 0,0194.

[CansaSCity]

Ich glaube ich habe gerade einen rieeesen Hänger....

In der Aufgabe steht doch, dass die Tabelle bei n zu Hashenden Elementen n(1 + ²) Elementen groß sein darf...

richtig???

Also wenn man das ausmultipliziert, dann steht da doch etwas von .. sprich mehr Elemente wie eigentlich zu hashen sind...

Sollte man damit nicht allein schon ein konfliktfreies hashen hinbekommen??? Einfach jedem Element sein eigenes Feld, sind ja genug da...
Einziges Problem hierbei, sind ja dann nur die Blöcke... aber das würde doch heißen dass die Hashtabelle mit 2 Hashfunktionen und Blöcken eigentlich ziemlich doof ist....


Also irgendwas stimmt da wohl nicht, wahrscheinlich habe ich was übersehen oder falsch verstanden... bitte Helft mir

[Tankwart]

Sollte man damit nicht allein schon ein konfliktfreies hashen hinbekommen??? Einfach jedem Element sein eigenes Feld, sind ja genug da...
Einziges Problem hierbei, sind ja dann nur die Blöcke... aber das würde doch heißen dass die Hashtabelle mit 2 Hashfunktionen und Blöcken eigentlich ziemlich doof ist....

FixedEpsilon sollte auch konfliktfrei sein, bei FixedSize wird das Epsilon ja immer kleiner, bis kein Durchlauf mehr erfolgreich ist. Die Hashfunktionen bilden ja nicht surjektiv ab, auch wenn genügend freie Plätze wären sind evtl. alle in Frage kommenden Blöcke voll.

[Chrisss]

es ist die rede von elementen, nicht blöcken, das ganze teilt sich noch durch deine blockgröße(im vorgegebenen init-teil is das auch so eingebaut)

ne frage zur implementierung :versucht ihr elemente zu verdrängen wenn die 2 blöcke voll sind so wie als hinweis auf dem blatt steht?
Und wenn ja : wenn die blöcke, in die man ein element verdrängen kann, auch voll sind, verdrängt ihr dann sozusagen in einer ebene tiefer ?
hab momentan nur verdrängen mit tiefe 1 aber das klappt natürlich nicht weil irgendwann eifnach zu viele blöcke voll sind, muss da noch rumbasteln dran. Geht das aber schonma in die richtige Richtung?^^

[Tankwart]

Wenn beide voll sind stecken wir das Element trotzdem rein und versuchen das verdrängte einzufügen, wenn wieder kein Platz ist wieder eins verdrängen usw. bis a) ein Platz gefunden b) eine Schranke erreicht ist.

[CansaSCity]

Verändert ihr dann die Blockgröße???? Weil sonst würde find den Block ja nie wieder finden, aber dadurch wäre die invariante verletzt, dass ein Block m-groß ist.

Und es ist schließlich gefordert, dass es in einen von den Beiden Blöcken drin sein muss. Wenn diese aber nun mal voll sind, sehe ich keine Möglickeit bei m-großen Blöcken alle erforderlichen Elemente unter zu bringen. Verdrängen würde ja entweder ein Element in den falschen Block stoßen, oder müsste es zerstören. Wenn man die Blockgröße ändert dann sehe ich das gefährdet:

"find muss also nur zwei Blöcke durchsuchen und ist garantiert in konstanter
Zeit ausführbar, [...]"

Wenn das so wäre, dass wir die Blockgröße nach bedarf ändern, und alle Elemente auf die selben Felder gehasht werden, dann haben wir für Find eine Laufzeit von O(2*(n/2)^2)

[...]falls auch B konstant.

Heißt dass, wir dürfen das für den Spezialfall vernachlässigen???

Denkt ihr wir dürfen Listen verwenden?

Zusatzdaten, die linear mit der Gr¨oße der Hashtabelle wachsen,
sind nicht erlaubt (da sonst e ziemlich sinnlos)

Eigentlich gehören die Pointer ja zu unserer Hashtabelle, verursachen aber natürlich overhead. Aber ausser Arrays verursacht jede Datenstruktur overhead. Und dann bleibt uns algorithmisch gesehen nicht mehr viel Spielraum, was nicht besonders für eine Algorithmenaufgabe sprechen würde.


-==[Edit]==-
Also ich habe es mal mit dem Fall vernachlässigen und Arrays gemacht...

bei fixed epsilon, und mit nem 2,1 Ghz Starken Rechner habe ich es auf 1,93 Sekunden geschafft... muss gleich nochmal schauen ob ich was optimieren kann...

Dafür will mein 2. Test einfach nicht aufhören... ich habe mir mal die Testmethode angesehen, die läuft so lange durch bis successfull runs = 0 ist.

Ich lasse mir mal die Werte nebenbei ausgeben. Ich bin gerade bei 25000 Elementen mit einem Epsilon von ... und er läuft weiter???

Hört der überhaupt noch auf???
[/Edit]

[Chrisss]

Also angenommen du betrachtest ein Element, welches du Einfügen willst: Mögliche Blöcke wären zum Beispiel die Blöcke 42 und 24

Nun betrachtest du ein Element im block 42, und schaust dir an was die Hashfunktionen beim Auswerten dieses Elements ausspuckt:
Logischerweise wird z.b. h[1] dir 42 ausspucken, aber es kann durchaus sein, dass h[0] dir den Block 10 ausspuckt.
Schau dir die Hashfunktionen mal an, was da (ohne die modulu-operationen) für astronomische werte rauskommen!
Das verstreut die Elemente auf der Hashtabelle wirklich komplett, vor allem bei großen Integern wie im Framework verwendet werden.

Die Invariante besagt nur, dass jedes Element in den 2 Blöcken steckt, welche die hashfunktionen h0 und h1 ausspucken, es ist nirgends die Rede davon, dass für jedes Element in einem Block, der 2. theoretisch mögliche Block identisch ist.
Überleg mal, wenn die 2 möglichen Blöcke so zusammenhängen würden, dann wäre es unmöglich eine Hashtabelle zu konstruieren, sobald es mehr als 8 Elemente mit gleichem Hashwert h0 gibt, weil Hashwert h1 für diese auch gleich wäre --> Kollosion, Blöcke zu voll --> geht nicht

Ich hoffe ich hab das jetzt alles richtig verstanden und erklärt.

Zur Implementierung (hab gestern nicht mehr weitergemacht), ich machs momentan so dass ich das ganze als insert-Methode schreibe, denkt ihr dass das zulässig ist? Weil insert-Methode schreiben is ja noch extra eine der Bonuspunkt-Aufgaben.
Im Prinzip kann ich im construct ja j-i mal insert machen.. ne sinnvolle Vorverarbeitung fällt mir momentan nicht ein


EDIT: Wenn du die Blockgröße immer erweiterst um Elemente einzufügen, so ist das epsilon ja sinnlos, da dein platzverbrauch mit der zahl der kollisionen wächst. Und da sich deine Datenstruktur dadurch dynamisch vergrößert ist es sehr unwahrscheinlich, dass es bei fixedSize irgendwann mal einen run gibt, der nicht erfolgreich ist, auser vllt wenn der java-speicher vollläuft hust^^^^


EDIT2: Ich bin zu dumm das verdrängen zu implementieren... kann ich denn auf irgendeine intelligente Art das zu verdrängende Element aussuchen? Ich versuchs momentan so, dass ich mir anschaue, in welche Blöcke denn die bereits vorhandenen Elemente gesteckt werden können, und sobald ich eins finde, welches in einen Block, der nicht den 2 Blöcken für mein einzugügendes Element entspricht, passt, überschreibe ich dieses und rufe mein insert eben erneut auf für das verdrängte.
Das funktioniert aber schon bei n = 64 nicht mehr -.- Da dreht sich die Sache mit dem verdrängen nämlich irgendwie im Kreis bis die versuche aufgebraucht sind...

[CansaSCity]

"Ne du hast das Wenn du die Blockgröße immer erweiterst um Elemente einzufügen, so ist das epsilon ja sinnlos, da dein platzverbrauch mit der zahl der kollisionen wächst. Und da sich deine Datenstruktur dadurch dynamisch vergrößert ist es sehr unwahrscheinlich, dass es bei fixedSize irgendwann mal einen run gibt, der nicht erfolgreich ist, auser vllt wenn der java-speicher vollläuft hust^^^^"

Immer wenn ich einen Block erweitert habe, habe ich dafür einen anderen Block kleiner gemacht in dem noch Platz war. Die Blöcke sollen aber einheitlich groß bleiben.

Mein nächster an die Anforderungen angepasster Algorithmus wird nun schauen ob von dem Element was auch nicht in den 2.Block gepasst hat, es ein Element gibt, was mit der ersten Hashfunktion da reingehasht wurde. Wenn ja wird geprüft ob es für den Block der von seiner 2. Hashfunktion gefunden wird noch Platz gibt. Wenn nicht wird das nächste Element gesucht. Beim letzten denke ich werde ich dann das Ganze eine stufe tiefer forcieren.

So etwas musste ich schonmal implementieren. Und zwar kann man sich das vorstellen wie bei der Reise nach Jerusalem, nur dass sich die Leute nur auf manche Stühle setzen können. Wenn einer keinen Platz findet, schubst er einen Weg der sich dann erneut einen Platz sucht, usw...

Natürlich muss man hier auch aufpassen, wie oft man das macht, sonst gerät man in eine Endlosschleife und am besten nimmt man nicht immer den letzten sondern einen zufälligen der aufstehen muss....

Ich bin mal gespannt ob der Algorithmus läuft...