Inleiding tot hebzuchtige algoritmen met Java

1. Inleiding

In deze tutorial gaan we dat doen hebzuchtige algoritmen introduceren in het Java-ecosysteem.

2. Hebzuchtig probleem

Wanneer u met een wiskundig probleem wordt geconfronteerd, kunnen er verschillende manieren zijn om een ​​oplossing te ontwerpen. We kunnen een iteratieve oplossing implementeren, of enkele geavanceerde technieken, zoals het verdeel en heersprincipe (bijv. Quicksort-algoritme) of benadering met dynamische programmering (bijv. Knapzakprobleem) en nog veel meer.

Meestal zoeken we naar een optimale oplossing, maar helaas krijgen we niet altijd zo'n uitkomst. Er zijn echter gevallen waarin zelfs een suboptimaal resultaat waardevol is. Met behulp van enkele specifieke strategieën of heuristieken , we kunnen onszelf zo'n kostbare beloning verdienen.

In deze context, gegeven een deelbaar probleem, een strategie die in elke fase van het proces de lokaal optimale keuze of "hebzuchtige keuze" neemt, wordt een hebzuchtig algoritme genoemd.

We stelden dat we een "deelbaar" probleem moesten aanpakken: een situatie die kan worden omschreven als een reeks subproblemen met bijna dezelfde kenmerken. Als gevolg hiervan, meestal een hebberig algoritme zal worden geïmplementeerd als een recursief algoritme.

Een hebberig algoritme kan een manier zijn om ons ondanks een barre omgeving naar een redelijke oplossing te leiden; gebrek aan rekenbronnen, beperking van de uitvoeringstijd, API-beperkingen of enige andere soort beperkingen.

2.1. Scenario

In deze korte tutorial gaan we een hebzuchtige strategie implementeren om gegevens uit een sociaal netwerk te extraheren met behulp van de API.

Laten we zeggen dat we graag meer gebruikers willen bereiken op de "little-blue-bird" social media. De beste manier om ons doel te bereiken, is door originele inhoud te posten of iets opnieuw te tweeten dat enige interesse wekt bij een breed publiek.

Hoe vinden we zo'n publiek? Welnu, we moeten een account met veel volgers vinden en wat inhoud voor hen tweeten.

2.2. Klassiek versus hebzuchtig

We houden rekening met de volgende situatie: Ons account heeft vier volgers, die elk, zoals weergegeven in de afbeelding hieronder, respectievelijk 2, 2, 1 en 3 volgers hebben, enzovoort:

Met dit doel in gedachten, zullen we degene met meer volgers onder de volgers van ons account nemen. Daarna herhalen we het proces nog twee keer totdat we de 3e graad van verbinding bereiken (vier stappen in totaal).

Op deze manier definiëren we een pad gemaakt van gebruikers, dat ons naar de grootste volgersbasis van ons account leidt. Als we wat inhoud aan hen kunnen richten, zullen ze zeker onze pagina bereiken.

We kunnen beginnen met een “traditionele” aanpak. Bij elke stap voeren we een zoekopdracht uit om de volgers van een account te krijgen. Als resultaat van ons selectieproces zal het aantal accounts bij elke stap toenemen.

Verrassend genoeg zouden we uiteindelijk 25 zoekopdrachten uitvoeren:

Hier doet zich een probleem voor: de Twitter API beperkt dit type zoekopdracht bijvoorbeeld tot 15 elke 15 minuten. Als we proberen meer oproepen uit te voeren dan is toegestaan, krijgen we een 'Snelheidslimiet overschreden code - 88‘Of’Geretourneerd in API v1.1 wanneer een verzoek niet kan worden verwerkt omdat de snelheidslimiet van de toepassing voor de bron is opgebruikt“. Hoe kunnen we een dergelijke limiet overwinnen?

Welnu, het antwoord ligt vlak voor ons: een hebberig algoritme. Als we deze aanpak gebruiken, kunnen we bij elke stap aannemen dat de gebruiker met de meeste volgers de enige is die in overweging moet worden genomen: uiteindelijk hebben we slechts vier vragen nodig. Een hele verbetering!

De uitkomst van deze twee benaderingen zal verschillend zijn. In het eerste geval krijgen we 16, de optimale oplossing, terwijl in het laatste het maximale aantal bereikbare volgers slechts 12 is.

Zal dit verschil zo waardevol zijn? We beslissen later.

3. Implementatie

Om de bovenstaande logica te implementeren, initialiseren we een klein Java-programma, waarin we de Twitter API nabootsen. We maken ook gebruik van de bibliotheek van Lombok.

Laten we nu onze component definiëren SocialConnector waarin we onze logica zullen implementeren. Merk op dat we een teller gaan plaatsen om oproepbeperkingen te simuleren, maar we zullen deze verlagen tot vier:

openbare klasse SocialConnector {privé boolean isCounterEnabled = true; privé int teller = 4; @Getter @Setter List-gebruikers; openbare SocialConnector () {gebruikers = nieuwe ArrayList (); } openbare boolean switchCounter () {this.isCounterEnabled =! this.isCounterEnabled; retourneer this.isCounterEnabled; }} 

Vervolgens gaan we een methode toevoegen om de lijst met volgers van een specifiek account op te halen:

openbare lijst getFollowers (String-account) {if (counter <0) {throw new IllegalStateException ("API-limiet bereikt"); } else {if (this.isCounterEnabled) {counter--; } voor (SocialUser-gebruiker: gebruikers) {if (user.getUsername (). equals (account)) {return user.getFollowers (); }}} retourneer nieuwe ArrayList (); } 

Om ons proces te ondersteunen, hebben we enkele klassen nodig om onze gebruikersentiteit te modelleren:

openbare klasse SocialUser {@Getter private String gebruikersnaam; @Getter privélijst volgers; @Override public boolean is gelijk aan (Object obj) {return ((SocialUser) obj) .getUsername (). Equals (gebruikersnaam); } openbare SocialUser (String gebruikersnaam) {this.username = gebruikersnaam; this.followers = nieuwe ArrayList (); } openbare SocialUser (String gebruikersnaam, lijstvolgers) {this.username = gebruikersnaam; this.followers = volgers; } openbare ongeldige addFollowers (lijstvolgers) {this.followers.addAll (volgers); }}

3.1. Hebzuchtig algoritme

Eindelijk is het tijd om onze hebzuchtige strategie te implementeren, dus laten we een nieuw onderdeel toevoegen - Hebzuchtig algoritme - waarin we de recursie uitvoeren:

openbare klasse GreedyAlgorithm {int currentLevel = 0; laatste int maxLevel = 3; SocialConnector sc; openbaar GreedyAlgorithm (SocialConnector sc) {this.sc = sc; }}

Dan moeten we een methode invoegen findMostFollowersPath waarin we de gebruiker met de meeste volgers vinden, ze tellen en dan doorgaan naar de volgende stap:

openbaar lang findMostFollowersPath (String-account) {long max = 0; SocialUser toFollow = null; Lijst met volgers = sc.getFollowers (account); voor (SocialUser el: volgers) {lange followersCount = el.getFollowersCount (); if (followersCount> max) {toFollow = el; max = volgersaantal; }} if (currentLevel <maxLevel - 1) {currentLevel ++; max + = findMostFollowersPath (toFollow.getUsername ()); } terugkeer max; }

Onthouden: Hier maken we een hebzuchtige keuze. Elke keer dat we deze methode noemen, we kiezen één en slechts één element van de lijst en ga verder: we zullen nooit meer terugkomen op onze beslissingen!

Perfect! We zijn er klaar voor en we kunnen onze applicatie testen. Daarvoor moeten we onthouden om ons kleine netwerk te vullen en ten slotte de volgende eenheidstest uit te voeren:

openbare leegte greedyAlgorithmTest () {GreedyAlgorithm ga = nieuw GreedyAlgorithm (preparNetwork ()); assertEquals (ga.findMostFollowersPath ("root"), 5); }

3.2. Niet-hebzuchtig algoritme

Laten we een niet-hebzuchtige methode bedenken, alleen maar om met onze ogen te kijken wat er gebeurt. We moeten dus beginnen met het bouwen van een Niet-hebzuchtig algoritme klasse:

openbare klasse NonGreedyAlgorithm {int currentLevel = 0; laatste int maxLevel = 3; SocialConnector tc; openbaar NonGreedyAlgorithm (SocialConnector tc, int level) {this.tc = tc; this.currentLevel = niveau; }}

Laten we een gelijkwaardige methode maken om volgers op te halen:

openbare long findMostFollowersPath (String-account) {List followers = tc.getFollowers (account); lang totaal = currentLevel> 0? volgers.size (): 0; if (currentLevel  0; i--) {if (count [i-1]> max) {max = count [i-1]; }} retourneer totaal + max; } totaal retourneren; }

Als onze klas klaar is, kunnen we enkele eenheidstests voorbereiden: een om te verifiëren dat de oproeplimiet overschreden is en een andere om de geretourneerde waarde te controleren met een niet-hebzuchtige strategie:

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

4. Resultaten

Het is tijd om ons werk te herzien!

Eerst hebben we onze hebzuchtige strategie uitgeprobeerd en de doeltreffendheid ervan gecontroleerd. Vervolgens hebben we de situatie geverifieerd met een uitgebreide zoekopdracht, met en zonder de API-limiet.

Onze snelle hebzuchtige procedure, die telkens lokaal optimale keuzes maakt, levert een numerieke waarde op. Aan de andere kant krijgen we niets van het niet-hebzuchtige algoritme, vanwege een omgevingsbeperking.

Als we de output van de twee methoden vergelijken, kunnen we begrijpen hoe onze hebzuchtige strategie ons heeft gered, zelfs als de opgehaalde waarde niet optimaal is. We kunnen het een lokaal optimum noemen.

5. Conclusie

In veranderlijke en snel veranderende contexten zoals sociale media, kunnen problemen waarvoor een optimale oplossing moet worden gevonden, een vreselijke hersenschim worden: moeilijk te bereiken en tegelijkertijd onrealistisch.

Beperkingen overwinnen en API-aanroepen optimaliseren is nogal een thema, maar, zoals we hebben besproken, hebzuchtige strategieën zijn effectief. Het kiezen van dit soort benadering bespaart ons veel pijn en levert in ruil waardevolle resultaten op.

Houd er rekening mee dat niet elke situatie geschikt is: we moeten onze omstandigheden elke keer evalueren.

Zoals altijd is de voorbeeldcode van deze tutorial beschikbaar op GitHub.


$config[zx-auto] not found$config[zx-overlay] not found