Discussion :

[souki22]

Bonjour à tous,

J'ai une classe nommée T qui contient comme champs :
- float F
- string S
et j'ai besoin d'écrire une fonction booléenne qui admet comme arguments un vector<T> v ainsi qu'un élément E1 de type T et qui informe si l'élément E1 possède un "frère jumeau" dans la liste v selon le sens suivant :
E1 possède un frère jumeau s'il existe trois éléments E2, E3, et E4 de v tels que E1.F=E2.F, E1.S=E3.S, E3.F=E4.F, E2.S=E4.S
J'ai écrit une fonction mais il s'avère que mon vecteur v est très grand et ma fonction prend beaucoup de temps à l'exécution (je fais trois boucles for sur v).
Voici la fonction :

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
bool hasATwin(const T& E1, const vector<T>& v)
{
    vector<T>::const_iterator it2 = v.begin();
    vector<T>::const_iterator it3, it4;
    T E2, E3, E4;
 
    for(; it2 != v.end(); ++it2)
    {
        for(it3=it2+1; it3 != v.end(); ++it3)
        {
            for(it4 = v.begin(); it4 != v.end(); ++it4)
            {
                E2 = *it2; E3 = *it3; E4 = *it4;
                if(E1.F == E2.F &&
                   E1.S == E3.S &&
                   E3.F == E4.F &&
                   E2.S == E4.S())
                    return true;
            }
        }
    }
    return false;
}

Auriez vous des idées pour l'optimiser question temps ?

Bien cordialement.

[ternel]

Ton code travaille en N*N*N

Tu remarqueras que ta condition (E1.F=E2.F, E1.S=E3.S, E3.F=E4.F, E2.S=E4.S) signifie:
E1 et E2 ont le même F
E3 et E4 ont le même F

E1 et E3 ont le même S
E2 et E4 ont le même S

Il serait pas mal de lister les éléments par leur valeur de F, et de même, de les filtrer par valeur de S.
Fais deux vecteurs intermédiaires (contenant non pas des éléments mais des pointeurs ou des indices dans v)
Le premier contiendra les éléments de v ayant le même F que E1, le second ceux ayant le même S.
(std::copy_if, par exemple)

C'est peut-être un début qui devrait te permettre d'aller plus vite, en réduisant non pas la complexité, mais la taille à explorer

D'un autre coté, chercher trois éléments par contrainte, je ne suis pas certain de pouvoir faire mieux que N*N*N.
Le seul moyen de diminuer la complexité, ce serait qu'un tri permette d'explorer plus vite.

Peut-être qu'une map ou une multimap t'aiderait.

[jblecanard]

+1 pour leternel, même si je ne suis pas d'accord sur la complexité : la recherche d'un élément dans une map est une recherche à une contrainte sur N éléments et n'est pas pour autant de complexité N ! Moi je testerais déjà avec une relation d'ordre (en spécialisant std::less par exemple) sur T avec une multimap si T a une sémantique d'entité et avec une map si T a une sémantique de valeur.

[Mat.M]

bonjour oui std :: multimap ou std :: map est approprié voire carrément une recherche sous forme d'arborescence/arbre binaire..peut-être que std :: multimap suffit