Introduzione a Greedy Algorithms con Java

1. Introduzione

In questo tutorial, introdurremo algoritmi avidi nell'ecosistema Java.

2. Problema avido

Quando si affronta un problema matematico, ci possono essere diversi modi per progettare una soluzione. Possiamo implementare una soluzione iterativa, o alcune tecniche avanzate, come il principio divide et impera (es. Algoritmo Quicksort) o l'approccio con programmazione dinamica (es. Problema dello zaino) e molte altre.

La maggior parte delle volte cerchiamo una soluzione ottimale, ma purtroppo non sempre otteniamo un risultato del genere. Tuttavia, ci sono casi in cui anche un risultato non ottimale è prezioso. Con l'aiuto di alcune strategie specifiche, o euristiche , potremmo guadagnarci una ricompensa così preziosa.

In questo contesto, dato un problema divisibile, una strategia che in ogni fase del processo prende la scelta ottimale localmente o "scelta avida" è chiamata algoritmo avido.

Abbiamo affermato che dovremmo affrontare un problema "divisibile": una situazione che può essere descritta come un insieme di sottoproblemi con, quasi, le stesse caratteristiche. Di conseguenza, il più delle volte, verrà implementato un algoritmo avido come algoritmo ricorsivo .

Un algoritmo avido può essere un modo per condurci a una soluzione ragionevole nonostante un ambiente difficile; mancanza di risorse computazionali, vincoli sui tempi di esecuzione, limitazioni API o qualsiasi altro tipo di restrizione.

2.1. Scenario

In questo breve tutorial, implementeremo una strategia avida per estrarre dati da un social network utilizzando la sua API.

Diciamo che vorremmo raggiungere più utenti sul social "uccellino azzurro". Il modo migliore per raggiungere il nostro obiettivo è pubblicare contenuti originali o ritwittare qualcosa che susciti interesse in un vasto pubblico.

Come troviamo un tale pubblico? Bene, dobbiamo trovare un account con molti follower e twittare alcuni contenuti per loro.

2.2. Classico contro avido

Prendiamo in considerazione la seguente situazione: Il nostro account ha quattro follower, ognuno dei quali ha, come illustrato nell'immagine sottostante, rispettivamente 2, 2, 1 e 3 follower e così via:

Con questo scopo nella nostra mente, prenderemo quello con più follower tra i follower del nostro account. Quindi ripeteremo il processo altre due volte fino a raggiungere il 3 ° grado di connessione (quattro passaggi in totale).

In questo modo, definiamo un percorso fatto di utenti, portandoci alla più vasta base di follower dal nostro account. Se riusciamo a indirizzare loro dei contenuti, raggiungeranno sicuramente la nostra pagina.

Possiamo iniziare con un approccio "tradizionale". Ad ogni singolo passaggio, eseguiremo una query per ottenere i follower di un account. Come risultato del nostro processo di selezione, il numero di account aumenterà a ogni passaggio.

Sorprendentemente, in totale, finiremmo per eseguire 25 query:

Qui sorge un problema: ad esempio, l'API di Twitter limita questo tipo di query a 15 ogni 15 minuti. Se proviamo a eseguire più chiamate di quelle consentite, otterremo un " Codice limite di frequenza superato - 88 " o " Restituito nell'API v1.1 quando una richiesta non può essere servita a causa dell'esaurimento del limite di frequenza dell'applicazione per la risorsa “. Come possiamo superare un tale limite?

Bene, la risposta è proprio di fronte a noi: un algoritmo avido. Se utilizziamo questo approccio, ad ogni passaggio, possiamo presumere che l'utente con il maggior numero di follower sia l'unico da considerare: alla fine, abbiamo bisogno solo di quattro query. Un bel miglioramento!

Il risultato di questi due approcci sarà diverso. Nel primo caso otteniamo 16, la soluzione ottimale, mentre nel secondo il numero massimo di followers raggiungibili è solo 12.

Questa differenza sarà così preziosa? Decideremo più tardi.

3. Implementazione

Per implementare la logica di cui sopra, inizializziamo un piccolo programma Java, dove imiteremo l'API di Twitter. Useremo anche la biblioteca di Lombok.

Definiamo ora il nostro componente SocialConnector in cui implementeremo la nostra logica. Nota che metteremo un contatore per simulare le restrizioni sulle chiamate, ma lo abbasseremo a quattro:

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

Quindi aggiungeremo un metodo per recuperare l'elenco dei follower di un account specifico:

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

Per supportare il nostro processo, abbiamo bisogno di alcune classi per modellare la nostra entità utente:

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. Algoritmo avido

Infine, è il momento di implementare la nostra strategia greedy, quindi aggiungiamo un nuovo componente - GreedyAlgorithm - in cui eseguiremo la ricorsione:

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

Quindi dobbiamo inserire un metodo findMostFollowersPath in cui troveremo l'utente con il maggior numero di follower, li conteremo e quindi procederemo al passaggio successivo:

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

Ricorda: qui è dove eseguiamo una scelta avida. Pertanto, ogni volta che chiamiamo questo metodo, sceglieremo un solo elemento dalla lista e andremo avanti: non torneremo mai indietro sulle nostre decisioni!

Perfetto! Siamo pronti per iniziare e possiamo testare la nostra applicazione. Prima di ciò, dobbiamo ricordarci di popolare la nostra piccola rete e, infine, eseguire il seguente test unitario:

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

3.2. Algoritmo non avido

Creiamo un metodo non avido, semplicemente per verificare con i nostri occhi cosa succede. Quindi, dobbiamo iniziare con la creazione di una classe 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

In contesti mutevoli e in rapida evoluzione come i social media, i problemi che richiedono di trovare una soluzione ottimale possono diventare una spaventosa chimera: difficile da raggiungere e, allo stesso tempo, irrealistica.

Il superamento dei limiti e l'ottimizzazione delle chiamate API è un bel tema, ma, come abbiamo discusso, le strategie avide sono efficaci. La scelta di questo tipo di approccio ci risparmia molto dolore, restituendo in cambio risultati preziosi.

Tieni presente che non tutte le situazioni sono adatte: dobbiamo valutare ogni volta le nostre circostanze.

Come sempre, il codice di esempio di questo tutorial è disponibile su GitHub.