HÜ 11 b)

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

HÜ 11 b)

Beitrag von m_stoica »

Wie ist denn die Aufgabe b) gemeint?
Wenn man sich die nachfolgenden Teilaufgaben anschaut, dann sieht man, dass die Threadversion nicht richtig sortieren sollte. Bei mir
funktioniert es aber auch mit Threads prima. (auf einem zwei Prozessoren Rechner)

Ist es vielleicht so gemeint, dass wir mit dem einen Thread nur den linken Teil der Liste und mit dem anderen Thread nur den rechten Teil der Liste sortieren?
Das würde natürlich dazu führen, das jeweils die zwei hälften sortiert sind, aber die Liste ingesammt nicht.

Oder sollen wir vielleicht einfach nicht auf das Ende beider Threads warten? Aber warum sollten wir absichtlich Fehler rein machen?

Sollen wir eigentlich immer rekursiv zwei neue Threads starten? Dann würden nämlich insgesamt mehr als zwei Threads parallel arbeiten, und ich hatte es eigentlich so verstanden, dass es nur zwei Threads geben soll.

Grüße,
Michael

Jonathan
Mausschubser
Mausschubser
Beiträge: 47
Registriert: 10. Okt 2008 13:37

Re: HÜ 11 b)

Beitrag von Jonathan »

Natürlich soll man mit jedem Thread je nur einen Teil der Liste sortieren, sonst wird ja nichts durch die Parallelisierung beschleunigt.

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: HÜ 11 b)

Beitrag von m_stoica »

mit NUR meinte ich ohne die zwei sortierten Teillisten wieder "zusammenzufassen" sodass die ganze liste sortiert ist. (Also z.B ohne dem rekursiven Aufruf
von slowsort (A,i,j -1) am ende)

Ondori
Mausschubser
Mausschubser
Beiträge: 89
Registriert: 28. Okt 2006 19:50

Re: HÜ 11 b)

Beitrag von Ondori »

Ich fürchte ich habe es auch noch nicht ganz verstanden.
Sollen wir die Liste der Zahlen nur einmal (in main) aufteilen und jeweils einen Teil von einem Thread sortieren lassen und die Slowsort-Implementierung nicht verändern (dann hätte man denke ich 2 getrennt sortierte Listen, die aber nicht zusammenpassen)?
Oder sollen wir versuchen in Slowsort rumzumachen?

Thx

fetzer
Kernelcompilierer
Kernelcompilierer
Beiträge: 522
Registriert: 1. Okt 2008 17:18

Re: HÜ 11 b)

Beitrag von fetzer »

Ondori hat geschrieben:Oder sollen wir versuchen in Slowsort rumzumachen?
Thx
Dann würdest du ja mehrere Threads durch die vielen rekursiven Aufrufe starten und nicht nur 2, welche auf den verschiedenen Kernen ausgeführt werden und was auch in top/htop sichtbar wird (vgl. Ausgabe ohne Threads).
m_stioca hat geschrieben:Das würde natürlich dazu führen, das[s]...
Das haben wir als Antwort auf die Frage angenommen ;) Die Antwort haben wir dann durch eine bearbeitete main()-Methode ergänzt, sodass am Ende wieder eine korrek sortierte Liste ausgegeben wird. Ich tippe darauf, dass wir dadurch lernen sollen, dass eine Aufteilung auch Probleme schaffen kann und nicht nur löst. So wird durch Threads ein Programm nicht automatisch "schneller".

Mira`
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 27. Okt 2006 20:41

Re: HÜ 11 b)

Beitrag von Mira` »

In der Aufgabe steht aber auch nur "Was KÖNNTEN sie tun, damit die Liste richtig sortiert wird". D.h. wir müssen keinen Code schreiben sondern lediglich mündlich eine Variante darlegen, nach der die Liste für dieses Beispiel am Ende korrekt sortiert WÄRE.

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: HÜ 11 b)

Beitrag von m_stoica »

Ja. Mein Problem ist aber, dass bereits von vornherein alles wunderbar läuft mit Threads. Das Programm arbeitet auch doppelt so schnell (auf einem zwei Kern-Prozessor) und die Liste ist ordentlich sortiert.

Mira`
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 27. Okt 2006 20:41

Re: HÜ 11 b)

Beitrag von Mira` »

Dann hast du im Prinzip ja alles "richtig" gemacht, aber eben net im Sinne der Aufgabenstellung.

Du übergibst die zu sortierende Liste dem slowsort einmal mit i=0, j=199 für den ersten Thread und für den 2. Thread eben mit i=200 und j=399 und operierst auf ein und der selben Liste parallel. Wenn du das so machst, bekommst du auch das "erwartete" Ergebnis. Du hast oben was geschrieben von "nachdem Zusammenfügen der Listen"...genau das soll ja nicht gemacht werden. 1 Liste als Ausgangspunkt auf dieser 2 Threads parallel ohne jegliches zusammenfügen operieren.

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: HÜ 11 b)

Beitrag von m_stoica »

vll ist es so gemeint. Für mich macht das aber keinen Sinn: Dann bräuchte ich ja keine Threads für einen speed up. Den Geschwindigkeitsschub erhält man dann nämlich vorallem deshalb, weil man die zwei letzten Teillisten nichtmehr "zusammenfasst". Dadurch spart man sich 400 rekursive Aufrufe!
Wäre vielleicht nett wenn sich einer der Tutoren oder Assistenten mal dazu äußern würde wie das nun gemeint ist.

fetzer
Kernelcompilierer
Kernelcompilierer
Beiträge: 522
Registriert: 1. Okt 2008 17:18

Re: HÜ 11 b)

Beitrag von fetzer »

Da du nur auf einer absteigend sortierten Liste arbeitest macht das insofern Sinn, als dass du beide Liste am Ende noch aneinanderhängen musst (und nicht "mergen"). Dies ist in einer Lösung ohne Threads so nicht vorgesehen. Daher hast du bei Threads nicht nur den Aufwand, das Threading einzubauen, sondern auch das Ergebnis der Threads nocheinmal zu bearbeiten, da die Liste dann so ja nicht wirklich bearbeitet ist.

Wirklich Sinn macht das natürlich nur für absteigend sortierte Listen. Alle anderen müsste man "mergen" und fährt dann wohl gleich mit anderen Algorithmen besser. Aber man muss ja nicht gleich das hier implementieren können ;)

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: HÜ 11 b)

Beitrag von mister_tt »

fetzer hat geschrieben:Wirklich Sinn macht das natürlich nur für absteigend sortierte Listen. Alle anderen müsste man "mergen" und fährt dann wohl gleich mit anderen Algorithmen besser.
Nicht nur. Das klappt auch mit manchen Listen, die nicht absteigend sortiert sind...

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: HÜ 11 b)

Beitrag von m_stoica »

fetzer hat geschrieben:Da du nur auf einer absteigend sortierten Liste arbeitest macht das insofern Sinn, als dass du beide Liste am Ende noch aneinanderhängen musst (und nicht "mergen"). Dies ist in einer Lösung ohne Threads so nicht vorgesehen
Für eine Lösung mit Threads ist das aber so vorgesehen ?

fetzer
Kernelcompilierer
Kernelcompilierer
Beiträge: 522
Registriert: 1. Okt 2008 17:18

Re: HÜ 11 b)

Beitrag von fetzer »

mister_tt hat geschrieben:
fetzer hat geschrieben:Wirklich Sinn macht das natürlich nur für absteigend sortierte Listen. Alle anderen müsste man "mergen" und fährt dann wohl gleich mit anderen Algorithmen besser.
Nicht nur. Das klappt auch mit manchen Listen, die nicht absteigend sortiert sind...
Ja gut, es sind halt alle Listen, bei denen alle Elemente größer bzw. kleiner der Zahlen sind, die auf der anderen Seite stehen...

Antworten

Zurück zu „Archiv“