Introduction
Při odlazování dijkstrova algoritmu jsem se snažil dosáhnout co nejlepšího poměru výkonu a využití paměti. Nebudu zapírat, že jsem nad tím strávil trochu víc času, než je zdrávo, ale výsledek, podle mě, stojí za to.
Optimalizace dijkstrova algoritmu
Původní algoritmus využíval dvourozměrného pole typu int, které bylo alokováno na velikost V*V. V případě semestrálky to dělá maximální velikost 2000*2000, což je zbytečně velké číslo. Tento typ jsem ořízl na short, čímž jsem problém akorát vydělil dvěma. To ale přispělo k rapidnímu snížení využití operační paměti.
Optimalizace grafu
Další věc, kterou bylo nutné brát v úvahu je rychlost práce s grafem a s tím spojené paměťové nároky grafu. Původně graf reprezentovaný polem vrcholů a polem hran byl předělán na obdobu grafu reprezentovaného seznamem sousednosti.
Graf tedy obsahuje pouze jedno jednorozměrné pole typu Node (vrchol). Každý vrchol pak obsahuje HashMap hran, kde pod indexem (druhého vrcholu spojeného touto hranou) jakožto klíčem je uložena daná hrana. HashMapa byla vybrána z hlediska kompromisu mezi výkonem a paměťovou náročností.
Protože se v zadaní uvažuje pouze s neorientovaným grafem, využil jsem tohoto a předešel jsem duplicitnímu uchovávání reference na hranu u obou propojených vrcholů. Reference na hranu je tak ukládána vždy v HashMapě vrcholu s menším indexem. V grafu byla dále implementována metoda getEdge(a int, b int), která dokáže velmi rychle vrátit hranu mezi dvěma vrcholy. Postup je jednoduchý, vezme se menší z indexu a, b, na základě tohoto indexu se vytáhne vrchol z pole vrcholů a poté se použije index b jako klíč pro HashMapu, která již vrátí požadovanou hranu.
Tento graf se ukázal jako velmi dobrý kompromis mezi výkonem a paměťovou náročností.
Rychlost Dijkstrova algoritmu
Poznámka: Časy byly naměřeny na pc s procesorem C2D E6600@2,4 Ghz.
První verze Dijkstrova algoritmu potřebovala přibližně 800 ms (1,25x za sekundu) pro projetí grafu o velikosti 2000 vrcholů a 200 000 hran. Po výše uvedené optimalizaci se tento čas zkrátil na přibližně 200 ms (5x za sekundu), což vychází na 4 násobné zrychlení.
Vzhledem k zadání, které uvažuje nad velmi intenzivním procházení grafu, kde například může nastat situace, která bude vyžadovat procházení grafu 50x za sebou, tento čas 200*50 = 10s stále není optimální.
Jako řešení jsme zvolili možnost využití plného výkonu procesoru - zejména procesorů s více jádry. Tohoto bylo docíleno použitím více vláknového procházení grafu. To znamená, že je možné procházet graf například 20x současně. Toto řešení zvýšilo rychlost procházení grafu na 25 průchodů za sekundu, což je další 5 násobné zlepšení.
Test výkonu prohledávače grafu
Na obrázku dole je zobrazen test výkonu tohoto řešení procházení dijkstrova algoritmem. Test je proveden na grafu o velikosti 2000 vrcholů a cca 202000 hran. Tento graf byl prohledáván dijkstrovým algoritmem 100x za sebou s vláknováním až 50 vláken. Zvýrazněná svislá čára naznačuje přibližně ideální počet vláken.