Discussion :

[istdasklar]

Bonjour..... Je voudrait parcourir une list via un iterateur , mais aléatoirement.

En effet, le fait que tout soit linéaire, les premiers elements sont calculer avant les derniers. Et pour ce que je fais ca pose probleme. On pourait faire par exemple, un parcours avec comme point de depart un point aléatoire, et a la fin, on parcours le debut.....

Vous avez des idées?

[koala01]

Salut,

Ainsi que je te l'expliquais dans l'autre sujet, la liste n'a, malheureusement, pas vocation à fournir un acces aléatoire...

Par contre, comme tout conteneur, elle dispose de sa taille, et, de ce fait, tu peux toujours envisager un choix aléatoire de l'élément dont la position est de l'ordre de 0(==liste.begin() ) <= N < size()

Comme la liste est une liste doublement chainée (tu peux la parcourrir vers l'avant comme vers l'arrière), tant que tu maintiens une valeur qui indiquerait la position de l'itérateur actuel dans la liste, tu pourras sur base de cette valeur et de la position choisie aléatoirement, décider d'avancer ou de reculer jusqu'à l'élément correspondant, voire, si l'élément sélectionné aléatoirement est de l'ordre de 0<= N <= position actuelle/2 (ou de position actuelle *2<= N<=size()-1 ), décider de recommencer carrément au début... Mais le gain de temps ne sera pas *forcément* important (tout dépendant, évidemment, du nombres d'itérations )

Cependant, il faut bien être conscient du fait que ce parcours se fera de manière tout à fait séquentiellle: reculer de 5 positions, cela signifie faire actuel -1, actuel -1, actuel -1, actuel -1, actuel -1

Et comme tu envisages quand meme de créer une liste de 100.000 éléments, cela risque de tres rapidement commencer à prendre... un temps certain...

Ce type d'acces sera plutot dévolu à la classe vector... Mais la classe vector sera plus lente dans une forte mesure au niveau de l'ajout ou du retrait d'éléments...

Du coup, il serait *peut etre* intéressant, si, à un moment donné, tu dois effectuer beaucoups d'acces aléatoires sur une liste figée (sur le moment du moins) d'envisager de "copier" l'ensemble des itérateurs sur la liste dans un tableau dont la taille est connue à l'avance (ben oui, on connait liste.size()) et de faire ces acces aléatoires sur ce tableau...

Par exemple:

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
 
/* fonction qui permet de fournir un acces aléatoire à une liste figée au
   moment de l'appel
   @in: la liste à parcourrir aléatoirement
 */
void LaFonction(std::list<letype> & laliste)
{
    std::vector<std::list<letype>::iterator> tab;//le tableau
    tab.resize(laliste.size());//on redimentionne le tableau à la taille connue
    //la boucle qui remplit le tableau
    for(std::list<letype>::iterator it=laliste.begin();it!=laliste.end();it++)
    {
        tab.insert(it);
    }
    //toute la gestion "aléatoire"
}

Il faut cependant attirer ton attention sur deux limitations de la manière de travailler:

• Le remplicage du tableau prendra d'autant plus de temps que la liste contiendra de nombreux éléments
• Tu peux appeler les différentes méthodes des itérateurs, mais tu ne dois en aucun cas décider de supprimer l'un de ces éléments

Du coup, il faudra veiller à ce que le temps de remplicage du tableau soit "rentabilisé" par le nombre d'acces aléatoires

[alskaar]

Si j etais toi je ferais une iteration de la chaine pour affecter une valeur random a tes objets, puis un tri de ta liste en fonction de la valeur random.

tu peux aussi recup une valeur random a la construction de l'objet et toujours le tri apres.

[koala01]

Si j etais toi je ferais une iteration de la chaine pour affecter une valeur random a tes objets, puis un tri de ta liste en fonction de la valeur random.

tu peux aussi recup une valeur random a la construction de l'objet et toujours le tri apres.

En fait, si l'on met ce sujet en rapport avec un autre du demandeur, on se rend compte qu'il se dirige vers une liste d'etres vivants qui vivent, se dupliquent et meurent, dont la limite haute tourne aux allentours de 100.000 individus... mais en partant d'un seul et unique individu

Du coup, il devient difficile, d'envisager de modifier une valeur aléatoirement pour l'ensemble des individus, et le parcours des individus, pour ne modifier qu'une valeur sur certains d'eux à peine, risque de prendre sensiblment plus de temps sur une liste que sur un tableau...

C'est la raison pour laquelle je propose cette solution, en attirant quand meme l'attention sur ses limites

[loufoque]

Bonjour..... Je voudrait parcourir une list via un iterateur , mais aléatoirement.

Alors change de conteneur, parce que faire ça avec std::list c'est pas très malin.

[HanLee]

En fait, là pour moi tu devrais prendre std::vector.

D'après ce que je vois, t'as besoin :
- de rajouter des éléments à la fin du conteneur (OK)
- d'accéder aléatoirement aux éléments du conteneur (OK)
- de supprimer un élément au milieu (voir justification)

Si je considère que tu ne remplis pas ton tableau (mais avec un tableau temporaire) pendant que tu le parcours, alors, tu n'as qu'à échanger l'élément à supprimer avec le dernier, puis faire un pop_back(), pour supprimer un élément.

Par contre après quand tu dois ajouter les éléments du tableau temporaire au tableau initial, on peut plus faire de splice(). (c'est le prix à payer)

Sinon, pour accéder aux éléments aléatoirement, tu n'as qu'à stocker un tableau d'indices, et en construire une permutation avec std::random_shuffle() (voir <algorithm>).

[loufoque]

Après sinon tu peux créer ta propre structure de données qui arrive à combiner l'accès aléatoire et l'effacement en O(1).
Un truc à base de table de hachage le permet peut-être plus ou moins.