Java Developer Advocate chez Oracle, José Paumard nous présente la nouvelle API Gatherers qui, depuis Java 24, vient se greffer sur l’API Stream Java sortie il y’a 11 ans avec Java 8.

Tout comme l’API Collector, José commence par rappeler que l’API Gatherers est indépendante de l’API Stream. Cette API a été introduite dans Java via la JEP 485 Stream Gatherers conduite par Viktor Klang. Les plus curieux pourront regarder la vidéo Youtube du Deep Dive qu’a animé Viktor lors de la conférence JavaOne qui s’est tenue en mars 2025.

L’article The Gatherer API permet également d’approfondir votre étude des Gatherers. Notez que le site dev.java permet désormais d’exécuter des snippets Java (pas directement dans le navigateur, mais sur un serveur Cloud).

Toutes les classes et interfaces de l’API Gatherers ont été ajoutées au package java.util.stream.

Opérations intermédiaires et terminales d’un Stream

Pour rappel, un Stream se connecte à une source de données (collections, fichier, générateur de nombres aléatoires, regex). Un stream est composé de :

1. zéro, une ou plusieurs opérations intermédiaires qui retournent un Stream
2. une seule et unique opération terminale qui retourne un résultat et clôture le Sream.

Viktor assimile l’API Stream à celle d’un Builder : on décrit un pipeline d’opérations puis on appelle l’opération terminale pour déclencher son traitement.

Exemples d’opération terminales proposées par l’API Stream :

• reduce() : opération de réduction
• findFirst() : renvoie un objet de type Optional qui encapsule le premier élément du Stream s’il existe, ne consomme pas tous les éléments du Streams.
• collect() : prend en paramètre un Collector
• toList() : méthode raccourcie disponible depuis Java 16

Les Collector permettent de créer ses propres opérations de réduction. Gatherer est le pendant des Collector pour les opérations intermédiaires. Une différence notable est qu’un Collector ne peut pas interrompre un Stream : il ne le connait pas.

Le JDK propose de nombreuses opérations intermédiaires comme map(), filter(), dropWhile(), limit() ou bien encore mapMulti() ajoutée plus récemment. L’API Gatherers va nous permettre de créer nos propres opérations intermédiaires. Ce n’était pas possible jusque-là. Parmi ces opérations intermédiaires, il existe des opérations stateless comme filter() et des opérations statefull come sorted() qui doivent consommer tous les éléments du stream avant de produire quelque chose vers le down stream.

Il n’y avait pas moyen de créer d’opérations intermédiaires jusqu’aux Gatherers.

Que propose l’API Gatherer ?

L’interface générique Gatherer s’appuie sur 3 paramètres :

interface Gatherer<T, A, R> { 
    Integrator<A, T, R> integrator(); 
}

• T : type des éléments consommés
• A : type mutable utilisé en interne par les Gatherers
• R : type des éléments poussés dans le down stream

Avec sa méthode principale integrator(), José compare l’interface Gatherer à une interface fonctionnelle de type Supplier.

L’interface Gatherer met à disposition 3 interfaces fonctionnelles imbriquées dont nous étudierons le fonctionnement : Downstream, Greedy et Integrator.
Exemple de le l’interface Integrator :

@FunctionalInterface
interface Integrator<A, T, R> {
    boolean integrate(A state, T element, Downstream<? super R> downstream); 
}

Afin de pouvoir utiliser le Gatherer, l’interface Stream de l’API Stream propose désormais depuis Java 24 la méthode gather :

Stream<R> downStream = upstream.gather(gatherer);

Le JDK s’enrichit de la classe factory Gatherers (notez son pluriel) utilisées par les différentes implémentations des méthodes of() de l’interface Gatherer.

Publier dans le Downstream

Un Downstream reçoit des données traitées par une opération intermédiaire. C’est le flux de sortie d’un Gatherer.
Voici un exemple de Gatherer chargé de pousser un élément dans le Downstream :

Gatherer<T, ?, R> gatherer = Gatherer.of(
     (_, element, downStream) -> downStream.push(element) // returns a boolean
);

Le booléen renvoyé en retour est important. Son fonctionnement est subtil : renvoyer false permet l’arrêt du traitement des éléments suivants. Il ne se passe alors plus rien lorsqu’on pousse des éléments au downStream qui n’en accepte désormais plus. Aucune exception n’est levée. Cela peut surprendre.

Dans le jargon de l’API Gatherer, lorsqu’un Integrator retourne directement la valeur du downstream.push(element), on dit qu’il est Greedy. Il traitera nécessairement tous les éléments du Stream. Son exécution est optimisée. Exemple :

Gatherer<T, ?, R> gatherer = Gatherer.of(
    Integrator.of((_, element, downstream) -> downstream.push(element))
);

Lorsqu’un Integrator n’utilise pas de coupe-circuit et consomme donc l’intégralité des éléments reçus, il est recommandé d’utiliser la méthode factory Integrator.ofGreedy() pour instancier un Integrator :

Gatherer<T, ?, R> gatherer = Gatherer.of(
    Integrator.ofGreedy((_, element, downstream) -> downstream.push(element))
);

Un Downstream possède un état nommé rejecting. La méthode isRejecting() de l’interface Downstream propose d’y accéder. Cet état a 3 propriétés :

1. Commence à false
2. Ne peut commuter que de false vers true (ne peut pas se rouvrir)
3. L’état de peut commuter que lors d’un push() => règle spécifique aux API du JDK

José nous met en garde : dans un Integrator, l’appel à la méthode isRejecting() ne sert à rien. Il s’agit d’une fausse optimisation qui s’apparente à du code mort.

(_, element, downstream) -> {
    if (downstream.isRejecting()) { //
        return false;               // Condition inutile
    }                               // 
    return downstream.push(mapper.apply(element));
}

José continue sa présentation en nous expliquant les bonnes pratiques à adopter lorsqu’on publie sur le Downstream :

• Ne pas faire de test isRejecting() sur le Downstream
• Privilégiez l’usage de la méthode allMath() plus efficace que takeWhile()
• Fermer les ressources si nécessaire. Lorsque le Stream agit sur un fichier, il faut fermer le fichier et ne pas oublier le try with ressources

Exemple exempté de bugs :

(_, element, downstream) -> {
    try (Stream<R> elements = flatMapper.apply(element);) {
        return elements.allMatch(downstream::push); 
    }
}

Un Downstream n’est pas un objet thread-safe. Il est donc nécessaire de ne pas générer d’effet de bord sur les données externes. Attention aux race conditions et plus particulièrement dans les parallel streams.
A ce titre, la méthode Gatherer.oSequential() permet de créer un Gatherer séquentiel (non parallélisable).

L’élément state est un état mutable pouvant être utilisé par le Gatherer. En complément de l’Integrator, il est nécessaire de fournir à l’API de création d’un Gatherer un Supplier chargé d’initialiser l’état du state.

Exemple d’un Gatherer limitant le nombre d’éléments et initialisant un compteur :

class Counter { long count = 0L; }

var gatherer = Gatherer.ofSequential( 
    Counter::new, // the initializer
    (state, element, downstream) -> {
        if (state.count++ < limit) {
            return downstream.push(element);
        } else {
            return false;
        }
});

A noter que l’opérateur var retient le type des classes anonymes.

Pour agir sur l’ensemble des données du Gatherer, on peut stocker les éléments dans une collection tel qu’un HashSet dans l’exemple suivant « Distinct Gatherer »:

var gatherer = Gatherer.ofSequential(
    () -> new Object() { Set<T> set = new HashSet<>(); },
    (state, element, downstream) -> {
        if (state.set.add(element)) {
            return downstream.push(element);
        } else {
            return true;
        }
});

Pour publier l’état final d’un Gatherer, on peut ajouter après l’Initializer et l’Integrator une 3ième lambda de type BiConsumer agitant comme finisher et pouvant consommer tous les éléments du state :

var gatherer = Gatherer.ofSequential(
    () -> new Object() { Set<T> set = new TreeSet<>(); },
    (state, element, downstream) -> { ... },
    (state, downstream) -> { // finisher
        state.set.stream().allMatch(downstream::push);
});

Les Parallel Gatherers

Les développeurs Java peuvent choisir de construire un Gather supportant ou non le parallélisme et les parallel Streams. A cet effet, 2 méthodes de type fabrique sont à leur disposition :

1. Gatherer.of()
2. Gatherer.ofSequential()

Pour supporter le parallélisme, l’API Gatherer adopte le principe suivant : un objet state par thread. Cela permet de ne pas utiliser de collections synchronisées dégradant les performances.
Dans chaque Stream parallèle, on a donc autant de state que de threads. A la fin de l’opération intermédiaire, il est nécessaire d’utiliser un Combiner pour combiner tous les états.

Ce Combiner est un 4^ième paramètre à passer à la méthode factory of() :

var gatherer = Gatherer.of(
    () -> new Object() { Set<T> set = new HashSet<>(); }, 
    (state, element, downstream) -> { // executed in
        state.set.add(element); // different threads
        return true;
    },
    (state1, state2) -> { // combiner
        state1.set.addAll(state2.set);
        return state1;
    },
    (state, downstream) -> { // finisher
        state.set.allMatch(downstream::push);
    }
);

Les Sequential Gatherers ne peuvent pas être appelés en même temps depuis différents thhreads. Ils ne possèdent pas de Combiner. Pour autant, José nous explique que l’API Stream est capable de séquencer les appels vers un Sequential Gatherer. Cette fonctionnalité est nouvelle et donc à utiliser avec précaution. Tester les perfs.

Pour aller plus loin, José nous invite à consulter le repo GitHub SvenWoltmann/stream-gatherers. Le JDK vient avec de nouveaux Gatherers comme scan(), fold() ou bien encore mapConcurrent().
Des librairies tierces comme gatherers4j proposent également leur propres gatherers : reverse(), repeat(n), groupBy(fn) …

Pour conclure, retenons qu’un Gatherer est construit sur 4 éléments. Tous ne sont pas obligatoires.

Conférence : Devoxx France 2024
Date : 17 avril 2024
Speakers : Abdellfetah Sghiouar (Google), Cédrick Lunven (DataStax)
Format : Deep Dive (3h)
Slides : https://github.com/datastaxdevs/conference-2024-devoxx-france/blob/main/slides.pdf
Vidéo Youtube : https://www.youtube.com/watch?v=6n8JysFyVA8
Repo GitHub : https://github.com/datastaxdevs/conference-2024-devoxx-france

Dans ce Deep Dive de 3h (anciennement nommé Université à Devoxx France), Abdellfetah Sghiouar et Cédrick Lunven nous expliquent comment intégrer l’intelligence artificielle générative (la fameuse GenAI) dans nos applications Java, et ceci sans expertise en machine learning ou en Python (ce qui tombe bien). Après nous avoir initié aux Large Language Models (LLMs) et aux techniques de prompting, ils nous apprennent à coder en Java avec LangChain4J et Spring AI pour utiliser le LLM Gemini de Google dans nos projets Java.

L’approche Retrieval Augmented Generation (RAG) est illustrée par son intégration avec des bases de données vectorielle comme Apache Cassandra, ceci pour générer des réponses avec nos propres données. Les Developer Advocates de Google et de DataStax nous donnent des stratégies pour minimiser les erreurs et les hallucinations des LLMs. Les modèles multimodaux (LMM) plus avancés seront également introduits.

Cédrick est Developer Advocate chez DataStax
Il y’a 10 ans, il s’est fait connaitre par la communauté en créant le projet ff4j.
Ces dernières années, il a énormément travaillé sur Cassandra. Cédrick contribue aux projets OpenSource Langchain4j et Spring AI. Je l’ai personnellement rencontré dans le cadre du projet Spring Petclinic Reactive.

Abdel est Developer Advocate chez Google
Expert en Kubernetes, il travaille notamment sur le déploiement des solutions d’IA sur k8s.

Introduction

Abdel souligne le rôle prépondérant de Google dans le domaine de l’IA Generative.

• La GenAI a émergé en 2017 avec l’invention du modèle Transformer par Google
• En 2018, Google a créé le modèle de langage BERT qui a permis d’améliorer les performances en traitement automatique des langues (NLP en anglais).
• En 2019, création de AlphaFold permettant de prédire comment une protéine se développe à partir de leur séquence en acides aminés. Là où un doctorant passé toutes ses études à prédire la structure d’une protéine, AlphaFold l’a fait pour toutes les protéines sur la terre
• 2019 : Google ouvre en open source le modèle text-to-text Transfer Transformer.
• 2021 : Google introduit LaMDA, un modèle de langage conçu spécifiquement pour améliorer les interactions conversationnelles entre les humains et les systèmes d’IA
• 2022 : sorti du modèle de langage PaLM
• 2023 : sorti de PalM 2
• 2024 : lancement du chatbot Gemini (anciennement connu sous le nom de Bard)

Abdel poursuit sa présentation par un rappel des termes utilisés dans l’IA.

L’IA englobe les différentes techniques permettant de reproduire le raisonnement humain.

Le Machine Learning (ML) inclue le Deep Learning qui inclue à son tour l’IA Générative.
Le ML nécessite des données d’entrainement et fait appel à la Data Science.
Le GenAI inclue Image Gen et LLM.

Les LLM sont des réseaux de neurones basés sur l’architecture Transformers. Ils sont capables de reconnaitre, prédire et générer du langage.

Un LLM génère un mot à la fois. Il calcule la probabilité du prochain mot en se basant sur une approche statistique.

Le fonctionnement d’un LLM et de l’IA générative est particulièrement bien illustré sur le site du Financial Times ig.ft.com/generative-ai

Le site https://lifearchitect.ai/models/ référence la taille de nombreux LLM :

PaLM 2 a été entrainé sur 340 milliards de paramètres et, en ce mois d’avril 2024, bat tous les records.
Se référer à l’article Pathways Language Model (PaLM): Scaling to 540 Billion Parameters for Breakthrough Performance

D’après Abdel, les LLMs se sont démocratisés grâce à la disponibilité de cartes graphiques moins onéreuses et à la possibilité d’entrainer son modèle dans le Cloud.
Autre hypothèse formulée : les investisseurs croient désormais en l’IA !

Cas d’utilisation des LLM en 2024 :

• Langage : écrire du texte, faire des résumé, extraction de texte, créer un chat, classification, recherche, idéation
• Code : génération de code (boilerplate), complétion de code (compagnon/assistant), chat, conversion de code
• Speech : speech-to-speech (traduction), text-to-speech
• Vision : génération d’images, édition, captioning, image Q&A, image search, génération des transcripts de vidéos (comme à Devoxxx France 2024 

Google propose de nombreuses offres regroupées dans le portfolio Vertex AI :

La première démo en Java de ce Deep Dive commence par l’utilisation de Vertex AI en ajoutant la dépendance maven com.google.cloud:google-vertexai

La classe Demo01_VertexClientChat fait appel à Gemini Pro pour répondre à quelques questions :

@Test
void testChat() throws Exception {
    try (VertexAI vertexAI = new VertexAI(GCP_PROJECT_ID, GCP_PROJECT_LOCATION)) {
        GenerateContentResponse response;

        GenerativeModel model = new GenerativeModel("gemini-pro", vertexAI);
        ChatSession chatSession = new ChatSession(model);

        response = chatSession.sendMessage("Hello.");
        System.out.println(ResponseHandler.getText(response));

        response = chatSession.sendMessage("What are all the colors in a rainbow?");
        System.out.println(ResponseHandler.getText(response));

        response = chatSession.sendMessage("Why does it appear when it rains?");
        System.out.println(ResponseHandler.getText(response));
    }
}

Une seconde démo demande au LLM multimodal gemini-vision-pro de décrire la photo d’un coucher de soleil. Le code envoie simultanément au LLM l’image et la question. Le code Java dépend du client Java Gemini et donc de Vertex AI.
Extrait de la classe Demo02_VertexClientVisionPro :

@Test
void testVision() throws Exception {
  // Load the image
  byte[] imageBytes;// = Files.readAllBytes(Paths.get(imageName));
  String resourcePath = "/img1.png"; // Resource path in the classpath

  try (InputStream is = Demo02_VertexClientVisionPro.class.getResourceAsStream(resourcePath)) {
    assertThat(is).isNotNull();
    imageBytes = is.readAllBytes();
    System.out.println("Image bytes read successfully. Length: " + imageBytes.length);
    try (VertexAI vertexAI = new VertexAI(GCP_PROJECT_ID, GCP_PROJECT_LOCATION)) {
      GenerativeModel model = new GenerativeModel("gemini-pro-vision", vertexAI);
      GenerateContentResponse response = model.generateContent(
          ContentMaker.fromMultiModalData(
              "What is this image about?",
              PartMaker.fromMimeTypeAndData("image/jpg", imageBytes)
          ));

      System.out.println(ResponseHandler.getText(response));
    }
  } catch (IOException e) {
    System.out.println("Error reading the image file.");
  }
}

Gemini

Gemini est le modèle d’IA le plus performant de Google Deep Mind. C’est un modèle multimodale pouvant traiter à la fois du texte, des images et de la vidéo.
Une version Nano est en cours d’incorporation dans Flutter afin d’utiliser la carte graphique du téléphone.
Gemini 1.5 accepte en entrée un livre d’un million de mots. On est loin des premiers prompts limités à quelques centaines de mots.

3 adresses permettent de tester Gemini :

1. https://console.cloud.google.com/vertex-ai/model-garden :
2. https://ai.google.dev/ : nécessite une clé
3. https://ai.google.dev/examples

Démo possible sur https://gemini.google.com/app avec un simple compte Google. Exemple « Quelle est la hauteur de la tour Eiffel ? »

Gemma

Gemma est un modèle OpenSource mis à disposition par Google. Basé sur Gemini, Gemma est téléchargeable depuis HuggingFace. On peut le déployer n’importe où et l’utiliser en Java.

Abdel poursuit ce talk par une démo de la webapp bed-time-stories.web.app créée par Guillaume Laforge et qui permet de générer une histoire pour les enfants. La démo utilise Vertex AI. Abdel utilise Gemma avec quelques commandes curl pour générer une histoire.
Cedrick reprend la main.

Langchain4j

Le projet ollama permet de faire tourner des LLM en local sur son poste de dév.
On peut installer ollama sur Mac, Linux et Windows : https://ollama.com/download
Ollama vient avec une CLI permettant de récupérer un modèle de LLM comme gemma:2b et gemma:7b
Commande permettant de faire tourner un modèle :

> ollama run gemma:7b
Nul besoin de compte (mais peut-être d’une carte Nvidia ?)

Une fois le modèle démarré, on peut l’interroger à base d’une simple commande curl :

curl http://localhost:11434/api/generate -d '{
"model": "gemma:7b",
"prompt": "Pourquoi le ciel est bleu ?"
}'

Plutôt que de passer par curl ou d’utiliser en Java un RestTemplate, Cédric propose d’utiliser la librairie Langchain4j pour faire cette demande.
Langchain4j est une implémentation de Langchain, bibliothèque populaire du monde Python et JavaScript.
Le code suivant est extrait de la classe _21_GemmaChat :

@Test
void talkWithGemma() {
    ChatLanguageModel gemma = OllamaChatModel.builder()
            .baseUrl("http://localhost:11434/api/")
            .modelName("gemma:7b")
            .build();

    System.out.println(gemma.generate("Present yourself , the name of the model, who trained you ?"));
}

L’interface ChatLanguageModel vient de langchain4j-core et la classe OllamaChatModel vient de langchain4j-ollama.

Langchain4j sait manipuler des images. La classe _14_ImageModel_GenerateTest montre comment faire générer une photo d’un coucher de soleil sur une plage de Malibu au LLM Vertex AI. Cette fois ci, on utilise la librairie langchain4j-vertexai avec le builder VertexAiImageModel
D’autres classes d’abstraction de langchain4j existent : LanguageModel, ImageModel

Langchain4j est le leader fournissant le modèle théorique. Tous les fournisseurs de LLM implémentent le langage model, créent une Pull Request et la soumettent à la communauté. Particulièrement doués en IA, les chinois contribuent également.
Voici les LLM supportés par Lanchain4j :

Cédric continue le talk par une démo utilisant langchain4j-gemini avec le modèle StreamingChatLanguageModel et l’appel au builder VertexAiGeminiStreamingChatModel
Se référer au test _10_LanguageModelSayHello

Spring AI

Plus jeune et développé par l’équipe Spring, le framework Spring AI est un concurrent de Langchain4j.
Cédrick nous montre un HelloWorld en Spring Boot basé sur Gemini:

@SpringBootTest
class _01_LanguageModel_SayHelloTest {

    @Autowired
    private VertexAiGeminiChatClient client;

    @Value("classpath:/prompts/system-message.st")
    private Resource systemResource;

    @Test
    void roleTest() {
        String request = "Tell me about 3 famous pirates from the Golden Age of Piracy and why they did.";
        String name = "Bob";
        String voice = "pirate";
        UserMessage userMessage = new UserMessage(request);
        SystemPromptTemplate systemPromptTemplate = new SystemPromptTemplate(systemResource);
        Message systemMessage = systemPromptTemplate.createMessage(Map.of("name", name, "voice", voice));
        Prompt prompt = new Prompt(List.of(userMessage, systemMessage));
        ChatResponse response = client.call(prompt);
        System.out.println(response.getResult().getOutput().getContent());
    }

}

La classe _01_LanguageModel_SayHelloTest montre l’utilisation de classes d’abstraction comme UserMessage, Message, Prompt ou bien encore ChatResponse.
La configuration du LLM est centralisée dans le fichier application.properties :

spring.ai.vertex.ai.gemini.projectId=devoxxfrance
spring.ai.vertex.ai.gemini.location=us-central1
spring.ai.vertex.ai.gemini.chat.options.model=gemini-pro
spring.ai.vertex.ai.gemini.chat.options.temperature=0.8
spring.ai.vertex.ai.gemini.chat.options.topK=2
spring.ai.vertex.ai.gemini.chat.options.topP=0.9
spring.ai.vertex.ai.gemini.chat.options.maxTokens=100
#spring.ai.vertex.ai.gemini.credentialsUri=

Prompt Engineering

La seule commande envoyée à un LLM est une ligne de texte, le fameux prompt.
Quelques bonnes pratiques permettant d’interagir avec le LLM nous sont données :

Comme contraintes, il peut être intéressant de demander au LLM de ne pas répondre aux questions dont il ne connait pas la réponse. Cela permet de limiter les hallucinations. Exemple de contexte : « Si l’on te pose des questions qui sort des objectifs qu’on t’a donné, répond que tu ne sais pas. »
Avec un prompt assez long, on peut souvent contourner les frontières du LLM.

En complément de cette phrase, on envoie au LLM différents paramètres.

Température comprise entre 0 et 1 : niveau d’expression qu’on donne au LLM
0 : plus précis, robotique
1 : créatif, hallucination possible
Le choix de la température dépend des uses cases. Dans le cas d’une recherche documentaire par exemple, on emploie une température basse.

Top P favorisant la diversité et la créativité.
Jusqu’à combien de mots tu peux mettre des réponses avec un degré de probabilité
Spécifiez une valeur faible pour les réponses moins aléatoires et une valeur plus élevée pour les réponses plus aléatoires

Top K similaire au Top P, mais en moins dynamique

Tokens : taille de la réponse
Plus la réponse est longue, plus le cout augmente et sa précision baisse.

Des techniques avancées de prompt engineering permettent d’améliorer la rédaction des prompts.

Few-Shot Learning

On envoie au LLM quelques exemples afin qu’ils comprennent mieux ce que l’on souhaite lui demander.

Chain of Thoughts

Chaine de pensée : donner un raisonnement pour que le LLM trouve le résultat.

CoT + Self consistency

Le LLM utilise plusieurs raisonnements et sélectionne la réponse finale en fonction du plus grand nombre de réponses similaires.

ReAct

Les LLM savent désormais faire appel à des systèmes externes, comme par exemple se brancher sur Bing ou appeler un service météo.

Prompt Best Practices

Nous sont données 10 bonnes pratiques de prompt engineering :

1. Un exemple vaut 100 instructions
2. DARE Determine Appropriate Response
   • Rôles, Personas, Public : votre vision
   • Objectifs : votre mission
   • Portée : si tu ne le sais pas, dis-le-moi !
3. Adapter la température au cas d’utilisation
4. Utilisez un langage naturel détaillé pour dévoiler une chaîne d’invites
5. Structurer les prompts. L’ordre est important. Cédrick recommande de spécifier au prompt quel est l’objectif
6. Responsible AI and filters : lorsqu’on enlève les filtres d’un LLM OpenSource on peut avoir de grosses surprises (ex : débrayer la procédure de fabrication d’une bombe).
7. Test, Measure, Improve, Repeat : revue par le même LLM ou même d’autres LLM
8. Be specific, no open questions. Se limiter (ex: 500 caractères). Sinon le contexte dilue la question
9. Review from multiple people
10. Detailed algorithms and reasoning problems

Prompt Template

Java permet d’utiliser des templates de prompt. Cédrick compare un template à une boite avec des trous, du publipostage Word, un template Velocity ou encore un template Mustache.
A cet effet, Langchain4j et Spring IA fournissent tous les 2 une classe PromptTemplate
La classe _16_PromptTemplateTest donne un exemple d’utilisation :

@Test
void prompt() {
    PromptTemplate promptTemplate = PromptTemplate.from("""
        Explain me why a {{profile}} should attend conference {{conference}}.
        The conference is on {{current_date}} at {{current_time}} with {{current_date_time}}
        """);

    Map<String, Object> variables = new HashMap<>();
    variables.put("profile", "Java Developer");
    variables.put("conference", "Devoxx France");

    Prompt prompt = promptTemplate.apply(variables);
    Response<String> response = getLanguageModel("text-bison").generate(prompt);
    System.out.println(response.content());
}
protected LanguageModel getLanguageModel(final String modelName) {
    return VertexAiLanguageModel.builder()
            .project(GCP_PROJECT_ID)
            .endpoint(GCP_PROJECT_ENDPOINT)
            .location(GCP_PROJECT_LOCATION)
            .publisher(GCP_PROJECT_PUBLISHER)
            .modelName(modelName)
            .build();
}

Limitations des LLM

Un LLM :

• a une date de fraicheur des informations
• n’a pas accès à la base documentaire de l’entreprise
• peut halluciner si il n’est pas bien prompté
• accepte un nombre limité de tokens en entrée
• est lent à répondre

Pour utiliser ses propres connaissances, il est nécessaire d’utiliser un Retrieval-Augmented Generation (RAG)

Vector Search

Pour enrichir les données d’un LLM, il faut les stocker dans une base vectorielle.
Avant cela, il faut les convertir en vecteur. C’est le moment où vous devez faire appel à vos souvenirs de cours de maths.

Un vecteur possède une direction et une longueur.
Il est représenté dans un espace à plusieurs dimensions.
En fonction du modèle (vidéo, texte, image), on n’utilise pas la même dimension.
La longueur d’un vecteur s’appelle la norme et se calcule par la racine carrée de la somme des coefficients au carré.
Dans un espace en 3D, la sphère a pour norme |v|=1
Les composantes d’un vecteur sont appelés Embeddings.

Le Prompt est également transformé en vecteur.
On recherche des vecteurs qui sont proches les uns des autres. Cela nécessite de calculer une similarité entre 2 vecteurs.
En maths, il y’a plusieurs possibilités de calculer une distance. Un slide est préférable à un long discours :

La plus connue est la distance euclidienne. Elle s’appelle L2 et nécessite beaucoup de calculs.
Cédrick nous fait remarquer que la dimension des vecteurs d’une base vectorielle est multiple de 284.
Les bases vectorielles utilisent plus couramment la distance nommée « Angular distance » ou « cosine similarity »

Chaque base de données implémente sa propre formule. Le plus important consiste à trouver les vecteurs les plus proches. Le plus simple consiste à travailler sur la sphère unité. Je vous laisse apprécier :

Ces calculs amènent beaucoup de zéro après la virgule. En Java, on arrive facilement aux limites de la précision du type double et il est nécessaire d’utiliser des BigDecimal.
La métrique à utiliser dépend du cas d’utilisation.

Le k-Nearest Neighbors (kNN) est une technique fondamentale dans le domaine du Vector Search. Elle permet de trouver les k vecteurs les plus proches d’un vecteur requête (query vector) dans un espace vectoriel. Les présentateurs nous invitent à lire l’article K Nearest Neighbor Classification – Animated Explanation for Beginners

Les calculs de similarité permettant de trouver quels sont les vecteurs les plus proches sont longs, d’où la nécessité d’approximer. L’Approximate Nearest Neighbors (ANN) est un ensemble de techniques qui cherchent à identifier les k voisins les plus proches d’un vecteur requête (query vector) dans un espace vectoriel de haute dimension, mais en introduisant une approximation pour gagner en efficacité.

Le partitionnement des datasets se fait dans un graphe de proximité.
Chaque point du graphe est un vecteur. Le edge est la distance (calculée lorsqu’on sauve le vecteur).

Naturellement, de nombreuses bases vectorielles comme qdrant ou milvus se sont lancées dans le secteur des embeddings. Les bases NoSQL et relationnelles existantes se sont également mises à supporter les vecteurs. On peut citer pgvector sur PostgreSQL, Elasticsearch, Neo4j (qui faisait déjà du graphe) mais encore Apache Cassandra.

Cassandra

Cassandra est une base OSS gouvernée par la fondation Apache.
C’est une base tabulaire, ce qui signifie qu’on ne peut pas faire de jointure lors d’un select et qu’il faut penser au requêtage dès la sauvegarde en dénormalisant les données.
Cassandra ferait une parfaite matrice d’adjacence.
Les nœuds sont distribués et contiennent entre 2 à 4 To de données. L’ajout d’un nœud nécessite de répartir les données. Cassandra scale très bien. Les données sont redondées.

La version 5 de Cassandra introduit le nouveau type Vector :

CREATE TABLE IF NOT EXISTS vsearch.products (
  id int PRIMARY KEY,
  name TEXT,
  description TEXT,
  item_vector VECTOR<FLOAT, 5> //5-dimensional embedding
);

Ainsi qu’un nouvel index de stockage attaché appelé StorageAttachedIndex :

CREATE CUSTOM INDEX IF NOT EXISTS ann_index
ON vsearch.products(item_vector)
USING 'StorageAttachedIndex';

ANN est une famille d’algorithme de recherche approximative.
L’opérateur ANN OF permet d’effectuer efficacement des recherches ANN sur leurs données lors d’une recherche CQL :

SELECT * FROM vsearch.products
ORDER BY item_vector ANN OF [0.15, 0.1, 0.1, 0.35, 0.55]
LIMIT 1;

Le site ann-benchmarks.com compare les performances brutes des algorithmes de recherche approximative des plus proches voisins.

Aujourd’hui, presque toutes les bases utilisent la technique du HNSW (pour Hierarchical Navigable Small World) avec des Vector Index stockés dans plusieurs couches : Lucene (Elastic, Solr, OpenSearch, MongoDB), Weaviate, Qdrant, PGVector.

Lucene avait déjà implémenté l’algo HNSW. Cassandra l’a utilisé dans Cassandra. Un problème majeur à son utilisation est que Java utilise beaucoup de mémoire, notamment lorsque dataset et sharding augmentent. Les ingénieurs de Cassandra ont donc planché sur une autre solution.
Dans un premier temps, Cassandra a testé l’algo DiskANN (papier implémenté par Microsoft en C). lls l’ont recodé en Java et l’ont baptisé jVector. Le projet jVector utilise Java 21 et la nouvelle API Vector du projet Panama permettant d’exploiter les instructions SIMD.

Vanama stocke le graphe sur un seul layer et crée plus de liens que nécessaires. Les distances sont précalculées lors de l’indexation. En mémoire, on ne monte plus les vecteurs en entier, mais des données plus petites, les centroids, et ceci par quantification. Au lieu de travailler avec un Vecteur, on utilise des centroids.

Le plus souvent, dans des cas métiers, une recherche par vecteur n’est pas suffisante. Il est nécessaire d’exploiter des métadonnées : date d’indexation, auteur, prise en compte des habilitations …
Lecture conseillé : 5 Hard Problems in Vector Search, and How Cassandra Solves Them

Pour choisir sa base de données vectorielles, Cédrick conseille aux architectes d’utiliser le comparateur Vector DB Comparison

Repartons dans notre IDE préféré pour montrer l’utilisation de Langchain4j et de Cassandra.
Cédrick utilise la nouvelle classe d’abstraction : EmbeddingModel
On lui donne du texte et il sort un vecteur.

Code extrait de la classe _51_EmbeddingModel :

@Test
void testEmbeddingModel() {
    Response<Embedding> embedding = getEmbeddingModelGecko().embed("Hello, World!");
    log.info("Dimension: {}", embedding.content().dimension());
    log.info("Vector: {}", embedding.content().vectorAsList());
}

protected EmbeddingModel getEmbeddingModelGecko() {
    return VertexAiEmbeddingModel.builder()
            .project(GCP_PROJECT_ID)
            .endpoint(GCP_PROJECT_ENDPOINT)
            .location(GCP_PROJECT_LOCATION)
            .publisher(GCP_PROJECT_PUBLISHER)
            .modelName("textembedding-gecko@001")
            .build();
}

La modélisation des données sous Cassandra est complexe. Aussi, pour faciliter la modélisation, l’usage de Cassio est recommandé.

S’en suit la démo _54_CassandraVectorStore montrant l’usage de tags pour filtrer des requêtes. La classe EmbeddingStore est mise à l’honneur.

@Test
void langchain4jEmbeddingStore() {
    // I have to create a EmbeddingModel
    EmbeddingModel embeddingModel = getEmbeddingModelGecko();

    // Embed the question
    Embedding questionEmbedding = embeddingModel
            .embed("We struggle all our life for nothing")
            .content();

    // We need the store
    EmbeddingStore<TextSegment> embeddingStore = new CassandraCassioEmbeddingStore(
            getCassandraSession(), TABLE_NAME, EMBEDDING_DIMENSION);

    // Query (1)
    log.info("Querying the store");
    embeddingStore
            .findRelevant(questionEmbedding, 3, 0.8d)
            .stream().map(r -> r.embedded().text())
            .forEach(System.out::println);

    // Query with a filter(2)
    log.info("Querying with filter");
    embeddingStore.search(EmbeddingSearchRequest.builder()
            .queryEmbedding(questionEmbedding)
            .filter(metadataKey("author").isEqualTo("nietzsche"))
            .maxResults(3).minScore(0.8d).build())
            .matches()
            .stream().map(r -> r.embedded().text())
            .forEach(System.out::println);

}

En production, il manque encore des fonctionnalités pour, par exemple, rafraichir les données de la base vectorielle tout en optimisant le cout.

A ce jour, toutes les bases de données vectorielles ne savent pas encore implémenter tous les filtres de Langchain4j. La distribution Cloud de Cassandra nommée AstraDB ajoute les filtres manquants.

Retrieval Augmented Generation (RAG)

Le processus Retrieval Augmented Generation (RAG) consiste à optimiser le résultat d’un LLM. 2 types de RAG existent : naive et advanced.

Un vecteur de dimension 1000 ne peut pas stocker l’intégralité d’un document. On découpe donc ce document en morceau (chunk). Il existe plusieurs techniques pour faire du chunking.
Des préprocesseurs commencent par lire les documents (avec par exemple Apache Tika et Apache PDFBox), retirent les balises, normalisent l’encodage (UTF-8). Ceci pour ne conserver que le texte brut. Chaque extension de fichier (ex : markdown) demande un parseur.
Sur OpenAI, on peut mettre entre 256 et 512 tokens par vecteur de dimension 1536.
Pour garder le contexte, les segments doivent se superposer.

Astuce pour sauvegarder le segment : ajouter un hash dans les métadonnées du document, ce qui évite de le réindexer pour rien.

Nouvelle démo basée sur le test_62_NaiveRag_RetrievalTest et montrant l’usage des interfaces ContentRetriever et Assistant de langchain4j :

@Test
void shouldRetrieveContent2() {

    ContentRetriever contentRetriever = EmbeddingStoreContentRetriever.builder()
            .embeddingStore(new AstraDbEmbeddingStore(getCollectionRAG()))
            .embeddingModel(getEmbeddingModelGecko())
            .maxResults(2)
            .minScore(0.5)
            .build();

    // configuring it to use the components we've created above.
    Assistant ai = AiServices.builder(Assistant.class)
            .contentRetriever(contentRetriever)
            .chatLanguageModel(getChatLanguageModelChatBison())
            .chatMemory(MessageWindowChatMemory.withMaxMessages(10))
            .build();

    String response = ai.answer("Who is Johnny?");
    System.out.println(response);
}

Les advanced RAG consistent à mettre à disposition un query router utile, par exemple, pour séparer les requêtes des tenants, exploiter les niveaux de confidentialité des documents …

Lors de longues discussions, on peut atteindre les limites du LLM. Il est alors possible de faire un résumer de l’historique de la conversation. Usage des Query Transformer et de la classe CompressingQueryTransformer de langchain4j.

Lorsqu’il y’a plusieurs résultats, il faut les agréger via des Query Aggregator. Les algorithmes de reranking peuvent utiliser d’autres algorithmes. La star du reranking s’appelle Cohere.
La classe de test _66_AdvancedRag_QueryReranking en donne un exemple d’utilisation :

@Test
void shouldRerankResult() {

    // Re Ranking
    ScoringModel scoringModel = CohereScoringModel.withApiKey(System.getenv("COHERE_API_KEY"));

    ContentAggregator contentAggregator = ReRankingContentAggregator.builder()
            .scoringModel(scoringModel)
            .minScore(0.8)
            .build();

    RetrievalAugmentor retrievalAugmentor = DefaultRetrievalAugmentor.builder()
            .contentRetriever(createRetriever("/johnny.txt"))
            .contentAggregator(contentAggregator)
            .build();

    Assistant assistant =  AiServices.builder(Assistant.class)
            .chatLanguageModel(getChatLanguageModelChatBison())
            .retrievalAugmentor(retrievalAugmentor)
            .chatMemory(MessageWindowChatMemory.withMaxMessages(10))
            .build();

    System.out.println( assistant.answer("Tell me 10 things about Johnny"));
}

A noter l’utilisation des interfaces RetrievalAugmentor et ScoringModel de langchain4j.

Functions calling & Semantic Search

Ce talk se termine par une démonstration de la notion de Tool de langchain4j.
Pour récupérer la météo à Paris, Gemini sait qu’il existe une API permettant de récupérer le temps.
En java, on annote une méthode avec @Tool, ce qui permet au LLM d’appeler ce tool lorsqu’on lui pose la question d’additionner 2 nombres.
Extrait de la classe de test _71_CallFunctionTest :

static ChatLanguageModel model= VertexAiGeminiChatModel.builder()
        .project(GCP_PROJECT_ID)
        .location(GCP_PROJECT_LOCATION)
        .modelName("gemini-pro")
        .build();

static class Calculator {
    @Tool("Adds two given numbers")
    double add(double a, double b) {
        System.out.printf("Called add(%s, %s)%n", a, b);
        return a + b;
    }
}

interface Assistant {
    String chat(String userMessage);
}

@Test
void testFunctionCalling1() {



    Calculator calculator = new Calculator();

    Assistant assistant = AiServices.builder(Assistant.class)
            .chatLanguageModel(model)
            .chatMemory(MessageWindowChatMemory.withMaxMessages(10))
            .tools(calculator)
            .build();

    String answer = assistant.chat("How much is 754 + 926?");
    System.out.println(answer);
}

D’ici quelques jours / semaines, après un repos bien mérité des organisateurs, l’intégralité des vidéos des keynotes, conférences et universités présentées lors de Devoxx France 2023 seront disponibles sur Youtube sur la chaîne Devoxx FR. Mes notes pourrons vous aider à vous faire rapidement un aperçu de leur contenu avant de les visionner.

Tout comme l’édition précédente, je n’y aurais pas été découvrir les dernières technos hypes de 2023. Paradoxalement, il m’a semblé y avoir plus de conférences sur le SQL que le NoSQL. Kubernetes, les applications natives, le Craft et Docker auront été au rendez-vous de cette 11^ième édition.

Mes notes classées par ordre de préférence :

1. Value Types et Pattern Matching – José Paumard et Rémi Forax
2. Loi de Conway : lorsque les bonnes pratiques ne suffisent plus – Julien Topçu
3. Gestion de la dette d’architecture dans le contexte d’hypercroissance – Cyril Beslay
4. CRAC vs GraalVM, pour un démarrage plus rapide – Lilian Benoit
5. Voyage au centre de la Veille – Fabien Hiegel et David Franck
6. Avoir un journal de codeur / codeuse – Sandrine Banas
7. Bootiful Spring Boot 3 – Josh Long
8. Le Craft : des concepts au déploiement à l’échelle – Matthieu Vincent et Guillaume Le Dain
9. A la découverte d’Accelerate – Geoffrey Graveaud
10. Container Builders : Which is the best image builder ? – Christian Nader
11. From Dallas to Happy days : Tips to positively hack your life – Emmanuel Bernard
12. Docker au service du DevSecOps – Carmen Piciorus
13. Le Cache HTTP – Hubert Sablonnière
14. Le Guide du Maitre du Donjon : Maitriser la cybersécurité en créant des challenges CTF – Adam Bertrand
15. Comment être condamné par la CNIL ? – Juliette Audema
16. Clean as You Code your projects – Nolwenn Cadic et Marco Comi

D’ici quelques jours, l’intégralité des vidéos des conférences et universités présentées lors de Devoxx France 2022 sont disponibles sur la chaîne Devoxx FR de Youtube.

Si vous souhaitez rapidement vous faire un avis sur leur contenu avant de les visionner ou si vous souhaitez garder une trace écrite de ce que vous y avez appris, je mets librement à disposition l’ensemble de mes 13 notes prises au cours de ces 3 jours riches en contenus et en découvertes. Entre les retards SNCF et mon Macbook vieillissant qui fait des siennes, le nombre est moindre que les années précédentes. Mais promis, j’essaierai de me rattraper en 2023 

Fait marquant, cette édition 2022 n’aura pas fait place à de nouvelles technos hypes. On peut se souvenir de Quarkus en 2019, Kafka en 2016 ou bien encore Angular.JS en 2013. Cette 10^ième édition aura été celle de la maturité : retours d’expérience, architecture, état de l’art, sécurisation du code et approfondissement du fonctionnement de la plateforme Java étaient au rendez-vous.

Mes notes classées par ordre de préférence :

1. Loom nous protègera-t-il du Braquage Temporel ? – José Paumard et Rémi Forax
2. OAuth 2.1 expliqué simplement (même si tu n’es pas dev) ! – Julien Topçu
3. Mieux maitriser TLS, OpenSSL et les certificats – Mathieu Humbert
4. Architecture microservices et coherence des données : mais on fait comment dans la vraie vie ? – Jean-François James
5. Valhalla, to the hell and back – Rémi Forax
6. Major migration made easy – Tim te Beek
7. Cybersécurité et générateur de nombres aléatoires – Mathis Hammel
8. Comprendre GraphQL – Guillaume Scheibel et Geoffroy Couprie
9. Connaissez-vous vraiment JWT ? – Karim Pinchon
10. A la découverte des Docker Dev Environments – Djordje Lukic et Guillaume Lours
11. Pourquoi DevOps ne tient pas ses promesses ? – Gérôme Egron et Guillaume Mathieu
12. Dans les coulisses du Cloud – Cécile Morange
13. Construire et déployer son application avec Argo dans Kubernetes – Paul-Henry Perrissel et Nicolas Mpacko Tongo

D’ici quelques jours, l’intégralité des vidéos des conférences et universités présentées lors de Devoxx France 2019 sont disponibles sur la chaîne Devoxx FR de Youtube.

Si vous souhaitez rapidement vous faire un avis sur leur contenu avant de les visionner ou si vous souhaitez garder une trace écrite de ce que vous y avez appris, je mets librement à disposition l’ensemble de mes 18 notes prises au cours de ces 3 jours riches en contenus et en découvertes.

Lors de cette édition 2019, les 2 frameworks hypes du moment Quarkus et Micronaut étaient sur le devant de la scène en permettant de développer des applications Java modernes et natives grâce à GraalVM. Poussée par l’essor des microservices, l’intégration de Java à Docker et son orchestrateur Kubernetes est de plus en plus poussée. Les indémodables étaient également de la partie : design d’API REST, montée de version de Java, qualimétrie, JavaEE (oups, pardon, JakartaEE) et sécurité.

Mes notes classées par ordre de préférence :

1. Quarkus : pourquoi et comment faire une appli Java Cloud Native avec Graal VM (Emmanuel Bernard et Clément Escoffier)
2. D’architecte à Métarchitecte : une évolution nécessaire (Rémi Cocula)
3. Construire son JDK en 10 étapes (José Paumard)
4. Observabilité, Mythes, réalité et Chaos (Benjamin Gakic)
5. Cycle de vie des applications dans Kubernetes (Charles Sabourdin et Jean-Christophe Sirot)
6. Micronaut, le framework JVM ultra-light du futur (Olivier Revial)
7. La gestion de l’authentification et de l’autorisation dans une architecture microservices ? Pas de soucis ! (Vivien Maleze et Florian Garcia)
8. Du monolithe aux microservices chez leboncoin (Eric Lefevre-Ardant)
9. Un turbo dans ton workflow GitHub (Alain Hélaïli)
10. Sonar Smash (Helen Wallace et James Mac Mahon)
11. De Java 8 à Java 11 sur un gros projet : les pièges à éviter (Alexis Dmytryk et Thomas Collignon)
12. Oubliez Java EE, voilà Jakarta EE ! (Jean-François James et Sébastien Blanc)
13. La JVM et Docker, vers une symbiose parfaite (Guillaume Scheibel)
14. Migrer ses APIs vers GraphQL : pourquoi ? comment ! (Guillaume Scheibel)
15. Au secours, mon projet BigData est en production! (Vincent Devillers)
16. SpringBoot avec Kotlin, Kofu et les Coroutines (Sébastien Deleuze)
17. 50 points de contrôle d’une API REST (François-Guillaume Ribreau)
18. Dev environments: use the nix, Luke! (Clément Delafargue et Hussein Ait-Lahcen)

Si vous souhaitez rapidement vous faire un avis sur leur contenu avant de les visionner ou si vous souhaitez garder une trace écrite de ce que vous y avez appris, je mets librement à disposition mes notes prises au cours de ces 3 jours.

Les sujets sont variés : le langage Java bien évidemment, des frameworks comme Spring et RxJS, de l’outillage pour vos test tests et vos builds, de l’infrastructure avec Docker et Kubernetes, de l’architecture avec DDD et OpenAPI, sans oublier des sujets plus connexes tels la place du développeur en entreprise ou bien l’apprentissage du code aux enfants.

1. Développeur, reprends le digital en main (Alain Hélaïli)
2. Après Java 8, Java 9 et 10 (Jean-Michel Doudoux)
3. Les 12 factors Kubernetes (Etienne Coutaud)
4. Un Loof çà va, de Loof, bonjour les dégâts (Nicolas et Thomas De Loof)
5. Java dans Docker (Charles Sabourdin et Jean-Christophe Sirot)
6. Migrer à Spring Boot 2 lorsqu’on a une « vraie » application (Julien Dubois)
7. Spring Framework 5 : Feature Highlights & Hidden Gems (Juergen Hoeller)
8. DDD & Event Sourcing à la rescousse pour implémenter la GDPR (Jérôme Avoustin et Guillaume Lours)
9. En finir avec les problèmes de gestion de dépendance grâce à Gradle 5 (Cédric Champeau)
10. Architecture hexagonale pour les nuls (Youen Chéné)
11. Effective Java, Third Edition : Keepin’ it Effective (Joshua Bloch)
12. Les Cookies HTTP #RetourAuxSources (Hubert Sablonnière)
13. Nouvelle génération de tests pour projets Java (Vincent Massol)
14. RxJS : les clefs pour comprendre les observables (Thierry Chatel)
15. Swagger 2 est mort, vive OpenAPI 3 (Sébastien Lecacheur et Grégory Bloquel)

Faisant partie des algorithmes de la théorie des graphes, l’algorithme de Kruskal permet de rechercher un arbre recouvrant de poids minimum.

Une application pratique de l’algorithme de Kruskal consiste à relier tous les ordinateurs d’un même réseau local avec une longueur optimale de fibre optique.

Dans ce billet, vous trouverez une implémentation Java de cet algorithme. Il m’aura permis de résoudre le problème Fibre Optique donné en finale du concours du Meilleur Dev de France 2017.

import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;


public class KruskalAlgo {

    /**
     * Détermine l'arbre couvrant de poids minimum (ARPM) à partir d'un graphe connexe non-orienté et pondéré.
     * <p>
     * Utilise l'algorithme de Kruskal
     * @see https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal
     *
     * @param vertices graphe constitué d'un ensemble de points dans un plan à 2 dimensions.
     * @return arrêtes de l'arbre couvrant de poids minimum dans ce graphe.
     */
    static List<Edge> compute(List<Vertex> vertices) {

        // Calcule les arêtes et leur poids
        List<Edge> allEdges = new ArrayList<>();
        for (int i = 0; i < vertices.size(); i++) {
            for (int j = i + 1; j < vertices.size(); j++) {
                allEdges.add(new Edge(vertices.get(i), vertices.get(j)));
            }
        }

        // Tri par poids ascendant
        allEdges.sort(Comparator.comparingDouble(Edge::getWeight));

        // Applique l'algo de Kruskal
        List<Edge> graph = new ArrayList<>();
        int i = 0;
        while (graph.size() < vertices.size() - 1) {
            Edge edge = allEdges.get(i++);
            int id1 = edge.u.clusterId;
            int id2 = edge.v.clusterId;
            // L'arête est ajouté au compute si ses 2 sommets n'appartiennent pas au même réseau
            if (id1 != id2) {
                graph.add(edge);
                // Regroupe les sommets des 2 réseaux venant d'être reliés
                for (Vertex v : vertices)
                    if (v.clusterId == id2) {
                        v.clusterId = id1;
                    }
            }
        }

        return graph;
    }

    static class Vertex {

        static int NEX_ID = 0;

        private final int x;

        private final int y;

        private int clusterId = NEX_ID++;

        Vertex(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Edge {

        private final Vertex u;

        private final Vertex v;

        private final double weight;

        Edge(Vertex v1, Vertex v2) {
            this.u = v1;
            this.v = v2;
            this.weight = Math.hypot(Math.abs(v1.x - v2.x), Math.abs(v1.y - v2.y));
        }

        double getWeight() {
            return weight;
        }
    }


    public static void main(String args[]) throws FileNotFoundException {
        List<Vertex> vertices = new ArrayList<>();
        vertices.add(new Vertex(0, 2));
        vertices.add(new Vertex(0, 0));
        vertices.add(new Vertex(1, 1));
        vertices.add(new Vertex(2, 1));
        vertices.add(new Vertex(3, 2));
        vertices.add(new Vertex(4, 2));
        vertices.add(new Vertex(3, 0));

        List<Edge> graph = KruskalAlgo.compute(vertices);

        System.out.println(graph.stream().mapToDouble(Edge::getWeight).sum()); // 7.656854249492381
    }
}

Dans le cas d’un système monétaire non canonique, utiliser un algorithme glouton ne donnera pas nécessairement un résultat optimal. Il est nécessaire de passer par la méthode algorithmique dite de programmation dynamique.

Voici l’implémentation Java récursive par programmation dynamique de rendu de monnaie :

package com.javaetmoi.algo;

import java.util.HashMap;
import java.util.Map;

/**
 * Résolution par programmation dynamique et récursivité du calcul de rendu de monnaie.
 */
public class AlgoRenduMonnaie {

    /**
     * Système de monnaie (exemple de l'Euro : [1, 2, 5, 10, 20, 50, 100, 200, 500])
     */
    private long[] pieces;

    /**
     * Cache des résultats intermédiaires.
     * <p>
     * Format : Map<Montant, Map<IndexPiece, RenduMonnaie>>
     */
    private Map<Long, Map<Integer, RenduMonnaie>> resultatsIntermediaires = new HashMap<>();

    /**
     * Constructeur
     *
     * @param pieces système de monnaire utilisé par l'algorithme.
     */
    public AlgoRenduMonnaie(long[] pieces) {
        this.pieces = pieces;
    }

    /**
     * Méthode principale exécutant l'algorithme de rendu de monnaie.
     * <p>
     * Cette méthode peut-être appelée plusieurs fois.
     * Elle réutilisera les résultats des précédents appels.
     *
     * @param montant somme à rendre
     * @return résultat optimal ou <code>null</code> si rendu de monnaie impossible
     */
    public RenduMonnaie calculerRenduMonnaieOptimal(long montant) {
        initResultatsIntermediaires();
        return calculeMonnaie(montant);
    }

    /**
     * Structure de données renvoyée par l'algorithme et également utilisée pour les calculs intermédiaires.
     */
    public class RenduMonnaie {

        private final long montant;
        /**
         * Pour chaque piece du systeme monétaire, conserve le nombre minimal de pieces à rendre pour le montant donné.
         */
        private final int[] nbPiecesARendre;

        /**
         * Constructeur pour un montant à 0.
         */
        RenduMonnaie() {
            this.montant = 0;
            this.nbPiecesARendre = new int[pieces.length];
        }

        RenduMonnaie(long montant, RenduMonnaie precedent, int indexPiece) {
            this.montant = montant;
            int length = precedent.nbPiecesARendre.length;
            nbPiecesARendre = new int[length];
            System.arraycopy(precedent.nbPiecesARendre, 0, nbPiecesARendre, 0, length);
            nbPiecesARendre[indexPiece]++;
        }

        public int[] getNbPiecesARendre() {
            return nbPiecesARendre;
        }

        public long getMontant() {
            return montant;
        }

        public int nbPieces() {
            int nbPieces = 0;
            for (int i = 0; i < pieces.length; i++) {
                nbPieces += nbPiecesARendre[i];
            }
            return nbPieces;
        }

        public String toString() {
            StringBuilder str = new StringBuilder();
            for (int i = 0; i < nbPiecesARendre.length; i++) {
                if (nbPiecesARendre[i] != 0) {
                    str.append(nbPiecesARendre[i]).append("x").append(pieces[i]).append("€ ");
                }
            }
            return str.toString();
        }
    }

    /**
     * Renvoie l'index de la pièce la plus proche d'un montant.
     */
    private Integer getIndexPieceMax(long montant) {
        Integer pieceMax = null;
        for (int i = 0; i < pieces.length; i++) {
            if (pieces[i] <= montant) {
                pieceMax = i;
            }
        }
        return pieceMax;
    }

    /**
     * Initialise le cache avec le 1er résultat : rendre un montant de zéro consiste à ne rendre aucune pièce.
     */
    private void initResultatsIntermediaires() {
        RenduMonnaie renduZero = new RenduMonnaie();
        Map<Integer, RenduMonnaie> zeroMap = new HashMap<>();
        for (int i = 0; i < pieces.length; i++) {
            zeroMap.put(i, renduZero);
        }
        resultatsIntermediaires.put(0L, zeroMap);
    }

    /**
     * Méthode appelée récursivement.
     *
     * @param montant somme à rendre
     * @return résultat optimal ou <code>null</code> si rendu de monnaie impossible
     */
    private RenduMonnaie calculeMonnaie(long montant) {
        Integer indexPieceMax = getIndexPieceMax(montant);
        if (indexPieceMax == null) {
            return null;
        }
        resultatsIntermediaires.putIfAbsent(montant, new HashMap<>());
        RenduMonnaie meilleurRendu = null;
        int meilleurePiece = -1;
        for (int indexPiece = indexPieceMax; indexPiece >= 0; indexPiece--) {
            long nouveauMontant = montant - pieces[indexPiece];
            resultatsIntermediaires.putIfAbsent(nouveauMontant, new HashMap<>());
            RenduMonnaie renduOptimal = resultatsIntermediaires.get(nouveauMontant).get(indexPiece);
            if (renduOptimal == null) {
                renduOptimal = calculeMonnaie(nouveauMontant);
            }
            if (renduOptimal != null) {
                if ((meilleurRendu == null) || (meilleurRendu.nbPieces() > renduOptimal.nbPieces())) {
                    meilleurRendu = renduOptimal;
                    meilleurePiece = indexPiece;
                }
            }
        }
        if (meilleurRendu != null) {
            meilleurRendu = new RenduMonnaie(montant, meilleurRendu, meilleurePiece);
            resultatsIntermediaires.get(montant).put(meilleurePiece, meilleurRendu);
        }
        return meilleurRendu;
    }
}

Le test unitaire JUnit associé valide différents cas de tests et documente son utilisation :

package com.javaetmoi.algo;

import org.junit.Ignore;
import org.junit.Test;

import static org.junit.Assert.*;


public class MonnaieTest {

    @Test
    public void monnaie_2_5_10_montant_1() {
        calculerMonnaie(new long[]{2, 5, 10}, 1L, null);
    }

    @Test
    public void monnaie_2_5_10_montant_5() {
        calculerMonnaie(new long[]{2, 5, 10}, 5L, 1);
    }

    @Test
    public void monnaie_2_5_10_montant_6() {
        calculerMonnaie(new long[]{2, 5, 10}, 6L, 3);
    }

    @Test
    public void monnaie_2_5_10_montant_10() {
        calculerMonnaie(new long[]{2, 5, 10}, 10L, 1);
    }

    @Test
    public void monnaie_2_5_10_montant_37() {
        calculerMonnaie(new long[]{2, 5, 10}, 37L, 5);
    }

    @Test
    public void monnaie_1_3_4_montant_6() {
        calculerMonnaie(new long[]{1, 3, 4}, 6L, 2);
    }

    @Test
    @Ignore
    public void monnaie_1_2_5_10_20_50_100_200_500_montant_1989() {
        calculerMonnaie(new long[]{1, 2, 5, 10, 20, 50, 100, 200, 500}, 1989L, 11);
    }

    private void calculerMonnaie(long[] pieces, long montant, Integer nbPiecesAttendues) {
        AlgoRenduMonnaie algo = new AlgoRenduMonnaie(pieces);
        AlgoRenduMonnaie.RenduMonnaie rendu = algo.calculerRenduMonnaieOptimal(montant);

        if (nbPiecesAttendues == null) {
            assertNull(rendu);
            return;
        }
        assertNotNull(rendu);
        for (int i = 0; i < pieces.length; i++) {
            if (rendu.getNbPiecesARendre()[i] != 0) {
                System.out.println("Nombre de pièces de " + pieces[i] + " € : " + rendu.getNbPiecesARendre()[i]);
            }
        }

        assertEquals(montant, rendu.getMontant());
        assertEquals(nbPiecesAttendues.intValue(), rendu.nbPieces());
    }

}

Plus le système monétaire est dense et plus le montant à rendre est élevé, plus il y’a de chance que la récursivité provoque des débordements de pile d’appel (je vous invite à tester le test annoté avec @Ignore). Passer par une impléemntation itérative permettrait de résoudre ce problème.

Pour complexifier le problème, on pourrait tenir compte du nombre de pièces disponibles dans la caisse et adapter le rendu de monnaie en conséquences. La mise en cache des résultats intermédiaires ne serait alors plus possible.

Références :

• Problème de rendu de monnaie, Wikipedia
• Rendu de monnaie, bases de programmation dynamique, Jill-Jênn Vie & Clémence
• Corrigé du contrôle des connaissances Algorithmique & Programmation (INF431)

1. Préparez-vous à la modularité selon Java 9
2. Java 9 modulo les modules
3. Spring Framework 5.0
4. Spring Reactive
5. Kit d’orchestration avec Docker Swarm mode
6. Docker sous Windows
7. Cloudifie ton monolithe
8. Event-Sourcing et CQRS par la pratique
9. Problèmes rencontrés avec les microservices
10. 10 méthodes pour rendre heureux un développeur en entreprise
11. Tech Lead dans pizza team XXL
12. Log me tender
13. Java 10 et le Pattern-Matching
14. Ingest node Elasticsearch