Info08.de - Forum des Erstsemester Jahrgangs 2008

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 komme...

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

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...

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 log...

Ok funktioniert gar nicht gut...

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

"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 ...

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 kein...

Ich glaube ich habe gerade einen rieeesen Hänger.... In der Aufgabe steht doch, dass die Tabelle bei n zu Hashenden Elementen n(1 + \epsilon ²) Elementen groß sein darf... richtig??? Also wenn man das ausmultipliziert, dann steht da doch etwas von n + n*\epsilon .. sprich mehr Elemente wie eigentlic...

du bist mein Held

Also ich habe ein O(k) im schlimmsten Fall, den sollen wir ja schließlich angeben. Und zwar rührt der leider daher, dass wenn ein Array voll läuft, ein neues Array allociert und reallociert werden muss, wenn du poppst und es leerläuft. Allocieren ist abhängig von k, weil du für k Elemente Platz scha...