Bienvenue sur le forum !

Si vous souhaitez rejoindre la communauté, cliquez sur l'un de ces boutons !

Qt 5 : 5.7.1 - Qt Creator : 4.2.0 - Qt Installer : 2.0.3 - JOM : 1.1.2 - Qt Build suite : 1.7.0 - VS Qt 5 : 2.0.0

[Qt/C++] Aide pour QFuture/QtConcurrent

Bonsoir à tous,

Je viens de découvrir ce forum, et il tombe à pic puisque j'ai un problème avec un petit programme.
Voilà, pour m'amuser je me suis fait un benchmark basé sur les nombres premiers, qui calcule donc les premiers de 1 à un certain nombre, que l'utilisateur rentre, par la méthode du crible d'érastothène (pour ceux qui connaissent). C'est pas la meilleure méthode, mais elle est facile à implémenter.

Je voudrais maintenant l'optimiser pour le multithread, pour m'exercer, et parceque ça m'amuse. J'ai donc regardé du coté de QFutureWatcher, mais je ne trouve que peu d'exemples, et ils ne sont pas clairs, surtout en ce qui concerne la fonction map de QtConcurrent.

Je vous met le code :

.cpp :
#include "monThread.h"

structure donnees;
int nombrePremiers=0;

int algo()
{
int max = 0, limite = 0;

limite = racine(nombrePremiers);
for(int i = 2;i <= limite;i++)
{
if(donnees.tableauStruct[i] == true)
{
max = nombrePremiers/i;
for(int j = i; j <= max; j++)
{
donnees.tableauStruct[j*i] = false;
}
}
}
}
structure calculAlgo(int nombre)
{
nombrePremiers = nombre;
donnees.tableauStruct.resize(nombre+1);

for(int a=0;a<=nombre+1;a++)
{
donnees.tableauStruct.append(true);
}

donnees.tempsStruct=0;

int temps = 0;

QFutureWatcher<void> futureWatcher;

QTime time;

time.start();

futureWatcher.setFuture(QtConcurrent::map(donnees.tableauStruct, algo));
donnees.tableauStruct[0] = false;

futureWatcher.waitForFinished();

temps = time.elapsed();
donnees.tempsStruct=temps;

return donnees;
}

int racine(int nombre)
{
int i;
float y;

y = nombre;
i = * (long *) &y;
i = 0x5f375a86 - (i >> 1);
y = * (float * ) &i;
return ceil(nombre * y);
}
.h
#ifndef MONTHREAD
#define MONTHREAD

#include <QtGui>

typedef struct structure structure;
struct structure
{
int tempsStruct;
QVector<bool> tableauStruct;
};

structure calculAlgo(int nombre);
int racine(int nombre);

#endif
Bon, là c'est le code modifié, à la base le QVector du .h était un QBitArray. En fait je n'ai pas du tout compris ce que faisait la fonction map. Pour moi, elle prend une séquence (ici le QVector, ça marchait pas avec QBitArray), et applique la fonction passée en deuxième parametre à chacun des composants de la séquence. Le problème c'est que dans mon cas précis je ne vois pas comment faire pour séparer le calcul.

Au cas où, le principe du crible est assez simple. Il parcourt le tableau et pour chaque item calcule les multiples, chaque multiple est assigné d'un false dans le tableau, il fait ça pour tous les nombres jusqu'a la racine carrée du nombre entré par l'utilisateu, il ne sert logiquement à rien d'aller plus loin.

Si vous pouviez m'aider pour séparer le calcul en deux, ça m'aiderait beaucoup, ça fait des heures que je patauge. Le code ici présenté ne marche pas, inutile de l'essayer.

Merci

Réponses

  • C'est pas un problème de programmation, c'est un problème d'algo... Pour pouvoir exécuter sur plusieurs threads il faut que ton algorithme soit parallélisable, que tu puisses séparer le travail à effectuer.

    Essaie de voir comment tu peux t'organiser, par exemple : Imagine que vous êtes 4 personnes autours d'une table et que vous devez résoudre le problème pour les nombres premiers de 1 à 1000, comment séparerais-tu le travail entre les convives ? Sachant que chacun a sa feuille de papier devant lui, et qu'il y a un grand tableau au milieu de la table (on peut aussi considérer que les personnes ne trichent pas, ne regardent pas la feuille de leur voisin).
  • December 2010 modifié
    Merci de ta réponse. En je me suis rendu compte que cet algorithme est difficilement parallélisable, je ne peux pas déléguer une boucle à un thread et la suivante a un autre, puisque le second a besoin que la première boucle terminée. Donc j'ai mis des QFuture future = QtConcurrent::run(algo). Je dois dire que ça marche plutôt bien, même si un seul thread est utilisé. Je l'ai fait pour deux boucles, et entre le programme normal et celui qui fait appel à deux thread j'ai gagné plus de 15 secondes sur un calcul qui en durait 49.

    Je ne comprend pas bien pourquoi j'ai gagné du temps d'ailleurs, quand le programme voit le future.waitForFinished() il s'arrête non ? Donc c'est comme si j'avais juste fait appel à une fonction ?
  • December 2010 modifié
    Je ne sais pas d'où vient ton augmentation de performances, as-tu répété plusieurs fois le test, sans aucun autre programme en fonctionnement ?

    Par contre il doit y avoir moyen de paralléliser en se cassant un peu la tête :
    - Lorsque la boucle qui élimine les multiples de 2 est passé au delà de 3, tu peux déjà lancer la boucle de 3 en parallèle. Il y aura juste les multiples 6 qui seront marqué deux fois, ce qui n'est pas grave.
    - Lorsque la boucle qui élimine les multiples de 2 et celle qui élimine les multiples de 3 ont de nouveau laissé un oprhelin (le 5) on peut lancer la boucle du 5.
    - et ainsi de suite...

    Voilà un début d'idée, on voit qu'on peut paralléliser mais avec une certaine redondance, on ira donc en théorie pas deux fois plus vite avec deux threads.
    Par contre pas sur que ce soit implémentable avec QtConcurrent, peut être voir du côté de QThreadPool...
  • Merci de ta réponse

    Pour l'amélioration des performances, je l'ai testé sous toutes les coutures, avec du multiCore, avec du singleCore, je gagne en performances. Et pas qu'un peu. Voilà le code modifié avec les threads :
    #include "monThread.h"

    structure donnees;
    int temps=0, max = 0, limite = 0, i = 0, nombrePremiers = 0;

    void algo2()
    {
    for(int a=0;a<=nombrePremiers+1;a++)
    {
    donnees.tableauStruct.setBit(a,true);
    }
    }

    void algo()
    {
    if(donnees.tableauStruct.testBit(i) == true)
    {
    max = nombrePremiers/i;
    for(int j = i; j <= max; j++)
    {
    donnees.tableauStruct.setBit(j*i,false);
    }
    }
    }

    structure calculAlgo(int nombre)
    {
    donnees.tableauStruct.resize(nombre+1);
    nombrePremiers = nombre;
    QTime time;

    time.start();

    QFuture<void> future2 = QtConcurrent::run(algo2);
    future2.waitForFinished();

    donnees.tempsStruct=0;

    donnees.tableauStruct.setBit(0,false);
    donnees.tableauStruct.setBit(1,false);

    limite = racine(nombre);
    for(i = 2;i <= limite;i++)
    {
    QFuture<void> future = QtConcurrent::run(algo);
    future.waitForFinished();
    }
    temps = time.elapsed();
    donnees.tempsStruct=temps;

    return donnees;
    }

    int racine(int nombre)
    {
    int k;
    float y;

    y = nombre;
    k = * (long *) &y;
    k = 0x5f375a86 - (k >> 1);
    y = * (float * ) &k;
    return ceil(nombre * y);
    }
    Pour ton idée de parallélisation ça ne semble pas être une mauvaise idée, mais je n'ai pas réussi à l'implanter. Le programme met énormément de temps à résoudre l'algorithme, bon j'ai essayé avec QtConcurrent aussi. Mais je ne vois pas en quoi QThreadPool diffère, on l'utilise comme ça il me semble : QThreadPool::globalInstance()->start(algo);

    Donc ça revient au même qu'un run de QtConcurrent non ?
Connectez-vous ou Inscrivez-vous pour répondre.