Algorithmen[Prog 2]

[Chrisss]

Meiner läuft jez bis n = 128 >.<
ich weis nich ich bin echt zu doof für die programmier-aufgaben obwohl das doch sicher ganz simpel is !!
Ich verdränge momentan so, dass ich im 2. Block für mein Element suche, ob ich eins finde, welches in einen völlig anderen Block kommt, wenn ja ersetze ich es mit meinem Element und rufe erneut mein insert auf.. funktioniert dann aber auch irgendwann nicht mehr ..
ich kriegs irgendwie nich hin das gibts nich und ich hab auch absolut keine idee worans liegt oder wie ichs besser machn kann

[CansaSCity]

Ok funktioniert gar nicht gut...

Es blockiert ziemlich schnell, also schon bei 16 Elementen... also das verdrängen/tauschen muss man wohl geschickter machen

[ryo]

Bei mir genauso. Bei 16 hauts mich raus

[Chrisss]

jemand noch ne idee wie man das verdrängen richtig implementiert? Teste atm die Elemente der Blöcke darauf, ob eine der HashFunktionen sie NICHT auf block1 und auch NICHT auf block2 schiebt, und wenn ich ein solches finde ersetze ich es mit dem einzugügenden und versuche, das verdrängte Element einzufügen.. Aber es passiert immer, dass es dann beim verdrängen immer zu einem Hin-und-Her verdrängen zwischen 2 Elementen(oder blöcken hab das net genau überprüft) kommt und somit dann wenn die versuche aufgebraucht sind eben die Exception wirft

[CansaSCity]

Ich weiß halt nicht wie viel Overhead wir produzieren dürfen.

Eine weitere Idee von mir, ist nur nach der ersten Funktion zu hashen und die Buckets ermstal zu vergrößern, so viel Platz wie sie halt brauchen. Dann merke ich mir nur die Übergelaufenen, was problemlos gehen sollte weil diese anzahl logarithmisch zur anzahl der Elemente wächst.

Dann schaue ich mir die Elemente in den Übergelaufenen Buckets noch einmal an, die stark übergelaufenen zuerst. Wenn ich dann ein Element gefunden habe, was in ein nicht übergelaufenes Bucket mit der 2. Hashfunktion zeigt, setze ich es da rein. Und zwar solange bis alle Buckets wieder die Ursprüngliche Größe haben...


Aber für den Algorithmus wären Listen echt was schönes.... denkt ihr das geht klar???

Oder vll Vorschläge für eine andere Datenstruktur mit der so etwas effizient funktioniert oder zumindest möglich ist???

Ich werde es jetzt mal mit nem 2-Dimensionalen Array probieren.

[Chrisss]

2-Dimensionale Arrays hab ich die ganze Zeit schon in Verwendung.
Hab jetzt versucht mir die schon verdrängten Elemente zu merken, damit ich da nich in nen sinnlosen kreislauf reinkomme
Scheint bis jetzt auch zu funktionieren aber es fühlt sich nicht wirklich schnell an^^
Und bei FixedSize hatte es glaub erhebliche anlaufschwierigkeiten^^
FixedSize das kleinste epsilon war 0.0649 und dabei gabs noch ne quote von 0.1
Also fühlt sich nicht wirklich effizient oder schnell an, leider
Hat jemand vllt noch ne Idee wie man das ganze wirklich gut implementieren kann.. ich könnte wetten das geht einfacher.
Könnte die Punkte denk ich echt gebrauchen =x mir fällt nur nix mehr ein momentan

EDIT: Ich muss die grenze für Verdräng-Versuche ziemlich hoch stellen damit es bei 0.1 epsilon überhaupt gut läuft omg
was mach ich falsch^^^^^^

[CansaSCity]

Mein oben beschriebener Algorithmus funktioniert... Hier meine Werte:

1 25045 1.0
2 11607 1.0
4 10909 1.0
8 13004 1.0
16 16789 1.0
32 23215 1.0
64 37546 1.0
128 67005 1.0
256 122529 1.0
512 249794 1.0
1024 461008 1.0
2048 965653 1.0
4096 2007867 1.0
8192 4002841 1.0
16384 10300932 1.0
32768 18563281 1.0
65536 37825449 1.0
131072 77279724 1.0
262144 231364335 1.0
524288 454180279 1.0
1048576 1363507680 1.0

[ryo]

Kleine Nebenfrage:

Es heißt bei der a) "Entwerfen Sie detailliert die interne Darenstruktur"

Kann mir mal jemand erklären, warum das 4 Punkte gibt? Ich meine, wenn ich jetzt z.B. n 2-dim Array nehme, dann bekomme ich 4 Punkte allein dafür, dass ich schreibe: mache ein 2Dim Array mit den Größen array[x][y]? Versteh ich hier was falsch?

[CansaSCity]

ach mist, ich hatte keine assertions an.... jetzt ist mir aufgefallen dass ich nen Fehler drin hatte und der deswegn so schnell war...

schön langsam bin ich echt am verzweifeln

[kimbo]

anfangs war meine idee auch, 2d-arrays zu benutzen.
leider hab ich jetzt aber kp, wie das funktionieren soll, da mit generics generell keine arrays erstellt werden können (laut eclipse).
daher bin ich auf listen umgestiegen, was jedoch laufzeit kostet.
daher meine frage: wie macht ihr das mit den 2d-arrays.
danke im voraus,
kornykimbo