streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban fogunk mohó algoritmusokat vezet be a Java ökoszisztémában.

2. Kapzsi probléma

Matematikai problémával szembesülve többféle módon lehet megoldást megtervezni. Megvalósíthatunk iteratív megoldást, vagy néhány fejlett technikát, mint például a divide and conquer elv (pl. Quicksort algoritmus) vagy a megközelítés dinamikus programozással (pl. Knapsack probléma) és még sok más.

Legtöbbször optimális megoldást keresünk, de sajnos nem mindig kapunk ilyen eredményt. Vannak azonban olyan esetek, amikor még a nem optimális eredmény is értékes. Néhány konkrét stratégia vagy heurisztika segítségével , kereshetünk magunknak ilyen értékes jutalmat.

Ebben az összefüggésben, tekintettel egy osztható problémára, azt a stratégiát, amely a folyamat minden szakaszában a lokálisan optimális választást vagy „kapzsi választást” választja, kapzsi algoritmusnak nevezzük.

Kijelentettük, hogy foglalkoznunk kell egy „osztható” problémával: Olyan helyzet, amelyet szinte ugyanazokkal a tulajdonságokkal rendelkező részproblémákként lehet leírni. Ennek következtében legtöbbször a a kapzsi algoritmust rekurzív algoritmusként valósítják meg.

A kapzsi algoritmus módja lehet arra, hogy a zord környezet ellenére ésszerű megoldáshoz vezessen minket; számítási erőforrások hiánya, végrehajtási időbeli korlátozás, API korlátozások vagy bármilyen más korlátozás.

2.1. Forgatókönyv

Ebben a rövid bemutatóban mohó stratégiát fogunk megvalósítani, hogy adatokat nyerjünk ki egy közösségi hálózatból az API segítségével.

Tegyük fel, hogy több felhasználót szeretnénk elérni a „kis-kék-madár” közösségi oldalon. Célunk elérésének legjobb módja az eredeti tartalom közzététele, vagy újbóli tweetelés, amely a közönség érdeklődését váltja ki.

Hogyan találhatunk meg ilyen közönséget? Nos, meg kell találnunk egy fiókot sok követővel, és tweetelni kell nekik néhány tartalmat.

2.2. Klasszikus vs. kapzsi

A következő helyzetet vesszük figyelembe: Fiókunknak négy követője van, amelyek mindegyikének az alábbi képen látható módon 2, 2, 1 és 3 követője van, és így tovább:

Ezzel a céllal a fejünkben felvesszük azt, amelyiknek több követője van a számlánk követői között. Ezután még kétszer megismételjük a folyamatot, amíg el nem érjük a kapcsolat 3. fokát (összesen négy lépés).

Ily módon meghatározzuk a felhasználók útját, amely a számlánk legnagyobb követői bázisához vezet. Ha valamilyen tartalmat meg tudunk címezni nekik, akkor biztosan eljutnak az oldalunkra.

Kezdhetjük „hagyományos” megközelítéssel. Minden egyes lépésben végrehajtunk egy lekérdezést, hogy megszerezzük a fiók követőit. Kiválasztási folyamatunk eredményeként a fiókok száma minden lépésben növekszik.

Meglepő módon összesen 25 lekérdezést hajtunk végre:

Itt felmerül egy probléma: Például a Twitter API korlátozza az ilyen típusú lekérdezéseket 15 percenként 15-re. Ha a megengedettnél több hívást próbálunk végrehajtani, akkor egyA sebességhatár túllépte a kódot - 88VagyVisszaadva az API v1.1-ben, amikor egy kérést nem lehet kiszolgálni az erőforrás kimerült alkalmazás sebességkorlátozása miatt“. Hogyan lehet túllépni egy ilyen határt?

Nos, a válasz előttünk áll: kapzsi algoritmus. Ha ezt a megközelítést alkalmazzuk, akkor minden egyes lépésnél feltételezhetjük, hogy a legtöbb követővel rendelkező felhasználó az egyetlen, aki figyelembe veszi: Végül csak négy lekérdezésre van szükségünk. Elég javulás!

E két megközelítés eredménye eltérő lesz. Az első esetben 16-ot kapunk, az optimális megoldást, míg az utóbbiban az elérhető követők maximális száma csupán 12.

Ennyire értékes lesz ez a különbség? Majd később döntünk.

3. Végrehajtás

A fenti logika megvalósításához inicializálunk egy kis Java programot, ahol utánozzuk a Twitter API-t. Használjuk a Lombok könyvtárat is.

Most definiáljuk a komponensünket SocialConnector amelyben megvalósítjuk logikánkat. Ne feledje, hogy számlálót fogunk használni a híváskorlátozások szimulálására, de négyre csökkentjük:

public class SocialConnector {private boolean isCounterEnabled = true; privát int számláló = 4; @Getter @Setter List felhasználók; public SocialConnector () {felhasználók = new ArrayList (); } public logikai kapcsolóCounter () {this.isCounterEnabled =! this.isCounterEnabled; adja vissza ezt.isCounterEnabled; }} 

Ezután hozzáadunk egy módszert egy adott fiók követői listájának lekéréséhez:

public List getFollowers (Karakterlánc-fiók) {if (számláló <0) {dobjon új IllegalStateException-t ("elérte az API-korlátot"); } else {if (this.isCounterEnabled) {számláló--; } a (SocialUser felhasználó: felhasználók) számára {if (user.getUsername (). egyenlő (fiók)) {return user.getFollowers (); }}} return new ArrayList (); } 

Folyamatunk támogatásához néhány osztályra van szükségünk a felhasználói entitás modellezéséhez:

public class SocialUser {@Getter private String felhasználónév; @Getter privát lista követői; @Orride public boolean egyenlő (Object obj) {return ((SocialUser) obj) .getUsername (). Egyenlő (felhasználónév); } public SocialUser (String felhasználónév) {this.username = felhasználónév; this.followers = new ArrayList (); } public SocialUser (karakterlánc felhasználónév, követők listája) {this.username = felhasználónév; ez.követők = követők; } public void addFollowers (Követők listája) {this.followers.addAll (követők); }}

3.1. Kapzsi algoritmus

Végül itt az ideje a kapzsi stratégiánk megvalósításának, ezért adjunk hozzá egy új komponenst - Kapzsi Algoritmus - amelyben elvégezzük a rekurziót:

public class GreedyAlgorithm {int currentLevel = 0; végső int maxLevel = 3; SocialConnector sc; public GreedyAlgorithm (SocialConnector sc) {this.sc = sc; }}

Ezután be kell illesztenünk egy módszert findMostFollowersPath amelyben megtaláljuk a legtöbb követővel rendelkező felhasználót, megszámoljuk őket, majd folytatjuk a következő lépéssel:

public long findMostFollowersPath (String fiók) {long max = 0; SocialUser toFollow = null; Követők listája = sc.getFollowers (fiók); mert (SocialUser el: követők) {long followersCount = el.getFollowersCount (); if (followersCount> max) {toFollow = el; max = followersCount; }} if (currentLevel <maxLevel - 1) {currentLevel ++; max + = findMostFollowersPath (toFollow.getUsername ()); } return max; }

Emlékezik: Itt mohó választást hajtunk végre. Mint minden alkalommal, amikor ezt a módszert hívjuk, csak egy elemet választunk a listáról és folytassa: Soha többé nem térünk vissza döntéseinkre!

Tökéletes! Készen állunk az indulásra, és tesztelhetjük alkalmazásunkat. Előtte emlékeznünk kell arra, hogy feltöltsük apró hálózatunkat, és végre kell hajtanunk a következő egységtesztet:

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

3.2. Nem kapzsi algoritmus

Hozzunk létre egy nem mohó módszert, pusztán azért, hogy szemünkkel ellenőrizzük, mi történik. Tehát el kell kezdenünk a NonGreedyAlgorithm osztály:

nyilvános osztály NonGreedyAlgorithm {int currentLevel = 0; végső int maxLevel = 3; SocialConnector tc; public NonGreedyAlgorithm (SocialConnector tc, int szint) {this.tc = tc; this.currentLevel = szint; }}

Hozzunk létre egy egyenértékű módszert a követők beolvasására:

public long findMostFollowersPath (karakterlánc-fiók) {List followers = tc.getFollowers (account); hosszú összesen = currentLevel> 0? követők.méret (): 0; if (currentLevel  0; i--) {if (count [i-1]> max) {max = count [i-1]; }} visszatérés összesen + max; } hozam összesen; }

Amint osztályunk készen áll, készíthetünk néhány egységtesztet: Az egyik a híváskorlát túllépésének, a másik pedig a kapzsi stratégiával visszaadott érték ellenőrzésére:

public void nongreedyAlgorithmTest () {NonGreedyAlgorithm nga = new NonGreedyAlgorithm (PreparNetwork (), 0); Assertions.assertThrows (IllegalStateException.class, () -> {nga.findMostFollowersPath ("root";});}); } public void nongreedyAlgorithmUnboundedTest () {SocialConnector sc = PreparNetwork (); sc.switchCounter (); NonGreedyAlgorithm nga = új NonGreedyAlgorithm (sc, 0); assertEquals (nga.findMostFollowersPath ("gyökér"), 6); }

4. Eredmények

Ideje áttekinteni munkánkat!

Először kipróbáltuk mohó stratégiánkat, ellenőrizve annak hatékonyságát. Ezután kimerítő kereséssel igazoltuk a helyzetet, az API korlátozásával és anélkül.

Gyors kapzsi eljárásunk, amely minden alkalommal helyileg optimális döntéseket hoz, számértéket ad vissza. Másrészt semmit sem kapunk a nem mohó algoritmusból, egy környezeti korlátozás miatt.

A két módszer kimenetét összehasonlítva megérthetjük, hogy mohó stratégiánk mentett meg minket, még akkor is, ha a visszakeresett érték nem optimális. Nevezhetjük helyi optimumnak.

5. Következtetés

Változtatható és gyorsan változó összefüggésekben, például a közösségi médiában, az optimális megoldás megtalálását igénylő problémák félelmetes kimérává válhatnak: Nehezen elérhetőek, ugyanakkor irreálisak.

A korlátok leküzdése és az API-hívások optimalizálása meglehetősen téma, de amint megbeszéltük, a kapzsi stratégiák hatékonyak. Az ilyen megközelítés választása sok fájdalmat takarít meg számunkra, értékes eredményeket hozva cserébe.

Ne feledje, hogy nem minden helyzet megfelelő: Minden alkalommal értékelnünk kell körülményeinket.

Mint mindig, az oktatóanyag példakódja elérhető a GitHubon.