Discussion :

[PolkovnikMedved]

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 !");
    }
}

[pseudocode]

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);
}

[tbc92]

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

[pseudocode]

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]

[PolkovnikMedved]

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