Seite 1 von 2

Praktikum 8 getBucket()

Verfasst: 26. Jun 2007 16:14
von 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?

Verfasst: 26. Jun 2007 16:58
von 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.

Verfasst: 26. Jun 2007 17:20
von 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ä

Verfasst: 26. Jun 2007 18:22
von Talos
Ich hab die Buckets jetzt einfach mal Sortiert gespeichert...am Donnerstag kann ich dann sagen ob es so gewünscht ist oder nicht

Verfasst: 29. Jun 2007 10:25
von 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?

Verfasst: 29. Jun 2007 10:37
von n-finity
jop

Verfasst: 29. Jun 2007 16:28
von 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.

Verfasst: 30. Jun 2007 17:38
von 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.

Verfasst: 30. Jun 2007 18:50
von 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.

Verfasst: 30. Jun 2007 19:33
von Christoph B
joa, wenn du die einfach so reinhaust schon

Verfasst: 30. Jun 2007 22:10
von 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 :P

Verfasst: 1. Jul 2007 17:15
von 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)

Verfasst: 1. Jul 2007 18:15
von 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.

Verfasst: 1. Jul 2007 18:33
von 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...

Verfasst: 1. Jul 2007 22:09
von citta
giftnudel hat geschrieben: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.