Въведение в алчните алгоритми с Java

1. Въведение

В този урок ще въведем алчни алгоритми в екосистемата на Java.

2. Алчен проблем

Когато се сблъскате с математически проблем, може да има няколко начина за проектиране на решение. Можем да приложим итеративно решение или някои усъвършенствани техники, като например принцип на разделяне и завладяване (например Quicksort алгоритъм) или подход с динамично програмиране (напр. Проблем с раницата) и много други.

През повечето време търсим оптимално решение, но за съжаление не винаги получаваме такъв резултат. Има обаче случаи, когато дори неоптимален резултат е ценен. С помощта на някои специфични стратегии или евристики , можем да си спечелим такава ценна награда.

В този контекст, при даден делим проблем, стратегия, която на всеки етап от процеса взема локално оптимален избор или „алчен избор“, се нарича алчен алгоритъм.

Ние заявихме, че трябва да се обърнем към „делим“ проблем: Ситуация, която може да бъде описана като набор от подпроблеми с почти същите характеристики. В резултат на това през повечето време алчен алгоритъм ще бъде реализиран като рекурсивен алгоритъм .

Алчният алгоритъм може да бъде начин да ни доведе до разумно решение въпреки суровата среда; липса на изчислителни ресурси, ограничение по време на изпълнение, ограничения на API или някакъв друг вид ограничения.

2.1. Сценарий

В този кратък урок ще приложим алчна стратегия за извличане на данни от социална мрежа, използвайки нейния API.

Да предположим, че бихме искали да достигнем до повече потребители в социалната мрежа „малка синя птица“. Най-добрият начин да постигнем целта си е да публикуваме оригинално съдържание или да пуснем повторно нещо в Twitter, което ще предизвика известен интерес у широка аудитория.

Как да намерим такава публика? Е, трябва да намерим акаунт с много последователи и да публикуваме малко съдържание за тях.

2.2. Класика срещу алчни

Ние вземаме предвид следната ситуация: Нашият акаунт има четирима последователи, всеки от които има, както е показано на изображението по-долу, съответно 2, 2, 1 и 3 последователи и т.н.:

С тази цел в съзнанието си ще вземем тази с повече последователи сред последователите на нашия акаунт. След това ще повторим процеса още два пъти, докато достигнем 3-та степен на връзка (общо четири стъпки).

По този начин ние дефинираме път, направен от потребители, който ни води до най-голямата база последователи от нашия акаунт. Ако можем да им адресираме някакво съдържание, те със сигурност ще стигнат до нашата страница.

Можем да започнем с „традиционен“ подход. На всяка една стъпка ще изпълняваме запитване, за да привлечем последователите на акаунт. В резултат на нашия процес на подбор броят на акаунтите ще се увеличава на всяка стъпка.

Изненадващо, в крайна сметка бихме изпълнили 25 заявки:

Тук възниква проблем: Например, Twitter API ограничава този тип заявка до 15 на всеки 15 минути. Ако се опитаме да извършим повече обаждания от позволеното, ще получим „ Ограничението за скорост е надвишено - 88 “ или „ Върнато в API v1.1, когато заявка не може да бъде обслужвана поради изчерпване на ограничението за скоростта на приложението за ресурса “. Как можем да преодолеем такава граница?

Е, отговорът е точно пред нас: алчен алгоритъм. Ако използваме този подход, на всяка стъпка можем да приемем, че потребителят с най-много последователи е единственият, който трябва да вземе предвид: В крайна сметка се нуждаем само от четири запитвания. Съвсем подобрение!

Резултатът от тези два подхода ще бъде различен. В първия случай получаваме 16, оптималното решение, докато във втория максималният брой достижими последователи е само 12.

Дали тази разлика ще бъде толкова ценна? Ще решим по-късно.

3. Прилагане

За да приложим горната логика, ние инициализираме малка Java програма, където ще имитираме Twitter API. Ще се възползваме и от библиотеката на Ломбок.

Сега, нека дефинираме нашия компонент SocialConnector, в който ще приложим нашата логика. Обърнете внимание, че ще поставим брояч, за да симулираме ограничения на повикванията, но ще го намалим до четири:

public class SocialConnector { private boolean isCounterEnabled = true; private int counter = 4; @Getter @Setter List users; public SocialConnector() { users = new ArrayList(); } public boolean switchCounter() { this.isCounterEnabled = !this.isCounterEnabled; return this.isCounterEnabled; } } 

След това ще добавим метод за извличане на списъка на последователите на конкретен акаунт:

public List getFollowers(String account) { 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(); } } } return new ArrayList(); } 

За да поддържаме процеса си, са ни необходими няколко класа, за да моделираме потребителския си обект:

public class SocialUser { @Getter private String username; @Getter private List followers; @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(String username, List followers) { this.username = username; this.followers = followers; } public void addFollowers(List followers) { this.followers.addAll(followers); } }

3.1. Алчен алгоритъм

И накрая, време е да приложим нашата алчна стратегия, така че нека добавим нов компонент - GreedyAlgorithm - в който ще извършим рекурсията:

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

След това трябва да вмъкнем метод findMostFollowersPath, в който ще намерим потребителя с най-много последователи, да ги преброим и след това да преминем към следващата стъпка:

public long findMostFollowersPath(String account) { long max = 0; SocialUser toFollow = null; List followers = sc.getFollowers(account); for (SocialUser el : followers) { long followersCount = el.getFollowersCount(); if (followersCount > max) { toFollow = el; max = followersCount; } } if (currentLevel < maxLevel - 1) { currentLevel++; max += findMostFollowersPath(toFollow.getUsername()); } return max; }

Запомнете: Тук правим алчен избор. Като такъв, всеки път, когато извикаме този метод, ние ще изберем един и само един елемент от списъка и ще продължим напред: Никога няма да се връщаме към решенията си!

Перфектно! Готови сме да тръгнем и можем да тестваме нашето заявление. Преди това трябва да запомним да попълним малката си мрежа и накрая да изпълним следния единичен тест:

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

3.2. Алчно алчен алгоритъм

Нека създадем не-алчен метод, просто за да проверим с очите си какво се случва. И така, трябва да започнем с изграждането на клас NonGreedyAlgorithm :

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

Let's create an equivalent method to retrieve followers:

public long findMostFollowersPath(String account) { List followers = tc.getFollowers(account); long total = currentLevel > 0 ? followers.size() : 0; if (currentLevel 
    
      0; i--) { if (count[i-1] > max) { max = count[i-1]; } } return total + max; } return total; }
    

As our class is ready, we can prepare some unit tests: One to verify the call limit exceeds and another one to check the value returned with a non-greedy strategy:

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. Results

It's time to review our work!

First, we tried out our greedy strategy, checking its effectiveness. Then we verified the situation with an exhaustive search, with and without the API limit.

Our quick greedy procedure, which makes locally optimal choices each time, returns a numeric value. On the other hand, we don't get anything from the non-greedy algorithm, due to an environment restriction.

Comparing the two methods' output, we can understand how our greedy strategy saved us, even if the retrieved value that is not optimal. We can call it a local optimum.

5. Conclusion

В променлив и бързо променящ се контекст като социалните медии, проблемите, които изискват намирането на оптимално решение, могат да се превърнат в ужасна химера: Трудно достъпна и в същото време нереална.

Преодоляването на ограниченията и оптимизирането на API повикванията е доста тема, но както вече обсъждахме, алчните стратегии са ефективни. Изборът на този вид подход ни спестява много болка, връщайки ценни резултати в замяна.

Имайте предвид, че не всяка ситуация е подходяща: Всеки път трябва да оценяваме обстоятелствата си.

Както винаги, примерният код от този урок е достъпен в GitHub.