Introduktion til grådige algoritmer med Java

1. Introduktion

I denne vejledning skal vi introducere grådige algoritmer i Java-økosystemet.

2. Grådigt problem

Når du står over for et matematisk problem, kan der være flere måder at designe en løsning på. Vi kan implementere en iterativ løsning eller nogle avancerede teknikker, såsom opdele og erobre princip (fx Quicksort-algoritme) eller tilgang med dynamisk programmering (fx Knapsack-problem) og mange flere.

Det meste af tiden søger vi efter en optimal løsning, men desværre får vi ikke altid et sådant resultat. Der er dog tilfælde, hvor selv et suboptimalt resultat er værdifuldt. Ved hjælp af nogle specifikke strategier eller heuristikker , måske tjener vi os selv sådan en dyrebar belønning.

I denne sammenhæng givet et delbart problem, en strategi, der på hvert trin i processen tager det lokalt optimale valg eller "grådigt valg" kaldes en grådig algoritme.

Vi sagde, at vi skulle tage fat på et "delbart" problem: En situation, der kan beskrives som et sæt underproblemer med næsten de samme egenskaber. Som en konsekvens, det meste af tiden, en grådig algoritme vil blive implementeret som en rekursiv algoritme.

En grådig algoritme kan være en måde at føre os til en rimelig løsning på trods af et hårdt miljø; mangel på beregningsressourcer, begrænsning af eksekveringstid, API-begrænsninger eller andre former for begrænsninger.

2.1. Scenarie

I denne korte vejledning implementerer vi en grådig strategi for at udtrække data fra et socialt netværk ved hjælp af dets API.

Lad os sige, at vi gerne vil nå ud til flere brugere på det "lille-blå-fugl" sociale. Den bedste måde at nå vores mål er at sende oprindeligt indhold eller re-tweet noget, der vil vække interesse for et bredt publikum.

Hvordan finder vi et sådant publikum? Nå, vi skal finde en konto med mange tilhængere og tweet noget indhold til dem.

2.2. Klassisk mod grådig

Vi tager højde for følgende situation: Vores konto har fire tilhængere, som hver har, som vist i billedet nedenfor, henholdsvis 2, 2, 1 og 3 tilhængere og så videre:

Med dette formål i vores sind tager vi den med flere tilhængere blandt tilhængerne af vores konto. Derefter gentager vi processen to gange, indtil vi når 3. grad af forbindelse (i alt fire trin).

På denne måde definerer vi en sti lavet af brugere, der fører os til den største følgere-base fra vores konto. Hvis vi kan adressere noget indhold til dem, når de helt sikkert vores side.

Vi kan starte med en "traditionel" tilgang. Ved hvert enkelt trin udfører vi en forespørgsel for at få tilhængerne af en konto. Som et resultat af vores udvælgelsesproces vil antallet af konti stige hvert trin.

Overraskende nok vil vi i alt ende med at udføre 25 forespørgsler:

Her opstår et problem: For eksempel begrænser Twitter API denne type forespørgsel til 15 hvert 15. minut. Hvis vi prøver at foretage flere opkald end tilladt, får vi en “Satsgrænse overskredet kode - 88“, Eller“Returneret i API v1.1, når en anmodning ikke kan leveres på grund af, at applikationens hastighedsgrænse er opbrugt for ressourcen“. Hvordan kan vi overvinde en sådan grænse?

Svaret ligger lige foran os: En grådig algoritme. Hvis vi bruger denne tilgang ved hvert trin, kan vi antage, at brugeren med flest tilhængere er den eneste, der skal overveje: I sidste ende har vi kun brug for fire forespørgsler. En hel forbedring!

Resultatet af disse to tilgange vil være anderledes. I det første tilfælde får vi 16, den optimale løsning, mens i sidstnævnte er det maksimale antal tilgængelige følgere kun 12.

Vil denne forskel være så værdifuld? Vi beslutter senere.

3. Implementering

For at implementere ovenstående logik initialiserer vi et lille Java-program, hvor vi efterligner Twitter API. Vi bruger også Lombok-biblioteket.

Lad os nu definere vores komponent SocialConnector hvor vi implementerer vores logik. Bemærk, at vi lægger en tæller for at simulere opkaldsbegrænsninger, men vi sænker den til fire:

public class SocialConnector {private boolean isCounterEnabled = true; privat int-tæller = 4; @Getter @Setter Liste brugere; offentlig SocialConnector () {brugere = ny ArrayList (); } offentlig boolsk switchCounter () {this.isCounterEnabled =! this.isCounterEnabled; returner dette.isCounterEnabled; }} 

Derefter tilføjer vi en metode til at hente tilhængernes liste over en bestemt konto:

public List getFollowers (String-konto) {if (counter <0) {throw new IllegalStateException ("API-grænse nået"); } ellers {if (this.isCounterEnabled) {counter--; } for (SocialUser-bruger: brugere) {hvis (user.getUsername (). er lig med (konto)) {return user.getFollowers (); }}} returner ny ArrayList (); } 

For at understøtte vores proces har vi brug for nogle klasser for at modellere vores brugerenhed:

offentlig klasse Socialbruger {@Getter privat String-brugernavn; @Getter private Liste tilhængere; @Override offentlige boolske er lig med (Objekt obj) {return ((SocialUser) obj) .getUsername (). Er lig med (brugernavn); } offentlig Socialbruger (streng brugernavn) {this.username = brugernavn; this.followers = ny ArrayList (); } public SocialUser (String username, List followers) {this.username = username; this.followers = tilhængere; } public void addFollowers (List followers) {this.followers.addAll (followers); }}

3.1. Grådig algoritme

Endelig er det tid til at implementere vores grådige strategi, så lad os tilføje en ny komponent - Grådig algoritme - hvor vi udfører rekursionen:

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

Så er vi nødt til at indsætte en metode findMostFollowersPath hvor vi finder brugeren med flest tilhængere, tæller dem og fortsætter til næste trin:

offentlig lang findMostFollowersPath (strengkonto) {lang maks = 0; Socialbruger tilFølg = null; Liste over tilhængere = sc.getFollowers (konto); for (SocialUser el: followers) {long followersCount = el.getFollowersCount (); hvis (followersCount> max) {toFollow = el; max = followersCount; }} hvis (currentLevel <maxLevel - 1) {currentLevel ++; max + = findMostFollowersPath (toFollow.getUsername ()); } returnere maks. }

Husk: Her udfører vi et grådigt valg. Som sådan, hver gang vi kalder denne metode, vi vælger et og kun et element fra listen og gå videre: Vi vil aldrig nogensinde gå tilbage på vores beslutninger!

Perfekt! Vi er klar til at gå, og vi kan teste vores ansøgning. Før det skal vi huske at udfylde vores lille netværk og endelig udføre følgende enhedstest:

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

3.2. Ikke-grådig algoritme

Lad os oprette en ikke-grådig metode, blot for at kontrollere med vores øjne, hvad der sker. Så vi er nødt til at starte med at bygge en Ikke-grådig algoritme klasse:

offentlig klasse NonGreedyAlgorithm {int currentLevel = 0; final int maxLevel = 3; SocialConnector tc; offentlig NonGreedyAlgorithm (SocialConnector tc, int niveau) {this.tc = tc; this.currentLevel = niveau; }}

Lad os oprette en tilsvarende metode til at hente følgere:

public long findMostFollowersPath (String-konto) {List followers = tc.getFollowers (account); lang total = nuværende niveau> 0? followers.størrelse (): 0; hvis (nuværende niveau  0; i--) {if (count [i-1]> max) {max = count [i-1]; }} returnerer alt + maks. } returnere i alt; }

Da vores klasse er klar, kan vi forberede nogle enhedstest: En til at kontrollere opkaldsgrænsen overstiger og en anden til at kontrollere værdien, der returneres med en ikke-grådig strategi:

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 = ny NonGreedyAlgorithm (sc, 0); assertEquals (nga.findMostFollowersPath ("root"), 6); }

4. Resultater

Det er tid til at gennemgå vores arbejde!

Først prøvede vi vores grådige strategi og kontrollerede dens effektivitet. Derefter bekræftede vi situationen med en udtømmende søgning med og uden API-grænsen.

Vores hurtige grådige procedure, der foretager lokalt optimale valg hver gang, returnerer en numerisk værdi. På den anden side får vi ikke noget fra den ikke-grådige algoritme på grund af en miljøbegrænsning.

Sammenligning af de to metoders output kan vi forstå, hvordan vores grådige strategi reddede os, selvom den hentede værdi ikke er optimal. Vi kan kalde det et lokalt optimalt.

5. Konklusion

I foranderlige og hurtigt skiftende sammenhænge som sociale medier kan problemer, der kræver at finde en optimal løsning, blive en forfærdelig kimære: Svær at nå og samtidig urealistisk.

At overvinde begrænsninger og optimere API-opkald er et ganske tema, men som vi har diskuteret, er grådige strategier effektive. At vælge denne type tilgang sparer os for meget smerte og returnerer værdifulde resultater til gengæld.

Husk, at ikke alle situationer er egnede: Vi skal evaluere vores forhold hver gang.

Som altid er eksempelkoden fra denne vejledning tilgængelig på GitHub.