Programmierabenteuer bei Hackerrank
Programmieren macht mir Spaß, weil ich damit den Computer dazu bringen kann, interessante Probleme zu lösen. Besonders spannend sind Probleme, die sich nicht einfach durch eine mathematische Gleichung lösen lassen. Stattdessen muss der Computer in mehreren Schritten die beste Lösung konstruieren oder zahlreiche Alternativlösungen durchforsten und daraus die beste Lösung auswählen. Im Studium habe ich dafür effiziente Algorithmen und Datenstrukturen kennengelernt. Doch wie im Sport ist auch beim Programmieren ein regelmäßiges Training erforderlich, damit nichts in Vergessenheit gerät.
Mit Hackerrank habe ich eine Plattform gefunden, auf der ich Algorithmen aus der Studienzeit wiederholen und neue Algorithmen hinzulernen kann. Es gibt zahlreiche Problemstellungen, die sofort im Browser in der gewünschten Programmiersprache gelöst werden können. Beim Klick auf den Button “Submit” wird der eingereichte Algorithmus auf zahlreiche Testfälle angewendet. Viele Testfälle beinhalten tausende oder hunderttausende Daten. Sie gelten nur dann als bestanden, wenn die richtige Lösung innerhalb eines vorgegebenen Zeitfensters ermittelt wird (z.B. innerhalb von 6 Sekunden). Um diese Tests zu bestehen, muss der Algorithmus effizient arbeiten, z.B. mit linearer oder logarithmischer Laufzeit. Einige meiner Algorithmen haben zunächst nur die kleinen Testfälle bestanden, da sie für die großen Testfälle noch zu langsam waren. Die interessante Herausforderung bestand dann darin, den Algorithmus ordentlich zu beschleunigen!
Interessante Problemstellungen, die ich auf Hackerrank gefunden habe (gekürzt):
- Auf einer Reihe von Häusern sollen Funktransmitter installiert werden. Ermitteln Sie die minimale Anzahl von Transmittern, die benötigt wird, damit jedes Haus in der Reichweite von mindestens einem Transmitter liegt. Zur Challenge
- Gegeben ist eine Reihe von Aufgaben mit jeweils einer Ausführungsdauer und einer Deadline. Die Aufgaben sollen in einer Reihenfolge ausgeführt werden, bei der die Überschreitung der Deadlines möglichst gering ist. Geben Sie den maximalen Betrag an, um den eine Aufgabe ihre Deadline überschreitet, wenn die optimale Reihenfolge gewählt wird. Zur Challenge
- Die Mitgliedsstaaten der UN möchten Menschen zum Mond schicken. Gegeben ist eine Liste mit Paaren von Astronauten, die jeweils aus dem gleichen Land kommen. Daraus sollen Paare von Astronauten gebildet werden, die aus verschiedenen Ländern kommen. Wie viele solche Paare gibt es? Zur Challenge
Algorithmen, Datenstrukturen und Programmiertechniken, die ich anhand der Probleme geübt habe:
- Disjoint Data Set: Eine Datenstruktur, um disjunkte Mengen zu verwalten.
- Segmentbaum: Eine Datenstruktur, um Intervalle zu verwalten.
- Dynamische Programmierung: Eine Methode zum Entwickeln von Algorithmen zur Lösung von Optimierungsproblemen. Sie beinhaltet die Aufteilung des Problems in Teilprobleme und die systematische Speicherung von Zwischenresultaten.
- Tiefensuche, Breitensuche, binäre Suche
- Greedy-Algorithmen, Floodfill-Algorithmus
Fallbeispiel: Dijkstra-Algorithmus mit Priority-Queue in Java beschleunigen
Bei der Challenge Find the Path ist eine 2D-Matrix mit gewichteten Positionen (x,y) gegeben. Nun geht es darum, den Pfad mit dem geringsten Gesamtgewicht zwischen zwei Positionen from = (x1, y1) und to = (x2, y2) zu finden. Es soll eine Methode entwickelt werden, die zwei Positionen from und to als Parameter entgegennimmt und das Gewicht des kürzesten Pfades zurückgibt (der Pfad selbst muss nicht aufgezeichnet werden).
Dazu bietet sich der Dijkstra-Algorithmus an. Die Gewichte der Zellen werden als Abstände zwischen zwei Knoten im Graphen interpretiert.
Ein möglicher Ansatz in Java sieht wie folgt aus:
private static int findShortestPathLength(Position from, Position to){
PriorityQueue<Position> pq = new PriorityQueue<Position>(new PositionComparator());
Position[][] positions = new Position[weights.length][weights[0].length];
init(from, pq, positions);
while(pq.size()!=0){
Position p = pq.poll();
//equals wurde in der Klasse Position überschrieben
if( p.equals(to)){
return p.pathLength;
}
Position n = null;
if(p.x-1 >= 0){
n = positions[p.x-1][p.y];
if(pq.contains(n)) {
update(pq, p, n);
}
}
if(p.x+1 < weights.length) {
n = positions[p.x + 1][p.y];
if(pq.contains(n)) {
update(pq, p, n);
}
}
if(p.y-1 >=0 ){
n = positions[p.x][p.y - 1];
if(pq.contains(n)) {
update(pq, p, n);
}
}
if(p.y+1 < weights[0].length){
n = positions[p.x][p.y + 1];
if(pq.contains(n)) {
update(pq, p, n);
}
}
}
return -1;
}
Die Methode findShortestPathLength arbeitet mit den Hilfsmethoden init und update:
private static void init(Position from, PriorityQueuepq, Position[][] positions) { for(int i = 0; i<= weights.length-1; i++){ for(int j= 0; j<= weights[0].length-1; j++){ Position p = new Position(i,j); positions[i][j] = p; pq.add(p); } } pq.remove(from); //Position from kommt an die erste Stelle //pathLength für die restlichen Positionen wurde mit Integer.MAX_VALUE initialisiert (siehe Klasse Position) from.pathLength = weights[from.x][from.y]; pq.add(from); } private static void update(PriorityQueue pq, Position p, Position n) { int alternativ = p.pathLength + weights[n.x][n.y]; if (alternativ < n.pathLength) { n.pathLength = alternativ; pq.remove(n); pq.add(n); } }
Der Code orientiert sich stark an dem üblichen Pseudo-Code für den Dijkstra-Algorithmus, der auch bei Wikipedia zu finden ist: Beim Initialisieren werden zunächst alle Positionen in eine Prioritätswarteschlange pq eingereiht. Die Position from wird an die vorderste Stelle geschoben. Anschließend wird in einer while-Schleife in jedem Schritt die vorderste Position aus der Warteschlange entfernt. Für die vier Nachbarn dieser Positionen werden die Pfadlängen aktualisiert, sofern sie noch in der Schlange enthalten sind. Sobald die erste Position in der Schlange der Position to entspricht, kann die Schleife abgebrochen und die kürzeste Pfadlänge zurückgegeben werden.
Den vollständigen Code gibt es hier zum Download: Datei Solution.zip
Die Datei enthält eine main-Methode, in der die Testdaten aus der Datei test2.txt eingelesen werden. Der Pfad zu dieser Datei muss in der main-Methode korrekt angepasst werden!
Die Testdatei ist wie folgt aufgebaut:
- In der ersten Zeile ist die Anzahl der Zeilen und Spalten der 2D-Matrix gegeben.
- In den folgenden Zeilen werden die Gewichte der gesamten Matrix angegeben.
- Danach wird die Anzahl der nachfolgenden Queries (Abfragen) angegeben.
- Es folgen die Abfragen, wobei jede Abfrage aus 4 Werten für x1 y1 x2 y2 besteht.
Das Programm ruft für jede Abfrage die Methode findShortestPathLength auf und druckt das Gewicht für den kürzesten Pfad zwischen from=(x1,y1) und to=(x2,y2) auf der Konsole aus.
Optimierung 1: die contains-Methode ersetzen
Die Testdatei enthält eine Matrix mit 7 Zeilen, 5000 Spalten und beachtliche 30.000 Abfragen! Auf meinem Laptop braucht das Programm ca. 120 Sekunden, um alle Ergebnisse zu liefern. Das lässt sich noch deutlich beschleunigen.
Als erstes schauen wir uns die contains-Methode an, die in jeder Iteration der while-Schleife bis zu 4 mal aufgerufen wird. Sie hat eine Laufzeitkomplexität von O(n), d.h. im schlechtesten Fall müssen alle n Elemente der Warteschlange überprüft werden, um festzustellen, ob das gesuchte Element enthalten ist oder nicht.
Ich führe ein 2D-Matrix finished vom Typ Boolean ein, um mir zu merken, ob eine Position schon aus der Warteschlange entfernt wurde. Die contains-Aufrufe werden durch eine Überprüfung der Matrix ersetzt, die stets in konstanter Zeit O(1) erfolgt:
private static int findShortestPathLength(Position from, Position to){
PriorityQueue<Position> pq = new PriorityQueue<Position>(new PositionComparator());
Position[][] positions = new Position[weights.length][weights[0].length];
//Matrix wird automatisch mit false initialisiert
boolean[][] finished = new boolean[weights.length][weights[0].length];
init(from, pq, positions);
while(pq.size()!=0){
Position p = pq.poll();
finished[p.x][p.y] = true;
if( p.equals(to)){
return p.pathLength;
}
Position n = null;
if(p.x-1 >= 0){
n = positions[p.x-1][p.y];
if(!finished[n.x][n.y]) {
update(pq, p, n);
}
}
if(p.x+1 < weights.length) {
n = positions[p.x + 1][p.y];
if(!finished[n.x][n.y]) {
update(pq, p, n);
}
}
if(p.y-1 >=0 ){
n = positions[p.x][p.y - 1];
if(!finished[n.x][n.y]) {
update(pq, p, n);
}
}
if(p.y+1 < weights[0].length){
n = positions[p.x][p.y + 1];
if(!finished[n.x][n.y]) {
update(pq, p, n);
}
}
}
return -1;
}
Die Laufzeit für 30.000 Abfragen reduziert sich damit auf ca. 45 Sekunden!
Optimierung 2: Die Initialisierung verkürzen
Wenn die contains-Methode nicht mehr genutzt wird, entfällt auch die Notwendigkeit, alle Positionen gleich zu Beginn in die Warteschlange einzureihen. Die init-Methode kann wie folgt gekürzt werden:
private static void init(Position from, PriorityQueue pq, Position[][] positions) {
for(int i = 0; i<= weights.length-1; i++){
for(int j= 0; j<= weights[0].length-1; j++){
Position p = new Position(i,j);
positions[i][j] = p;
}
}
from.pathLength = weights[from.x][from.y];
pq.add(from);
}
In der Warteschlange müssen nun viel weniger Positionen verwaltet werden. Die Laufzeit verkürzt sich dadurch auf ca. 5 Sekunden.
Optimierung 3: Verzicht auf remove
Die PriorityQueue in Java bietet keine Aktualisierungsmethode. Um ein Element in der Schlange zu verändern, muss es daher mit remove zunächst aus der Schlange entfernt und anschließend mit add sofort wieder eingefügt werden (vgl. Hilfsmethode update der Klasse Solution). Die remove-Methode besitzt ebenfalls eine Laufzeitkomplexität O(n). Das lineare Durchsuchen der ganzen Schlange, um das zu entfernende Element zu finden, wirkt sich negativ auf die Laufzeit aus.
Für die vorliegenden Testdaten lohnt es sich, einfach auf den remove-Aufruf zu verzichten. Anstatt die Pfadlänge einer Position zu aktualisieren, wird einfach eine Kopie der Position mit der neuen Pfadlänge in die Warteschlange eingereiht. Sollte die Pfadlänge das neue Minimum sein, wird die Position automatisch an die Spitze der Schlange gesetzt.
Auf die Matrix positions kann nun verzichtet werden. Ich streiche auch die Methoden init und update.
private static int findShortestPathLength(Position from, Position to){
PriorityQueue<Position> pq = new PriorityQueue<Position>(new PositionComparator());
boolean[][] finished = new boolean[weights.length][weights[0].length];
from.pathLength = weights[from.x][from.y];
pq.add(from);
while(pq.size()!=0){
Position p = pq.poll();
finished[p.x][p.y] = true;
if( p.equals(to)){
return p.pathLength;
}
Position n = null;
if(p.x-1 >= 0){
n = new Position(p.x-1, p.y);
if(!finished[n.x][n.y]) {
n.pathLength = p.pathLength + weights[n.x][n.y];
pq.add(n);
}
}
if(p.x+1 < weights.length) {
n = new Position(p.x+1, p.y);
if(!finished[n.x][n.y]) {
n.pathLength = p.pathLength + weights[n.x][n.y];
pq.add(n);
}
}
if(p.y-1 >=0 ){
n = new Position(p.x, p.y-1);
if(!finished[n.x][n.y]) {
n.pathLength = p.pathLength + weights[n.x][n.y];
pq.add(n);
}
}
if(p.y+1 < weights[0].length){
n = new Position(p.x, p.y+1);
if(!finished[n.x][n.y]) {
n.pathLength = p.pathLength + weights[n.x][n.y];
pq.add(n);
}
}
}
return -1;
}
Die Laufzeit liegt jetzt bei ca. 500 Millisekunden.
In diesem Fall überwiegen die Vorteile beim Verzicht auf das remove gegenüber den Nachteilen, die durch das "Zumüllen" der Warteschlange mit überflüssigen Positionen entstehen. Ein Blick in die Testdatei zeigt, dass bei den Abfragen die Abstände zwischen y1 und y2 eher gering sind. Die Abfragen beziehen sich also auf kurze Pfade. Dadurch müssen nicht so viele Elemente in die Warteschlange aufgenommen werden, bis die kürzeste Pfadlänge gefunden wurde. Wenn längere Pfade gebildet werden sollen, ist zu erwarten, dass sich die Laufzeit mit einer aufgeblähten Warteschlange stark erhöht.
Es lohnt sich bei der Laufzeitoptimierung häufig, auf die Besonderheiten der vorliegenden Eingabedaten zu achten!
Fazit
Mit dieser Optimierung lässt sich bei der Hackerrank-Challenge ca. die Hälfte aller Testfälle in der vorgegebenen Zeit lösen. Um die restlichen Tests zu bestehen, muss der algorithmische Ansatz erweitert werden. Hinweise dazu gibt es im Editorial der Challenge.
Mal was anderes: http://www.forstbetrieb-preussing.de/index.html
