«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, в которой мы будем имитировать API Twitter. Мы также будем использовать библиотеку 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<SocialUser> 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<SocialUser> followers) {
this.username = username;
this.followers = followers;
}
public void addFollowers(List<SocialUser> followers) {
this.followers.addAll(followers);
}
}Для поддержки нашего процесса нам нужны классы для моделирования нашего пользовательского объекта:
3.1. Жадный алгоритм
public class GreedyAlgorithm {
int currentLevel = 0;
final int maxLevel = 3;
SocialConnector sc;
public GreedyAlgorithm(SocialConnector sc) {
this.sc = sc;
}
}Наконец, пришло время реализовать нашу жадную стратегию, поэтому давайте добавим новый компонент — GreedyAlgorithm — в котором мы будем выполнять рекурсию:
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;
}Затем нам нужно вставить метод findMostFollowersPath, в котором мы найдем пользователя с наибольшим количеством подписчиков, посчитаем их, а затем перейдем к следующему шагу:
Помните: здесь мы выполняем жадный выбор. Таким образом, каждый раз, когда мы вызываем этот метод, мы выбираем один и только один элемент из списка и идем дальше: мы никогда не откажемся от своих решений!
public void greedyAlgorithmTest() {
GreedyAlgorithm ga = new GreedyAlgorithm(prepareNetwork());
assertEquals(ga.findMostFollowersPath("root"), 5);
}Идеально! Мы готовы к работе и можем протестировать наше приложение. Перед этим нам нужно не забыть заполнить нашу крошечную сеть и, наконец, выполнить следующий модульный тест:
3.2. Нежадный алгоритм
public class NonGreedyAlgorithm {
int currentLevel = 0;
final int maxLevel = 3;
SocialConnector tc;
public NonGreedyAlgorithm(SocialConnector tc, int level) {
this.tc = tc;
this.currentLevel = level;
}
}Давайте создадим нежадный метод, просто чтобы проверить своими глазами, что происходит. Итак, нам нужно начать с создания класса NonGreedyAlgorithm:
public long findMostFollowersPath(String account) {
List<SocialUser> followers = tc.getFollowers(account);
long total = currentLevel > 0 ? followers.size() : 0;
if (currentLevel < maxLevel ) {
currentLevel++;
long[] count = new long[followers.size()];
int i = 0;
for (SocialUser el : followers) {
NonGreedyAlgorithm sub = new NonGreedyAlgorithm(tc, currentLevel);
count[i] = sub.findMostFollowersPath(el.getUsername());
i++;
}
long max = 0;
for (; i > 0; i--) {
if (count[i-1] > max) {
max = count[i-1];
}
}
return total + max;
}
return total;
}Давайте создадим эквивалентный метод для получения подписчиков:
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. Результаты
Пришло время подвести итоги нашей работы!
Сначала мы опробовали нашу жадную стратегию, проверив ее эффективность. Затем мы проверили ситуацию полным перебором, с ограничением API и без него.
Наша быстрая жадная процедура, которая каждый раз делает локально оптимальный выбор, возвращает числовое значение. С другой стороны, мы ничего не получаем от нежадного алгоритма из-за ограничения среды.
Сравнивая вывод двух методов, мы можем понять, как наша жадная стратегия спасла нас, даже если полученное значение не является оптимальным. Мы можем назвать это локальным оптимумом.
5. Заключение
В изменчивых и быстро меняющихся контекстах, таких как социальные сети, проблемы, требующие поиска оптимального решения, могут стать ужасной химерой: труднодостижимой и в то же время нереалистичной.
Преодоление ограничений и оптимизация вызовов API — это отдельная тема, но, как мы уже говорили, жадные стратегии эффективны. Выбор такого подхода избавляет нас от многих проблем, давая взамен ценные результаты.
Имейте в виду, что не каждая ситуация подходит: нам нужно каждый раз оценивать наши обстоятельства.