1. Introducción
En este tutorial, vamos a introducir algoritmos codiciosos en el ecosistema de Java.
2. Problema codicioso
Al enfrentarse a un problema matemático, puede haber varias formas de diseñar una solución. Podemos implementar una solución iterativa, o algunas técnicas avanzadas, como el principio de dividir y conquistar (por ejemplo, algoritmo Quicksort) o el enfoque con programación dinámica (por ejemplo, problema de mochila) y muchos más.
La mayoría de las veces, buscamos una solución óptima, pero lamentablemente no siempre obtenemos ese resultado. Sin embargo, hay casos en los que incluso un resultado subóptimo es valioso. Con la ayuda de algunas estrategias específicas o heurísticas , podríamos ganarnos una recompensa tan preciosa.
En este contexto, dado un problema divisible, una estrategia que en cada etapa del proceso toma la opción localmente óptima o "elección codiciosa" se denomina algoritmo codicioso.
Decimos que debemos abordar un problema “divisible”: una situación que puede describirse como un conjunto de subproblemas con, casi, las mismas características. Como consecuencia, la mayoría de las veces, se implementará un algoritmo codicioso como un algoritmo recursivo .
Un algoritmo codicioso puede ser una forma de llevarnos a una solución razonable a pesar de un entorno hostil; falta de recursos computacionales, restricción de tiempo de ejecución, limitaciones de API o cualquier otro tipo de restricción.
2.1. Guión
En este breve tutorial, implementaremos una estrategia codiciosa para extraer datos de una red social usando su API.
Digamos que nos gustaría llegar a más usuarios en las redes sociales del “pajarito azul”. La mejor manera de lograr nuestro objetivo es publicar contenido original o retuitear algo que despierte cierto interés en una amplia audiencia.
¿Cómo encontramos tal audiencia? Bueno, debemos buscar una cuenta con muchos seguidores y tuitear algún contenido para ellos.
2.2. Clásico contra codicioso
Tenemos en cuenta la siguiente situación: Nuestra cuenta tiene cuatro seguidores, cada uno de los cuales tiene, como se muestra en la imagen siguiente, respectivamente 2, 2, 1 y 3 seguidores, y así sucesivamente:
Con este propósito en nuestra mente, tomaremos el que tenga más seguidores entre los seguidores de nuestra cuenta. Luego repetiremos el proceso dos veces más hasta llegar al 3er grado de conexión (cuatro pasos en total).
De esta forma, definimos un camino de usuarios que nos lleva a la base de seguidores más amplia de nuestra cuenta. Si podemos dirigirles algún contenido, seguramente llegarán a nuestra página.
Podemos comenzar con un enfoque "tradicional". En cada paso, realizaremos una consulta para obtener los seguidores de una cuenta. Como resultado de nuestro proceso de selección, el número de cuentas aumentará en cada paso.
Sorprendentemente, en total terminaríamos realizando 25 consultas:
Aquí surge un problema: por ejemplo, la API de Twitter limita este tipo de consulta a 15 cada 15 minutos. Si intentamos realizar más llamadas de las permitidas, obtendremos un " Código de límite de frecuencia excedido - 88 ", o " Devuelto en API v1.1 cuando una solicitud no se puede atender debido a que el límite de frecuencia de la aplicación se ha agotado para el recurso. “. ¿Cómo podemos superar ese límite?
Bueno, la respuesta está frente a nosotros: un algoritmo codicioso. Si utilizamos este enfoque, en cada paso, podemos asumir que el usuario con más seguidores es el único a considerar: al final, solo necesitamos cuatro consultas. ¡Toda una mejora!
El resultado de esos dos enfoques será diferente. En el primer caso, obtenemos 16, la solución óptima, mientras que en el segundo, el número máximo de seguidores alcanzables es simplemente 12.
¿Será tan valiosa esta diferencia? Decidiremos más tarde.
3. Implementación
Para implementar la lógica anterior, inicializamos un pequeño programa Java, donde imitaremos la API de Twitter. También haremos uso de la biblioteca de Lombok.
Ahora, definamos nuestro componente SocialConnector en el que implementaremos nuestra lógica. Tenga en cuenta que vamos a poner un contador para simular restricciones de llamadas, pero lo reduciremos a cuatro:
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; } } Luego, agregaremos un método para recuperar la lista de seguidores de una cuenta específica:
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(); } Para respaldar nuestro proceso, necesitamos algunas clases para modelar nuestra entidad de usuario:
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 codicioso
Finalmente, es hora de implementar nuestra estrategia codiciosa, así que agreguemos un nuevo componente, GreedyAlgorithm , en el que realizaremos la recursividad:
public class GreedyAlgorithm { int currentLevel = 0; final int maxLevel = 3; SocialConnector sc; public GreedyAlgorithm(SocialConnector sc) { this.sc = sc; } }Luego, necesitamos insertar un método findMostFollowersPath en el que encontraremos al usuario con más seguidores, los contaremos y luego procederemos al siguiente paso:
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; }Recuerde: aquí es donde realizamos una elección codiciosa. Como tal, cada vez que llamemos a este método, elegiremos uno y solo un elemento de la lista y seguiremos adelante: ¡Nunca retrocederemos en nuestras decisiones!
¡Perfecto! Estamos listos para comenzar y podemos probar nuestra aplicación. Antes de eso, debemos recordar completar nuestra pequeña red y, finalmente, ejecutar la siguiente prueba unitaria:
public void greedyAlgorithmTest() { GreedyAlgorithm ga = new GreedyAlgorithm(prepareNetwork()); assertEquals(ga.findMostFollowersPath("root"), 5); }3.2. Algoritmo no codicioso
Creemos un método no codicioso, simplemente para comprobar con nuestros ojos lo que sucede. Entonces, debemos comenzar con la construcción de una clase 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
En contextos cambiantes y cambiantes como las redes sociales, los problemas que requieren encontrar una solución óptima pueden convertirse en una terrible quimera: difíciles de alcanzar y, al mismo tiempo, poco realistas.
Superar las limitaciones y optimizar las llamadas a la API es un gran tema, pero, como hemos comentado, las estrategias codiciosas son efectivas. Elegir este tipo de enfoque nos ahorra mucho dolor y nos devuelve valiosos resultados a cambio.
Tenga en cuenta que no todas las situaciones son adecuadas: debemos evaluar nuestras circunstancias en todo momento.
Como siempre, el código de ejemplo de este tutorial está disponible en GitHub.