Code Story en java : Jajascript et les performances

Cet article est le dernier d'une série de trois articles sur ma participation à Code Story en Java. Les articles précédents sont :

• Ma participation à CodeStory en java : Intro
• CodeStory en java : Scalaskel et la calculette

Je vais essayer de vous faire un retour sur l'étape qui a donné le plus de difficultés à tous les participants : Jajascript.

L'énoncé

Voici l'énoncé tel que nous l'avons reçu :

Location d’astronef sur Jajascript

Votre cousin par alliance, Martin O. sur la planète Jajascript vient de monter sa petite entreprise de vol spatial privé: Jajascript Flight Rental. Il loue aux grosses corporations son astronef lorsqu’elles ont de fortes charges ou un pépin avec leurs propres appareils. Il s’occupe de la maintenance et de l’entretien de son petit astronef. Il ne pouvait s’en payer qu’un pour démarrer.

Ces grosses corporations envoient des commandes de location qui consistent en un intervalle de temps, et le prix qu’ils sont prêts à payer pour louer l’astronef durant cet intervalle.

Les commandes de tous les clients sont connues plusieurs jours à l’avance. Ce qui permet de faire un planning pour une journée. Les commandes viennent de plusieurs sociétés différentes et parfois elles se chevauchent. On ne peut donc pas toutes les honorer.

Idéalement, il faut donc être capable de prendre les plus rentables, histoire de maximiser les gains de sa petite entreprise, et de s’acheter d’autres astronefs. Votre cousin passe des heures à trouver le planning idéal et vous demande pour un planning donné de calculer une solution qui maximise son gain.

Exemple

Considérez par exemple le cas où la JajaScript Flight Rental à 4 commandes :

MONAD42 : heure de départ 0, durée 5, prix 10
META18 : heure de départ 3, durée 7, prix 14
LEGACY01 : heure de départ 5, durée 9, prix 8
YAGNI17 : heure de départ 5, durée 9, prix 7

La solution optimale consiste à accepter MONAD42 et LEGACY01, et le revenu est de 10 + 8 = 18. Remarquez qu’une solution à partir de MONAD42 et YAGNI17 est faisable (l’avion serait loué sans interruption de 0 à 14) mais non optimale car le bénéfice ne serait que de 17.

Précisions

L’identifiant d’un vol ne dépasse jamais 50 caractères, les heures de départs, durée et prix sont des entiers positifs raisonnablement grands.

Serveur

Votre serveur doit répondre aux requêtes http POST de la forme http://serveur/jajascript/optimize avec un payload de la forme :

[
    { "VOL": "NOM_VOL", "DEPART": HEURE, "DUREE": DUREE, "PRIX": PRIX }, ...
]

En reprenant l’exemple ci dessus :

[
    { "VOL": "MONAD42", "DEPART": 0, "DUREE": 5, "PRIX": 10 },
    { "VOL": "META18", "DEPART": 3, "DUREE": 7, "PRIX": 14 },
    { "VOL": "LEGACY01", "DEPART": 5, "DUREE": 9, "PRIX": 8 },
    { "VOL": "YAGNI17", "DEPART": 5, "DUREE": 9, "PRIX": 7 }
]

Vous devrez répondre le résultat suivant :

{
      "gain" : 18,
      "path" : ["MONAD42","LEGACY01"]
}

Le gain représentant la somme optimale, path représentant l’ordre des vols.

Bons calculs !

Premier algo très naïf

Le premier algo que j'ai pondu était très naïf, je calculais absolument toutes les solutions possibles (voir plusieurs fois chaque solution). Voici la méthode principale de l'époque :

private void calculate(Planning actualPlanning, Collection commandesToAdd) {
    if (actualPlanning != null) {
        addToPlanningsIfBetter(actualPlanning);
    }
    for (Commande commandeToAdd : commandesToAdd) {
        if (actualPlanning == null || actualPlanning.canAddCommande(commandeToAdd)) {
            Planning newPlanning = new Planning(actualPlanning);
            newPlanning.addCommande(commandeToAdd);
            Collection newCommandesToAdd =
                Collections2.filter(commandesToAdd, new FilterCommande(commandeToAdd));
            calculate(newPlanning, newCommandesToAdd);
        }
    }
}

Dans cet algo récursif, je parcours toutes les commandes, et pour chaque commande, je regarde si elle est compatible à mon planning actuel, si elle l'est je l'ajoute au planning et je fais l'appel récursif. Cet algo est donc ni élégant ni performant, mais a le mérite de marcher. Pour les étapes précédentes cela suffisait, je me suis donc arrêté là, enfin jusqu'à la surprise.

La surprise

Pour Jajascript, ils nous ont fait une petite surprise, ils se sont mis à tester les performances... La méthode pour tester les performances était la suivante : le robot envoie une requête avec un certain nombre de commandes, si je réponds en moins de 30 secondes, il en envoie plus, et ce jusqu'à ce que je réponde en plus de 30 secondes. Voici la liste complète des marches utilisées par le robot :

• 5 commandes
• 10 commandes
• 15 commandes
• 20 commandes
• 25 commandes
• 30 commandes
• 35 commandes
• 40 commandes
• 45 commandes
• 50 commandes
• 55 commandes
• 60 commandes
• 65 commandes
• 70 commandes
• 75 commandes
• 80 commandes
• 85 commandes
• 90 commandes
• 95 commandes
• 100 commandes
• 150 commandes
• 250 commandes
• 500 commandes
• 1000 commandes
• 1500 commandes
• 2000 commandes
• 2500 commandes
• 3000 commandes
• 3500 commandes
• 4000 commandes
• 5000 commandes
• 10000 commandes
• 50000 commandes

Du coup mon premier algo naïf répondait en plus de 30 secondes à partir de 30 commandes (nous ne connaissions pas le max à l'époque qui semblait être aux alentours de 100 commandes). Il a donc fallu optimiser tout ça. Je ne vais pas vous présenter tous les commits d'optimisation par lesquels je suis passés (ça représente près de 50 commits...). Je vais plutôt tenter de vous montrer les grandes étapes ainsi que les performances associées. Pour les performances, je n'ai inclus que le calcul brut (sans la couche HTTP ou Json).

Algo récursif optimisé

Après quelques commits, je suis arrivé à un algo récursif un peu plus optimisé :

private void calculate(Planning actualPlanning, Collection commandesToAdd) {
    if (actualPlanning != null) {
        addToPlanningsIfBetter(actualPlanning);
    }
    Iterator itCommande = commandesToAdd.iterator();

    while (itCommande.hasNext()) {
        Commande commandeToAdd = itCommande.next();
        itCommande.remove();
        if (actualPlanning == null || actualPlanning.canAddCommande(commandeToAdd)) {
            calculate(new Planning(actualPlanning).addCommande(commandeToAdd), newArrayList(commandesToAdd));
        }
    }
}

Les grosses différences pour en arriver là sont (pas toutes visibles dans le code ci-dessus) :

• Tri des commandes par heure de départ croissante
• On ne stocke que le meilleur planning
• On enlève la commande courante avant de continuer dans la récursivité
• On stocke l'heure de fin d'un planning afin de savoir rapidement si une commande est compatible avec

Pour les plus curieux, le diff complet est dispo sur github. Cet algo tiens jusqu'à 70 commandes à peu près (c'est déjà beaucoup mieux, mais on est loin des 50000 commandes...).

Algo récursif très optimisé

Afin d'aller au bout des optimisations de l'algo récursif, j'ai modifié/enlevé tout ce qui prenait du temps sans changer l'algo. L'optimisation principale dans cette étape a été le passage en types primitifs avec utilisation de tableau d'entier. Quand on regarde le code obtenu, on a un peu l'impression de revoir du C... Toutes ces optimisations permettent tout de même d'atteindre les 5000 commandes environs. Pour les plus curieux, le diff complet est disponible sur github.

Algo itératif

Atteignant les limites du récursif, il a fallu passer à un algo itératif. Cet algo repose sur une pile des dernières solutions trouvées, afin de regarder dans ces solutions laquelle est la meilleure pour une commande donnée. Voici la méthode principale :

private void calculateIteratif() {
    // Parcours de toutes les commandes
    for (int i=0; i= solution.heureFin
                    && solution.prix > bestPrice ) {
                bestSolutionToAdd = solution;
                bestPrice = solution.prix;
            }
        }

        lastSolutions.removeFirst();

        boolean[] newAceptedCommands = Arrays.copyOf(bestSolutionToAdd.acceptedCommands, bestSolutionToAdd.acceptedCommands.length);
        newAceptedCommands[i] = true;
        Solution newSolution = new Solution(ends[i], bestSolutionToAdd.prix + prices[i], newAceptedCommands);
        lastSolutions.addLast(newSolution);
    }

    for (Solution solution : lastSolutions) {
        addToPlanningsIfBetter(solution.acceptedCommands, solution.prix);

    }
}

Ce passage en itératif permet d'atteindre 200000 commandes environ (ce qui était suffisant pour le concours). Pour les plus curieux, le diff complet est disponible sur github

Algo itératif optimisé

Je vais maintenant vous présenter le code final obtenu après encore quelques optimisations, et finalement un retour à de l'objet pur (ce qui me fait perdre un peu en performance, mais rend le code tellement plus lisible). Avant d'arriver à ce résultat, je suis passé par un BitSet plutôt qu'un tableau de booléens, ce qui m'avait fait gagner pas mal (classe à connaître donc). Si vous voulez voir tout les commits intermédiaires, ça se passe sur github.

Voici tout d'abord la classe Solution permettant de stocker une solution trouvée :

import com.google.common.base.Optional;
import com.google.common.primitives.Ints;

import java.util.LinkedList;
import java.util.List;

public class Solution implements Comparable {
    public final int price;
    public final int endTime;
    public final Optional oldSolution;
    public final Flight newFlight;

    Solution(int price, Optional oldSolution, Flight newFlight) {
        this.price = price;
        this.oldSolution = oldSolution;
        this.newFlight = newFlight;
        this.endTime = newFlight.endTime;
    }

    public List getFlights() {

        LinkedList flights = new LinkedList();
        flights.add(newFlight);

        Optional currentSolution = oldSolution;
        while (currentSolution.isPresent()) {
            flights.addFirst(currentSolution.get().newFlight);
            currentSolution = currentSolution.get().oldSolution;
        }

        return flights;
    }

    public boolean isBetterThan(Optional bestSolutionToAdd) {
        return !bestSolutionToAdd.isPresent() || price > bestSolutionToAdd.get().price;
    }

    @Override
    public int compareTo(Solution o) {
        return Ints.compare(price, o.price);
    }
}

Le point principal à noter dans cette classe, est la façon de stocker une solution. Plutôt que de stocker une image complète d'une solution, on stocke la solution précédente plus la commande qu'on lui a ajoutée. Cette technique permet d'économiser énormément de mémoire, mais permet également de diminuer énormément le coup de la création d'une solution (appel au constructeur).

Voici maintenant la classe JajascriptService contenant tout l'algo :

import com.google.common.base.Function;
import com.google.common.base.Optional;
import com.google.common.collect.Lists;

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class JajascriptService {

    /**
     * Flights to optimize.
     */
    private List flights;
    /**
     * Last solutions found.
     */
    private LinkedList lastSolutions = new LinkedList();


    public JajascriptService(List flights) {
        this.flights = flights;
        Collections.sort(this.flights);
    }

    public JajaScriptResponse calculate() {

        Solution solution = calculateSolution();

        // Construct the path with the array of accepted flights.
        List path = Lists.transform(solution.getFlights(), new Function() {
            @Override
            public String apply(Flight input) {
                return input.getName();
            }
        });

        return new JajaScriptResponse(solution.price, path);
    }

    private static class BestSolutions {
        Optional bestCompatibleSolution = Optional.absent();
        Optional bestSolutionWithEquivalentEndTime = Optional.absent();

        int getPriceOfCompatibleSolution() {
            return getPriceOfAnOptionalSolution(bestCompatibleSolution);
        }

        int getPriceOfEquivalentEndTimeSolution() {
            return getPriceOfAnOptionalSolution(bestSolutionWithEquivalentEndTime);
        }

        private static int getPriceOfAnOptionalSolution(Optional optionalSolution) {
            return optionalSolution.isPresent() ? optionalSolution.get().price : 0;
        }
    }

    /**
     * @return an optimal solution.
     */
    private Solution calculateSolution() {
        // Iterate on all flights.
        for (Flight flight : flights) {
            // Pre-calculate endTime for future needs.
            flight.calculateEndTime();

            BestSolutions bestSolutions = getBestSolutionsForAFlight(flight);

            int newPrice = flight.price + bestSolutions.getPriceOfCompatibleSolution();

            if (newPrice > bestSolutions.getPriceOfEquivalentEndTimeSolution()) {
                // Add the new solution to FIFO only if it's better than other solution with lower or equal endTime.
                lastSolutions.addLast(new Solution(newPrice, bestSolutions.bestCompatibleSolution, flight));
            }

            if (bestSolutions.bestCompatibleSolution.isPresent()) {
                // If we found a compatible solution, we remove all solution with endTime lower than last flight startTime and lower price.
                removeOldSolutions(flight.startTime, bestSolutions.bestCompatibleSolution.get().price);
            }
        }

        // Search the best solution in FIFO.
        Collections.sort(lastSolutions);
        return lastSolutions.getLast();
    }

    /**
     * Remove all solution with lower or equal endTime than lastStartTime and lower price than priceOfCompatibleSolution.
     */
    private void removeOldSolutions(int lastStartTime, int priceOfCompatibleSolution) {
        Iterator lastSolutionIterator= lastSolutions.iterator();

        while (lastSolutionIterator.hasNext()) {
            Solution oldSolution = lastSolutionIterator.next();
            if (oldSolution.endTime <= lastStartTime
                    && oldSolution.price < priceOfCompatibleSolution) {
                lastSolutionIterator.remove();
            }
        }
    }

    /**
     * Get the best solution in {@link JajascriptService#lastSolutions} for a flight.
     */
    private BestSolutions getBestSolutionsForAFlight(Flight flight) {
        BestSolutions bestSolutions = new BestSolutions();
        // Search the best solution in FIFO we can take for this flight.
        for (Solution solution : lastSolutions) {
            if (flight.startTime >= solution.endTime && solution.isBetterThan(bestSolutions.bestCompatibleSolution)) {
                bestSolutions.bestCompatibleSolution = Optional.of(solution);
            }
            if (flight.endTime >= solution.endTime && solution.isBetterThan(bestSolutions.bestSolutionWithEquivalentEndTime)) {
                bestSolutions.bestSolutionWithEquivalentEndTime = Optional.of(solution);
            }
        }
        return bestSolutions;
    }
}

Cette version étant plutôt bien commentée, je vous laisse lire les commentaires...

Au final, cette version permet de traiter 1 000 000 de commandes en 200 millisecondes.

Différences entre les algos

En guise de récapitulatif, voici un petit graphique avec les performances de tous les algos

J'espère que ce retour sur ma participation à ce concours passionnant vous a plu. J'espère avoir le temps de vous faire un petit retour sur ma participation en Ceylon et en Scala, mais je ne vous garantis rien...