Discussion :

[CliffeCSTL]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[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?

[CliffeCSTL]

Pcq je compare toutes les valeurs.

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

[ternel]

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

[CliffeCSTL]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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?

[CliffeCSTL]

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

[CedricMocquillon]

Un truc du genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Iradrille]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[ternel]

Personnellement, j'irai plus "algorithm"ement:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

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 C++11 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

[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

[Astraya]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Iradrille]

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.

[Astraya]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

[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?

[Joel F]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[CedricMocquillon]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Arzar]

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

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.