Not logged in. · Lost password · Register

thejonny
Member since Oct 2012
71 posts
Subject: aufgabe3 : halde (wie in uebung:) )
Hallo :)

Hab mal nen neuen thread aufgemacht  für fragen zur lösung aus der uebung:)

und zwar steht in der aufgabenstellung, dass wlist05 sortiert werden können muss. wenn man eine ganz naive immpementierung von wsort und eine ganz naive realloc() hat, die alle zeilen einmal malloct, und für jede zeile ein realocc(oldlines, (nzeilen)*sizeof(char*)) macht, um sich fuer einen neuen pointer platzzumachen, werden dort 7973*(101+16) bytes für die zeilen belegt, was ja noch kein problem darstellt, aber dann werden in jedem realloc() alle pointer kopiert, und kein altes speicherstück passt, also wird es immer platz für einen pointe mehr kopiert.
dann werden nur für die pointer durch das neuanlegen (7973*(7973+1)/2)*sizeof(char*) =  254306808 bytes  (bei 8byte pointerlaenge im cip) allokiert, was ja nicht ganz aufgeht (128MiB = 1<<27 = 134217728)

muss das realloc dann doch intelligenter sein?

Viele Grüße,
Jonathan
izibi
Blockchain-Exorzist
(Administrator)
Member since Oct 2012
557 posts
Quote by thejonny:
muss das realloc dann doch intelligenter sein?

Wäre wahrscheinlich einfacher, die wsort in der Hinsicht zu optimieren (d.h. nicht pro Zeile ein realloc sondern z.B. immer den Speicher verdoppeln, wenn er voll ist), aber das kann eigentlich kaum Sinn dieser Aufgabe sein.
lusiux
SP-Team
Member since Oct 2005
444 posts
In reply to post #1
Quote by thejonny on 2013-05-22, 18:37:
und zwar steht in der aufgabenstellung, dass wlist05 sortiert werden können muss. wenn man eine ganz naive immpementierung von wsort und eine ganz naive realloc() hat, die alle zeilen einmal malloct, und für jede zeile ein realocc(oldlines, (nzeilen)*sizeof(char*)) macht, um sich fuer einen neuen pointer platzzumachen, werden dort 7973*(101+16) bytes für die zeilen belegt, was ja noch kein problem darstellt, aber dann werden in jedem realloc() alle pointer kopiert, und kein altes speicherstück passt, also wird es immer platz für einen pointe mehr kopiert.
dann werden nur für die pointer durch das neuanlegen (7973*(7973+1)/2)*sizeof(char*) =  254306808 bytes  (bei 8byte pointerlaenge im cip) allokiert, was ja nicht ganz aufgeht (128MiB = 1<<27 = 134217728)

Die wlist05 war für eine naive 32-Bit wsort-Implementierung ausgelegt. Bei der Umstellung auf 64-Bit haben wir vergessen die Liste zu verkleinern.

Ab sofort befindet sich im pub-Verzeichnis eine neue (und kleinere) wlist05.

Quote by thejonny on 2013-05-22, 18:37:
muss das realloc dann doch intelligenter sein?

Nein.
Vorsicht: Dieser Post kann Spuren von Sarkasmus, Ironie und Nuessen enthalten.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen