Praktikum 8 getBucket()

noggybear
Neuling
Neuling
Beiträge: 9
Registriert: 9. Nov 2006 19:58

Praktikum 8 getBucket()

Beitrag 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?

Benutzeravatar
giftnudel
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 3. Mai 2005 11:26

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

Benutzeravatar
mnoll
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 17. Jul 2006 23:03

Beitrag 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ä

Talos
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 29. Apr 2004 14:03
Kontaktdaten:

Beitrag 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

Benutzeravatar
mnoll
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 17. Jul 2006 23:03

Beitrag 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?

n-finity
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 22. Dez 2006 15:38
Kontaktdaten:

Beitrag von n-finity »

jop

Benutzeravatar
Simon MD
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 5. Mai 2007 12:27
Wohnort: Nieder-Ramstadt
Kontaktdaten:

Beitrag 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.
"Erfolg ist die Feigheit vor der eigenen Inkompetenz"
- Oliver Kalkofe -

citta
Mausschubser
Mausschubser
Beiträge: 96
Registriert: 7. Nov 2006 21:52

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

jno
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 18. Mai 2007 09:41

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

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

joa, wenn du die einfach so reinhaust schon

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag 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

Benutzeravatar
giftnudel
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 3. Mai 2005 11:26

Beitrag 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)

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

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

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

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

citta
Mausschubser
Mausschubser
Beiträge: 96
Registriert: 7. Nov 2006 21:52

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

Antworten

Zurück zu „Archiv“