Floris' Blog

Recently I saw this article on AMD’s Java developer zone on Garbage collection tuning. Don’t expect a very deep discussion of all flags related to tuning though. The article divides the problem on whether your optimizing for throughput or latency, and serves as a starting point to optimizing your application.

Some interesting points:

• Decide on whether you need throughput or low latency,
• -XX:+UseParallelGC enables the parallel collector ONLY FOR THE YOUNG generation,
• -XX:+UseParallelOldGC is actually the newer implementation and processes the young as well as the old generations,
• Tune the nursery size.

This is another article I wrote for the newsletter of my employer. These articles are intended as an introduction to algorithms. This one takes a look at the shortest path algorithm. Text is in Dutch:

Het kortste pad algoritme kom je in veel puzzels tegen. In sommige puzzels is het overduidelijk dat hiernaar gevraagd word, en in andere moet je door het verhaal heen prikken om het te vinden. Over het algemeen komt het erop neer dat er gevraagd wordt om een enkele waarde terug te geven die zo klein mogelijk is, waarbij je veel invoer data krijgt waarmee je een graaf op kunt bouwen. In veel gevallen is de exacte route niet van belang (er zouden meerdere oplossingen kunnen zijn, wat het jureren ingewikkelder maakt) en is er sprake van een startpunt in de graaf.

Voor hele kleine structuren zou je de oplossing kunnen vinden door recursief door alle oplossingen te gaan: je begint in het gegeven startpunt. Voor iedere uitgaande mogelijkheid kijk je of de knoop aan de andere kant nog niet in je huidige pad zit. Als het er wel in zit ga je verder met de volgende uitgaande mogelijkheid. Anders kijk je of de knoop waar je heen gaat voldoet aan bepaalde eindcriteria (een te bezoeken punt). Als dat zo is dan bereken je de pad lengte, die sla je op, en je gaat verder met de volgende uitgaande mogelijkheid. Anders herhaal je deze stappen voor de betreffende knoop (weer alle volgende uitgaande mogelijkheden nalopen). Als je geen uitgaande paden meer hebt, dan ga je naar terug naar de knoop waar je vandaan kwam om daar de volgende optie te proberen.

Deze manier van oplossen is al snel onbruikbaar. Het aantal te proberen paden loop snel op, waarbij veel stukjes van de route meerdere keren uitgerekend worden.

De oplossing voor dit probleem is de door Edsger Dijkstra bedacht in 1959. De essentie van de oplossing is dat je bij iedere stap een knoop kiest die nog niet eerder gekozen is en die de kleinste afstand heeft vanaf de start-knoop. Een mooie visualisatie hiervan is door de knopen als voorwerpen voor te stellen die met draadjes aan elkaar zitten en op tafel liggen. Als je nu de start-knoop van tafel pakt en omhoog trekt, dan komt even later een knoop van tafel die op de kleinste afstand van de start zit. De volgende knoop die van tafel komt heeft ook een minimale afstand vanaf de start. Eventuele overbodige verbindingen zijn te herkennen als draden die slap hangen tussen twee knopen die van tafel zijn.

Het algoritme begint door voor iedere knoop een paar waardes te initialiseren: de ‘vorige knoop’ (nuttig om de optimale route terug te kunnen geven, maar vaak niet nodig) en de ‘minimale afstand’ die we op oneindig initialiseren, behalve voor de startknoop: die krijgt 0 als afstand. Verder maken we een set waarin alle knopen zitten.

Zolang de set niet leeg is voeren we de volgende stappen uit. Eerst zoeken we in de set naar de knoop met de laagste minimale afstand. Dit is de knoop die van tafel zou komen. Deze knoop noemen we ‘A’ en we halen deze uit de set. We gaan over alle uitgaande verbindingen van A. Voor iedere knoop aan de andere kant van die verbinding (laten we deze ‘C noemen) kijken we of de minimale afstand groter is dan de minimale afstand van A plus de afstand van de verbinding. Als dat het geval vervangen we de minimale afstand van C door de minimale afstand van A plus de afstand van de verbinding en wordt de waarde ‘vorige knoop’ van C gezet op A.

Voor verschillende problemen zijn er kleine optimalisaties te maken in het algoritme. Je kunt eerder stoppen als je de afstand naar het gevraagde punt gevonden hebt. Je kan ook de set initialiseren met alleen de startknoop en er elementen aan toe voegen als de minimale afstand wordt aangepast. Dit helpt het zoekwerk naar de knoop met de laagste minimale afstand te versnellen. Er zijn ook data structuren die het vinden van die knoop versnellen (priority queue), maar al deze optimalisaties kosten extra geheugen of boekhoud -werkzaamheden, waardoor ze niet altijd een verbetering betekenen.

Dijkstra’s algoritme is het bekendste algoritme voor het oplossen van kortste pad problemen. Er zijn er echter meer, of varianten:

Floyd-Warshall algoritme – berekent de kortste afstand van ieder punt naar ieder ander punt. Bruikbaar als in een probleem vanuit (veel) verschillende startpunten routes bepaald moeten worden. Nadeel is dat alleen al het opslaan van al die afstanden kwadratisch is met het aantal knopen (en je snel te weinig geheugen hebt).

A* algoritme – een optimalisatie voor kortste pad problemen. Je zoekt dan niet naar de knoop met de kortste afstand vanaf de startknoop maar naar de knoop met de laagste waarde voor ‘kortste afstand vanaf de startknoop’ plus een geschatte afstand tot de eindknoop. De schatting moet hierbij nooit overschatten. Dit zorgt ervoor dat de gezochte oplossing eerder gevonden wordt.

Op Spoj kun je de volgende puzzels doen om met shortest pad te spelen:
440. The Turtle´s Shortest Path - Eenvoudig, maar let op I/O
96. Shopping
3405. Almost Shortest Path