Praktikum 8 getBucket()

[noggybear]

Was heißt dies genau:

"Stellen Sie sicher, dass auch nach einem Aufruf von sort() die Buckets (samt Be-
legung) noch für Aufrufe von getBucket() zur Verfügung stehen. Wir werden auch
Ihre Bucketbelegung testen."

Soll man hier die Buckets unsortiert lassen oder sollen sie sortiert sein?

[giftnudel]

Ich vermute mal, dass die ruhig sortiert sein können, dass nur überprüft wird, ob du wirklich proxmap sort oder einfach dein (schlechteres) Verfahren auf die gesamte Liste angewendet hast.

Im Zweifelsfall fällt dieser Fehler aber nach dem ersten Upload auf.

[mnoll]

Ich denke einfach das man hier nicht durch das Sortieren die Bucketbelegung verändern soll, sprich evtl die schon sortierten Keys löschen oä

[Talos]

Ich hab die Buckets jetzt einfach mal Sortiert gespeichert...am Donnerstag kann ich dann sagen ob es so gewünscht ist oder nicht

[mnoll]

Wie sieht es denn aus mit der Initialisierung der Buckets. Ich habe bei mir nur eine ArrayList reingeschoben wenn ich auch wirklich ein Element in einem Bucket habe. Ansonsten is das Bucket null. Jetzt bekomme ich bei jedem Buckettest: "Your code raised the following exception "NullPointerException: null" by accessing a (valid) bucket."
Wird da überall ne leere ArrayList verlangt?

[n-finity]

jop

[Simon MD]

Buckets können sortiert und unsortiert sein. Wichtig ist eigentlich nur, dass man sich die Buckets speichert und nicht nach jedem füllen und sortieren wieder löscht.

[citta]

Wenn die Buckets bereits sortiert sind, kann man das ja ausnutzen, so dass bei einem neuen Element das Element nur in die richtige Position eingefügt werden kann in O(n). Darf man das ausnutzen oder muss quasi in "kompletter" Sortieralgorithmus auf die Buckets angewandt werden? Was mich dabei stört ist der Abschnitt in der Aufgabenstellung:

Zur Sortierung mittels Proxmapsort werden die zu sortierenden Elemente zuerst unsortiert
in Buckets gruppiert. Diese Buckets werden danach mit einem beliebigen Sortieralgorithmus
sortiert und dann zur endgültigen sortierten Liste zusammengefügt.

[jno]

Also, wenn man zB bei den Doubles wie im Codegerüst vorgeschlagen floor als Mapkeyfunktion benutzt, dann sind die Buckets doch IN DER REGEL schon unsortiert oder nicht? Alles andere dürfte ein recht seltener Spezialfall sein.

[Christoph B]

joa, wenn du die einfach so reinhaust schon

[MisterD123]

@citta: frag doch einfach deinen tutor obs ok geht wenn du die buckets gleich sortiert machst und posaun das hier nich so rum sonst kriegt er noch verboten sowas zu akzeptieren

[giftnudel]

Zur Komplexität: in jedem Schritt O(n) macht unser O(n) Proxmap sort zu O(n^2) => Aufgabenstellung verfehtl! => max 5 Punkte im Testat ... (zumindest bei mir)

[Edoat]

Die Komplexität hängt, so wie ich das verstanden habe, hauptsächlich von der Map Key Funktion ab.

Die ist beim Praktikum aber vorgegeben (in den Vorlage-Dateien steht Math.floor für Doubles und Sortierung nach Anfangsbuchstaben für Strings), deshalb kann man da keine gute Komplexität für schlechte Eingabemengen erreichen, da man die Map Key Funktion nicht ändern darf.

[HolgerF]

Das war wohl eher eine Antwort auf citta und sein Vorhaben, die Buckets quasi per Insertion Sort schon direkt beim Füllen zu sortieren...

[citta]

Zur Komplexität: in jedem Schritt O(n) macht unser O(n) Proxmap sort zu O(n^2) => Aufgabenstellung verfehtl! => max 5 Punkte im Testat ... (zumindest bei mir)

Hmm...
Ja, es wäre O(n^2), wenn man denn annimmt, dass man alles in den gleichen Bucket einordnet, also quasi der worst case. Diesen Nachteil hat allerdings auch der Proxmapsort, bei dem man erst hinterher die Buckets mit Insertionsort sortiert.

Angenommen, ich habe 5 Sachen im Bucket, dann hätte ich 5n-Aufwand für einen Bucket. Ansonsten habe ich pro Eimer O(n^2) Aufwand, also n^2 mit n=5 in diesem speziellen Bucket.

In "glücklicheren" Fällen habe ich nach wie vor konstanten Aufwand, um Sachen in die Buckets zu legen.

Was mich zu dieser Unsicherheit trieb, waren auch ein paar Stellen in den Folien, z.B. 12-63, dort steht zur Beschreibung des Proxmapsorts

Worst case: n Schlüssel mit je O(n) -> O(n^2)

Was ähnlich klingt wie das, was an meiner Idee zu bemängeln war. Auf 12-69 steht nochmal "degeneriert zu Insertionsort", aber vielleicht interpretiere ich zuviel zwischen den Zeilen.

Vielleicht kann mich jemand den Hebel an meiner Unlogik ansetzen und mir erklären, was an meiner Erklärung auszusetzen ist. Hat ein wenig mein Interesse geweckt.

Werde wohl dennoch meine Einsendung revidieren, um unnötige Komplikationen zu ersparen. Lieber Strings und Doubles im Eimer, als das Testat.