Optimisation de methode

[christ001]

Bonjour a tous,

Je suis a la recherche d'aide sur l'optimisation de boucle.
J'ai 75 chiffres qui doit être combiné avec 5 autres chiffres.
Qui nous donnes 75*74*73*72*71=2 071 126 800 de possibilité.
Lorsque je fais cela via un seul process d'un ordinateur, cela mettrai énormément de temps.

J'aimerai décomposer cela, afin de faire cela en 10 process.
Qui permettrait de diviser le temps par 10 et également, utilisé les autres processeurs pour cela.
Mais en gardant toutes les possibilités.

Merci par avance de votre aide.

[fatal_error]

bj,

ca aurait été mieux si tu décrivais mieux ton pb, car il n'y a pas que paralléliser pour optimiser..

qd bien même:
75*74*...*71, ca correspond à tirer un arrangement de 5 el parmi 75.
si tu stockes tes el dans un vecteur de taille 75, il suffit de tirer 5 el parmi les 75, et de les ordonner (5! possibilités), idem, 120 possibilités.
tu peux donc générer chaque combinaison, et pour chacune d'entre elle paralléliser 12 bulks où chaque proc traite un arrangement.

[christ001]

Bonjour fatal_error

Merci pour ta réponse.
En gros, j'ai une table avec 75 enregistrements. Chaque enregistrement passe par une fonction afin de récupérer une valeur. Si la valeur est bonne la fonction indique 1 sinon 0.
Le but, c'est d'avoir une somme de 5.
Mais je ne vois pas comment découper cela.
Car générer le nombre de combinaison représente 2 071 126 800 enregistrements.
J'aurais penser que cela aurait pu être en formule mathématique

Un grand merci

[fatal_error]

remplaces vecteur par tableau.

Si la valeur est bonne la fonction indique 1 sinon 0.
Le but, c'est d'avoir une somme de 5.

ben applique ta fonction sur chacun des enregistrements, tu obtiens un tableau de 75 elements qui valent 0 ou 1.
tu récupères les indices des éléments qui valent 1 dans un tableau unos et ceux qui valent 0 dans un tableau nommé zeros
tu prends 5 el dans unos (ca te donne une somme de 5) et tu peux compléter par ceux que tu veux de zeros...(vu que ca changera pas la somme)

tu peux paralléliser les appèlent de ta fonction f (c'est probablement ca qui coute...)

edit: si ton but c'est juste d'avoir UNE somme qui vaut 5...
tu peux considérer un compteur (un entier) initialisé à 0.
chaqu'un de tes threads incremente l'entier(type std::atomic) et lis l'enregistrement associé. si le retour de la fonction vaut 1, tu stockes l'indices dans un tableau, et tu stoppes tes threads si jamais tu as stocké 5 elements ou si ton compteur vaut 75

[christ001]

D'accord. Je vais voir ça.

Merci

[christ001]

bonjour,

J'ai crée une nouvelle table avec un id

j'ai fait 5 boucles, comme ceci
PS : J'ai fait id > id -1 car aussi non, on aurait 5 fois les mêmes enregistrements.
********************************************************
BOUCLE1
BOCULE2 where id > BOUCLE1.id
BOCULE3 where id > BOUCLE2.id
BOCULE4 where id > BOUCLE3.id
BOCULE5 where id > BOUCLE4.id

5 inserts dans la nouvelle table.
incremenation de l'id
LOOP
LOOP
LOOP
LOOP
LOOP
********************************************************

Cela a mis environs une heure pour faire cela.
Donc c'est la fonction qui a prend du temps (je vais voir pourquoi)

Par contre, je n'arrive pas a comprendre ceci.

La table qui est lu a l'origine a 75 enregistrements.
Au final, j'ai un id max de 17259388
Qui fait 17259388*5, cela donne 86 296 940 enregistrements.
On est loin des 2 071 126 800

Pourquoi cette différence, car

75 enregistrements avec 5 possibilités différentes

75*74*73*72*71=2 071 126 800

Merci encore.

[fatal_error]

salut,

ya beaucoup de choses qui vont pas:
- tu ne définis pas c'est quoi boucle1 (idem les autres boucles): quel est son contenu?
- BOCULE2 where id > BOUCLE1.id, la requete me parait horrible: si boucle1.id vaut 0, tu vas récupérer 74 enregistrements dans boucle2!! et 73 enregistrements dans boucle3: idem tu récupères un enregistrement que tu as déjà récupéré (dans boucle2).
A beaucoup d'égards c'est pas bon:
* tu récupères plusieurs fois le même enregistrement
* tu vas traiter plusieurs fois le même enregistrement et ta fonction est couteuse...
* tu récupères ce lot d'enregistrement en boucle! (idem on sein de boucle 2, à la fin de ton programme, tu auras récupéré 74 fois ton dernier enregistrement...)



on ne sait pas quel id tu passes à tes boucles, ni quand tu t'arrêtes, ni ce qu'est boucle.id

c'est dur de deviner c'est quoi idmax que tu obtiens.

En revanche, 86 296 940/120 = 17259390, c'est environ ton idmax.
120=5! vient du fait que tu génères en fait des combinaisons de 5el parmi 15 et non 5 arrangements parmi 15.

par exemple pour les enregistrements <a,b,c,d,e>, tu ne considères pas <b,a,c,d,e>,... (idem toutes les permutations possibles). C'est le cas dans ton code ou tes enreigstrements sont ordonnés par ordre croissant (id > boucle.id)


edit:
j'ajoute:
ci-dessous un algo plus proche de ce qu'on attend d'un truc parallel

Code: Tout sélectionner

/**
 * unos contient les index dans le tableau enregistrements pour lesquels l'enregistrement vaut 1
 * zeros contient les ... vaut 0
 */
fonction thread(threadId)
    unos = tableau d'entier
    zeros = tableau d'entier

    //si thread 0, lit les records 0,5,10...
    //si thread 1, lit les records 1,6,11,...
    pour idx = threadId, idx < 75; idx += 5
        enregistrement = enregistrements[idx]

        //traiter est ta fonction couteuse qui doit retourner 0 ou 1
        si 0 == traiter(enregistrement)
            zeros.push(idx)
        sinon
            unos.push(idx)

    retourner unos, zeros

fonction main()
    enregistrements = select * from table;

    result = tableauDeResultat

    #parallel
    pour threadId = 0 à 4
        result[threadId] = thread(threadId); //result[threadId] contient unos et zeros du thread correspondant

    //on merge tout le monde
    unos = tableau
    zeros = tableau
    pour threadId = 0 à 4
        unos = unos.concat(result[threadId].unos)
        zeros = zeros.concat(result[threadId].zeros)




[lyceen95]

En gros, j'ai une table avec 75 enregistrements. Chaque enregistrement passe par une fonction afin de récupérer une valeur. Si la valeur est bonne la fonction indique 1 sinon 0.

Ca veut dire quoi ? Ce veut dire que si je calcule f(i) maintenant, je vais obtenir 0 ou 1. Et si je recalcule le même f(i) plus tard, je retrouverai la même valeur 0 ou 1.
En d'autres mots, on peut faire un traitement préalable :

Code: Tout sélectionner

Pour i =1 a 75
  si f(i) = 1 alors
      //  mémoriser ce nombre i dans un premier tableau
 sinon
      // Mémoriser ce nombre i dans un autre tableau
  fin
fin

Et ces 2 tableaux vont beaucoup nous aider pour la suite.
Et en plus la fameuse fonction très couteuse, on va l'appeler 75 fois dans cette boucle, et on n'en a plus du tout besoin par la suite. 75 appels au lieu de plusieurs milliards, c'est important.

[christ001]

D'accord. Merci

Bon je sais d'où vient l’écart :

min | max
-----+----------
0 | 17259389


donc 17259389+1 (le 0), on a 17259390

Je vais regarder ton algo de près, afin de bien le comprendre et de le reproduire.

Merci pour ton aide

[christ001]

hello lyceen95

Je vais ajouter un champ a ma nouvelle table et a chaque fois que la fonction sera passé par rapport a un enregistrement, il mettra le champ a jour. Qui fait que je pourrai lancer plusieurs fonction en même temps

Merci d'avoir repondu