1. Übung, in-place programmieren

meta72
Erstie
Erstie
Beiträge: 15
Registriert: 17. Apr 2013 13:40

1. Übung, in-place programmieren

Beitrag von meta72 »

Bedeutet in-place programmieren, dass man in rekursiv aufgerufenen Prozeduren auch keinen neuen Pointer auf ein bereits bestehendes ListItem erzeugen darf? An der Adresse des neuen Pointers würde dann ja die Adresse des ListItems stehen, was Speicherplatz bedarf und somit bei längeren Listen, bei denen die rekursive Prozedur öfter aufgerufen wird mehr Speicherplatz benötigt und somit der Speicherbedarf nicht unabhängig von der Listenlänge wäre. Oder verdenke ich mich hier gerade zu kompliziert?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 1. Übung, in-place programmieren

Beitrag von JannikV »

Hallo,

das ist eine sehr gute Frage.

Im letzten Jahr war es ok. Ich habe da selbst irgendwo eine Hilfsvariable benutzt. Ich denke es geht auch nicht immer ganz ohne. Daher müsste das eigentlich ok sein, wenn man es wirklich auf das Nötigste beschränkt.
Wichtig ist: keine neuen Objekte erzeugen. Maximal nen "Pointer" auf ein bestehendes Element setzen. (außer bei duplicate.. da muss ja wohl oder übel ein neues angelegt werden)

VG

jw.
Erstie
Erstie
Beiträge: 12
Registriert: 20. Apr 2013 11:54

Re: 1. Übung, in-place programmieren

Beitrag von jw. »

Nochmal zum Verständnis: darf man sowas machen wie ListItem<T> p = first; um sich zB den Listenkopf zu holen?
Wohingegen Code wie ListItem<T> p = new ListIten<T>(...); verboten ist? Ist das richtig so?

meta72
Erstie
Erstie
Beiträge: 15
Registriert: 17. Apr 2013 13:40

Re: 1. Übung, in-place programmieren

Beitrag von meta72 »

So hätte ich das jetzt auch verstanden, ersteres ist ein Pointer auf ein existierendes ListItem, das zweite erzeugt ein neues ListItem, also benötigt extra Speicherplatz.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 1. Übung, in-place programmieren

Beitrag von JannikV »

Ja genau.

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: 1. Übung, in-place programmieren

Beitrag von Domac »

Servus.

Für die rekursiven Aufgaben darf man aber durchaus Hilfsmethoden verwenden, oder?

Gruß
Extend my dropbox space (here).
Thanks!

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 1. Übung, in-place programmieren

Beitrag von JannikV »

Ja klar, anders ist das auch schwer oder unschön machbar. Hatten wir aber hier schon: viewtopic.php?f=166&t=27801
;-)

31chh0rn
Neuling
Neuling
Beiträge: 7
Registriert: 23. Apr 2013 17:00

Re: 1. Übung, in-place programmieren

Beitrag von 31chh0rn »

Hi,
ich gehe davon aus, dass der Teil "Das bedeutet, dass unabhängig von der
Eingabeliste der zur Bearbeitung benötigte Speicherplatz konstant sein muss." der Aufgabenstellung nicht für die rekursive Variante gilt, da diese ja für jedes ListItem für das ein rekursiver Aufruf geschehen muss, ein neues Stackframe erzeugt und damit der verwendete Speicher nicht unabhängig von der Listengröße sein kann, oder irre ich mich?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 1. Übung, in-place programmieren

Beitrag von JannikV »

Ja, das geht bei rekursiven Algorithmen natürlich nicht anders.. Stackframes zählen nicht dazu. (Wer noch kein GdI 3 gehört hat, oder sonst keine Erfahrung damit gesammelt hat weiß ohnehin noch nichts davon ^^)

VG

Lutz
Neuling
Neuling
Beiträge: 10
Registriert: 23. Apr 2013 18:31

Re: 1. Übung, in-place programmieren

Beitrag von Lutz »

Hallo, hab da auch mal eine Frage:
Der key eines ListItem darf nicht überschrieben werden, sondern nur der next-Wert.
heißt das jetzt:

ListItem<T> p = first.next.next;
first.next = p; ist erlaubt
first = p; ist nicht erlaubt
?
Bin mir grad unsicher, ob bei der dritten Zeile wirklich der key überschrieben wird.
mfg Lutz

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 1. Übung, in-place programmieren

Beitrag von JannikV »

Theoretisch ist die dritte Zeile auch in Ordnung. Da veränderst du ja keinen key von einem listitem.
First ist nur eine Referenz auf ein listitem.

VG

Lutz
Neuling
Neuling
Beiträge: 10
Registriert: 23. Apr 2013 18:31

Re: 1. Übung, in-place programmieren

Beitrag von Lutz »

ah ok, das vereinfacht das ganze, vielen dank :-)

veronika
Neuling
Neuling
Beiträge: 5
Registriert: 28. Apr 2013 17:02

Re: 1. Übung, in-place programmieren

Beitrag von veronika »

Darf man eine neue Liste erstellen? Also List<T> tmpList = new List<T>();? Denn die Liste enthält ja nur die Referenz auf das erste ListItem, und es wird kein neues ListItem erstellt.

Schnell
Nichts ist wie es scheint
Beiträge: 23
Registriert: 11. Feb 2010 22:27

Re: 1. Übung, in-place programmieren

Beitrag von Schnell »

Würde sagen nein, da "[...]sondern das alle Operationen auf der Eingabeliste durchgeführt werden
müssen".
Du hast zwar keine neuen Elemente UND der Speicherplatz ist von der Größe der Eingangsliste unabhängig (da ja immer nur genau 1 neues Objekt erzeugt wird), aber erstellst eben formal trotzdem ein neues Objekt List.
Es ist btw auch nicht notwendig.

Hirsch
Erstie
Erstie
Beiträge: 14
Registriert: 28. Apr 2013 18:21

Re: 1. Übung, in-place programmieren

Beitrag von Hirsch »

Aufgabe c) rotateTriples

Ohne Zwischenspeichern in einem neuen ListItem gehts doch nicht oder?

Bsp:
b auf d referenzieren -> c verschwunden
c auf a referenzieren -> alles was nach c kommt verschwunden

Gibts da ein Trick, oder kann man bspw. beide Operationen "auf einmal" ausführen.
Ansonsten geht doch nicht ohne Zwischenspeichern!
Seit 2h am Verzweifeln. Help pls.

Antworten

Zurück zu „Archiv“