Réutiliser une permutation d'un tri

Version imprimable

26/08/2009, 18h03
oodini

Réutiliser une permutation d'un tri

Bonjour,

J'ai 3 vecteurs. Un élément d'indice i d'un vecteur est lié aux éléments d'indice i des autres vecteurs. Ce qui veut dire que si je trie un vecteur, je dois trier les autres en effectuant les même permutations.

Y a-t-il moyen d'effectuer un tri sur un vecteur, de sauvegarder la séquence de permutation, et de l'utiliser sur les autres vecteurs ?

Vous allez me dire : "Il faut faire un vecteur de structures avec 3 éléments, correspondant aux 3 vecteurs, et effectuer le tri selon une des composantes de la structure."

Oui, mais au final, je dois fournir les données sous forme de 3 vecteurs indépendants.

Que feriez-vous ?

Merci.
26/08/2009, 19h55
cyberpi

Visiblement tu ne fais pas le tri toi-même, sinon ce ne serait pas compliqué d'appliquer en parallèle les mêmes permutations aux autres vecteurs.

Dans ton cas, avant le tri je récupérerais dans un tableau les adresses de tous les éléments de ton vecteur v1. Puis le tri. Puis avec deux boucles for je construirais un tableau pour dire où était placé dans le tableau original l'élément d'indice i (newValues[j] = i). Et enfin appliquer les mêmes changements aux vecteurs v2 et v3.
27/08/2009, 00h03
loufoque

Citation:

Que feriez-vous ?

Je ferais un adapteur autour du vecteur qui détecterait les permutations et les répercuterait sur les autres vecteurs.
27/08/2009, 00h07
cyberpi

Citation:

Envoyé par loufoque

Je ferais un adapteur autour du vecteur qui détecterait les permutations et les répercuterait sur les autres vecteurs.

Comment tu coderais-tu ton adapteur sur un container de la stl?

Remarque: tu vas faire nlogn permutations aussi sur les autres vecteurs, au lieu de juste n.

Salut,

Peut-être pourrais tu envisager un quatrième tableau, qui contiendrait un tuple manipulant... trois pointeurs (un par tableau à trier)...

Plutôt que de trier les trois tableaux, tu te "contenterait" de trier le tableau de tuple selon tes besoins, et tu choisirais tes objet au départ de cela.

Cela te donnerait un code sans doute proche de

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
#include <tr1/tuple>
class T1
{
    /* le type manipulé par le premier tableau  */
};
class T2
{
    /* le type manipulé par le deuxième tableau */
};
class T3
{
   /* le type manipulé par le troisième tableau */
};
 
/* pour s'éviter des écritures à rallonges et à charnières */
 
typedef std::tr1::tuple<T1*,T2*,T3> MyTuple;
 
/* foncteur utile pour le tri au départ de T1 */
struct lessByT1
{
    bool operator <(MyTyple const & t1, MyTuple const & t2)  const
    {
        return std::tr1::get<0>(t1)->laFonctionQuiVaBien()< 
               std::tr1::get<0>(t2)->laFonctionQuiVaBien()
    }
};
/* foncteur utile pour le tri au départ de T2 */
struct lessByT2
{
    bool operator <(MyTyple const & t1, MyTuple const & t2)  const
    {
        return std::tr1::get<1>(t1)->laFonctionQuiVaBien()< 
               std::tr1::get<1>(t2)->laFonctionQuiVaBien()
    }
};
 
/* foncteur utile pour le tri au départ de T3 */
struct lessByT3
{
    bool operator <(MyTyple const & t1, MyTuple const & t2)  const
    {
        return std::tr1::get<2>(t1)->laFonctionQuiVaBien()< 
               std::tr1::get<2>(t2)->laFonctionQuiVaBien()
    }
};
std::vector<T1> tab1;
std::vector<T2> tab2;
std::vector<T3> tab3;
std::vector<MyTuple> reftab;
/* remplissage des tableaux */
for(size_t i=0;i<TOTAL_ITEM; ++i)
{
    tab1.push_back(T1(/*...*/);
    tab2.push_back(T2(/*...*/);
    tab3.push_back(T3(/*...*/);
    reftab.push_back(std::tr1::make_tuple(&tab1[i],&tab2[i],&tab3[i]);
}
/* trions les éléments en fonction  de T1 */
std::sort(reftab.begin(),reftab.end(),lessByT1);
/* accédons au troisième élément d'après le tri */
std::tr1::get<0>(tabref[2])->laFonctionDeT1Requise();
std::tr1::get<1>(tabref[2])->laFonctionDeT2Requise();
std::tr1::get<2>(tabref[2])->laFonctionDeT1Requise();

Le code n'est absolument pas testé (mais, à moins d'une erreur d'attention, il devrait être juste) et présente, il est vrai, une indirection supplémentaire, mais il t'évite les problèmes liés au fait de devoir respecter les ordres de tri pour trois tableaux en simultané ;)

27/08/2009, 14h41
loufoque

Citation:

Le code n'est absolument pas testé (mais, à moins d'une erreur d'attention, il devrait être juste)

Il est faux, push_back invalide les pointeurs vers les éléments.

Citation:

Comment tu coderais-tu ton adapteur sur un container de la stl?

Ce serait relativement chiant à faire.
Des choses similaires existent déjà, comme zip_iterator dans boost, mais je ne pense pas que cela fonctionne avec un tri. (en effet, ça ne fonctionne pas, mais il y a un patch : https://svn.boost.org/trac/boost/ticket/1860)
27/08/2009, 14h52
3DArchi

Salut,
J'aurais tendance à suivre une démarche analogue à Koala si les opérations de tris sont fréquentes. Garder les trois premiers vecteurs non triés et utiliser un vecteur d'indice qui contient l'ordre que tu souhaites.

Citation:

Envoyé par loufoque

Il est faux, push_back invalide les pointeurs vers les éléments.

Il me semblait bien que je ne prenais pas quelque chose en compte :aie:

Ben selon la fréquence des insertions (ou des suppressions) et des tris, on pourrait faire un truc proche de

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
void update(std::vector<MyTuple>& t, std::vector<T1> const & tab1,
            std::vector<T2> const & tab2, std;;vector<T3> const & tab3)
{
    /* le premier test de cohérence qui me vient à l'esprit est de comparer
     * la taile de t par rapport à celle de l'un des tableaux...
     * mais nous pourrions nous arranger pour trouver un autre moyen (et
     * ce serait d'ailleurs préférable car la seule comparaison de taille
     * pourrait poser problème s'il n'y a pas de mise à jour entre une 
     * suppression et une insertion survenant juste après (ou vice 
     * versa ) )
     */
    if(t.size()!=tab1.size())
    {    t.clear(); /* pas besoin de delete parce que les pointeurs pointent
                     * vers des objets dont la durée de vie est gérée 
                     * par ailleurs
                     */
        for(size_t i=0;i<tab1.size();++i)/* "en théorie", le nombre d'objets
                                          * de tab1 doit être égal à celui de
                                          * tab2 et de tab3
                                          * cela pourrait être vérifé sous 
                                          * forme de précondition, mais 
                                          * cette responsabilité  revient à 
                                          * quelqu'un d'autre
                                          */
        {
            t.push_back(std::tr1::make_tuple(&tab1[i],&tab2[i],&tab3[i]);
        }
    }
}

Evidemment, l'idéal serait de mettre toutes ces fonctions de gestion des tableau dans une classe qui aurait cette responsabilité, car cela implique qu'il faut avoir la certitude que la mise à jour a été effectuée :D

Si nous créions une classe qui serait responsable de la gestion des différents tableaux, nous pourrions nous contenter d'un booléen pour indiquer s'il faut une mise à jour ou non, qui prendrait une valeur particulière (true :question:) à chaque insertion / suppression... et la valeur inverse (false, en l'occurence) quand la mise à jour a été effectuée.

Lorsque l'on soutaite effectuer un tri, "il n'y aurait qu'à" invoquer (ou non, selon les circonstances) la fonction de mise à jour de manière tout à fait transparente pour l'utilisateur avant d'effectuer réellement le tri :D

27/08/2009, 17h00
Arzar

Citation:

Envoyé par loufoque

Je ferais un adapteur autour du vecteur qui détecterait les permutations et les répercuterait sur les autres vecteurs.

Tu aurais un exemple ou un lien vers de la doc démontrant ce genre de technique ?

Comme je l'ai dit, tu prends le code de zip_iterator dans boost, t'appliques le patch pour corriger le bug (je vais essayer de faire pression que pour la résolution soit integrée dans le tronc prochainement) et voilà, tu as la solution.

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
#include <boost/iterator/zip_iterator.hpp>
#include <boost/range/as_array.hpp>
#include <algorithm>
#include <iostream>
 
struct first_element_compare
{
    bool operator()(const boost::tuple<int, int>& lft, const boost::tuple<int, int>& rgt) const
    {
         return boost::get<0>(lft) < boost::get<0>(rgt);
    }
};
 
int main()
{
    int foo[] = {9, 5, 6, 1};
    int bar[] = {1, 2, 3, 4};
 
    std::sort(
       boost::make_zip_iterator(
           boost::make_tuple(
               &foo[0],
               &bar[0]
           )
       ),
       boost::make_zip_iterator(
           boost::make_tuple(
               foo + 4,
               bar + 4
           )
       ),
       first_element_compare()
    );
 
    std::cout << boost::as_array(foo) << std::endl;
    std::cout << boost::as_array(bar) << std::endl;
}

affiche, avec le patch

Code:

Ah oui ! Désolé, j'avais lu trop vite, c'est effectivement une jolie solution le boost::iterator.

Dommage qu'on ait pas encore boost.Range_ex, ça simplifierait énormement la syntaxe. (Elle se fait désirer cette bibliothèque, ça fait déjà plusieurs mois qu'elle a été revue et acceptée dans Boost mais elle n'est toujours pas livrée dans la dernière version !)

Le code deviendrait :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 struct first_element_compare { bool operator()(const boost::tuple<int, int>& lft, const boost::tuple<int, int>& rgt) const { return boost::get<0>(lft) < boost::get<0>(rgt); } }; int main() { int foo[] = {9, 5, 6, 1}; int bar[] = {1, 2, 3, 4}; // combine sera disponible dans Boost.Range_ex std::sort(boost::combine(foo, bar), first_element_compare); }

28/08/2009, 16h34
loufoque

Citation:

combine sera disponible dans Boost.Range_ex

Attention, dans la version actuelle cela ne semble pas supporter un tuple de taille arbitraire.