Praktikum 8 getBucket()
Praktikum 8 getBucket()
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?
"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?
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?
Wird da überall ne leere ArrayList verlangt?
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.
-
- Computerversteher
- Beiträge: 370
- Registriert: 15. Okt 2006 18:28
- Wohnort: Wiesbaden
- Kontaktdaten:
- MisterD123
- Geek
- Beiträge: 811
- Registriert: 31. Okt 2006 20:04
- Wohnort: Weiterstadt
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.
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.
Hmm...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)
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
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.Worst case: n Schlüssel mit je O(n) -> O(n^2)
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.