Introduksjon til grådige algoritmer med Java

1. Introduksjon

I denne opplæringen skal vi introdusere grådige algoritmer i Java-økosystemet.

2. Grådig problem

Når du står overfor et matematisk problem, kan det være flere måter å utforme en løsning på. Vi kan implementere en iterativ løsning, eller noen avanserte teknikker, slik som delings- og erobringsprinsipp (f.eks. Quicksort-algoritme) eller tilnærming med dynamisk programmering (f.eks. Knapsack-problem) og mange flere.

Mesteparten av tiden søker vi etter en optimal løsning, men dessverre får vi ikke alltid et slikt resultat. Imidlertid er det tilfeller der selv et suboptimalt resultat er verdifullt. Ved hjelp av noen spesifikke strategier, eller heuristikker , vi kan tjene oss en så dyrebar belønning.

I denne sammenheng gitt et delbart problem, en strategi som på hvert trinn i prosessen tar det lokalt optimale valget eller "grådige valg" kalles en grådig algoritme.

Vi uttalte at vi skulle ta tak i et "delbart" problem: En situasjon som kan beskrives som et sett med underproblemer med nesten de samme egenskapene. Som en konsekvens, en grådig algoritme vil bli implementert som en rekursiv algoritme.

En grådig algoritme kan være en måte å føre oss til en rimelig løsning til tross for et tøft miljø; mangel på beregningsressurser, tidsbegrensning for kjøring, API-begrensninger eller andre former for begrensninger.

2.1. Scenario

I denne korte opplæringen skal vi implementere en grådig strategi for å trekke ut data fra et sosialt nettverk ved hjelp av API-en.

La oss si at vi vil nå ut til flere brukere på det "lille-blå-fugl" -samfunnet. Den beste måten å nå vårt mål er å legge ut originalt innhold eller tweet på nytt som vil vekke interesse for et bredt publikum.

Hvordan finner vi et slikt publikum? Vi må finne en konto med mange følgere og tweet noe innhold til dem.

2.2. Klassisk mot grådig

Vi tar hensyn til følgende situasjon: Kontoen vår har fire følgere, som hver har, som avbildet i bildet nedenfor, henholdsvis 2, 2, 1 og 3 følgere, og så videre:

Med dette formålet i tankene våre, tar vi den med flere tilhengere blant tilhengerne av kontoen vår. Deretter gjentar vi prosessen to ganger til vi når 3. grad av tilkobling (totalt fire trinn).

På denne måten definerer vi en bane laget av brukere, som fører oss til den største følgere-basen fra kontoen vår. Hvis vi kan adressere noe innhold til dem, kommer de helt sikkert til siden vår.

Vi kan starte med en “tradisjonell” tilnærming. Ved hvert trinn vil vi utføre et spørsmål for å få følgere av en konto. Som et resultat av utvelgelsesprosessen vil antall kontoer øke hvert trinn.

Overraskende nok vil vi totalt utføre 25 spørsmål:

Her oppstår et problem: For eksempel begrenser Twitter API denne typen spørsmål til 15 hvert 15. minutt. Hvis vi prøver å utføre flere samtaler enn tillatt, får vi en “Satsgrense overskredet kode - 88“, Eller“Returnert i API v1.1 når en forespørsel ikke kan serveres på grunn av at programmets hastighetsgrense er oppbrukt for ressursen“. Hvordan kan vi overvinne en slik grense?

Svaret ligger rett foran oss: En grådig algoritme. Hvis vi bruker denne tilnærmingen, i hvert trinn, kan vi anta at brukeren med flest følgere er den eneste som skal vurdere: Til slutt trenger vi bare fire spørsmål. Ganske en forbedring!

Resultatet av disse to tilnærmingene vil være forskjellig. I det første tilfellet får vi 16, den optimale løsningen, mens i sistnevnte er det maksimale antallet tilgjengelige følgere bare 12.

Vil denne forskjellen være så verdifull? Vi bestemmer oss senere.

3. Gjennomføring

For å implementere ovennevnte logikk initialiserer vi et lite Java-program, der vi etterligner Twitter API. Vi bruker også Lombok-biblioteket.

La oss nå definere komponenten vår SocialConnector der vi implementerer logikken vår. Merk at vi skal sette en teller for å simulere samtalebegrensninger, men vi senker den til fire:

public class SocialConnector {private boolean isCounterEnabled = true; privat int-teller = 4; @Getter @Setter List brukere; offentlig SocialConnector () {brukere = ny ArrayList (); } offentlig boolsk switchCounter () {this.isCounterEnabled =! this.isCounterEnabled; returner dette.isCounterEnabled; }} 

Deretter skal vi legge til en metode for å hente tilhengernes liste over en bestemt konto:

public List getFollowers (String-konto) {if (counter <0) {throw new IllegalStateException ("API-grense nådd"); } annet {if (this.isCounterEnabled) {counter--; } for (SocialUser bruker: brukere) {if (user.getUsername (). er lik (konto)) {return user.getFollowers (); }}} returner ny ArrayList (); } 

For å støtte prosessen vår trenger vi noen klasser for å modellere brukerenheten vår:

offentlig klasse SocialUser {@Getter private String brukernavn; @Getter private Listefølgere; @Override public boolean equals (Object obj) {return ((SocialUser) obj) .getUsername (). Equals (username); } offentlig sosial bruker (streng brukernavn) {this.username = brukernavn; this.followers = new ArrayList (); } public SocialUser (String username, List followers) {this.username = username; this.followers = følgere; } public void addFollowers (List followers) {this.followers.addAll (followers); }}

3.1. Grådig algoritme

Endelig er det på tide å implementere vår grådige strategi, så la oss legge til en ny komponent - Grådig algoritme - der vi skal utføre rekursjonen:

offentlig klasse Grådig algoritme {int currentLevel = 0; final int maxLevel = 3; SocialConnector sc; public GreedyAlgorithm (SocialConnector sc) {this.sc = sc; }}

Da må vi sette inn en metode findMostFollowersPath der vi finner brukeren med flest følgere, teller dem og fortsetter til neste trinn:

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

Huske: Her utfører vi et grådig valg. Som sådan, hver gang vi kaller denne metoden, vi velger ett og bare ett element fra listen og gå videre: Vi vil aldri gå tilbake på våre beslutninger!

Perfekt! Vi er klare til å gå, og vi kan teste søknaden vår. Før det må vi huske å fylle ut vårt lille nettverk og til slutt utføre følgende enhetstest:

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

3.2. Ikke-grådig algoritme

La oss lage en ikke-grådig metode, bare for å sjekke med øynene hva som skjer. Så vi må begynne med å bygge en Ikke grådig algoritme klasse:

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

La oss lage en tilsvarende metode for å hente følgere:

public long findMostFollowersPath (String account) {List followers = tc.getFollowers (account); lang total = gjeldende nivå> 0? followers.size (): 0; hvis (nåværende nivå  0; i--) {if (count [i-1]> max) {max = count [i-1]; }} returnerer totalt + maks; } retur totalt; }

Ettersom klassen vår er klar, kan vi forberede noen enhetstester: En for å bekrefte at samtalegrensen overstiger, og en annen for å sjekke verdien som 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 = new NonGreedyAlgorithm (sc, 0); assertEquals (nga.findMostFollowersPath ("root"), 6); }

4. Resultater

Det er på tide å gjennomgå arbeidet vårt!

Først prøvde vi ut vår grådige strategi ved å kontrollere effektiviteten. Så bekreftet vi situasjonen med et uttømmende søk, med og uten API-grensen.

Vår raske grådige prosedyre, som tar lokale optimale valg hver gang, gir en numerisk verdi. På den annen side får vi ikke noe fra den ikke-grådige algoritmen, på grunn av en miljøbegrensning.

Ved å sammenligne de to metodene, kan vi forstå hvordan vår grådige strategi reddet oss, selv om den hentede verdien ikke er optimal. Vi kan kalle det et lokalt optimalt.

5. Konklusjon

I foranderlige og raskt skiftende sammenhenger som sosiale medier kan problemer som krever å finne en optimal løsning bli en fryktelig kimære: vanskelig å nå og samtidig urealistisk.

Å overvinne begrensninger og optimalisere API-samtaler er ganske tema, men som vi har diskutert, er grådige strategier effektive. Å velge denne typen tilnærming sparer oss for mye smerte og gir verdifulle resultater i bytte.

Husk at ikke alle situasjoner er passende: Vi må evaluere forholdene våre hver gang.

Som alltid er eksempelkoden fra denne opplæringen tilgjengelig på GitHub.