Einführung in gierige Algorithmen mit Java

1. Einleitung

In diesem Tutorial werden wir gierige Algorithmen in das Java-Ökosystem einführen.

2. Gieriges Problem

Bei einem mathematischen Problem gibt es verschiedene Möglichkeiten, eine Lösung zu entwerfen. Wir können eine iterative Lösung oder einige fortgeschrittene Techniken implementieren, wie das Divide and Conquer-Prinzip (z. B. Quicksort-Algorithmus) oder einen Ansatz mit dynamischer Programmierung (z. B. Knapsack-Problem) und vieles mehr.

Meistens suchen wir nach einer optimalen Lösung, aber leider erzielen wir nicht immer ein solches Ergebnis. Es gibt jedoch Fälle, in denen sogar ein suboptimales Ergebnis wertvoll ist. Mit Hilfe bestimmter Strategien oder Heuristiken können wir uns eine so wertvolle Belohnung verdienen.

In diesem Zusammenhang wird angesichts eines teilbaren Problems eine Strategie, die in jeder Phase des Prozesses die lokal optimale Wahl oder „gierige Wahl“ trifft, als gieriger Algorithmus bezeichnet.

Wir haben erklärt, dass wir uns mit einem „teilbaren“ Problem befassen sollten: Eine Situation, die als eine Reihe von Teilproblemen mit fast denselben Merkmalen beschrieben werden kann. Infolgedessen wird meistens ein Greedy-Algorithmus als rekursiver Algorithmus implementiert .

Ein gieriger Algorithmus kann ein Weg sein, uns trotz einer rauen Umgebung zu einer vernünftigen Lösung zu führen. Mangel an Rechenressourcen, Ausführungszeitbeschränkungen, API-Einschränkungen oder anderen Einschränkungen.

2.1. Szenario

In diesem kurzen Tutorial werden wir eine gierige Strategie implementieren, um Daten aus einem sozialen Netzwerk mithilfe seiner API zu extrahieren.

Nehmen wir an, wir möchten mehr Benutzer im sozialen Bereich „Little Blue Bird“ erreichen. Der beste Weg, um unser Ziel zu erreichen, besteht darin, Originalinhalte zu veröffentlichen oder etwas neu zu twittern, das bei einem breiten Publikum Interesse weckt.

Wie finden wir ein solches Publikum? Nun, wir müssen einen Account mit vielen Followern finden und Inhalte für sie twittern.

2.2. Klassisch gegen Gierig

Wir berücksichtigen die folgende Situation: Unser Konto hat vier Follower, von denen jeder, wie im Bild unten dargestellt, 2, 2, 1 und 3 Follower hat und so weiter:

Zu diesem Zweck werden wir denjenigen mit mehr Anhängern zu den Anhängern unseres Kontos zählen. Dann wiederholen wir den Vorgang noch zweimal, bis wir den 3. Verbindungsgrad erreichen (insgesamt vier Schritte).

Auf diese Weise definieren wir einen Pfad, der aus Benutzern besteht und uns von unserem Konto aus zur größten Follower-Basis führt. Wenn wir Inhalte an sie adressieren können, werden sie sicherlich unsere Seite erreichen.

Wir können mit einem „traditionellen“ Ansatz beginnen. Bei jedem einzelnen Schritt führen wir eine Abfrage durch, um die Follower eines Kontos zu ermitteln. Aufgrund unseres Auswahlprozesses erhöht sich die Anzahl der Konten mit jedem Schritt.

Insgesamt würden wir überraschenderweise 25 Abfragen durchführen:

Hier tritt ein Problem auf: Beispielsweise beschränkt die Twitter-API diese Art von Abfrage auf 15 alle 15 Minuten. Wenn wir versuchen, mehr Anrufe als zulässig auszuführen, erhalten wir den Code " Ratenlimit überschritten - 88 " oder " In API v1.1 zurückgegeben, wenn eine Anforderung nicht bearbeitet werden kann, weil das Ratenlimit der Anwendung für die Ressource erschöpft ist." “. Wie können wir eine solche Grenze überwinden?

Nun, die Antwort liegt direkt vor uns: Ein gieriger Algorithmus. Wenn wir diesen Ansatz verwenden, können wir bei jedem Schritt davon ausgehen, dass der Benutzer mit den meisten Followern der einzige ist, der berücksichtigt werden muss: Am Ende benötigen wir nur vier Abfragen. Eine ziemliche Verbesserung!

Das Ergebnis dieser beiden Ansätze wird unterschiedlich sein. Im ersten Fall erhalten wir 16, die optimale Lösung, während im letzteren Fall die maximale Anzahl erreichbarer Follower lediglich 12 beträgt.

Wird dieser Unterschied so wertvoll sein? Wir werden später entscheiden.

3. Implementierung

Um die obige Logik zu implementieren, initialisieren wir ein kleines Java-Programm, in dem wir die Twitter-API nachahmen. Wir werden auch die Lombok-Bibliothek nutzen.

Definieren wir nun unsere Komponente SocialConnector, in der wir unsere Logik implementieren. Beachten Sie, dass wir einen Zähler setzen werden, um Anrufbeschränkungen zu simulieren, aber wir werden ihn auf vier senken:

public class SocialConnector { private boolean isCounterEnabled = true; private int counter = 4; @Getter @Setter List users; public SocialConnector() { users = new ArrayList(); } public boolean switchCounter() { this.isCounterEnabled = !this.isCounterEnabled; return this.isCounterEnabled; } } 

Dann fügen wir eine Methode hinzu, um die Follower-Liste eines bestimmten Kontos abzurufen:

public List getFollowers(String account) { if (counter < 0) { throw new IllegalStateException ("API limit reached"); } else { if (this.isCounterEnabled) { counter--; } for (SocialUser user : users) { if (user.getUsername().equals(account)) { return user.getFollowers(); } } } return new ArrayList(); } 

Zur Unterstützung unseres Prozesses benötigen wir einige Klassen, um unsere Benutzerentität zu modellieren:

public class SocialUser { @Getter private String username; @Getter private List followers; @Override public boolean equals(Object obj) { return ((SocialUser) obj).getUsername().equals(username); } public SocialUser(String username) { this.username = username; this.followers = new ArrayList(); } public SocialUser(String username, List followers) { this.username = username; this.followers = followers; } public void addFollowers(List followers) { this.followers.addAll(followers); } }

3.1. Gieriger Algorithmus

Schließlich ist es Zeit, unsere Greedy-Strategie zu implementieren. Fügen wir also eine neue Komponente hinzu - GreedyAlgorithm -, in der wir die Rekursion durchführen:

public class GreedyAlgorithm { int currentLevel = 0; final int maxLevel = 3; SocialConnector sc; public GreedyAlgorithm(SocialConnector sc) { this.sc = sc; } }

Dann müssen wir eine Methode findMostFollowersPath einfügen, in der wir den Benutzer mit den meisten Followern finden, sie zählen und dann mit dem nächsten Schritt fortfahren:

public long findMostFollowersPath(String account) { long max = 0; SocialUser toFollow = null; List followers = sc.getFollowers(account); for (SocialUser el : followers) { long followersCount = el.getFollowersCount(); if (followersCount > max) { toFollow = el; max = followersCount; } } if (currentLevel < maxLevel - 1) { currentLevel++; max += findMostFollowersPath(toFollow.getUsername()); } return max; }

Denken Sie daran: Hier treffen wir eine gierige Wahl. Daher wählen wir jedes Mal, wenn wir diese Methode aufrufen , ein und nur ein Element aus der Liste aus und fahren fort: Wir werden niemals wieder auf unsere Entscheidungen zurückgreifen!

Perfekt! Wir sind bereit zu gehen und können unsere Anwendung testen. Vorher müssen wir daran denken, unser winziges Netzwerk zu füllen und schließlich den folgenden Komponententest durchzuführen:

public void greedyAlgorithmTest() { GreedyAlgorithm ga = new GreedyAlgorithm(prepareNetwork()); assertEquals(ga.findMostFollowersPath("root"), 5); }

3.2. Nicht-gieriger Algorithmus

Lassen Sie uns eine nicht gierige Methode erstellen, nur um mit unseren Augen zu überprüfen, was passiert. Wir müssen also mit dem Erstellen einer NonGreedyAlgorithm- Klasse beginnen:

public class NonGreedyAlgorithm { int currentLevel = 0; final int maxLevel = 3; SocialConnector tc; public NonGreedyAlgorithm(SocialConnector tc, int level) { this.tc = tc; this.currentLevel = level; } }

Let's create an equivalent method to retrieve followers:

public long findMostFollowersPath(String account) { List followers = tc.getFollowers(account); long total = currentLevel > 0 ? followers.size() : 0; if (currentLevel 
    
      0; i--) { if (count[i-1] > max) { max = count[i-1]; } } return total + max; } return total; }
    

As our class is ready, we can prepare some unit tests: One to verify the call limit exceeds and another one to check the value returned with a non-greedy strategy:

public void nongreedyAlgorithmTest() { NonGreedyAlgorithm nga = new NonGreedyAlgorithm(prepareNetwork(), 0); Assertions.assertThrows(IllegalStateException.class, () -> { nga.findMostFollowersPath("root"); }); } public void nongreedyAlgorithmUnboundedTest() { SocialConnector sc = prepareNetwork(); sc.switchCounter(); NonGreedyAlgorithm nga = new NonGreedyAlgorithm(sc, 0); assertEquals(nga.findMostFollowersPath("root"), 6); }

4. Results

It's time to review our work!

First, we tried out our greedy strategy, checking its effectiveness. Then we verified the situation with an exhaustive search, with and without the API limit.

Our quick greedy procedure, which makes locally optimal choices each time, returns a numeric value. On the other hand, we don't get anything from the non-greedy algorithm, due to an environment restriction.

Comparing the two methods' output, we can understand how our greedy strategy saved us, even if the retrieved value that is not optimal. We can call it a local optimum.

5. Conclusion

In veränderlichen und sich schnell ändernden Kontexten wie Social Media können Probleme, die eine optimale Lösung erfordern, zu einer schrecklichen Chimäre werden: Schwer zu erreichen und gleichzeitig unrealistisch.

Das Überwinden von Einschränkungen und das Optimieren von API-Aufrufen ist ein ziemliches Thema, aber wie wir bereits besprochen haben, sind gierige Strategien effektiv. Die Wahl dieses Ansatzes erspart uns viel Schmerz und liefert im Austausch wertvolle Ergebnisse.

Denken Sie daran, dass nicht jede Situation geeignet ist: Wir müssen unsere Umstände jedes Mal bewerten.

Wie immer ist der Beispielcode aus diesem Tutorial auf GitHub verfügbar.