RSS Feed

Optymalizacja Grafu

Na mojej kochanej PWR realizowałem prostą implementację grafu z wyszukiwaniem najkrótszych ścieżek w grafie. Trochę się zirytowałem gdy mój cudowny kod chodził 20 razy wolniej ;] od kodu kolegi. Niestety moja chorobliwa ambicja nie odpuściła i postanowiłem zoptymalizować kod …..

Zabawę zacząłem z programikiem dotTrace który jest świetnym profilerem badającym wydajność programów. Fajną sprawą jest wyświetlanie ilości wywołań poszczególnych metod i czas ich trwania. Dzięki temu z łatwością możemy wydzielić bloki kodu w których najprawdopodobniej powinniśmy optymalizować. Zgodnie z zasadą 20/80 zmiana 20% najbardziej czasochłonnych linii kodu da 80% wzrost wydajności.

Po analizie i paru zmianach okazało się że źle przeprowadzałem testy. Zamiast ciągle operować na tym samym elemencie za każdym razem tworzyłem nową instancję klasy odpowiedzialnej za algorytm. Przy 1 Milionie wywołań algorytmu dawało to długi czas działania aplikacji po lekkiej modyfikacji czas wykonania spadł z 60 s do 320ms.

Conclusion:
Pamiętajmy o odpowiednim konstruowaniu testów 😛

Ciekawy jest także fakt że tak naprawdę czas wykonania mojego programu zajmuje tylko 56% czasu działania aplikacji. 44% pożerają procedury .netowe

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s