streamalism.org

1. Úvod

V tejto príručke sa chystáme zaviesť chamtivé algoritmy v ekosystéme Java.

2. Chamtivý problém

Keď stojíte pred matematickým problémom, môže existovať niekoľko spôsobov, ako navrhnúť riešenie. Môžeme implementovať iteračné riešenie alebo niektoré pokročilé techniky, napríklad princíp rozdeľuj a panuj (napr. Algoritmus Quicksort) alebo prístup s dynamickým programovaním (napr. Problém Knapsack) a mnoho ďalších.

Väčšinou hľadáme optimálne riešenie, bohužiaľ nie vždy dosiahneme taký výsledok. Existujú však prípady, kedy je hodnotný aj suboptimálny výsledok. Pomocou niektorých konkrétnych stratégií alebo heuristiky , mohli by sme si zarobiť takú vzácnu odmenu.

V tejto súvislosti, vzhľadom na deliteľný problém, stratégia, ktorá si v každej fáze procesu vyberie lokálne optimálnu voľbu alebo sa „nenásytná voľba“ nazýva chamtivý algoritmus.

Uviedli sme, že by sme sa mali zaoberať „deliteľným“ problémom: Situáciou, ktorú možno označiť ako súbor čiastkových problémov s takmer rovnakými vlastnosťami. V dôsledku toho sa väčšinou a chamtivý algoritmus bude implementovaný ako rekurzívny algoritmus.

Chamtivý algoritmus môže byť cestou, ktorá nás dovedie k rozumnému riešeniu napriek drsnému prostrediu; nedostatok výpočtových zdrojov, obmedzenie času vykonania, obmedzenia API alebo akýkoľvek iný druh obmedzení.

2.1. Scenár

V tomto krátkom tutoriáli implementujeme nenásytnú stratégiu na extrakciu údajov zo sociálnej siete pomocou jej API.

Povedzme, že by sme chceli osloviť viac používateľov v sociálnej sieti „malý modrý vták“. Najlepším spôsobom, ako dosiahnuť náš cieľ, je zverejniť pôvodný obsah alebo prepísať tweet, ktorý vzbudí záujem širokého publika.

Ako nájdeme také publikum? Musíme si nájsť účet s mnohými sledovateľmi a tweetovať pre nich nejaký obsah.

2.2. Klasický vs. chamtivý

Berieme do úvahy nasledujúcu situáciu: Náš účet má štyroch sledovateľov, z ktorých každý má, ako je znázornené na obrázku nižšie, 2, 2, 1 a 3 sledovateľov atď.:

S týmto cieľom si v mysli vezmeme ten, ktorý má medzi sledovateľmi nášho účtu viac sledovateľov. Potom postup zopakujeme ešte dvakrát, kým nedosiahneme 3. stupeň spojenia (celkovo štyri kroky).

Týmto spôsobom definujeme cestu vytvorenú používateľmi, ktorá nás vedie k najväčšej základni sledovateľov z nášho účtu. Ak im môžeme adresovať nejaký obsah, určite sa dostanú na našu stránku.

Môžeme začať s „tradičným“ prístupom. V každom jednotlivom kroku vykonáme dopyt, aby sme získali sledovateľov účtu. V dôsledku nášho výberového procesu sa počet účtov bude každým krokom zvyšovať.

Celkovo prekvapivo skončíme s 25 dotazmi:

Tu nastáva problém: Napríklad Twitter API obmedzuje tento typ dopytu na 15 každých 15 minút. Ak sa pokúsime uskutočniť viac hovorov, ako je povolené, dostaneme “Prekročený limit rýchlosti - 88„Alebo“Vrátené v rozhraní API v1.1, keď nie je možné vyhovieť požiadavke z dôvodu vyčerpania limitu rýchlosti aplikácie pre zdroj„. Ako môžeme prekonať takúto hranicu?

Odpoveď je priamo pred nami: chamtivý algoritmus. Ak použijeme tento prístup, v každom kroku môžeme predpokladať, že používateľ s najväčším počtom sledujúcich je jediný, koho treba brať do úvahy: Nakoniec potrebujeme iba štyri dotazy. Celkom vylepšenie!

Výsledok týchto dvoch prístupov bude odlišný. V prvom prípade dostaneme 16, optimálne riešenie, zatiaľ čo v druhom prípade je maximálny počet dosiahnuteľných sledovateľov iba 12.

Bude tento rozdiel taký cenný? Rozhodneme sa neskôr.

3. Implementácia

Aby sme implementovali vyššie uvedenú logiku, inicializujeme malý program Java, kde napodobníme Twitter API. Využijeme tiež knižnicu Lombok.

Teraz definujme našu zložku SocialConnector v ktorej implementujeme našu logiku. Upozorňujeme, že nastavíme počítadlo na simuláciu obmedzení hovorov, ale znížime ho na štyri:

verejná trieda SocialConnector {private boolean isCounterEnabled = true; private int counter = 4; @Getter @Setter Zoznam používateľov; public SocialConnector () {users = new ArrayList (); } public boolean switchCounter () {this.isCounterEnabled =! this.isCounterEnabled; vrátiť this.isCounterEnabled; }} 

Potom pridáme metódu na získanie zoznamu sledovateľov konkrétneho účtu:

public List getFollowers (reťazcový účet) {if (counter <0) {throw new IllegalStateException ("API limit reached"); } else {if (this.isCounterEnabled) {counter--; } for (SocialUser user: users) {if (user.getUsername (). equals (account)) {return user.getFollowers (); }}} vrátiť nový ArrayList (); } 

Na podporu nášho procesu potrebujeme niekoľko tried na modelovanie našej používateľskej entity:

public class SocialUser {@Getter private Reťazec používateľské meno; @Získať sledovateľov zo súkromného zoznamu; @ Override public boolean equals (Object obj) {return ((SocialUser) obj) .getUsername (). Equals (username); } public SocialUser (String username) {this.username = username; this.followers = new ArrayList (); } public SocialUser (používateľské meno v reťazci, sledovatelia v zozname) {this.username = používateľské meno; this.followers = sledovatelia; } public void addFollowers (sledovatelia zoznamu) {this.followers.addAll (sledovatelia); }}

3.1. Chamtivý algoritmus

Konečne je čas implementovať našu chamtivú stratégiu, pridajme preto nový komponent - Chamtivý algoritmus - v ktorej vykonáme rekurziu:

verejná trieda GreedyAlgorithm {int currentLevel = 0; final int maxLevel = 3; SocialConnector sc; public GreedyAlgorithm (SocialConnector sc) {this.sc = sc; }}

Potom musíme vložiť metódu findMostFollowersPath v ktorom nájdeme používateľa s väčšinou sledovateľov, spočítame ich a potom pokračujeme ďalším krokom:

public long findMostFollowersPath (reťazcový účet) {long max = 0; SocialUser toFollow = null; Zoznam sledovateľov = sc.getFollowers (účet); pre (SocialUser el: sledovatelia) {long followersCount = el.getFollowersCount (); if (sledovateľPočet> max) {toFollow = el; max = sledovateliaCount; }} if (currentLevel <maxLevel - 1) {currentLevel ++; max + = findMostFollowersPath (toFollow.getUsername ()); } návrat max; }

Pamätajte: Tu vykonávame chamtivú voľbu. Zakaždým, keď voláme túto metódu, vyberieme jeden a iba jeden prvok zo zoznamu a pokračujte: Už nikdy sa nevrátime k svojim rozhodnutiam!

Perfektné! Sme pripravení ísť a môžeme otestovať našu aplikáciu. Predtým si musíme uvedomiť, že je potrebné naplniť našu malú sieť a nakoniec vykonať nasledujúci test jednotky:

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

3.2. Non-Greedy Algorithm

Vytvorme nenásytnú metódu, iba aby sme očami skontrolovali, čo sa stane. Musíme teda začať s budovaním a NonGreedyAlgorithm trieda:

verejná trieda NonGreedyAlgorithm {int currentLevel = 0; final int maxLevel = 3; SocialConnector tc; public NonGreedyAlgorithm (SocialConnector tc, int level) {this.tc = tc; this.currentLevel = úroveň; }}

Vytvorme ekvivalentnú metódu na získanie sledovateľov:

public long findMostFollowersPath (reťazcový účet) {List sledovatelia = tc.getFollowers (účet); long total = currentLevel> 0? sledovatelia.size (): 0; if (currentLevel  0; i--) {if (count [i-1]> max) {max = count [i-1]; }} návratnosť spolu + max; } návratnosť celkom; }

Keď je naša trieda pripravená, môžeme pripraviť niekoľko testov jednotiek: Jeden na overenie prekročenia limitu hovoru a druhý na kontrolu vrátenej hodnoty pomocou nenáročnej stratégie:

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

4. Výsledky

Je čas skontrolovať našu prácu!

Najskôr sme vyskúšali našu nenásytnú stratégiu a skontrolovali jej účinnosť. Potom sme situáciu overili vyčerpávajúcim hľadaním, s limitom API aj bez neho.

Náš rýchly chamtivý postup, ktorý zakaždým umožňuje lokálne optimálne voľby, vráti číselnú hodnotu. Na druhej strane, z nenáročného algoritmu nedostaneme nič, kvôli obmedzeniu prostredia.

Ak porovnáme výstup týchto dvoch metód, môžeme pochopiť, ako nás naša nenásytná stratégia zachránila, aj keď získaná hodnota nie je optimálna. Môžeme to nazvať lokálnym optimom.

5. Záver

V premenlivých a rýchlo sa meniacich kontextoch, ako sú sociálne médiá, sa problémy, ktoré si vyžadujú nájdenie optimálneho riešenia, môžu stať strašnou chimérou: ťažko dosiahnuteľnou a zároveň nereálnou.

Prekonávanie obmedzení a optimalizácia volaní API je celkom téma, ale ako sme už diskutovali, nenásytné stratégie sú účinné. Zvolenie tohto druhu prístupu nám ušetrí veľa bolesti a vráti cenné výsledky výmenou.

Majte na pamäti, že nie každá situácia je vhodná: Musíme si vždy vyhodnotiť svoje podmienky.

Ako vždy, ukážkový kód z tohto tutoriálu je k dispozícii na GitHub.