[c++] functie efficientie -- references of niet

[anoniem]

Hallo allen, Ik ben met een programma bezig dat niet super complex is, maar het vergt nogal een hoop berekeningen. En het duurt dus ook verschrikkelijk lang.. Graag zou ik het geheel een stuk efficienter laten werken. Bijvoorbeeld de volgende functie: double findTime(double x, double y) { double t1 = round((double)acos(x),6); double t3 = round((double)asin(y),6); double t4 = round((double)PI-asin(abs(y)),6); if(t1==t3) return t1; else if(t1==t4) return t1; else if(-t1==t3) return -t1; else if(-t1==t4) return -t1; } Vrij simpele functie, maar hij wordt door het programma ruim 134 miljoen (!!) keer aangeroepen (helaas kan dat niet anders). Zou het programma als geheel sneller lopen als ik de 3 t-waardes maar 1 keer in het geheugen reserveer buiten de functie en vervolgens de pointers aan de functie meegeef als argumenten? Dus iets als: double *t1=0; double *t3=0; double *t4=0; do(onwijs vaak) t = findTime(x,y,t1,t3,t4) double findTime(double x, double y, double *t1, double *t3, double *t4) { t1 = round((double)acos(x),6); t3 = round((double)asin(y),6); t4 = round((double)PI-asin(abs(y)),6); if((double)t1==(double)t3) // ik moet recasten naar double denk ik? return t1; else if((double)t1==(double)t4) return t1; else if((double)-t1==(double)t3) return -t1; else if((double)-t1==(double)t4) return -t1; } Zou dit uiteindelijk sneller zijn? Thanks. Jasper

[anoniem]

[quote:d3c89cad14="jasperlevink"]Hallo allen, double *t1=0; double *t3=0; double *t4=0; else if((double)t1==(double)t4) return t1; else if((double)-t1==(double)t3) return -t1; else if((double)-t1==(double)t4) return -t1; [/quote:d3c89cad14]Pointers zijn iha niet sneller, verder wil je in de "if" de echte waarde van tx weten en niet niet het adres. Dus het is *t1, *t4 enz. Verder moet een pointer naar iets wijzen dat geldig is. Je gaat nu op een gevaarlijke manier (lees: onjuiste wijze) C gebruiken. Zeker als de code toevallig mocht werken. Wil je tijdwinst behalen in het eerste concept, dan moet je misschien kijken af de nauwkeurigheid lager zou mogen worden. De cos en sin berekeningen zullen de meeste CPU tijd nemen, tijdwinst verwacht ik niet. Misschien heeft het nog zin om een eigen algroritme te implementeren of een math libarary te kiezen die efficiënter werkt. Welke compiler/library gebruik je nu?

[anoniem]

Ok. Bedankt voor je antwoord! Ik gebruik XCode 2, volgens mij zit daar gcc in.. Voor de cos/sin gebruik ik cmath. Ik rond nu de resultaten af op 6 cijfers (ze zijn namelijk anders nooit exact gelijk). De t wordt weer gebruikt voor het berekenen van een nieuwe vector (in de richting van t) met een maximale lengte van 1000. Waarin naar verschillen van ordegrootte 1 wordt gekeken. Dus volgens mij moeten de cos/sin op ca 1/1000e correct werken. Klopt dat? Voor de zekerheid afronden op 1/10^6 lijkt me niet heel slecht. Maar hoe zorg ik ervoor dat mijn cos/sin ook ongeveer rond die zekerheid zitten? Bedankt. Jasper

[anoniem]

Ah, Apple gebruiker. Ik ken de genoemde compiler niet, ik gebruik zelf Visual Studio. Snelheid is te winnen door zo min mogelijk data te verplaatsen en zo efficient mogelijk gebruik te maken van de processor mogelijkheden. Je zou float kunnen gebruiken in plaats van double. Wat betreft de nauwkeurigheid, of 1/1000 genoeg is, daar kan ik niet veel over zeggen omdat de fout door kan werken in het eindresultaat. Op basis van de huidige resultaten kun je vemoedelijk al wel conclusies trekken. Gezien de nauwkeurigheid van float/double denk ik dat er geen tijdwinst is te behalen door hoger af te ronden. Je kan eventueel ook het cos/sin resultaat afbreken, dat is een fractie sneller dan afronden.

[anoniem]

Zou je iets meer kunnen vertellen over je bedoeling met bovenstaande code? Wat wil je bereiken en waar wil je het voor gebruiken? Waarom wordt het b.v. 134 miljoen maal aangeroepen? Het lijkt me dat je door een slimmer algoritme een veel hogere efficiëntie kunt halen, maar nu zijn er te weinig gegevens voorhanden om daar iets over te zeggen.

[anoniem]

Bedankt voor de reacties. Wat de functie moet doen is het volgende: De input is een vector (x,y) met lengte 1. Ik moet voor deze vector de positie op de eenheidscirkel vinden. (de theta in poolcoordinaten) Het geheel gaat om het volgende: Ik wil graag voor een punt weten of hij zich binnen of buiten een buis bevind die in een ellips rondloopt. Daarvoor kijk ik in het vlak van de ellips en kijk welke t er bij het punt zou horen als hij zich in de buis bevind. Vervolgens kijk ik of voor die t de buis ook daadwerkelijk daar loopt. Is dit duidelijker of nog steeds te sumier? Ik ben een beetje bang om een technisch verhaal te verzanden... Bedankt. Jasper

[anoniem]

Dit is al een stuk duidelijker, maar ik begrijp nog steeds niet waarom je dit 134 miljoen maal moet aanroepen? Helaas ben ik verder niet zo bekend met poolcoördinaten en heb ik ook niet echt tijd om me hier in te verdiepen, maar het lijkt me dat e.e.a. wel efficiënter kan werken als je je algoritme aanpast. Dus daarom vraag ik: Waarom roep je de methode 134 maal afzonderlijk aan? Daar ligt namelijk je grootste winst mogelijkheid.

[anoniem]

Ik heb nogal een groot grid 512^3.. En voor ieder punt ga ik controleren of het zich in een tube bevind.. (de tube heeft vrijheidsgraden radius, orientatie en curvature (gerepresenteerd als gedeelte van een ellips)) Ik weet dat het nogal omslachtig is, maar ik kan niks beters verzinnen... Bedankt. Jasper

[anoniem]

Oké, dat is al een stuk duidelijker .... Wat je eigenlijk moet doen is het volgende. Maak van je grid een Array of Linked list o.i.d. Geef deze eenmaal aan je methode mee en bedenk een recursief algoritme o.i.d. die het vuile werk opknapt met tail-recursie. Hierbij maak je gebruik van pointers zodat je stack niet te groot wordt. Helaas ben ik niet bekend met jouw materie, dus kan ik je geen concreet algoritme geven, maar ik ben er van overtuigd dat je op deze wijze een efficiënter algoritme uit kunt werken.

[anoniem]

Klinkt moeilijk, maar erg interessant!! Het duurde even voordat ik het wikipedia artikel erover begreep.. Ik ben niet echt opgeleid als programmeur, maar moet het toch vaak gebruiken (zit in de beeldverwerking). Zou je (of jullie) een boek aan kunnen bevelen met programmeer technieken? De talen zijn niet echt een probleem. Maar het zijn dit soort technieken waar mijn kennis een beetje te kort schiet.. Ik ga het proberen toe te passen! Ben nu alleen met iets anders bezig, als ik er weer mee aan de slag ga en voor problemen kom laat ik het zeker weten :) Bedankt! Jasper

[anoniem]

Het is lastig om een efficiënt algoritme te bedenken, vooral de wiskunde die daar bij komt kijken is minder leuk :lol:. Dat je iet met beeldverwerking deed vermoede ik al, gezien de vectoren en de apple :wink:. Helaas heb ik heel erg weinig tijd de komende 1,5 maand en dus kan ik me niet echt in je probleem verdiepen. Ik kan je helaas ook geen book of kant en klare oplossing aanbevelen, daar zou ik iets meer tijd voor uit moeten trekken en dat lukt voorlopig even niet. Toch ben ik er van overtuigd dat dit proces een stuk efficiënter moet kunnen door b.v. bepaalde al uitgerekende stukjes her te gebruiken en niet opnieuw uit te rekenen etc. Een goed algoritme bedenken die zoiets kan is echter één van de lastigste onderwerpen op programmeer gebied :wink: Veel succes met experimenteren en laat ons weten hoe het je vergaat!

[anoniem]

Je hebt toch echt mijn interesse geprikkeld. Intussen heb ik een [url=http://forum.computertotaal.nl/phpBB2/viewtopic.php?t=187610]nieuw topic[/url] geopend op zoek naar een geschikt boek :) Ik ben nog niet helemaal zeker of ik begrijp wat je bedoelde. Je bedoelde niet alleen zoiets toch? [code:1:a2aab8687e] double findTime(double x, double y) { return findTime_aux(round((double)acos(x),6), round((double)asin(y),6),round((double)(PI-asin(abs(y))),6)) } double findTime(double t1, double t3, double t4) { return t1 == t4 || t1 == t3 ? t1 : -t1 ; } [/code:1:a2aab8687e] Maar meer zoiets: (ik ben niet helemaal zeker van de pointer bewerking) [code:1:a2aab8687e] findTs( int x, int y, pointerToBool) { *pointerToBool = inTube(round((double)acos(x),6), round((double)asin(y),6),round((double)(PI-asin(abs(y))),6)); // hier probeer ik de waarde van het geheugenelementje aan te passen waar pointerToBool naar verwijst x<=maxx ? x++ : ( y <= ymax ? y++ : return ); // hier probeer ik een nested if te schrijven :) return findTs(x, y, ++pointerToBool) // Doe hetzelfde voor volgende x,y } bool inTube(double t1, double t3, double t4) { // is t in tube? } [/code:1:a2aab8687e] Ik heb dit snel even neergekrabbeld, dus syntax zal ongetwijfeld niet helemaal kloppen. Het gaat meer om het idee. Bedankt voor je hulp, Jasper

[anoniem]

Niet helemaal al, met de referentie in de tail recursie bedoelde ik de mogelijkheid om al eerder uitgerekende waarden her te gebruiken en door te geven. Je moet een algoritme bedenken die efficiënter met een oplossing komt, je zult dus intelligentie toe moeten voegen i.p.v. elke keer dom controleren of het kan. Ik kan je niet vertellen hoeveel winst je kunt boeken, want dan zou ik me er in moeten verdiepen en daar heb ik geen tijd voor, daarnaast is het best lastig. Tip: Er moet vast een afhankelijk in zitten toch? Als ik het goed begreep had je een 3-dimensionele representatie. Je hebt vectoren waarvan in één richting één vertice altijd gelijk is ... die hoef je niet elke keer opnieuw te berekenen. Als je hier slim over nadenkt en recursie met een stack meganisme combineert, dan moet je al redelijk wat winst kunnen pakken denk ik, maar denk er zelf ook maar eens goed over na. Laat je brein het werk doen, denken denken denken en als het klopt dan uitproberen met code. Misschien kun je wel een ander concept bedenken, zoals een 2e matric met daarin je tube, om daar vervolgens iets mee te doen ... ik zeg maar wat hoor ;-)

[anoniem]

Aha! Bedankt!!! Super dat je hier de tijd voor neemt. Nu denk ik dat ik het begrijp! Ik ga het een en ander proberen :) Bedankt!

[anoniem]

In die functie zit voornamelijk de meeste tijd in de [i:56f50f475c]acos[/i:56f50f475c] en [i:56f50f475c]asin[/i:56f50f475c] functie. Dat zou je op een of andere manier moeten versnellen, misschien door een efficientere versie die wellicht ergens op internet te vinden moet zijn. Ik denk wel dat je hierbij een precisie/snelheid afweging moet maken. Kijk ook of het mogelijk is of het mogelijk is of je kunt voorkomen dat de asin of acos van een x niet 2 keer (of vaker) uitgerekend worden. [quote:56f50f475c="Pinky & The Brain"]Niet helemaal al, met de referentie in de tail recursie bedoelde ik de mogelijkheid om al eerder uitgerekende waarden her te gebruiken en door te geven. Je moet een algoritme bedenken die efficiënter met een oplossing komt, je zult dus intelligentie toe moeten voegen i.p.v. elke keer dom controleren of het kan. Ik kan je niet vertellen hoeveel winst je kunt boeken, want dan zou ik me er in moeten verdiepen en daar heb ik geen tijd voor, daarnaast is het best lastig. [...][/quote:56f50f475c] Met staartrecursie heeft niet veel zin in een normale programmeertaal (lees: imperatieve taal). Het is een techniek die met name in functionele talen wordt gebruikt om het geheugengebruik te optimaliseren. Een staartrecursieve functie wordt in een imperatieve zoals C of Java taal normaliter als een gewone loop berekend. De accumulatie parameter is dan gewoon een parameter waarin je je resultaat construeert. Waar je waarschijnlijk op doelt is [url=http://en.wikipedia.org/wiki/Dynamic_programming]dynamisch programmeren[/url].

[anoniem]

[quote:18a31c3114="SHARK"] Met staartrecursie heeft niet veel zin in een normale programmeertaal (lees: imperatieve taal). Het is een techniek die met name in functionele talen wordt gebruikt om het geheugengebruik te optimaliseren. Een staartrecursieve functie wordt in een imperatieve zoals C of Java taal normaliter als een gewone loop berekend.[/quote:18a31c3114] Klopt, de staartrecursie haalt niet veel uit in dit geval, aangezien geheugenbereik hier niet hier geen probleem vormt. Toch zou het in een kleinere stack (mits het algoritme goed is) moeten resulteren dacht ik. Of optimaliseert een compiler dergelijke constructies weg? [quote:18a31c3114] De accumulatie parameter is dan gewoon een parameter waarin je je resultaat construeert. Waar je waarschijnlijk op doelt is [url=http://en.wikipedia.org/wiki/Dynamic_programming]dynamisch programmeren[/url].[/quote:18a31c3114] Klopt, maar volgens mij kan hij dit probleem dusdanig omvormen. Voor mijn gevoel is de huidige benadering erg lomp namelijk. :lol:

[anoniem]

Ik vind het leuk om jullie discussie te volgen, en ben blij dat hij er is. Helaas kan ik niet meedoen door mijn gebrekkige kennis. Ik zal wat meer informatie geven. Ik moet een aantal tubes plotten in een 3D grid of booleans. Waar een 1 betekent dat de betreffende pixel zich in een tube bevind en een 0 niet. De tubes hebben vrijheidsgraden: - radius (depending on position in tube) - orientation - curvature (expressed as a part of an ellips (y= a Sin(t) & x = b Cos (t) )) - translation Mijn aanpak is als volgt voor de gebogen tubes: [list:b199efe92e] Voor ieder punt in het grid controleer ik voor iedere tube of deze zich in de tube bevind. Met de orientatie van de tube roteer en transleer (matrixvermenigvuldiging) ik het volume zo, dat de tube zich in het xy vlak, gecentreerd rond de z-as zou bevinden. Indien de geroteerde z coordinaat redelijkerwijs mogelijk in de tube valt, ga ik met de x en y coordinaat aan de slag. Met de hierboven geplaatste functie controleer ik bij welke t het coordinaat zou horen op de eenheidscirkel (gecorrigeerd uiteraard voor de vorm van de ellips). Voor deze t bereken ik de locatie van de centerline van de gebogen tube. Als de afstand tot de centerline van de tube kleiner is dan de radius, bevind het punt zich in de tube.[/list:u:b199efe92e] Hoewel het software is die maar een paar keer gebruikt zal worden, ben ik zeker geintresseerd in hoe ik dit beter op kan lossen. Dat dit lomp en omslachtig is ben ik overtuigd :) Bedankt Jasper

[anoniem]

Hmmm... ik zou niet precies weten hoe je zoiets efficienter maakt. Als je er echt wat tijd in wilt steken dan zou ik je willen verwijzen naar [url=http://tog.acm.org/GraphicsGems/gems.html]Graphics Gems[/url] (zie ook [url=http://books.google.nl/books?q=graphics+gems&btnG=Boeken+zoeken]hier[/url]), een verzameling artikels over een breed scala aan beeldverwerkingsproblemen. Het is weliswaar een beetje gedateerd (1990-1995), maar er zitten veel interessante artikels in die wellicht ook in de richting van jou probleem komen. (ik heb gehoord dat er hier en daar op het internet nog wel een pdf versie te downloaden is :wink: )

[anoniem]

Ah.. Ik dacht dat dat boek ging over programmeren op de GPU. Maar dat is helemaal niet het geval begrijp ik. Moet ik toch maar eens gaan bekijken! Bedankt voor de tip! Jasper

[anoniem]

Wat je kunt doen is een truuk uit de spellen-wereld toepassen : behandel eerst alles als blokken & lijnstukken Als je namelijk kunt uitsluiten dat een lijn een bepaalt vlak niet eens kan kruisen (en dat is een relatief 'simpele' vergelijking zelfs in 3D) dan heb je al heel veel tijd gewonnen.