Algorithme pour obtenir le plus proche multiple en Java

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.

6 réflexions sur « Algorithme pour obtenir le plus proche multiple en Java »

  1. @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
  2. 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

Laisser un commentaire

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

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.