Lastfaktor
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 11.3 d)
Hallo,
bei der 11.3 d) soll man ja den Lastfaktor angeben. Ich dachte bislang der Lastfaktor ist
(Anzahl der eingetragenen Elemente) geteilt durch (Anzahl der Behälter).
Wenn das so ist, dann ist aber der Lastfaktor von Teilaufgabe a) und Teilaufgabe b) gleich oder?
Denn die tabelle ist ja gleich groß und es wurde auch genauso viel eingetragen.
Oder heißt Lastfaktor vielleicht doch, dass man
(Anzahl der belegten Buckets) geteilt durch (Anzahl der Buckets rechnet)
dann käme JEWEILS was anderes raus und in der aufgabe steht ja auch “geben sie füre ihre Lösungen zu a) und b) JEWEILS den Lastfaktor an”.
Was meint ihr?
s)
Ich habe mal in der Vorlesung den Prof gefragt.
der Lastfaktor ist für beide gleich, also:
(Anzahl der eingetragenen Elemente) geteilt durch (Anzahl der Behälter)
Begründung:
Es ist eine Schätzung mit dem dicken Daumen und deswegen ist es nicht relevant welches Sondierverfahren man verwendet.
Die Kollisionswahrscheinlichkeit wird also nicht “genau” berechnet.
(man könnte natürlich einen genaueren “Lastfaktor” bestimmen wenn man die Art der Sondierung mit in betracht zieht, ist aber hier nicht gewünscht.
man muss sich das ähnlich wie beim O-Kalkül vorstellen.)
Ich denke auch, dass beide gleich sind und das eine Fangfrage ist.
1 Like
Wenn man sich aber die Folien von der Übung anschaut, dann würde ich das auch als Anzahl belegter buckets durch Anzahl buckets-gesamt verstehen…
Wenn ich mir die Übungsfolien anschaue, komme ich zum genau umgekeherten Schluss,
nämlich, dass es Anzahl eingetragener Elemente geteilt durch Anzahl der Behälter ist.
s)
Hast recht. Aber ich hab doch 8 Elemente auf 9 buckets. Rundert ihr auf, weil an sich sind das keine 100% bei mir. Oder denkt ich jetzt falsch?
Die Anzahl aller Buckets ist die Mächtigkeit der Lösungsmenge der Hashfunktion x modulo 8. Wie groß ist sie bei dir?
What? Und jetzt bitte nochmal auf deutsch xD
Du hast eine Zahl. Diese dividierst du durch acht. Da kommt irgendein Rest raus. Wie viele verschiedene Reste sind möglich?
Die Antwort auf die letzte Frage ist die Anzahl aller möglichen Buckets.
Wieso hast du 9 Buckets?
Ich habe acht Buckets ( von 0 bis 7) und 8 eingetragene Elemente, geht also schön auf, ohne dass man da irgendwas runden müsste.
s)
NACHTRAG: Habe jetzt erst gemerkt, dass Chayyam ja genau auf das Gleiche hinaus wollte=)