[C++] 5 Threads die een file sorteren...

[Verwijderd]

Ik heb een vraag, ik heb 5 files waarbij bij de getallen door elkaar in staan. In het totaal zijn het 2000 getallen per file dus 10000 getallen. Als een getal in file 1 staat, staat het in de andere 4 zeker niet en andersom ook. Dus een getal komt maar in 1 file voor. Nu moet ik 5 threads maken die kijken wie het laagste getal heeft en die mag het in 1 nieuwe file schrijven. Die 5 threads sorteren dus die 5 files naar 1 file, iedere keer de thread met het laagste getal mag schrijven zodat op het einde die 5 files gesorteerd in die ene nieuwe file staan.
Nou is dat threads maken en zo geen probleem maar hoe laat ik die threads onder elkaar kijken wat ze voor waarde uit hun file hebben en wie dus mag schrijven?

[.oisyn]

is dit huiswerk? ik kan me niet voorstellen dat je in de werkelijkheid zo'n zelfde soort probleem met verschillende threads aanpakt

[Verwijderd]

Nee geen huiswerk er is hier op mijn werk een nieuwe en die moet die opdracht maken en aangezien ik de enige met een internetverbinding ben ben ik degene die het moet vragen.

[curry684]

Hierbij moet je het platform aangeven. Enne je zoekt naar het woord 'mutex' en/of 'critical section'.

[Verwijderd]

Platform winXP met servicepack 1 op Visual Studio .NET

[Verwijderd]

maar hoe laat ik dan die threads met elkaar communiceren?

[Sjaaky]

Dat kan met shared memory, pipes en vast nog wel een aantal manieren. Anders moet je de MSDN er eens bij pakken.

[.oisyn]

threads draaien allemaal in hetzelfde proces, dus ze kunnen ook allemaal bij hetzelfde geheugen

[jelmervos]

.oisyn schreef op 24 oktober 2002 @ 17:39:
threads draaien allemaal in hetzelfde proces, dus ze kunnen ook allemaal bij hetzelfde geheugen

Maar dat moet je wel beschermen met critical sections enz.

[.oisyn]

hoeft niet natuurlijk, das alleen als je ernaar gaat schrijven... niets mis met meerdere threads die tegelijk lezen

Maar idd, de topicstarter zal wat aan concurrency control moeten doen... dmv mutexen, semaphoren of events oid...

[Verwijderd]

Waarom laat je de parent niet schrijven en de threads alleen lezen/zoeken? Alleen de thread die het kleinste getal leverde hoeft verder te zoeken terwijl de andere threads kunnen blijven slapen, en zo'n beslissing is altijd makkelijker te maken door een "judging thread" (de parent) dan door de threads onderling.

Overigens is dit een mergesort probleem, en daar zijn efficientere algoritmes voor dan dit voorstel.

[MSalters]

De threads zijn volledig zinloos (tijdens de merge). Nadat de threads hun input gesorteerd hebben mag je ze exiten. Op win32 zou je eventueel de mergethread kunnen laten wachten op het exiten van de 5 reader threads.

PS. als dit een test opdracht is voor een nieuwe ( en zo lees ik post 3 ), terwijl jullie het zelf niet weten , dan

[Verwijderd]

MSalters schreef op 24 oktober 2002 @ 20:02:
De threads zijn volledig zinloos (tijdens de merge).

Ik zat te twijfelen of ik dit expliciet zou schrijven, maar het leek me beter het te indiceren door te suggereren dat er maar een thread loopt.

Op win32 zou je eventueel de mergethread kunnen laten wachten op het exiten van de 5 reader threads.

En waarom niet in een ander OS? (man pthread_join)

[Sjaaky]

Ik snap het idee nog niet helemaal. Het is een soort test opdracht om de kennis en autodidactische skills van een nieuwe medewerker te testen neem ik aan?? Maar dan is het niet echt logisch dat hij het op een forum mag vragen. Als multithreaded programmeren nieuw is voor het hele bedrijf, dan kan je beter met een boek of een flink artikel beginnen, ipv een topic op een forum.
Sowieso klinkt het niet als een opdracht voor een klant, want zoals .oisyn al in de 2e reply zei is dit niet iets wat je met meerdere threads oplost. (Behalve in een gedistribueerde omgeving, maar dat is wat anders).

[Verwijderd]

... maar hoe laat ik die threads onder elkaar kijken wat ze voor waarde uit hun file hebben ...

wat dacht je van Send/PostMessage () ???

... een nieuwe en die moet die opdracht maken en ...

dus toch huiswerk .. .

[xoror]

Verwijderd schreef op 24 oktober 2002 @ 22:05:
[...]

Ik zat te twijfelen of ik dit expliciet zou schrijven, maar het leek me beter het te indiceren door te suggereren dat er maar een thread loopt.


[...]

En waarom niet in een ander OS? (man pthread_join)

http://sources.redhat.com/pthreads-win32/

je kan posix threads ook onder windows gebruiken. veel fijner dan standaard windows api

[.oisyn]

[nohtml]

Verwijderd schreef op 24 oktober 2002 @ 22:58:

wat dacht je van Send/PostMessage () ?

wat dacht je van PostThreadMessage (), met Send en PostMessage kun je geen berichten sturen naar een thread, alleen naar een window.

Verder, en ik geloof dat ik dat al eens eerder heb gevraagd, kun je eens proberen normale interpunctie te gebruiken, ipv zinnen te onderbreken met 5 punten en vragen af te sluiten met 13 vraagtekens (bij wijze van spreke)? Ik zeg natuurlijk niet dat het verboden is, en het kan goed gebruikt worden om bepaalde dingen te accentueren, maar jij doet het in elke post, dat leest nogal irritant.

[curry684]

Verwijderd schreef op 24 oktober 2002 @ 17:05:
Ik heb een vraag, ik heb 5 files waarbij bij de getallen door elkaar in staan. In het totaal zijn het 2000 getallen per file dus 10000 getallen. Als een getal in file 1 staat, staat het in de andere 4 zeker niet en andersom ook. Dus een getal komt maar in 1 file voor. Nu moet ik 5 threads maken die kijken wie het laagste getal heeft en die mag het in 1 nieuwe file schrijven. Die 5 threads sorteren dus die 5 files naar 1 file, iedere keer de thread met het laagste getal mag schrijven zodat op het einde die 5 files gesorteerd in die ene nieuwe file staan.
Nou is dat threads maken en zo geen probleem maar hoe laat ik die threads onder elkaar kijken wat ze voor waarde uit hun file hebben en wie dus mag schrijven?

Ik zie dus echt totaal het nut niet hier van multithreading. De effectiefste manier om dit te doen is duidelijk om de 5 files eerst afzonderlijk te sorteren en daarna met behulp van een array van pointers er doorheen te waggelen. Oftewel de uiteindelijke merge-actie is al singlethreaded. En of je nu 5 threads spawnt die 5 files sorteren, of 1 thread die achter mekaar 5 files sorteert maakt totaal geen kont uit: je verbruikt evenveel processing time.

Singlethreaded dus gewoon imho.

Verwijderd schreef op 24 oktober 2002 @ 17:09:
Nee geen huiswerk er is hier op mijn werk een nieuwe en die moet die opdracht maken en aangezien ik de enige met een internetverbinding ben ben ik degene die het moet vragen.

En deze zin sluit niet uit dat jij zelf die nieuwe bent, en toevallig ook nog de enige met een internetverbinding

Maarruh het klinkt nogal onwaarschijnlijk dat 'die nieuwe' meteen een opdracht krijgt die te moeilijk is voor de rest van het bedrijf, en het dan ook nog via internet moet opzoeken... als het echt zo is: ontslaan die manager

[Verwijderd]

nee zo nieuw is hij ook weer niet maar hij moet leren met c++ te werken en aangezien ik helemaal geen verstand heb van multithreading kan ik hem daar niet mee helpen. En hij heeft een boekje met opdrachten wat hij moet doorwerken en daar staat die opdracht in.
En nee het is geen testopdracht en ook geen huiswerk en ook niet voor mij. En ik ben degene die ze admin noemen daarom heb ik internet .

[Verwijderd]

maar ik denk dat we al een heel eind komen met de informatie wat jullie gegeven hebben, dus in ieder geval bedankt voor jullie reacties.

[NaliXL]

Huh? Ligt dat nou aan mij, of word er hier gewoon bijzonder moeilijk gedaan? Zou het niet het gemakkelijkste zijn om iedere thread zijn getal te laten zoeken, en vervolgens de output-file te laten openen. Bevat die output-file een hoger getal dan het gevonden output-getal, dan overschrijf je, anders niet. Enige waar je rekening mee moet houden is dat meerdere threads tegelijkertijd zullen proberen te lezen/schrijven, dus zorg dat je je file lockt.

[curry684]

NaliXL schreef op 25 oktober 2002 @ 11:15:
Huh? Ligt dat nou aan mij, of word er hier gewoon bijzonder moeilijk gedaan? Zou het niet het gemakkelijkste zijn om iedere thread zijn getal te laten zoeken, en vervolgens de output-file te laten openen. Bevat die output-file een hoger getal dan het gevonden output-getal, dan overschrijf je, anders niet. Enige waar je rekening mee moet houden is dat meerdere threads tegelijkertijd zullen proberen te lezen/schrijven, dus zorg dat je je file lockt.

Uhm, het ligt niet aan jou dat er bijzonder moeilijk wordt gedaan, maar ik kan me ook met geen mogelijkheid voorstellen dat deze oplossing een fatsoenlijk resultaat produceert, of je omschrijft het compleet fout. Zoals ik het nu lees gooi je de helft van de data weg.

[Olaf van der Spek]

curry684 schreef op 25 oktober 2002 @ 09:25:
Ik zie dus echt totaal het nut niet hier van multithreading. De effectiefste manier om dit te doen is duidelijk om de 5 files eerst afzonderlijk te sorteren en daarna met behulp van een array van pointers er doorheen te waggelen. Oftewel de uiteindelijke merge-actie is al singlethreaded. En of je nu 5 threads spawnt die 5 files sorteren, of 1 thread die achter mekaar 5 files sorteert maakt totaal geen kont uit: je verbruikt evenveel processing time.

Singlethreaded dus gewoon imho.

Als je meerdere CPUs hebt is multi-threading wel handig voor het onafhankelijk sorteren van de vijf bestanden. Daarna heb je niks meer aan multi-threading.

[bloody]

waarom niet op de linux manier?
cat file1 > file6
cat file2 >> file6
cat file3 >> file6
cat file4 >> file6
cat file5 >> file6

cat file6 | sort | uniq > file7

dus file7 bevat de juiste info

[Soultaker]

bloody schreef op 25 oktober 2002 @ 11:46:
waarom niet op de linux manier?
cat file1 > file6
cat file2 >> file6
cat file3 >> file6
cat file4 >> file6
cat file5 >> file6

cat file6 | sort | uniq > file7

dus file7 bevat de juiste info

Gadverdamme. Zeg dan:

code:

sort a b c d e > resultaat

Dan is het WEL efficient (je hele uniq is sowieso overbodig).

[bloody]

wat jij wil

[Soultaker]

OlafvdSpek schreef op 25 oktober 2002 @ 11:43:
Als je meerdere CPUs hebt is multi-threading wel handig voor het onafhankelijk sorteren van de vijf bestanden. Daarna heb je niks meer aan multi-threading.

Zelfs voor meerdere CPU's heb je er niets aan. Het vergelijken van vijf getallen, 1 schrijven en weer 1 lezen, gaat net zo efficient in 1 thread, omdat je dan geen synchronisatiemechanismen meer nodig hebt.

[Olaf van der Spek]

Die vijf bestanden kunnen toch onafhankelijk gesorteerd worden? Dan heb je geen synchronisatie nodig.

[curry684]

OlafvdSpek schreef op 25 oktober 2002 @ 11:43:
Als je meerdere CPUs hebt is multi-threading wel handig voor het onafhankelijk sorteren van de vijf bestanden. Daarna heb je niks meer aan multi-threading.

Admitted.

* curry684 heeft nog wel eens de neiging voor 99.99% van de markt te werken

[Verwijderd]

Ja ik weet ook wel een efficientere oplossing gewoon single threaded, maar die opdracht is denk ik om multithreading te leren of dat bij die opdracht efficient is of niet.

[Olaf van der Spek]

Misschien dat je dan een betere opdracht kunt bedenken waar het wel efficient is threads te gebruiken?

[Verwijderd]

Dan moet je bij de schrijvers van dat boekje zijn. Het gaat er gewoon om dat diegene die die opdrachten maakt leert te werken met threads of dat efficienter kan single threaded of niet dat is eigenlijk niet van belang. Maar ik denk dat ik het nu wel begrijp hoe dat werkt nu kan ik de opdracht maker het proberen uit te leggen.

p.s. nogmaals bedankt voor jullie hulp.

[curry684]

Als ie moet leren hoe met threads en synchronizatie te werken laat 'm gewoon in een DOS-box de dining philosophers uitbeelden...

[Olaf van der Spek]

Verwijderd schreef op 25 oktober 2002 @ 12:46:
Dan moet je bij de schrijvers van dat boekje zijn. Het gaat er gewoon om dat diegene die die opdrachten maakt leert te werken met threads of dat efficienter kan single threaded of niet dat is eigenlijk niet van belang. Maar ik denk dat ik het nu wel begrijp hoe dat werkt nu kan ik de opdracht maker het proberen uit te leggen.

p.s. nogmaals bedankt voor jullie hulp.

Misschien dat jij dat boekje ook eens kunt doorlezen en de opgaven die erin staan kunt maken?