1. #1
    Nouveau membre du Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    octobre 2016
    Messages
    32
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 25
    Localisation : Belgique

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : octobre 2016
    Messages : 32
    Points : 25
    Points
    25

    Par défaut Diviser pour mieux régner

    Bonjour,

    J'ai un petit problème : je dois exécuter une requête SQL et je voudrais diviser les resultats obtenus sans perte de données. En gros, la requête doit faire un "BETWEEN a AND b". J'ai donc deux entiers A et B ainsi qu'un nombre de parties désiré C (approximatif, le plus important c'est d'avoir toutes les données sans doublons).

    Par exemple, j'ai réussi à avoir un algo qui me donne si A = 0, B = 10 et C = 5 (même chose si C = 4...) les valeurs suivantes [0,2], [3,5], [6,8], [9,10].

    Comme ça après au lieu de faire ma requête SQL "BETWEEN 0 AND 10" je peux faire 4 requêtes "BETWEEN 0 AND 2", "BETWEEN 3 AND 5" etc.

    L'algorithme fonctionne bien (en tout cas pour les valeurs testées...) mais il est assez expérimental et je me demandais si y a pas quelque chose de plus correct.

    Voici l'algo (en Java)

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
     
    import java.util.Scanner;
     
    public class Main {
     
        public static void main(String[] args) {
            int aMin;
            int aMax;
            int nbParts;
     
            Scanner sc = new Scanner(System.in);
            System.out.print("Min = ");
            aMin = sc.nextInt();
            System.out.print("Max = ");
            aMax = sc.nextInt();
            System.out.print("NbParts = ");
            nbParts = sc.nextInt();
     
            int onePart = ((aMax - aMin) / nbParts);
     
            System.out.println(onePart);
     
            if(aMin == aMax)
            {
                // 1 process
                System.out.println("Only one process with nb = " + ((aMin + aMax)/2));
            }
            else if(aMin < aMax)
            {
                // If nbParts > (aMax-Min) => onePart = 0
                if(onePart == 0)
                {
                    System.out.println("Infinite loop.");
                    System.exit(-1);
                }
     
                System.out.println("Several processes begin.");
     
                for(int i = aMin; i < aMax; i += (onePart + 1))
                {
                    int from = i;
                    int until = (i + onePart);
     
                    if(i > (aMax - onePart)) {
                        System.out.println("------------- LAST -------------");
                        System.out.println("FROM = " + from);
                        System.out.println("UNTIL = " + aMax);
                        break;
                    }
     
                    System.out.println("----------- ONE PROCESS -----------");
                    System.out.println("FROM = " + from);
                    System.out.println("UNTIL = " + until);
                }
            }
            else
                System.out.println("ERROR !");
        }
    }

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 033
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 033
    Points : 15 596
    Points
    15 596

    Par défaut

    Je ne suis pas bien sur d'avoir compris... c'est ca que tu veux ?

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // inputs: int aMin, aMax and nbParts
    int range = 1+aMax-aMin;
    int buckets = Math.min(range,Math.max(1,nbParts));
     
    for(int i=0; i<buckets; i++) {
        int from = aMin + i*(range)/buckets;
        int next = aMin + (i+1)*(range)/buckets - 1;
        System.out.printf("FROM=%d UNTIL=%d\n",from,next);
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 455
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 455
    Points : 3 039
    Points
    3 039

    Par défaut

    La difficulté, c'est avec une configuration comme A = 1, B=20 et C= 13 : on a 20 valeurs, et on veut 13 buckets.

    20 divisé par 13, ça fait 1.52 environ.
    Soit on arrondit à 1, et il va falloir 20 buckets, soit on arrondit à 2, et on va faire 10 buckets, soit on est rusé, et on se débrouille pour alterner : 20 = 1+2+1+2+1+2+1+2+2+1+2+1+2 : on a bien 13 buckets.

    Si on est tolérant sur le nombre de buckets, si on accepte d'avoir soit 10, soit 20 buckets alors qu'initialement on en avait demandé 13, alors la solution de pseudo-code semble bonne. Sinon, faut ruser.

    Je n'ai pas testé, mais j'essaierais ceci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    procedure decoupe ( a,b,c)
    nbuckets restants est un entier
    n_a_b restants est un entier 
    lg est un entier
    n_a_b restants = b-a +1
    nbuckets_restants = c
    
    x,y est un entier 
    tantque a < b
      lg = arrondi ( (b-a) / nbuckets_restants ,0) 
      print ( "BETWEEN" +  a + " AND " + (a + lg-1 )  )
      nbuckets_restants --
      a = a+lg 
      n_a_b restants =  b-a+1
    fin
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 033
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 033
    Points : 15 596
    Points
    15 596

    Par défaut

    Citation Envoyé par tbc92 Voir le message
    Si on est tolérant sur le nombre de buckets, si on accepte d'avoir soit 10, soit 20 buckets alors qu'initialement on en avait demandé 13, alors la solution de pseudo-code semble bonne. Sinon, faut ruser.
    Le nombre de bucket est celui demandé, sauf si C<1 (forcé à 1) ou C>nombre max d'élément (forcé au nombre max d'élément).

    A = 1, B=20 et C= 13 ---> 13 buckets: [1,1] [2,3] [4,4] [5,6] [7,7] [8,9] [10,10] [11,12] [13,13] [14,15] [16,16] [17,18] [19,20]

    A = 1, B=20 et C=0 ---> 1 buckets: [1,20]

    A = 1, B=20 et C=99 ---> 20 buckets: [1,1] [2,2] [3,3] [4,4] [5,5] [6,6] [7,7] [8,8] [9,9] [10,10] [11,11] [12,12] [13,13] [14,14] [15,15] [16,16] [17,17] [18,18] [19,19] [20,20]
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Nouveau membre du Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    octobre 2016
    Messages
    32
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 25
    Localisation : Belgique

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : octobre 2016
    Messages : 32
    Points : 25
    Points
    25

    Par défaut

    Citation Envoyé par pseudocode Voir le message
    Je ne suis pas bien sur d'avoir compris... c'est ca que tu veux ?

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // inputs: int aMin, aMax and nbParts
    int range = 1+aMax-aMin;
    int buckets = Math.min(range,Math.max(1,nbParts));
     
    for(int i=0; i<buckets; i++) {
        int from = aMin + i*(range)/buckets;
        int next = aMin + (i+1)*(range)/buckets - 1;
        System.out.printf("FROM=%d UNTIL=%d\n",from,next);
    }
    Désolé pour la réponse tardive mais :

    Un grand Merci ! Ton algo fonctionne avec les valeurs que j'ai testé et il est bien plus concis que celui que j'ai obtenu expérimentalement

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Explication de la résolution de récurrence diviser pour régner
    Par mamioop dans le forum Général Algorithmique
    Réponses: 3
    Dernier message: 26/12/2011, 20h25
  2. Diviser Pour Régner
    Par touftouf57 dans le forum Général Algorithmique
    Réponses: 13
    Dernier message: 01/11/2011, 18h48
  3. stratégie "Diviser pour régner"
    Par z_meryem dans le forum C
    Réponses: 7
    Dernier message: 31/03/2008, 03h03
  4. [complexité] Diviser pour règner, resolution recurrence
    Par rvfranck dans le forum Général Algorithmique
    Réponses: 4
    Dernier message: 22/10/2007, 10h59
  5. "diviser pour régner" itération - puissance n
    Par Sokoudan dans le forum Caml
    Réponses: 23
    Dernier message: 30/04/2007, 16h41

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo