Optimiser code c++

Version imprimable

20/06/2013, 09h28
CliffeCSTL

Optimiser code c++
Bonjour,

Je souhaite écrire une fonction en c++ la plus rapide et optimiser possible.

Il s'agit de comparer deux listes L1 et L2 (de même taille). La fonction retourne 1 si L1 domine L2, 2 si L2 domine L1 et 0 sinon.

Une liste L1 domine une liste L2 si L1[i] <= L2[i], quelque soit 'i'.
Code:

1 2 3 4 5 6 int compareListe(QList<int> & L1, QList<int> & L2) { int res = 0; [...] return res; }
J'ai déjà écrit la fonction, mais elle n'est pas assez rapide. Si vous avez de bonnes idées ...

Merci.
20/06/2013, 09h48
ternel

Quel est le sens de "domine"?

Pourquoi ne pas utiliser std::mismatch et comparer les valeurs désignées par ces itérateurs?

Par ailleurs, pourquoi penses-tu que ta fonction est lente?
20/06/2013, 09h53
CliffeCSTL

Pcq je compare toutes les valeurs.
20/06/2013, 09h59
CedricMocquillon

Je ne connais pas les QList (mais je pense que c'est des listes chainées). A mon avis tu irais plus vite à comparer des vecteurs (pour les temps d'accès).

Si tu as des informations sur la probabilité que pour la composante i il y ait égalité, tu peux également t'en servir pour réordonner tes vecteurs (en mettant dans les premières composantes celles qui ont le plus de probabilité d'être différentes).

Tu devrais également passer tes listes en const référence (il n'y a pas de raisons que tu les modifies)
20/06/2013, 10h17
ternel

std::mismatch n'est pas le meilleur choix pour tout comparer, en effet, mais jette quand même un œil sur <algorithm>

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int compareListe(const QList<int> & L1, const QList<L2>)
{
   int i = 0, d1 = 0, d2 = 0, n = L1.size();
 
   while (i < n)
   {
      if (L1[i] <= L2[i]) ++d1;
      if (L2[i] <= L1[i]) ++d2;
 
      ++i;
   }
 
   if (d1 == n) res = 1;
   else if (d2 == n) res = 2;
 
   return res;
}

20/06/2013, 10h54
Astraya

Pourquoi retourner 1 ou 2 et pas simplement la liste qui domine, tu économisera quelques instructions:
De plus while n'est pas plus "performant" que for...il est juste plus illisible dans ton cas.
Je ne comprends pas le sens de dominer non plus, dans ton test tu comprares toutes les valeurs et si tout les valeurs d'une listes sont supérieur alors cette liste est renvoyé? Mais uniquement si TOUTES les valeurs sont supérieurs?
20/06/2013, 10h57
CliffeCSTL

Une liste domine si ces valeurs sont inférieures ou égale à toutes celles de la deuxième.

Un truc du genre:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
bool compareListe(QList<int> const& left, QList<int> const& right)
{
    assert(left.size() == right.size());  //à voir ici comment tu gères deux listes de taille différente
    std::size_t size = left.size();
    for(std::size_t i = 0; i < size; ++i)
    {
        if(!(left[i] <= right[i]))
		return false;
    }	
    return true;
}

Par contre pour les QList il faut sans doute préférer les itérateurs à l'accès en [i] (mais si tu cherches la performance passe aux vecteurs!)

Citation:

Envoyé par CliffeCSTL

Une liste L1 domine une liste L2 si L1[i] <= L2[i], quelque soit 'i'.

Hello,

Avec deux listes identiques, c'est quoi le résultat attendu ? (Ton code renvoi 1 dans ce cas, ce qui semble bizarre).

Sinon, tu n'est pas obligé de parcourir les listes entières, tu peux t’arrêter dès que tu sais qu'aucune liste domine.

Tu peux faire quelque chose du genre (quand 2 listes identiques, L1 domine L2 et L2 domine L1, mon code renvoi 3 dans ce cas)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int compareListe(const std::vector<int> & l1, const std::vector<int> & l2) { if(l1.size() != l2.size()) { return 0; } auto it_l1 = l1.begin(); auto it_l2 = l2.begin(); auto it_end = l1.end(); bool a = true, b = true; while((a || b) && it_l1 != it_end) { a &= *it_l1 <= *it_l2; b &= *it_l2 <= *it_l1; ++it_l1; ++it_l2; } return a + 2 * b; }

Personnellement, j'irai plus "algorithm"ement:

Code:

1
2
3
4
5
6
7
int compareListe(QList<int> const& left, QList<int> const& right) {
    if (std::max_element(left.begin(), left.end()) < std::min_element(right.begin(), right.end())) return 1;

    if (std::max_element(right.begin(), right.end()) < std::min_element(left.begin(), left.end())) return -1;

    return 0;
}

ou mieux encore:

Code:

1
2
3
4
5
6
7
int compareListe(QList<int> const& left, QList<int> const& right) {
    auto left_bounds = std::minmax_element(left.begin(), left.end());
    auto right_bounds = std::minmax_element(right.begin(), right.end());
    if (left_bounds.second < right_bounds.first) return 1;
    if (left_bounds.first > right_bounds.second) return -1;
    return 0;
}

Cette version ne fais qu'un seul parcours de chaque liste.

La valeur retournée est classique: 1 si l'ordre est left puis right, -1 si l'ordre est right puis left, 0 sinon

20/06/2013, 11h50
CliffeCSTL

Je sais que les listes sont de même taille. Je sais que les valeurs sont comprisent entre 0 et m. Cette fonction dois retourner 1, 2 ou 0 (pas de bool ou de -1)
20/06/2013, 11h55
CedricMocquillon

Le truc c'est que ça ne correspond pas: si par exemple tu as les deux vecteurs suivants:
v1 = {1, 2, 10, 3} et
v2 = {2, 3, 11, 4}
Pour v1, le max est 10 et le min 1
Pour v2, le max est 11 et le min 2
Ton algo renvoie 0 car :
- 10 n'est pas plus petit que 2
- 11 nest pas plus petit que 1
Alors que v1 domine v2
[Edit]: ce message est en réponse à celle de leternel

Tu peux facilement, de façon optimisé faire:

1 - définir lequel est censé dominé l'autre avec la première valeur de la QList. Tu obtiendra le dominant potentiel.
2 - Tu boucles si un des éléments du dominant est plus petit. Dans ce cas la, aucun n'est dominant tu quitte direct. Si le dominant s’avère être toujours le dominant tu retourne sont chiffre associé.

Pas de code illisible avec des & || et autre truc sale ne servant a rien sauf a rentre illisible car au final l'assembleur est le même voir plus mauvais avec ces pratique.

Psedo code
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int compareListe(QList<int> const& L1, QList<int> const& L2) { int delta = L1[0] - L2[0]; int returnValue = 0; if(delta >0) L1 dominante possible returnValue = 1 else if(delta < 0) L2 dominante possible returnValue = 2 else Aucun dominant return returnValue ; if(L1.size() > 1) { for(int i = 1; i< L1.size(); ++i) { if(dominant[i] <= dominer[i]) return 0; } } return returnValue; }
Crois le ou pas, le code est plus long, mais plus rapide que ce que tu as pu voir. Surtout pour les longues listes... Le code est lisible simple et efficace. Ton compilateur sait extrêmement bien optimiser ça de lui même.

Cordialement

20/06/2013, 13h25
Iradrille

Citation:

Envoyé par Astraya

Le code est lisible simple et efficace.

Mais faux. ;)

L1 = { 1, 4 }
L2 = { 1, 0 }
(-> L2 domine L1)

delta = 0, donc tu ne détecte pas de dominant.

Effectivement, je pensais à strictement différent de 0 et en même temps un spedo code reste un psedo code, d'ou son nom, il est pas fait pour compiler mais pour réalisé un algorithm efficace et cohérent.
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 int compareListe(QList<int> const& L1, QList<int> const& L2) { int delta = 0; int index = 0; while(delta !=0) { delta = L1[index] - L2[index]; ++index; } int returnValue = 0; if(delta > 0) L1 dominante possible returnValue = 1 else if(delta < 0) L2 dominante possible returnValue = 2 else Aucun dominant return returnValue ; if(L1.size() > 1) { for(int i = 1; i< L1.size(); ++i) { if(dominant[i] <= dominer[i]) return 0; } } return returnValue; }
Pourquoi ce code est plus efficace sur les listes de plusieurs élement? Parce que on réalise un minimum d'instruction. La boucle ne réalise aucune autre instructions qu'un comparaison. Donc pour 10000 valeur tu aura 9999 comparaison au maximum... et c'est tout... :)

20/06/2013, 17h07
Astraya

Après CliffeCSTL si tu connais le mutlithread, tu peux procéder en 2 3 4 ... x thread de façon à comparer des blocs de ta QList. Par exemple un thread pour les 100 première valeur, le 2nd pour les 100 autres etc...
Combien as tu de valeur à comparer? pourquoi estimes tu que elle n'est pas assez rapide? as tu des contraintes de temps importantes dessus?

multithreader ce code c'est appliquer un cataplasme sur une jambe de bois, il ets fortement memory bound, tu vas rien accélérer.

Apres vu comment l'OP ne maitrise pas les algos de bases, je pense aue les soucis de threading vont lui passer au dessus de la tete.

tu verifie si *s1 <= *s2 jusqu'a ce que tu trouve un truc faux. Dans ce cas tu renvois 2 sinon tu sort et ut renvois 1.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 template<class Sequence> int compare( Sequence const& s1, Sequence const& s2) { typename Sequence::const_iterator i1 = s1.begin(); typename Sequence::const_iterator e1 = s1.end(); typename Sequence::const_iterator i2 = s2.begin(); typename Sequence::size_type eq; // Sinon y a forcement L1 <= L2 ou l'inverse while( (i1 != e1) ) { if( *i1++ > *i2++) return 2; else if(*i1++ == *i2++) eq++; } // Arrive ici, L1 <= L2, donc on retourne 1 si L1 != L2 return eq == std::distance(s1.begin(),s1.end() ? 0 : 1; }
devrait suffire.

L'algo est forcement en O(N) worst case, le retour anticipé permettant de short-cutter les cas ou on trouve tout de suite la dominance.

DISCLAIMER : j'ai pas bu mon café, y a pe des typos.

EDIT : j'ai oublié le cas 0

En fait l'algo proposé par Astraya est le bon. Comme l'a mis l'OP dans son premier post: une liste L domine une liste R si pour tout i L[i] <= R[i]. J'ai mis des tests U pour vérifier les différentes solutions proposées.

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
 
#include <algorithm>   //pour mismatch
#include <iterator>     //pour begin, end
#include <utility>       //pour pair
 
template<class InputIterator1, class InputIterator2>
bool is_less_or_equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
   while ( (first1!=last1) && (*first1<=*first2) )
   { ++first1; ++first2; }
   return first1==last1;
}
 
template<class Sequence>
int compareListe(Sequence const& L, Sequence const& R)
{
   auto res = std::mismatch(std::begin(L), std::end(L), std::begin(R));
 
   if(res.first == std::end(L))
      return 0;   //égalité "parfaite" entre L et R
 
   if(*res.first < *res.second)
   {
      //à priori L domine R.
      //on vérifie notre à priori sur le reste de la collection :
      if(is_less_or_equal(res.first, std::end(L), res.second))
         return 1; //notre à priori s'est vérifié
      return 0;
   }
 
   //à priori R domine L.
   //on vérifie notre à priori sur le reste de la collection :
   else if(is_less_or_equal(res.second, std::end(R), res.first))
      return 2; //notre à priori s'est vérifié
   return 0;
}
 
#define BOOST_TEST_MODULE route test
#include <boost/test/unit_test.hpp>
#include <vector>
#include <boost/assign/list_of.hpp>
 
BOOST_AUTO_TEST_CASE( test_dominance )
{
   using namespace boost::assign;
   BOOST_CHECK_EQUAL( compareListe(list_of(0)(1)(2)(3), list_of(1)(2)(3)(4)), 1 );
   BOOST_CHECK_EQUAL( compareListe(list_of(1)(2)(3)(4), list_of(0)(1)(2)(3)), 2 );
   BOOST_CHECK_EQUAL( compareListe(list_of(1)(2)(3)(4), list_of(1)(2)(3)(4)), 0 );
   BOOST_CHECK_EQUAL( compareListe(list_of(0)(1)(2)(3), list_of(1)(2)(0)(4)), 0 );
   BOOST_CHECK_EQUAL( compareListe(list_of(2)(1)(2)(3), list_of(1)(2)(3)(4)), 0 );
}

Pour le moment tous les algos présentés sont faux, excepté celui d'iradrille... donc ce n'est pas si simple que ça comme question :mouarf:

En se basant sur l'ago d'iradrille je pense qu'on peut optimiser un chouia, en s'économisant une comparaison lorsque deux élements de la liste sont identiques :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 int compareListe(const std::vector<int> & l1, const std::vector<int> & l2) { if(l1.size() != l2.size()) return 0; auto it_l1 = l1.begin(); auto it_l2 = l2.begin(); auto it_end = l1.end(); bool a = true, b = true; while((a || b) && it_l1 != it_end) { if(*it_l1 == *it_l2) goto next; bool dom = *it_l1 < *it_l2; a &= dom; b &= !dom; next: ++it_l1; ++it_l2; } return a + 2 * b; }
A ce stade, je ne vois pas comment faire mieux.

23/06/2013, 18h34
Joel F

ca reste de l'economie de bout chandelle. L'algo ets et reste un truc lineaire et memory bound.
23/06/2013, 19h14
CedricMocquillon

@Arzar: as-tu testé avec les tests U que j'ai mis? Chez moi, l'algo de iradrille et le tiens modifié me renvoient 3 dans le cas de deux séquences identiques.
Aurais tu un exemple pour lequel le code que j'ai mis (qui est la traduction de l'algo d'Astraya ) ne fonctionne pas? (j'ai beau chercher, je vois pas ce qui pourrait clocher)

[Edit] je viens de voir que c'est voulu par Iradrille, sachant que l'OP sur ce point n'a pas répondu sur le comportement souhaité
24/06/2013, 01h59
Arzar

Citation:

Envoyé par CedricMocquillon

Aurais tu un exemple pour lequel le code que j'ai mis |...]

Je ne l'avais pas vu :aie:
Tu as posté quelques minutes avant moi, et j'étais déjà en train de rédiger pendant ce temps.

Si j'ai bien compris la définition de "dominer": une liste L domine une liste R si pour tout i L[i] <= R[i].

Je pense que l'astuce n'est pas de parcourir toute la liste.
Si on a L[0]<R[0] alors on pose comme hypothèse que c'est vrai pour tout i et on s'arète dès que notre hypothèse est invalidée.

Comme on travail sur des listes l'utilisation des index n'est peut être pas le plus judicieux...
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 enum Dominant { L2Dominant, L1Dominant, SaisPas }; int compareListe(QList<int> & L1, QList<int> & L2) { if(L1.size()>0 && L1.size() == L2.size()) { QList<int>::const_iterator it1 = L1.begin(); QList<int>::const_iterator it2 = L2.begin(); Dominant d = SaisPas; while(it1!=L1.end()) { if(*it1!=*it2) { if(SaisPas==d) d = (*it1<*it2)?L1Dominant:L2Dominant; else if( (*it1<*it2)?L1Dominant:L2Dominant != d) return 0; } ++it1; ++it2; } if(d==L1Dominant) return 1; if(d==L2Dominant) return 2; } return 0; }