Archief - MATLAB optimalisatie

Beste,

Ik ben bezig met een MATLAB implementatie van variant van het Dijkstra algoritm of korte afstand algoritme. Dit algoritme werkt goed op onze test data, maar duurt eeuwen op echte data.

Bij deze moet ik de code optimaliseren, maar mijn MATLAB kennis is daarvoor te beperkt.

Het idee in het kort:
- van x vectoren in y dimensies moet ik alle afstanden kennen tussen alle vectoren.
- gezien x en y variabel zijn, werk ik met cellen {} van array's []
- de data op zich zijn objecten in MATLAB (eigen klassen)

Wat heb ik al gedaan:
- gezien x en y @ runtime gekend zijn, maak ik een variabel van {x} cellen waarbij elke cel [y] lege objecten vast houdt -> preallocation done
- de objecten werken met een handle, dus er moet niet constant een object gekopieerd worden naar zichzelf. Dus bv: mySet = mySet.sortOnDistance() moet niet meer. Ik kan direct: mySet.sortOnDistance() werken -> heel ruw: pass by ref waar mogelijk
- minder wiskundige bewerkingen, een benadering om een beslissing te maken is even goed (zoals c² = a² + b² ipv c = (a² + b²)^.5)

Zo ben ik al van 61uur reken werk naar 4uur rekenwerk kunnen gaan voor 1000 vectoren in 9D. Maar veel meer kan ik niet bedenken. Via veel testen heb ik kunnen achterhalen dat het aanmaken en werken met cellen, langer duurt dan het uitrekenen van afstanden.

tl;dr
Bijgevolg mijn vragen:
- bestaat er een datastructuur die het gedrag van cellen heeft? Dus SNEL dynamisch de variable uitbreiden met nieuwe objecten die in GROEP bij elkaar staan (dus geen array..).
- bestaat pass by reference? Het lijkt me dat matlab altijd een referentie geeft, indien de data gewijzigd wordt in een functie. Maar altijd een copy indien de data niet wijzig?

Matrices zijn the way to go in matlab. Gebruik matrices ipv cellen, zelfs als dat wat extra rekenwerk/kopieren vraagt. Gebruik pure data matrices ipv objecten, zelfs als dat uw design helemaal verkloot. Het is bekend dat cellen en objecten traag zijn in matlab. Matlab is namelijk gebouwd voor snelle numerieke matrix berekeningen en vereist toch een wat andere mindset bij het programmeren.

Het is me trouwens niet duidelijk waarom je een dynamisch uitbreidbare datastructuur nodig hebt, want daarvoor lijk je te zeggen dat je aan het begin van de berekening weet dat je x vectoren hebt.

NeverwinterX zei:

Matrices zijn the way to go in matlab. Gebruik matrices ipv cellen, zelfs als dat wat extra rekenwerk/kopieren vraagt. Gebruik pure data matrices ipv objecten, zelfs als dat uw design helemaal verkloot. Het is bekend dat cellen en objecten traag zijn in matlab. Matlab is namelijk gebouwd voor snelle numerieke matrix berekeningen en vereist toch een wat andere mindset bij het programmeren.

Klik om te vergroten...

Code dan porten naar Python dan lijkt me . Want de tijd is te kort om heel het algoritme op een structurele manier uit te werken.

NeverwinterX zei:

Het is me trouwens niet duidelijk waarom je een dynamisch uitbreidbare datastructuur nodig hebt, want daarvoor lijk je te zeggen dat je aan het begin van de berekening weet dat je x vectoren hebt.

Klik om te vergroten...

De input data op zich is ofwel 9D, 12D of 15D en 1000 vectoren bleek goed te zijn a.d.h.v. een paper. We moeten een manier vinden om die vectoren samen te nemen alla 'self-organizing map'. De input data is trouwens geluid waardoor at run time we nooit twee dezelfde uitkomsten zullen bekomen en het algoritme bezit een heuristic eigenschap.

De uitkomst is dus van dezelfde dimensie van als input, maar variabel in grootte, en variabel qua extra data (zoals gewicht per cluster etc).

Fraggie zei:

De input data op zich is ofwel 9D, 12D of 15D en 1000 vectoren bleek goed te zijn a.d.h.v. een paper. We moeten een manier vinden om die vectoren samen te nemen alla 'self-organizing map'. De input data is trouwens geluid waardoor at run time we nooit twee dezelfde uitkomsten zullen bekomen en het algoritme bezit een heuristic eigenschap.

De uitkomst is dus van dezelfde dimensie van als input, maar variabel in grootte, en variabel qua extra data (zoals gewicht per cluster etc).

Klik om te vergroten...

I see en heb je geen ruwe bovengrens voor de grootte van de uitkomst zodat je gewoon een matrix van die bovengrens grootte alloceert (en dus wat teveel voorziet)?

NeverwinterX zei:

I see en heb je geen ruwe bovengrens voor de grootte van de uitkomst zodat je gewoon een matrix van die bovengrens grootte alloceert (en dus wat teveel voorziet)?

Klik om te vergroten...

De code die mijn output aanvaard is reeds geschreven door mijn partner en alles is afgestemd op test data. Veel kunnen we er niet meer in veranderen zonder opnieuw dag en nacht te testen.

Ik heb waarschijnlijk je vraag niet 100% correct beantwoord, ik kan namelijk geen matrix aanmaken van objecten, wél een array.

Verder heb ik Octave gedownload een geprobeerd, maar het concept van objecten leek me net iets te abstract in die omgeving.

Momenteel heb ik al een paar uur bezig met de code te porten naar C# ipv Python, gezien ik dan kan genieten van de optimalisatie van het compileren in C#. Momenteel zijn de resultaten zeer goed:
15s voor:
- alloceren van memory
- uitrekenen van de afstanden
- bubble sorting

dit alles voor 0€ aan .NET software

vs

14400s in MATLAB aan 1000€?

*edit: eindresultaat is 30s execution time, bij deze heeft MATLAB afgedaan en wordt het Python + Numpy