Javaを使用した欲張りアルゴリズムの概要
1. 序章
このチュートリアルでは、がJavaエコシステムに欲張りアルゴリズムを導入します。
2. 貪欲な問題
数学の問題に直面した場合、解決策を設計する方法はいくつかあります。 反復ソリューション、または分割統治法などの高度な手法を実装できます(例: クイックソートアルゴリズム)または動的計画法によるアプローチ(例: ナップサック問題)など。
ほとんどの場合、私たちは最適な解決策を探していますが、残念ながら、必ずしもそのような結果が得られるとは限りません。 ただし、次善の結果でも価値がある場合があります。 いくつかの特定の戦略、またはヒューリスティック、 の助けを借りて、私たちはそのような貴重な報酬を得ることができます。
この文脈では、分割可能な問題が与えられた場合、
「分割可能な」問題に対処する必要があると述べました。これは、ほぼ同じ特性を持つ一連のサブ問題として説明できる状況です。 結果として、ほとんどの場合、欲張りアルゴリズムは再帰的アルゴリズムとして実装されます。
欲張りアルゴリズムは、過酷な環境にもかかわらず、合理的な解決策に導く方法になる可能性があります。 計算リソースの不足、実行時の制約、APIの制限、またはその他の種類の制限。
2.1. シナリオ
この短いチュートリアルでは、APIを使用してソーシャルネットワークからデータを抽出する欲張り戦略を実装します。
「小さな青い鳥」のソーシャルでより多くのユーザーにリーチしたいとします。 私たちの目標を達成するための最良の方法は、オリジナルのコンテンツを投稿するか、幅広い視聴者の興味を引くようなものをリツイートすることです。
どうやってそのような聴衆を見つけるのでしょうか? さて、私たちは多くのフォロワーを持つアカウントを見つけて、彼らのためにいくつかのコンテンツをツイートする必要があります。
2.2. クラシック対。 よく深い
次の状況を考慮します。アカウントには4人のフォロワーがいて、それぞれが下の画像に示すように、それぞれ2、2、1、3人のフォロワーを持っています。
この目的を念頭に置いて、アカウントのフォロワーの中でフォロワーが多い方を取り上げます。 次に、3番目の接続度(合計4つのステップ)に到達するまで、このプロセスをさらに2回繰り返します。
このようにして、ユーザーで構成されるパスを定義し、アカウントから最も広大なフォロワーベースに導きます。ユーザーにコンテンツを提供できれば、ユーザーは確実に私たちのページにアクセスします。
「従来の」アプローチから始めることができます。 すべてのステップで、アカウントのフォロワーを取得するためのクエリを実行します。 選択プロセスの結果、アカウントの数はステップごとに増加します。
驚いたことに、合計で25のクエリを実行することになります。
ここで問題が発生します。たとえば、Twitter APIは、このタイプのクエリを15分ごとに15に制限します。 許可されているよりも多くの呼び出しを実行しようとすると、「レート制限超過コード– 88 」、または「 API v1.1で、次の理由でリクエストを処理できない場合に返される」が表示されます。リソース“のアプリケーションのレート制限が使い果たされました。 どうすればそのような限界を克服できますか?
答えは私たちの目の前にあります。欲張りアルゴリズムです。 このアプローチを使用する場合、各ステップで、フォロワーが最も多いユーザーだけが考慮すべきであると想定できます。最終的に、必要なクエリは4つだけです。 かなり改善されました!
これら2つのアプローチの結果は異なります。 前者の場合、最適なソリューションは16になりますが、後者の場合、到達可能なフォロワーの最大数はわずか12です。
この違いはとても価値がありますか? 後で決めます。
3. 実装
上記のロジックを実装するために、TwitterAPIを模倣する小さなJavaプログラムを初期化します。Lombokライブラリも利用します。
次に、ロジックを実装するコンポーネントSocialConnectorを定義しましょう。 呼び出し制限をシミュレートするためにカウンターを配置することに注意してください。ただし、カウンターを4つに減らします。
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. 欲張りアルゴリズム
最後に、欲張り戦略を実装するときが来たので、再帰を実行する新しいコンポーネント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;
}
覚えておいてください:ここで貪欲な選択を行います。このように、このメソッドを呼び出すたびに、リストから1つだけの要素を選択し、次に進みます。私たちの決定に戻ることは決してありません!
完全! 準備が整い、アプリケーションをテストできます。 その前に、小さなネットワークにデータを入力し、最後に次の単体テストを実行することを忘れないでください。
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;
}
}
フォロワーを取得するための同等のメソッドを作成しましょう。
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;
}
クラスの準備ができたら、いくつかの単体テストを準備できます。1つは呼び出し制限を超えていることを確認し、もう1つは欲張りでない戦略で返された値を確認します。
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制限がある場合とない場合で、徹底的な検索を使用して状況を検証しました。
毎回ローカルで最適な選択を行う私たちの迅速な貪欲な手順は、数値を返します。 一方、環境の制限により、欲張りでないアルゴリズムからは何も得られません。
2つの方法の出力を比較すると、取得した値が最適ではない場合でも、欲張り戦略がどのように節約したかを理解できます。これを局所最適と呼ぶことができます。
5. 結論
ソーシャルメディアのように変化が激しく変化の激しい状況では、最適な解決策を見つける必要のある問題は恐ろしいキメラになる可能性があります。到達するのが難しく、同時に非現実的です。
制限の克服とAPI呼び出しの最適化は非常にテーマですが、これまでに説明したように、貪欲な戦略は効果的です。 この種のアプローチを選択すると、多くの苦痛が軽減され、代わりに貴重な結果が返されます。
すべての状況が適切であるとは限らないことに注意してください。私たちは毎回状況を評価する必要があります。
いつものように、このチュートリアルのサンプルコードは、GitHubから入手できます。