Algorithme pour obtenir le plus proche multiple en Java

[ 6 ] Commentaires
Share

Pour mon boulot, j’ai eu à écrire un algorithme sortant le multiple d’un nombre le plus proche (supérieur) d’un autre nombre donné en entré. Dans les faits, on cherchait le multiple de 50 le plus proche, tout en restant supérieur, de la longueur d’une liste passée en entrée. L’objectif de tout ça était d’envoyer à Oracle une requête présentant toujours le même nombre de paramètres, ce afin qu’Oracle puisse sauvegarder (mettre en cache, etc) cette requête (si j’ai bien compris, Oracle mets certaines requêtes en cache, si tant est qu’elles sont toujours sur le même pattern).

A l’origine, quelque soit la longueur de la liste au départ (et même si elle est vide), on faisait dans Oracle une requête finissant par un AND mon_id NOT IN (ma_liste_generee). La liste générée étant constituée des ID à exclure et complétée par les valeurs « -1 » jusqu’à ce que sa longueur fasse 1000.

Sauf que dans certains cas, notre version d’Oracle ne gérait pas bien ces 1000 paramètres, et du coup cette requête prenait quelque chose comme 150 secondes à s’exécuter. Problème, dans la quasi-totalité des cas, la liste à exclure était vide ! Et quand on enlevait cette partie de la requête, on se rendait compte que l’exécution de la requête ne prenait plus que… 0.03 seconde.

Donc ce qui m’a été demandé de faire : trouver un moyen de ne compléter cette requête que quand la liste est non vide (ça c’est simple), et si elle n’est pas vide, ne pas compléter jusqu’à 1000, mais compléter que jusqu’au multiple de 50 supérieur à la longueur de la liste passée en paramètre.

Et là, c’est le drame : il a fallu que j’aille chercher dans ma mémoire si j’avais pas fait dans mes études un truc intelligent pour faire ça…

Ce qui m’a d’ailleurs permis d’invalider ce graphique :

J’ai donc écris un premier algorithme, qui n’est pas beau à voir :

    private static final int MAX_ORACLE_IN = 1000;
    private static final int THRESHOLD = 50;
    private int getClosestUpperMultiple(int fitListSize){
    	int closestMultiple = fitListSize;
    	if(closestMultiple == 0 || closestMultiple == MAX_ORACLE_IN)
    		return closestMultiple;
    	
    	// On retourne le premier chiffre au dessus de fitListSize
    	// qui sera un multiple de THRESHOLD 
    	int i = fitListSize;
    	while(i < MAX_ORACLE_IN && closestMultiple == fitListSize){
    		if(i % THRESHOLD == 0){ // Au premier multiple de THRESHOLD, on assigne closestMultiple et on sort de la boucle
    			closestMultiple = i;
    		}
    		i++;
    	}
		return closestMultiple;
    }

Donc comme vous pouvez le voir, cet algo utilise un modulo pour savoir à quel moment arrêter. Mais bon, cet algorithme sous-entend une boucle : c’est moche. J’en ai fait par la suite un deuxième, un peu plus intelligent (à mes yeux), utilisant une division en bigInt :


    private static final int MAX_ORACLE_IN = 1000;
    private static final int THRESHOLD = 50;

private int getClosestUpperMultiple(int fitListSize){
   if(fitListSize == 0 || fitListSize == MAX_ORACLE_IN)
           return fitListSize;
   // On retourne le premier int au dessus de fitListSize qui sera un multiple de THRESHOLD
   return (int) (THRESHOLD * Math.ceil(divide(Double.valueOf(fitStopListSize), Double.valueOf(THRESHOLD), 2)));
}

public static Double divide(Double d1, Double d2, int scale) {
    if (d1 == null || d2 == null || d2.doubleValue() == 0)
        return null;
    BigDecimal p1 = BigDecimal.valueOf(d1);
    BigDecimal p2 = BigDecimal.valueOf(d2);
    p1 = p1.divide(p2, scale, RoundingMode.HALF_UP);
    return Double.valueOf(p1.doubleValue());
}

Pour la petite histoire, on a donc amélioré grandement les performances de ces requêtes.

Vous serez peut-être intéressé :

  • Bouts de codes Java qui reviennent assez souvent
    Je mets ici quelques conversions de types et quelques bouts de codes utilisés très fréquemment, et que je suis à chaque fois obligé d'aller chercher sur StackOverflow. Donc autant les rassembler ici. ...
  • Parsing de XML en Java : les élements DOM et la génération en String
    J'ai eu à faire un parsing de XML en Java, avec sortie en objet PoJo (un objet Java contenant juste les champs, setters et getters). Puis j'ai eu à faire l'inverse. Parce que la recherche de classes p...
  • Faire des Threads en Java-JEE
    L'idée de faire des threads sur une application web vient du fait que les processeurs des serveurs sous souvent sous-utilisés (je dirais en moyenne 20%), et donc on pourrait gagner en rapidité des app...
  • Installer et utiliser Phantom JS sur windows pour récupérer des pages web
    Pour mon boulot, j'ai eu besoin d'utiliser PhantomJS afin de récupérer une page web. L'idée était de générer une page web dont une grande partie est récupérée au load de la page en javascript, et d'en...
  • Nginx + PHP-FPM et WP-Super-Cache ?
    Bastien l'a évoqué dans les commentaires d'un précédent billet sur Nginx : plutôt que de mettre Nginx en reverse proxy avec Apache derrière, pourquoi ne pas faire gérer les requètes PHP directement pa...

6 commentaires sur ce billet

  1. syndrael dit :

    C’est le principe des requêtes préparées non ?

    RépondreRépondre
  2. Louis dit :

    @syndrael: heu, très bonne question, à vrai dire je n’en sais rien. Qu’entends tu par requêtes préparées ?

    RépondreRépondre
  3. syndrael dit :

    http://docs.oracle.com/javase/tutorial/jdbc/basics/prepared.html
    si ça peut t’aider.
    De façon capilotracté, c’est une pseudo pré-compilation des requetes qui cast par avance les paramètres et qui optimise l’exécution.
    J’espère avoir été assez clair. En tout cas testé et approuvé sur MySQL. Jamais sur Oracle.
    Bonnes fêtes au fait.
    S.

    RépondreRépondre
  4. Louis dit :

    @syndrael: Alors je crois que toutes nos requètes sont des preparedStatement. Par contre, je crois que nos DBA essaient de faire un truc en plus en fournissant un nombre toujours égal de paramètres.

    Mais très honnêtement, je ne saurais pas t’en dire davantage, je ne suis pas fan de ce qui tourne autour de la BDD…

    RépondreRépondre
  5. Fredo dit :

    Bonjour,
    Problématique intéressante, voici ce que j’aurais fait (en Php), j’omet volontairement le test préalable :

    $nDiv = 50; // Diviseur
    $nNbr = 367; // Nombre d'éléments trouvés dans la liste
    // On ajoute le diviseur (moins 1) au nombre d'éléments trouvés,
    // on divise cetta addition par le diviseur puis on l'arrondi,
    // enfin, on multiplie le résultat par le diviseur.
    return ceil(($nNbr + ($nDiv - 1)) / $nDiv) * $nDiv;
    // 367 = 400
    // 250 = 300

    🙂

    RépondreRépondre
  6. Louis dit :

    @Fredo: Merci !

    RépondreRépondre

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *