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.

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