Diviser pour mieux régner

Version imprimable

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:

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

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

Code:

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

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:

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

27/07/2017, 17h32
pseudocode

Citation:

Envoyé par tbc92

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]

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

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 :)