C# - Langdurig algoritme

[Verwijderd]

Hey iemand_die_dit_leest_en_mij_wil_helpen,

Ik ben bezig aan een programma dat zich bezighoudt met Sudoku puzzels.

Nu is het mij gelukt om dit te maken maar ik zit met enkele problemen.

Als ik een bepaalde chaos sudoku opstel zonder ingevulde getallen, dat duurt dit nagenoeg
eindeloos (ik ben gestopt na 2uur). Hoe kan ik ervoor zorgen dat ik tijdens de berekeningen
op een stop knop kan duwen, zonder " await Task.Delay(1) " te gebruiken? Want dit heeft namelijk
een heel grote invloed op de duurtijd van een oplossing.

Alle links of voorstellen zijn welkom!

Alvast bedankt,

Sam De Roeck

[Verwijderd]

het algoritme in een aparte thread laten draaien en deze killen als je wilt stoppen?

[wjvds]

De standaardprocedure voor dit soort problemen is om je algoritme in een aparte thread te laten draaien en daarin regelmatig te checken of er een boolean StoppedPressed true is die je set met een button. Als dat waar is, stop je je algoritme.

Threads simpelweg killen zoals robert90 aanraadt is niet netjes, want wat als je nog cleanup wil toevoegen later?

[Avalaxy]

Het lijkt alsof je dingen op de UI thread doet waardoor die bevriest en dus je stopknop niet werkt. Of was dat je probleem niet? Je vermeldt namelijk niet of je de stopknop al geprobeerd had.

Wat ik wel raar vind is dat het 2 uur duurt, zo ingewikkeld is sudoku niet toch? Klinkt alsof je algoritme niet klopt (danwel gruwelijk inefficiënt is) of dat je ergens een deadlock hebt. Doe je toevallig iets met async?

[Verwijderd]

Aparte threads... Dat is iets nieuw voor mij, daar moet ik wat over opzoeken.

@Avalaxy,

Ik werk momenteel met async in de methode die de puzzel oplost. Als ik geen Task.Delay gebruik lost hij de puzzel steeds snel op, namelijk bijna nooit boven de 0,5sec. Dit geldt voor bijna alle puzzels. Enkel, in de vorige editie van Humo stond een chaos sudoku. Deze gaf ik in maar dan zonder getallen en dan duurt het echt zeer lang. Bij de editie van deze week doet ie het wel .

Ik heb momenteel een stopknop maar als ik geen Delay gebruik, kan ik er niet op klikken tot het programma de oplossing gevonden heeft. Als ik het wel gebruik, kan ik de knop wel bedienen en werkt hij ook maar dan duurt het oplossen vaak langer (soms enkele seconden, anders dan weer een minuut).

Ik heb enkel C# ervaring door te proberen en van het 1/4 jaar aan de hogeschool. Misschien is dit topic misplaats bij IT Pro maar ik wil het wel graag oplossen.

[Onbekend]

Threads gebruiken is inderdaad het correcte antwoord.

Maar er zijn meerdere (slechtere) wegen naar Rome die soms wat sneller te programmeren zijn. Je kunt bijvoorbeeld ook periodiek controleren of de mouse pointer in een bepaalde rectangle zit waarna het programma wordt gestopt. (Let er dan wel op dat het tekenen van het form zelf niet regelmatig gebeurd zodat je niet weet of jouw mouse pointer in dat rechthoek staat.

[Xiphalon]

wjvds schreef op woensdag 20 januari 2016 @ 21:34:
De standaardprocedure voor dit soort problemen is om je algoritme in een aparte thread te laten draaien en daarin regelmatig te checken of er een boolean StoppedPressed true is die je set met een button. Als dat waar is, stop je je algoritme.

Threads simpelweg killen zoals robert90 aanraadt is niet netjes, want wat als je nog cleanup wil toevoegen later?

Dit.

En je kan in .net geen threads killen, dus dat was sowieso geen optie.

De mooiste manier is dus een thread (vrij grof; netter is een Task, of, wat ouder, een BackgroundWorker) aanmaken, en die via een CancellationToken laten weten dat deze moet stoppen. Je moet dus in de thread zelf regelmatig kijken of je moet stoppen.

Op msdn moet je met de termen met een Hoofdletter genoeg kunnen vinden

[Verwijderd]

Oke, Threading dus. Ik ga mezelf bijscholen. Bedankt voor de reacties!

[Bartjuh]

Wikipedia: Model-view-controller-model ?

[Caelorum]

Bartjuh schreef op woensdag 20 januari 2016 @ 22:11:
Wikipedia: Model-view-controller-model ?

Want als de model, de view en de controller op 1 en dezelfde thread zit lost dit het probleem op? Nee, dus.. Aparte threads, of de berekening in stukken opsplitsen en tasks gebruiken (die onderwater wel weer aparte threads gebruiken).

(Overigens zijn threads zeker wel te killen vanuit .net met een uitstap via p/invoke, maar dat wil je dus echt echt echt niet doen!)

[Bartjuh]

Caelorum schreef op woensdag 20 januari 2016 @ 23:14:
[...]
Want als de model, de view en de controller op 1 en dezelfde thread zit lost dit het probleem op? Nee, dus..

Euh, juist niet?

Gaat meer om het concept van de opbouw van een ui gebaseerd programma in afzonderlijke units met eigen functie en bepaalde onderlinge relaties, daar volgt dan op een natuurlijke manier threading uit.

[Caelorum]

Bartjuh schreef op woensdag 20 januari 2016 @ 23:27:
[...]

Euh, juist niet?

Gaat meer om het concept van de opbouw van een ui gebaseerd programma in afzonderlijke units met eigen functie en bepaalde onderlinge relaties, daar volgt dan op een natuurlijke manier threading uit.

Maar threads staan complete los van MVC. MVC is prima zonder threads te implementeren. Het hier noemen is dus irrelevant voor het vraagstuk.

[ZaZ]

Als je met async in de weer gaat zou ik me ook aan de regels van async houden.
Dus het stuk wat je task spawned bepaalt (niet de task zelf) dat ie 'm op de thread pool moet schuiven.
In je task poll je in je iteraties de CancellationToken die je ergens hebt meegegeven zodat je nog cleanup kan doen.

Wel effe uitkijken dat je dan niet meer op de UI thread zit en niet vanuit daar (of anders zonder te delegeren) je controls gaat aanspreken.

[pedorus]

Avalaxy schreef op woensdag 20 januari 2016 @ 21:38:
Wat ik wel raar vind is dat het 2 uur duurt, zo ingewikkeld is sudoku niet toch? Klinkt alsof je algoritme niet klopt (danwel gruwelijk inefficiënt is) of dat je ergens een deadlock hebt. Doe je toevallig iets met async?

Het oplossen van een ingewikkelde Sudoku is een kwestie van milliseconden inderdaad..

Maar in zijn algemeenheid is het natuurlijk inderdaad een kwestie van taken in een andere thread doen, en als het klaar is een berichtje sturen naar de ui thread en deze updaten, en bij een cancel een vlaggetje doorgeven aan de rekentaak. Nog voordat het Task framework er was bestond er al iets voor: de MSDN: BackgroundWorker Class (System.ComponentModel)

[Woy]

pedorus schreef op donderdag 21 januari 2016 @ 08:54:
[...]

Het oplossen van een ingewikkelde Sudoku is een kwestie van milliseconden inderdaad..

Maar in zijn algemeenheid is het natuurlijk inderdaad een kwestie van taken in een andere thread doen, en als het klaar is een berichtje sturen naar de ui thread en deze updaten, en bij een cancel een vlaggetje doorgeven aan de rekentaak. Nog voordat het Task framework er was bestond er al iets voor: de MSDN: BackgroundWorker Class (System.ComponentModel)

Op zich een goede oplossing, maar de TS is al bezig met met async/await. Door gebruik te maken van de Task Library en de gemaakte task te awaiten is het eenvoudiger voor de TS om het op te lossen.

C#:

var result = await Task.Run(()=>DoLongRunningCalc());

Dan moet je natuurlijk nog wel Synchronisatie toevoegen als je de Task wil cancellen

[ Voor 4% gewijzigd door Woy op 21-01-2016 12:19 ]

[AlphaRomeo]

Xiphalon schreef op woensdag 20 januari 2016 @ 21:56:
[...]
En je kan in .net geen threads killen, dus dat was sowieso geen optie.

Thread.Abort?

[Igoranze]

Threads inderdaad. Als je een Thread wilt stoppen/killen kun je dat ook doen d.m.v. het Observer/Observable Pattern.

[robertpNL]

AlphaRomeo schreef op donderdag 21 januari 2016 @ 12:54:
[...]

Thread.Abort?

Thread.Abort is geen thread killer. Het veroorzaakt een AbortException binnen de thread dat het moet stoppen.

Met een P/Invoke call TerminateThread zou je een thread daadwerkelijk kunnen killen.

[ Voor 6% gewijzigd door robertpNL op 21-01-2016 13:21 ]

[Xiphalon]

Dat werkt niet, er zit geen relatie tussen managed en unamaged threads. Zie bv: hier.

Samenvatting: de clrhost bepaald welke unmanaged thread de managed thread code uitvoert. Dat kan per slice een andere thread zijn, of meerdere managed threads per unmanaged thread. Doe je dus een p/invoke om een thread te killen aan de hand van het ThreadId wat je uit de managed thread haalt, heb je kans dat je de verkeerde sloopt, of zelfs de hele clr omver sloopt.

[Gomez12]

Xiphalon schreef op donderdag 21 januari 2016 @ 13:26:
Dat werkt niet, er zit geen relatie tussen managed en unamaged threads. Zie bv: hier.

Samenvatting: de clrhost bepaald welke unmanaged thread de managed thread code uitvoert. Dat kan per slice een andere thread zijn, of meerdere managed threads per unmanaged thread. Doe je dus een p/invoke om een thread te killen aan de hand van het ThreadId wat je uit de managed thread haalt, heb je kans dat je de verkeerde sloopt, of zelfs de hele clr omver sloopt.

Dat werkt wel, alleen niet op de manier zoals jij het beschrijft...

Maar het belangrijkste advies blijft gewoon het advies van Caelorum.

Caelorum schreef op woensdag 20 januari 2016 @ 23:14:
[...]
(Overigens zijn threads zeker wel te killen vanuit .net met een uitstap via p/invoke, maar dat wil je dus echt echt echt niet doen!)

Om het nog maar eens te herhalen : maar dat wil je dus echt echt echt niet doen!

Verder discussieren over p/invoke is dan ook zinloos, ja het kan ermee. Maar hiervoor is het echt gewoon zo ongeveer de foutste oplossing (zo ongeveer, want je kan bijv ook gewoon je pc softwarematig resetten om je thread af te knallen, dat is nog net iets fouter)

[Xiphalon]

Gomez12 schreef op donderdag 21 januari 2016 @ 13:56:
[...]

Dat werkt wel, alleen niet op de manier zoals jij het beschrijft...

[...]
Verder discussieren over p/invoke is dan ook zinloos, ja het kan ermee. Maar hiervoor is het echt gewoon zo ongeveer de foutste oplossing (zo ongeveer, want je kan bijv ook gewoon je pc softwarematig resetten om je thread af te knallen, dat is nog net iets fouter)

Oh? leg eens uit. Hoe zou het dan werken?

[robertpNL]

Geef alle threads binnen het clr process: Process.GetCurrentProcess().Threads
Opvragen bijbehorende pointer met OpenThread. En die dan als input meegeven aan TerminateThread.

Mee eens dat het verder onverstandig is.

[Xiphalon]

Tja dat doet er nog steeds niet aan af dat een unmaged thread meerdere managed threads kan zijn. Of dat in de tijd dat je uitzoekt welke unmanaged thread je moet hebben de managed thread wordt opgepakt door een andere unmanaged thread. Er is gewoon geen relatie tussen die twee typen threads, dus het kan gewoon niet.

Om nog maar te zwijgen van de managed boekhouding die je niet opruimt.

[elleP]

Ik denk overigens dat de sudoku waar je algoritme op vast loopt geen unieke oplossing heeft. Het maakt niet uit hoeveel tijd je er in stopt, er is geen 'pad' naar DE oplossing, dus je algoritme blijft rondjes draaien. Dit moet je kunnen detecteren en dan kan je vanuit je algoritme al stoppen.

Ik gok nu dat je een paar verschillende stappen doorloopt om te kijken of je nieuwe getallen in kan vullen. Als alle stappen geen nieuwe getallen opleveren, dan heeft het ook geen zin om ze opnieuw te doorlopen en kan je stoppen met de mededeling "onoplosbaar"

[Caelorum]

Xiphalon schreef op donderdag 21 januari 2016 @ 15:50:
Tja dat doet er nog steeds niet aan af dat een unmaged thread meerdere managed threads kan zijn. Of dat in de tijd dat je uitzoekt welke unmanaged thread je moet hebben de managed thread wordt opgepakt door een andere unmanaged thread. Er is gewoon geen relatie tussen die twee typen threads, dus het kan gewoon niet. [...]

Het kan zeker wel. Conceptueel is er geen relatie, maar in de praktijk zijn managed threads 1-op-1 te mappen op unmanaged threads in AFAIK alle bekende implementaties. En zelfs al zou dat er niet zijn, dan kan je met MSDN: Thread.BeginThreadAffinity Method (System.Threading) wel forceren dat de thread op 1 thread blijft hangen. (Ook SQL server 2005 en 2008 hebben een 1-op-1 mapping ongeacht wat die pagina claimt). Met wat andere hacky/foutgevoelige code kan je dan bepalen of er nog meer managed threads zijn gemapped op die unmanaged thread en zo niet de thread afknallen.
Maar we kunnen dit wel verder discussieren in een apart topic. Bovenstaande is ver voorbij wat TS nu zou moeten weten.


@elleP, Het is een beetje gokken wat hij/zij precies doet. Als het een simpele bruteforce is (met iets meer logica dan echt 11111, etc) dan zijn de meeste sudoku's nog steeds milliseconde werk en loop je ook weinig risico in een infinite loop te kopen.
Ik ben iig wel benieuwd naar zijn/haar uiteindelijke oplossing, wellicht dat we daar ook nog wel wat pointers kunnen geven.

[thof]

Goed dat je al met async-await werkt, dat scheelt al het een en ander.

Wat mij betreft:
- Async-await blijven gebruiken. Mocht je erg veel tasks/thread tegelijk gaan gebruiken switch dan naar de TaskParallelLibrary
- Gebruik cancellation tokens om lopende tasks te cancellen
- Je algoritme optimaliseren ;-)

Meet info:
http://blogs.msdn.com/b/d...lation-in-async-apis.aspx
http://blog.stephencleary...ions-of-asynchronous.html
http://blogs.msdn.com/b/p...4/12/async-await-faq.aspx

[Verwijderd]

Of een oplossing uniek is, lijkt me niet zo belangrijk wanneer je de puzzel probeert op te lossen. Wanneer je een puzzel wilt genereren, dan wel (tenzij je dat zelf niet belangrijk vindt). Maar als de puzzel niet opgelost kan worden, dan wordt er wel een melding gegeven. Het is trouwens bij een leeg (chaos) bord, dus meerdere oplossingen zijn er dan meestal.

Ik heb inderdaad het algoritme net verbeterd! Weliswaar op een macbook terwijl dat programma niet zo gemakkelijk werkt als VisualStudio.

BackgroundWorker lijkt mij de beste en eenvoudigste oplossing tot hier toe. Want na enig opzoekwerk ben ik tot het besluit gekomen dat ik nooit het niveau zal halen van een developer.

Met BackgroundWorker is het me gelukt om een taak in een richTextbox te laten starten, pauzeren, hervatten en resetten. Met Threading lukte me het ... euhm ... halvelings.

Er zijn wel meerdere manieren precies om dit probleem op te lossen. Als ik ooit een methode gecompileerd krijg, mag je op eigen risico mijn programma gebruiken

[Caelorum]

Verwijderd schreef op donderdag 21 januari 2016 @ 21:28:
[...]
BackgroundWorker lijkt mij de beste en eenvoudigste oplossing tot hier toe. Want na enig opzoekwerk ben ik tot het besluit gekomen dat ik nooit het niveau zal halen van een developer.[...]

Iedereen hier is ergens begonnen en ik durf te wedden dat de meeste in het begin problemen hadden met basale dingen als een for-loop en arrays. Geef de hoop dus nog niet op ^^
Daarnaast is het belangrijkste van software ontwikkeling dat de computer het eindresultaat genereerd dat je wil (liefst terwijl je nog leeft). Al het andere is bijzaak en leer je vanzelf als je het wil.

[pedorus]

Ook wel: Niemand is geboren als developer.

Ik ben het eigenlijk wel eens met dat BackgroundWorker wat outdated is. Bij de andere methode ontbrak denk ik een goed voorbeeld, zoals http://stackoverflow.com/a/10134604

[elleP]

Hehehe, ik had eerlijk gezegd niet eens gedacht aan het brute-forcen als oplosalgorithme, omdat het zo on-elegant is . Maar het is wel effectief!

[ Voor 10% gewijzigd door elleP op 26-01-2016 14:00 ]

[ocwil]

Threading inderdaad .
en mocht je nog wat meer willen lezen kunnen je ook de term "post-back" even opzoeken, kan soms ook handig zijn.

[Verwijderd]

Het leek me op het eerste zicht te ingewikkeld

Het aantal code dat je nodig had werd gehalveerd door backgroundWorker en die heeft uiteindelijk de klus geklaard!

Misschien dat ik later nog wel eens in contact kom met threading, wie weet... Bedankt voor het op weg helpen en ik zal zeker nog veel moeten lezen.

Waar zou een mens zijn zonder: google, msdn, stackoverflow en tweakers ?

[Corniel]

Voor bijna alle Sudoku's zou je algoritme zoals geroepen binnen enkele milliseconden klaar moeten zijn. Ver is een backgroundWorker hier een prima oplossing, maar nogmaals, als je de bug fixt in je sudoku-solver zou dat het probleem niet meer mogen zijn.

Nog een tip: ontwikkel je solver los van een eventuele (G)UI, en schrijf unit tests om te kijken of e.a. een beetje klopt.