Discussion :

[Kreatore]

Bonjour,

Je cherche à utiliser un ensemble ordonné sur l'insertion des éléments qui possède trois types d'accès :
- accès sur le plus ancien en o(1)
- accès sur le plus récent en o(1)
- accès aléatoire en o(log(n)) (pas forcément indiciel)
Avec n grand.

Je pensais utiliser un AVL mais je voulais savoir si vous connaissiez une autre méthode plus pratique, je ne cherche pas à recréer la roue Une sorte de tas peut-être ?

[jblecanard]

Salut !

Ta question n'est pas très claire, que veux-tu dire par "accès aléatoire en o(log(n)) (pas forcément indiciel)" ? Quelle est la clé d'accès dans ce mode ?

Si la relation d'ordre est l'ordre d'insertion et que tes contraintes ne concernent que l'accès, un simple std::vector fera l'affaire et sera meilleur que O(log(n)) en accès.

Si tu dois rechercher les éléments par clé, un std::unordered_map fera l'affaire et sera meilleur que O(log(n)).

Si ta relation d'ordre est sur la clé de recherche, c'est un std::map qu'il te faut.

Si j'ai bien compris ta question, il te faut une combinaison de std::vector (pour l'ordre) et de std::unordered_map (pour la recherche). Si tu dois supporter la suppression, utiliser une std::list en lieu et place d'un std::vector peut s'avérer judicieux. Si c'est bien ce que tu recherches mais que tu ne vois pas comment utiliser ces éléments pour l'implémenter proprement, nous pourrons t'aider .

[koala01]

Salut,

Le plus facile pour avoir un accès en O(log(n)) sur n'importe quel élément, c'est sans doute d'utiliser la classe std::set, à moins que tu ne veuilles pas de l'unicité des éléments (ce n'est pas un AVL, mais un Red Black Tree, ce qui revient grosso modo au même ).

Il ne resterait plus qu'à assurer l'accès à l'élément le plus récent et à l'élément le plus ancien, et pour ca, il y a une solution simple qui ne permet pas de supprimer un élément et une solution à peine moins simple qui pourrait même te permettre de supprimer des élément tout en étant sur de toujours obtenir le bon résultat.

La solution la plus simple pourrait prendre une forme proche de

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
template <typename T>
class MyContainer{
public:
    using const_iterator = typename std::set<T>::const_iterator;
    MyContainer():firstInserted_(datas_.end()), lastInserted_(datas_.end()){}
    void insert(T const & t){
        auto it = datas_.insert(t);
       /* si l'insertion réussi */
        if( it.second){
            /* si on n'a pas encore défini d'itérateur valide pour le premier élément */
            if (firstInserted_ == datas_.end())
                firstInserted_= it.first; // c'est que l'itérateur récupéré est le premier élément inséré
            /* et c'est de toutes façons aussi le dernier élément inséré */
            lastInserted_=it.first;
        }
    }
    const_iterator firstInserted()const{return firstInserted_;}
    const_iterator lastInserted() const{return lastInserted_;}
    const_iterator begin() const{return datas_.begin();}
    const_iterator end() const{return datas_.end();}
    size_t size() const{return datas_.size();}
    /* l'accès en O(log(n)) se fait ici */
    const_iterator find(T const & t) const{return datas_.find(t);}
private:
    std::set<T> datas_;
    const_iterator firstInserted_;
    const_iterator lastInserted_;
};

et elle pourrait être utilisée sous une forme proche de

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 main()
{
    MyContainer<int> obj;
    obj.insert(1);
    std::cout<<"first :"<<*(obj.firstInserted())
             <<" last :"<<*(obj.lastInserted())<<std::endl;
 
    obj.insert(2);
    obj.insert(3);
    std::cout<<"first :"<<*(obj.firstInserted())
             <<" last :"<<*(obj.lastInserted())<<std::endl;
    std::cout<<"all :"<<std::endl;
    size_t count =1;
    for(auto const & it : obj){
        std::cout<<count<<" : "<<it<<std::endl;
        ++count;
    }
    return 0;
}

[EDIT]Je me suis gouru de bouton, je voulais prévisualiser ma réponse.

Si tu veux aussi pouvoir gérer la suppression d'éléments, il va falloir un tout petit peu plus de réflexion.

On ne peut en effet pas se contenter de maintenir le premier et le dernier élément rajouté, tout simplement parce qu'on ne peut absolument pas faire la moindre présomption sur l'ordre dans lequel les éléments seront supprimés.

A chaque fois que l'utilisateur décidera de supprimer un élément, il risque de supprimer soit le premier élément qui a été ajouté, soit le dernier, soit... n'importe quel élément se trouvant entre les deux (dans l'ordre d'insertion, s'entend).

Nous devons donc trouver le moyen de garder une trace de l'ordre dans lequel les différents éléments ont été rajoutés. Et vu qu'il faut que l'accès au premier et au dernier élément se fasse en temps constant, la collection qui nous permettra de le faire est toute trouvée : il nous faut une liste doublement chainée (note qu'une liste simplement chainée pourrait sans doute également suffire ). Ca tombe bien, le standard nous en propose une avec la classe template deque!

L'idée est alors que, pour chaque élément ajouté, nous allons ajouter l'itérateur vers l'élément rajouté à la fin d'une liste doublement chainée et que, chaque fois que nous voudrons retirer un élément, nous veillerons à le supprimer aussi bien de la liste que du set.

Cela pourrait prendre la forme de

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
template <typename T>
class MyContainer{
public:
    using const_iterator = typename std::set<T>::const_iterator;
    MyContainer(){}
    void insert(T const & t){
        auto it = datas_.insert(t);
       /* si l'insertion réussi */
        if( it.second){
            /* on rajoute l'itérateur à la liste */
            inserted_.push_back(it.first);
        }
    }
    const_iterator firstInserted()const{return *(inserted_.begin());}
    const_iterator lastInserted() const{return *(inserted_.rbegin());}
    const_iterator begin() const{return datas_.begin();}
    const_iterator end() const{return datas_.end();}
    size_t size() const{return datas_.size();}
    void erase(const_iterator item){
        /* si l'élément que l'on s'apprête à supprimer est valide
         */
        if(item!= datas_.end()){
            /* recherchons l'élément dans la liste représentant 
             * l'ordre d'insertion
             */
            auto it = inserted_.begin();
            while(*(it) != item && it!= inserted_.end())
                ++it;
            /* si on a trouvé l'élément dans la liste (cela
             * sera normalement toujours le cas, vu que l'élément
             * à supprimer est valide)
             */
            if(it != inserted_.end()){
                /* alors, on le supprime de la liste */
                inserted_.erase(it);
            }
            /* et on le supprime du set */
            datas_.erase(item);
        }
    }
private:
    std::set<T> datas_;
    std::deque<const_iterator> inserted_;
};

que nous pourrions utiliser sous la forme de

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 main()
{
    MyContainer<int> obj;
    obj.insert(1);
    std::cout<<"first :"<<*(obj.firstInserted())
             <<" last :"<<*(obj.lastInserted())<<std::endl;
 
    obj.insert(2);
    obj.insert(3);
    std::cout<<"first :"<<*(obj.firstInserted())
             <<" last :"<<*(obj.lastInserted())<<std::endl;
    std::cout<<"all :"<<std::endl;
    size_t count =1;
    for(auto const & it : obj){
        std::cout<<count<<" : "<<it<<std::endl;
        ++count;
    }
    std::cout<<"erasing "<<*(obj.firstInserted())<<std::endl;
    obj.erase(obj.firstInserted());
    std::cout<<"first :"<<*(obj.firstInserted())
             <<" last :"<<*(obj.lastInserted())<<std::endl;
    return 0;
}

En fait, je disais au début que cette solution était un peu plus compliquée. Disons qu'elle méritait un peu plus de réflexion, mais le code qui permet d'obtenir le résultat escompté n'est pas forcément plus compliqué

NOTA: la syntaxe que j'ai utilisée ici utilise les possibilités de C++11. La transformation du code pour respecter l'ancienne norme (celle d'avant 2011 ) n'est pas vraiment compliquée. Mais, si tu as un problème pour faire la transformation, tu sais où t'adresser

[Kreatore]

Ta question n'est pas très claire, que veux-tu dire par "accès aléatoire en o(log(n)) (pas forcément indiciel)" ? Quelle est la clé d'accès dans ce mode ?

Mes excuses, je précise.
Une première approche serait de retourner un élément aléatoirement de l'ensemble selon une loi uniforme approchée.
Une seconde approche serait de retourner le k ième élément inséré dans l'ensemble.
La clé d'accès n'est pas l'élément mais l'ordre dans lequel on insert les éléments dans l'ensemble. Cette clé d'accès n'existe donc pas pour l'utilisateur dans la première approche. Dans la deuxième approche, je voudrais retourner le kième insérer parmi n éléments de l'ensemble.

Un std::vector serait parfait sauf que pour supprimer un élément je suis obligé de tout décalé(comportement par défaut), au lieu de faire un swap et de supprimer le dernier, pour conserver l'ordre d'insertion.

Je ne pense pas pouvoir utiliser de clé pour faire cela car il y aurait des problèmes d'indice lors de la suppression.

Je lis ta réponse koala01

[Bousk]

std::deque ?

[Kreatore]

Le plus facile pour avoir un accès en O(log(n)) sur n'importe quel élément, c'est sans doute d'utiliser la classe std::set, à moins que tu ne veuilles pas de l'unicité des éléments (ce n'est pas un AVL, mais un Red Black Tree, ce qui revient grosso modo au même ).

Je pense en effet que mon approche du problème n'est forcément la bonne. Simplifions le problème en disant que l'accès au plus ancien et au plus récent est contenu dans l'accès indiciel en log(n). Un std::set ou std::map utilise l'ordre sur l'élément ou la clé. Mais je ne comprends pas comment on peut l'utiliser dans ce cas-ci.

Si je veux une méthode my_set.get(i) par exemple avec n éléments, la méthode find de set ou map prend seulement en compte une recherche qui appartient d'une façon ou d'une autre à mon arbre(soit l'objet soit la clé).

Or avec l'ordre d'insertion, je ne peux pas utiliser de clé et je ne peux donc pas utiliser find().
J'ai de fait deux questions :
- pensez-vous qu'il existe une formule permettant de trouver le parcourt exacte dans un AVL pour atteindre l'élément i sachant qu'on insert toujours par la droite ?
- sinon, si en plus de la balance, je rajoute et maintient sur chaque noeud de l'AVL le nombre de fils gauche et droit, ce soit faisable ?

Peut-être existe-t-il un type de ce genre déjà implémenté ?

[Kreatore]

std::deque ?

For operations that involve frequent insertion or removals of elements at positions other than the beginning or the end, deques perform worse and have less consistent iterators and references than lists and forward lists.

Je cherche à pouvoir supprimer un élément à n'importe quelle position.

[Bousk]

Pourrais-tu te mettre d'accord avec ton besoin ?
D'abord,

Je cherche à utiliser un ensemble ordonné sur l'insertion des éléments qui possède trois types d'accès :
- accès sur le plus ancien en o(1)
- accès sur le plus récent en o(1)
- accès aléatoire en o(log(n)) (pas forcément indiciel)

Maintenant,

Je cherche à pouvoir supprimer un élément à n'importe quelle position.

Et après ?

Si tu recherches la collection magique, je crains que tu ne trouves pas.

[jblecanard]

Diable, ce que tu veux est plus difficile que prévu ! Bousk n'a pas tort, es-tu sûr de ne pas en vouloir trop ? Le fait que tu veuilles un accès en O(log(n)) me suggère que non car les collections qui supportent la recherche par indices sont bien meilleurs que O(log(n)). Tu es donc prêt à sacrifier de la perf d'accès pour pouvoir supprimer proprement.

- pensez-vous qu'il existe une formule permettant de trouver le parcourt exacte dans un AVL pour atteindre l'élément i sachant qu'on insert toujours par la droite ?
- sinon, si en plus de la balance, je rajoute et maintient sur chaque noeud de l'AVL le nombre de fils gauche et droit, ce soit faisable ?

Il semble en effet que ce soit faisable. Par contre, ça va te faire beaucoup de boulot pour avoir quelque chose de fiable, il te faudra écrire de bon tests. Ca serait mieux d'exploiter la STL mais là je vois pas trop comment.

[Kreatore]

jblecanard, oui je suis prêt à sacrifier de la performance, surtout que log(n) reste plutôt bon

Le lien que tu m'as donné à l'air intéressé, je vais suivre cette piste même si la STL reste puissante et fiable, je ne trouve pas comment l'utiliser.

[Kalith]

Je n'ai pas regardé la complexité des opérations en détail, mais tu peux aussi regarder du côté de cet article qui décrit une alternative à std::set. En remplaçant std::vector par std::list dans l'implémentation, peut être que tu peux arriver à quelque chose qui se rapproche de ce que tu veux ?

[Kreatore]

Bonjour !

Le problème de la liste c'est l'accès aléatoire et le problème du vector c'est la suppression(puisque je veux conserver l'ordre). La complexité est importante pour la solution que je veux mettre en place. Je vais essayer de rassembler les besoins de cette collection (qui peut-être existe ) :
- Les éléments sont triés dans l'ordre d'insertion
- La différence entre o(n) et o(logn) est importante pour cette collection.
- L'accès aléatoire est critique.
- Insertion et suppression sont aussi importante l'une que l'autre.

Maintenant la piste que j'implémente :
- AVL
- Ajout du nombre de fils gauche représentant alors directement l'indice du noeud

Du coup pour un accès aléatoire il suffit si on va à gauche de prendre ce nombre et si on va à droite d'ajouter le nombre de nœuds laisser à gauche.

Bref. Je sais pas si c'est très compréhensible. Le seul problème c'est que la taille de la collection est limitée avec cette méthode. Mais bon on avoisine sur 32 bits les quelques milliards et même presque le double ou plus ? Si un matheux à la réponse

Sinon j'aimerais bien voir une implémentation simple d'AVL avec la gestion de la balance, si vous connaissez une source libre. J'ai réussi à faire les rotations et à rééquilibrer mais je n'ai aucune idée pour faire cela de façon propre ni pour la suppression...