Введение в жадные алгоритмы на Java

1. Введение

В этом руководстве мы собираемся представить жадные алгоритмы в экосистеме Java.

2. Жадная проблема

Столкнувшись с математической проблемой, может быть несколько способов найти решение. Мы можем реализовать итеративное решение или некоторые продвинутые методы, такие как принцип «разделяй и властвуй» (например, алгоритм быстрой сортировки) или подход с динамическим программированием (например, задача о рюкзаке) и многое другое.

В большинстве случаев мы ищем оптимальное решение, но, к сожалению, не всегда получаем такой результат. Однако бывают случаи, когда ценен даже неоптимальный результат. С помощью некоторых конкретных стратегий или эвристики , мы могли бы заработать себе такую драгоценную награду.

В этом контексте для данной делимой проблемы стратегия, которая на каждом этапе процесса принимает локально оптимальный выбор или «жадный выбор», называется жадным алгоритмом.

Мы заявили, что должны обратиться к «делимой» проблеме: ситуации, которую можно описать как набор подзадач с почти одинаковыми характеристиками. Как следствие, большую часть времени жадный алгоритм будет реализован как рекурсивный алгоритм .

Жадный алгоритм может привести нас к разумному решению, несмотря на суровые условия; отсутствие вычислительных ресурсов, ограничение времени выполнения, ограничения API или любые другие ограничения.

2.1. Сценарий

В этом коротком руководстве мы собираемся реализовать жадную стратегию извлечения данных из социальной сети с помощью ее API.

Допустим, мы хотим привлечь больше пользователей в социальной сети «синяя птичка». Лучший способ достичь нашей цели - опубликовать оригинальный контент или ретвитнуть что-то, что вызовет интерес у широкой аудитории.

Как нам найти такую ​​аудиторию? Что ж, мы должны найти учетную запись с большим количеством подписчиков и написать для них какой-то контент.

2.2. Классический против Жадного

Мы принимаем во внимание следующую ситуацию: у нашей учетной записи четыре подписчика, у каждого из которых, как показано на изображении ниже, соответственно 2, 2, 1 и 3 подписчика и так далее:

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

Таким образом, мы определяем путь пользователей, ведущий к самой обширной базе подписчиков в нашей учетной записи. Если мы сможем адресовать им какой-то контент, они обязательно попадут на нашу страницу.

Можно начать с «традиционного» подхода. На каждом этапе мы будем выполнять запрос, чтобы получить подписчиков учетной записи. В результате нашего процесса отбора количество учетных записей будет увеличиваться с каждым шагом.

Удивительно, но в итоге мы выполнили 25 запросов:

Здесь возникает проблема: например, Twitter API ограничивает этот тип запроса до 15 каждые 15 минут. Если мы попытаемся выполнить больше вызовов, чем разрешено, мы получим « Код превышения лимита скорости - 88 » или « Возвращенный в API v1.1, когда запрос не может быть обработан из-за того, что лимит скорости приложения был исчерпан для ресурса. «. Как мы можем преодолеть такой предел?

Что ж, ответ прямо перед нами: жадный алгоритм. Если мы используем этот подход, на каждом этапе мы можем предположить, что пользователь с наибольшим количеством подписчиков - единственный, кого следует учитывать: в конце концов, нам нужно всего четыре запроса. Хорошее улучшение!

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

Будет ли эта разница настолько ценной? Решим позже.

3. Реализация

Чтобы реализовать вышеуказанную логику, мы инициализируем небольшую программу на Java, в которой мы имитируем Twitter API. Мы также воспользуемся библиотекой Lombok.

Теперь давайте определим наш компонент 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; } }

Then we need to insert a method findMostFollowersPath in which we'll find the user with most followers, count them, and then proceed to the next step:

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; }

Remember: Here is where we perform a greedy choice. As such, every time we call this method, we'll choose one and only one element from the list and move on: We won't ever go back on our decisions!

Perfect! We are ready to go, and we can test our application. Before that, we need to remember to populate our tiny network and finally, execute the following unit test:

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

3.2. Non-Greedy Algorithm

Let's create a non-greedy method, merely to check with our eyes what happens. So, we need to start with building a NonGreedyAlgorithm class:

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.