Algorithmen[Prog 2]

[Chrisss]

java generic arrays googlesuche
Du erstellst das Array als Array von Object und castest auf den generische typ
das ganze produziert dir dann ne unchecked-warning die aber in der init-methode durch annotation unterdrückt wird
K[][] table = (K[][]) new Object[bla][bluub]

[Johann]

Ich werd hier auch langsam wahnsinnig. Meine Lösung scheint Keys zu verdoppeln, dabei habe ich jede Stelle, die irgendwie schreibend auf das Array zugreift kontrolliert. Es wird nur verschoben, aber trotzdem kriege ich ständig den "Element xyz mehrmals in Hashtabelle". Hatte das auch jemand und weiß, was da so der Standardfehler ist und dazu führen könnte?

[SLS]

Ich werd hier auch langsam wahnsinnig. Meine Lösung scheint Keys zu verdoppeln, dabei habe ich jede Stelle, die irgendwie schreibend auf das Array zugreift kontrolliert. Es wird nur verschoben, aber trotzdem kriege ich ständig den "Element xyz mehrmals in Hashtabelle". Hatte das auch jemand und weiß, was da so der Standardfehler ist und dazu führen könnte?

Ich hatte auch diese Problem. Dann habe ich debuggt und herausgefunden, dass es tatsächlich in der Eingabe mehrmals dieselben Zahlen vorkommen können.
Lösung: Vor dem Einfügen zunächst gucken (find()), ob der Element nicht schon drinne ist.

[CansaSCity]

Jungs habt ihr neue Errungenschaften???

Ich glaube ich gebe es auf... ich komme gerade mal bis zur 16... und das auch nur mit 0.2% ...

Ich hatte so viele Ansätz, so viele Algorithmen, habe sie jetzt auch versucht alle ineinander zu bauen... kein Erfolg...

Ich kann sie ja mal hier aufzählen vll kommen euch irgendwelche Ideen:

1.
Hashen nach der ersten Funktion,
wenn das fehl schlägt nach der 2.
wenn das fehl schlägt kick ich das (depth%bucketSize). Element aus dem Bucket welches ich nach der ersten Hashfunktion bestimmt habe und suche für das Element einen neuen Platz... hab das bis zu einer rekursiontiefe von 100 gemacht... aber war nicht besser wie bei 10

wenn das fehl schlägt dann kick ich ein Element aus dem Bucket welches ich durch die 2. Hashfunktion erhalte...




2. Ich hashe alle Elemente nach der ersten Funktion. Wenn ein Element nicht mehr reinpasst, schaue ich mir ein nach und nach ein nichtvolles Bucket nach dem anderen an und suche Elemente in den 2 zielbuckts meines aktuellen keys die in dieses leere Bucket gehasht wird. Wenn das klappt, vertausche ich sie.


3. (wie 1) Wenn ich merke dass ich über eine Tiefe von 10 hinaus bin, versuche ich die Buckets zu balancieren, indem ich mir die Anzahl der bisher eingetragenen Elemente geben lasse und durch 4 Teile. Daraufhin versuche ich alle Buckets möglichst auf diese Größe zu bringen (bis ich keins mehr vertauschen kann was zur balancierung beiträgt). Wenn das erreicht ist, gehts weiter mit dem einfügen und einem depth von 0.


4. Ich fülle alle elemente nach ihrer ersten Hashfunktion ein und leihe mir Felder von anderen Buckets, falls diese zu groß werden. Wenn alle Elemente eingefüllt sind, versuche ich für die Buckets, die zu groß sind, durch die 2 Hashfunktion felder zu finden, in denen sie noch Platz finden....
(Ich dachte dass die 4 meine Lösung sei... aber entweder war ich zu doof zum implementieren, oder sie hört sich für mich nur gut an.)




Naja dann wünsch ich euch noch viel Erfolg, mir reichen theoretisch die Punkte für das remove implementieren... vll bekomm ich irgendwo noch ein paar Gnadenpunkte so dass es etwas konfortabler wird...

machts gut

[Johann]

Lösung: Vor dem Einfügen zunächst gucken (find()), ob der Element nicht schon drinne ist.

Woah vielen Dank. Das hats echt rausgerissen, endlich läuft der Scheiß.

Zu oben:

Mein Ansatz und der Ansatz laut http://en.wikipedia.org/wiki/Cuckoo_hashing ist:

Man fügt einfach in Bucket #1 ein wenns geht, ansonsten Bucket #2 (wobei ich die mische, also in einer Schleife checke, evtl. kann man hier optimieren). Wenn beide voll sind werden nacheinander Bucket #1 und Bucket #2 durchgegangen und es wird versucht ein Element zu verdrängen. Das übernimmt eine rekursive Funktion. Ich sage z.B. "Probier Element 1 aus Bucket 1 woanders hinzubringen". Das geschieht indem es dessen beide Hashwerte (also Buckets) berechnen und dort nach Lücken sucht. Gibts dort keine Lücke nimmt es wiederum ein Element aus den beiden Buckets und versucht diese wiederum zu verschieben. Gelingt es einmal, wird rekursiv zurück durchverschoben bis der ursprünglich gewünschte Platz frei ist. Gelingt es nicht (wird durch eine Tiefensperre ermöglicht, also z.B. maximale Rekursionstiefe 2 oder 3 oder so), gibt es einen Fehler zurück und das nächste Element aus den ganz anfänglichen Buckets wird zu verdrängen versucht.

[Dre]

Mein Ansatz und der Ansatz laut http://en.wikipedia.org/wiki/Cuckoo_hashing ist:...

Yo, genauso haben wir das auch gemacht. Wusste gar nicht, dass das unter nem Namen läuft.