streamalism.org

1. Uvod

U ovom uputstvu idemo uvesti pohlepne algoritme u ekosustav Java.

2. Pohlepni problem

Kad se suočite s matematičkim problemom, postoji nekoliko načina za oblikovanje rješenja. Možemo implementirati iterativno rješenje ili neke napredne tehnike, poput principa podijeli i osvoji (npr. Quicksort algoritam) ili pristup s dinamičkim programiranjem (npr. Knapsack problem) i mnogim drugima.

Većinu vremena tražimo optimalno rješenje, ali nažalost, ne postižemo uvijek takav ishod. Međutim, postoje slučajevi kada je čak i neoptimalan rezultat vrijedan. Uz pomoć nekih specifičnih strategija ili heuristike , mogli bismo si zaraditi tako dragocjenu nagradu.

U tom kontekstu, s obzirom na djeljivi problem, strategija koja u svakoj fazi procesa zauzima lokalno optimalan izbor ili "pohlepni izbor" naziva se pohlepnim algoritmom.

Izjavili smo da bismo se trebali pozabaviti "djeljivim" problemom: situacijom koja se može opisati kao skup potproblema s, gotovo, istim karakteristikama. Kao posljedica toga, većinu vremena, a pohlepni algoritam bit će implementiran kao rekurzivni algoritam.

Pohlepni algoritam može nas dovesti do razumnog rješenja unatoč surovom okruženju; nedostatak računalnih resursa, ograničenje vremena izvršenja, API ograničenja ili bilo koje druge vrste ograničenja.

2.1. Scenarij

U ovom kratkom vodiču implementirat ćemo pohlepnu strategiju za izdvajanje podataka s društvene mreže pomoću njezinog API-ja.

Recimo da bismo željeli dosegnuti više korisnika na društvenoj mreži "mala plava ptica". Najbolji način za postizanje našeg cilja je objavljivanje izvornog sadržaja ili ponovno tvitovanje nečega što će pobuditi neko zanimanje široke publike.

Kako pronaći takvu publiku? Pa, moramo pronaći račun s mnogim sljedbenicima i objaviti neki sadržaj za njih.

2.2. Klasika protiv pohlepnika

Uzimamo u obzir sljedeću situaciju: Naš račun ima četiri sljedbenika, od kojih svaki ima, kao što je prikazano na donjoj slici, 2, 2, 1 i 3 sljedbenika, i tako dalje:

S ovom svrhom u mislima, među sljedbenike našeg računa uvest ćemo onu s više sljedbenika. Zatim ćemo postupak ponoviti još dva puta dok ne dosegnemo 3. stupanj povezanosti (ukupno četiri koraka).

Na taj način definiramo put napravljen od korisnika koji nas vodi do najveće baze sljedbenika s našeg računa. Ako im uspijemo uputiti neki sadržaj, sigurno će doći na našu stranicu.

Možemo započeti s „tradicionalnim“ pristupom. U svakom pojedinom koraku izvršit ćemo upit kako bismo privukli sljedbenike računa. Kao rezultat našeg postupka odabira, broj računa će se povećavati u svakom koraku.

Iznenađujuće, ukupno bismo na kraju izveli 25 upita:

Ovdje se pojavljuje problem: Primjerice, Twitter API ograničava ovu vrstu upita na 15 svakih 15 minuta. Ako pokušamo obaviti više poziva nego što je dopušteno, dobit ćemo "Ograničenje cijene premašeno je kodom - 88", ili "Vraća se u API v1.1 kada se zahtjev ne može poslužiti zbog iscrpljenog ograničenja brzine aplikacije za resurs“. Kako možemo prevladati takvu granicu?

Pa, odgovor je pred nama: Pohlepni algoritam. Ako se poslužimo ovim pristupom, u svakom koraku možemo pretpostaviti da je jedini korisnik koji ima najviše sljedbenika: Na kraju trebamo samo četiri upita. Prilično poboljšanje!

Ishod ta dva pristupa bit će različit. U prvom slučaju dobivamo 16, optimalno rješenje, dok je u potonjem maksimalan broj dostupnih sljedbenika tek 12.

Hoće li ta razlika biti toliko vrijedna? Odlučit ćemo kasnije.

3. Provedba

Da bismo implementirali gornju logiku, inicijaliziramo mali Java program, gdje ćemo oponašati Twitter API. Također ćemo se poslužiti knjižnicom Lombok.

Sada, definirajmo našu komponentu SocialConnector u kojem ćemo implementirati našu logiku. Imajte na umu da ćemo staviti brojač za simulaciju ograničenja poziva, ali snizit ćemo ga na četiri:

javna klasa SocialConnector {private boolean isCounterEnabled = true; privatni brojač int = 4; @Getter @Setter Popis korisnika; javni SocialConnector () {korisnici = novi ArrayList (); } public boolean switchCounter () {this.isCounterEnabled =! this.isCounterEnabled; vrati this.isCounterEnabled; }} 

Zatim ćemo dodati metodu za dohvaćanje popisa sljedbenika određenog računa:

javni popis getFollowers (račun niza) {if (brojač <0) {baciti novi IllegalStateException ("dosegnuto ograničenje API-ja"); } else {if (this.isCounterEnabled) {counter--; } za (SocialUser korisnik: korisnici) {if (user.getUsername (). je jednako (račun)) {return user.getFollowers (); }}} return new ArrayList (); } 

Da bismo podržali naš proces, trebaju nam neke klase za modeliranje našeg korisničkog entiteta:

javna klasa SocialUser {@Getter private String korisničko ime; @Getter private Lista sljedbenika; @Override public boolean equals (Object obj) {return ((SocialUser) obj) .getUsername (). Equals (korisničko ime); } javni SocialUser (korisničko ime niza) {this.username = korisničko ime; this.followers = novi ArrayList (); } javni SocialUser (korisničko ime niza, sljedbenici popisa) {this.username = korisničko ime; this.followers = sljedbenici; } public void addFollowers (Popis sljedbenika) {this.followers.addAll (sljedbenici); }}

3.1. Pohlepni algoritam

Napokon, vrijeme je da provedemo našu pohlepnu strategiju, pa dodajmo novu komponentu - Pohlepni algoritam - u kojem ćemo izvesti rekurziju:

javni razred GreedyAlgorithm {int currentLevel = 0; konačni int maxLevel = 3; SocialConnector sc; javni GreedyAlgorithm (SocialConnector sc) {this.sc = sc; }}

Zatim moramo umetnuti metodu findMostFollowersPath u kojem ćemo pronaći korisnika s većinom sljedbenika, prebrojati ih, a zatim prijeći na sljedeći korak:

javni long findMostFollowersPath (niz računa) {long max = 0; SocialUser toFollow = null; Popis sljedbenika = sc.getFollowers (račun); za (SocialUser el: followers) {long followersCount = el.getFollowersCount (); if (followersCount> max) {toFollow = el; max = followersCount; }} if (currentLevel <maxLevel - 1) {currentLevel ++; max + = findMostFollowersPath (toFollow.getUsername ()); } povratak max; }

Zapamtiti: Ovdje izvodimo pohlepni izbor. Kao takav, svaki put kad pozovemo ovu metodu, izabrat ćemo jedan i samo jedan element s popisa i krenite dalje: Nikada se nećemo vraćati svojim odlukama!

Savršen! Spremni smo za početak i možemo testirati našu prijavu. Prije toga moramo se sjetiti popuniti našu sićušnu mrežu i na kraju izvršiti sljedeći jedinični test:

javna praznina greedyAlgorithmTest () {GreedyAlgorithm ga = novi GreedyAlgorithm (pripremitiNetwork ()); assertEquals (ga.findMostFollowersPath ("root"), 5); }

3.2. Nepohlepni algoritam

Stvorimo ne pohlepnu metodu, samo da provjerimo svojim očima što se događa. Dakle, moramo započeti s izradom a NonGreedyAlgorithm razred:

javna klasa NonGreedyAlgorithm {int currentLevel = 0; konačni int maxLevel = 3; SocialConnector tc; javni NonGreedyAlgorithm (SocialConnector tc, int razina) {this.tc = tc; this.currentLevel = level; }}

Stvorimo ekvivalentnu metodu za preuzimanje sljedbenika:

public long findMostFollowersPath (String account) {Popis sljedbenika = tc.getFollowers (račun); dugo ukupno = trenutni nivo> 0? followers.size (): 0; if (currentLevel  0; i--) {if (count [i-1]> max) {max = count [i-1]; }} povratak ukupno + max; } ukupni povrat; }

Kako je naša klasa spremna, možemo pripremiti neke jedinične testove: Jedan za provjeru premašenog ograničenja poziva i drugi za provjeru vraćene vrijednosti s ne pohlepnom strategijom:

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

4. Rezultati

Vrijeme je da pregledate naš rad!

Prvo smo isprobali našu pohlepnu strategiju, provjeravajući njezinu učinkovitost. Zatim smo situaciju provjerili iscrpnom pretragom, sa i bez ograničenja API-ja.

Naš brzi pohlepni postupak, koji svaki put donosi lokalno optimalne izbore, vraća numeričku vrijednost. S druge strane, iz nepohlepnog algoritma ne dobivamo ništa zbog ograničenja okoline.

Uspoređujući izlaz dvije metode, možemo razumjeti kako nas je pohlepna strategija spasila, čak i ako je preuzeta vrijednost koja nije optimalna. To možemo nazvati lokalnim optimumom.

5. Zaključak

U promjenjivom kontekstu koji se brzo mijenja, poput društvenih medija, problemi koji zahtijevaju pronalaženje optimalnog rješenja mogu postati stravična himera: teško dostupna i istodobno nerealna.

Prevladavanje ograničenja i optimizacija API poziva prilično je tema, ali, kao što smo razgovarali, pohlepne strategije su učinkovite. Odabir ove vrste pristupa štedi nam mnogo boli, vraćajući vrijedne rezultate u zamjenu.

Imajte na umu da nije svaka situacija prikladna: svaki put moramo procijeniti svoje okolnosti.

Kao i uvijek, primjer koda iz ovog vodiča dostupan je na GitHubu.