Optimiser algorithme C++

Version imprimable

19/04/2014, 17h21
CliffeCSTL

Optimiser algorithme C++

Bonjour,

J'ai besoin d'un algorithme qui me génère 'n' nombres aléatoires compris entre 0 et 'N_MAX' et avec un minimum d'écart 'ep_min' entre 2 nombre (Le plus optimiser possible).
Je tiens à préciser que j'ai déjà un algo qui fonctionne et je souhaite l'améliorer
Merci.

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 #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> #define N_MAX 256 int main(void) { unsigned short ep_min = 8; unsigned short last_nb = 0, nb = 0, diff = 0, min = N_MAX, max = 0, min_diff = N_MAX, max_diff = 0, i = 0, count = 0, count_ite = 0; srand( time(NULL) ); last_nb = (1 + rand()% N_MAX); for(; i < 15000; i++) { do { count_ite++; nb = (1 + rand()% N_MAX); diff = ((nb > last_nb)? (nb - last_nb): (last_nb - nb)); } while(diff < ep_min); if (diff < ep_min) { count++; } if (nb > max) { max = nb; } if (nb < min) { min = nb; } if (diff > max_diff) { max_diff = diff; } if (diff < min_diff) { min_diff = diff; } printf("%d (%d)\n", nb, diff); last_nb = nb; } printf("Miss: %d - %d%% / %d - %d -> %d - %d, %d", count, ((count * 100) / 15000), count_ite, min, max, min_diff, max_diff); return 0; }
Édit: Avec une notion de pages (N_MAX / ep_min) c'est chaud, mais peut-être qu'un forumeur a un algo avec :mrgreen:
C'est chaud, parce qu'on connait la dernière page prise et il faut éviter de la reprendre pour le nouveau nombre :mrgreen:
Simple, mais:

Si le nombre de pages est petit cela complique
Il faut contrôler le modulo: % nombre de pages
Sans modulo, il faut gérer au moins 3 ou 4 cas: si on veut un nombre avant ou après, si c'est la première ou la dernière page, ...
Si la nouvelle page sélectionnée est juste à côté de l'ancienne (juste avant ou juste après), il faut gérer le déplacement de l'ancien nombre dans l'ancienne page (*)

L'algo naïf est très bien surtout si ep_min est petit :whistle:

* -> |<-Ok: X-><-Not Ok: Y->||<-X->Ancien Nombre<-Y->||<-Not Ok: X-><-Ok: Y->|, avec (X + Y + 1) = ep_min

Citation:

Envoyé par CliffeCSTL

Je tiens à préciser que j'ai déjà un algo qui fonctionne et je souhaite l'améliorer

Hello,

Montres ce que tu as, quelle est la complexité de ton algo ?

L'écart doit être entre 2 nombres consécutifs ? ou 2 nombres générés ?
(Je part du principe que c'est entre 2 nombres générés)

As-tu des contraintes sur n, N_MAX, ep_min ?
si N_MAX - (n*ep_min*2) est petit, il va falloir faire gaffe au choix des nombres aléatoires, un mauvais choix et il n'y à plus de solution possible.

Si tu as N_MAX / n grand et N_MAX / (n*ep_min*2) grand, alors un algo naïf marchera bien. Malgré le temps d'exec non borné tu seras quasiment en O(n).
Algo naïf : générer un nombre, s'il ne convient pas, on en génère un autre, niveau code, quelque chose du genre
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 struct hash { int ep_min2; bool operator()(int a) const { return std::hash(a - (a % ep_min2)); } }; struct comp { int ep_min; bool operator()(int a, int b) const { return std::abs(a-b) < ep_min; } }; std::unordered_set<int, hash{ep_min * 2}, comp{ep_min}> nbs(2*n); for(int i=0; i<n; ++i) { int nb; do { nb = rand() % nMax; } while(nbs.find(nb) != nbs.end()); std::cout << nb << endl; }
(Oui je sais, rand() c'est mal, à remplacer).

Sinon tu peux utiliser un arbre pour stocker les intervalles valides, tu auras un temps d'exec borné en O(n log(n)) (je crois ?)
Par exemple si tu veux générer des nombres entre 0 (inclus) et 100 (exclus), avec ep_min == 5 :
Code:

1 2 3 4 ]-1; 100[ (100%) 20 ]-1; 16[ (17.58%) ]24; 100[ (82.42%)
Tu commences avec un seul intervalle : ]-1; 100[, tu as donc 100% de chance d'utiliser cet intervalle. Tu génère un premier nombre : 20
Tu crée 2 intervalles fils et leur attribue leur probabilité d'être utilisés.

Pour chaque nombre à générer, tu effectue un parcours de l'arbre en profondeur en respectant les probabilités de prendre chaque branche.
Dès que tu arrives sur une feuille de l'arbre, tu as ton intervalle final, et tu es sur que le nombre généré sera correct.

Pour éviter que ça se transforme en un algo en O(n²), il faut maintenir un arbre équilibré.

Algo Scolaire: :ptdr: :ptdr:

PS: On peut supprimer quelques variables :whistle:

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
#define N_MAX 256
 
int main(void)
{
    unsigned short ep_min = 8;
    unsigned short last_nb = 0, nb = 0, diff = 0, min = N_MAX, max = 0, min_diff = N_MAX, max_diff = 0, i = 0, count = 0, count_ite = 0;
 
    unsigned short direction = 0, max_N_MAX = (N_MAX - ep_min + 1);
 
    srand( time(NULL) );
 
    last_nb = (1 + rand() % N_MAX);
 
    for(; i < 30000; i++) {
        if (last_nb >= max_N_MAX) {
            nb = (1 + rand() % (last_nb - ep_min));
        } else if (last_nb <= ep_min) {
            nb = (last_nb + ep_min + rand() % (max_N_MAX - last_nb));
        } else {
            direction = (rand() % 2);
 
            if (direction == 1) {
                nb = (last_nb + ep_min + rand() % (max_N_MAX - last_nb));
            } else {
                nb = (1 + rand() % (last_nb - ep_min));
            }
        }
 
        diff = ((nb > last_nb)? (nb - last_nb): (last_nb - nb));
 
        if (diff < ep_min) { count++; }
        if (nb > max) { max = nb; }
        if (nb < min) { min = nb; }
        if (diff > max_diff) { max_diff = diff; }
        if (diff < min_diff) { min_diff = diff; }
 
        printf("%d: (%d) - %d\n", nb, diff, direction);
 
        last_nb = nb;
    }
 
    printf("Miss: %d - %d%% / %d - %d -> %d - %d, %d", count, ((count * 100) / 30000), count_ite, min, max, min_diff, max_diff);
 
    return 0;
}

Et celui avec les pages, mais pas optimal

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
#define N_MAX 256
 
int main(void)
{
    unsigned short ep_min = 8;
    unsigned short last_nb = 0, nb = 0, diff = 0, min = N_MAX, max = 0, min_diff = N_MAX, max_diff = 0, i = 0, count = 0, count_ite = 0;
    unsigned range = (floor(N_MAX / ep_min) + (((N_MAX % ep_min) != 0)? 1: 0)), current_page = 0, last_page = 0;
 
    srand( time(NULL) );
 
    last_page = (rand() % range);
 
    if (range <= 5) { return 0; }
 
    for(; i < 15000; i++) {
//      range - 3: une de moins pour l'ancienne, et 2 autres pour chaque côté
        current_page = (last_page + 2 + rand() % (range - 3));
        if (current_page >= range) { current_page -= range; }
 
        nb = (current_page * ep_min + (1 + rand() % ep_min));
 
//      Seulement pour tronquer la dernière page si (N_MAX % ep_min) != 0
        if (nb > N_MAX) { nb = N_MAX; }
 
        diff = ((nb > last_nb)? (nb - last_nb): (last_nb - nb));
 
        if (diff < ep_min) { count++; }
        if (nb > max) { max = nb; }
        if (nb < min) { min = nb; }
        if (diff > max_diff) { max_diff = diff; }
        if (diff < min_diff) { min_diff = diff; }
 
        printf("%d: %d -> %d (%d)\n", nb, last_page, current_page, diff);
 
        last_nb = nb;
        last_page = current_page;
    }
 
    printf("%d - Miss: %d - %d%% / %d - %d -> %d - %d, %d", range, count, ((count * 100) / 15000), count_ite, min, max, min_diff, max_diff);
 
    return 0;
}

23/04/2014, 11h14
skeud

J'ai rapidemment survolé le sujet, tu voudrais un générateur de nombre aléatoire mais lissé? Du style bruit de perlin?

Cette manière permet de généré des nombre aléatoire mais en fesant en sorte que chaque nombre soit lié avec celui qui le précède pour évité les grands écarts. Avec un peu de modification, tu pourrais limiter le MAX et le MIN pour avoir ce que tu veux non?
23/04/2014, 11h18
Iradrille

Citation:

Envoyé par skeud

J'ai rapidemment survolé le sujet, tu voudrais un générateur de nombre aléatoire mais lissé? Du style bruit de perlin?

Cette manière permet de généré des nombre aléatoire mais en fesant en sorte que chaque nombre soit lié avec celui qui le précède pour évité les grands écarts. Avec un peu de modification, tu pourrais limiter le MAX et le MIN pour avoir ce que tu veux non?

Justement, il faut un écart > ep_min entre 2 nombres.
23/04/2014, 11h33
skeud

Beh tu peux modifier le retour du bruit de perlin pour avoir cet écart, en le relançant tant que tu n'as pas cet écart de respecté non?
24/04/2014, 12h13
CliffeCSTL

Mon problème initial c'est de positionner des points sur un cercle aléatoirement en s'arrurant qu'ils sont suffisamment éloigner (un angle minimal de "ep_min" entre 2 points).
24/04/2014, 12h42
JolyLoic

Je ne sais pas d'où vient ta contrainte d'espacement minimum, mais selon les cas, une solution hyper simple est de tirer des valeurs comme multiple de cet intervalle minimal. Genre, si c'est 5°, plutôt que de tirer des valeurs entre 0 et 360, tu tires des valeurs entre 0 et 72, et multiplie le résultat par 5...