Koodikatselmointi 2

[anroysko]

Latauksen päivä ja kellonaika; 27.4.2018 Klo 23.

Ilmeisesti projektissa etsitään lyhyintä reittiä painottamattomassa grid-verkossa. Tässä tapauksessa suora dfs saavuttaa aikavaativuuden O(V) verrattuna normaalin A*:n O(V log V):hen. Myös A*:n saa tässä tapauksessa käyttämällä min-heapin sijasta suoraan arrayListejä, niin, että kun haluaisi pushata heappiin uuden elementin, jonka hinta on K, niin sen sijaan pushaa K:nteen arrayListiin tuon elementin, ja käymällä vain näitä arrayListejä järjestyksessä läpi, saavuttaa O(V) aikavaativuuden, ja käytännössä todennäköisesti paljon nopeamman koodin.

Koodi on käytännössä aika hidas, kun V=10^6 sillä kesti yli minuutti ratkaista tyhjä kartta. En tunne javaa kauhean hyvin jotta osaisin osoittaa syyllistä koodia. Veikkaan että ainakin nodejen indeksien käyttö arrayissä ja vastaavissa, yllä oleva aikavaattivuuttakin parantava optimisaatio, ja cameFrom-mapin korvaaminen arrayListillä auttaisivat.

Testit ja coverage toimivat hyvin.