Discussion :

[tom42]

Bonjour,
je cherche à décaler tous les éléments d'une liste, de n pas vers la droite mais je n'ai trouvé que l'algo naîf (j'ai honte d'être aussi nul )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
decalage(liste,m) :
debut
|   pour i de 0 à m faire
|   |   pour j 0 à card(liste) de  faire
|   |   |   si j = card(liste)-1 faire 
|   |   |   |   liste[0] <- liste[card(liste)-1]
|   |   |   sinon 
|   |   |   |   liste[j+1] <- liste[j]
|   |   |   fin si
|   |   fin pour
|   fin pour
fin

Voila, donc si n est le cardinal de liste, j'aimerais faire un peu mieux que O(m*n)
Merci d'avance.

[tom42]

Oups, je viens de m'apperçevoir que cet algo ne fonctionne pas du tout.
Je vais donc revoir mes prétentions à la baisse, je suis preneur même en O(nm) .

[souviron34]

c'est un tableau, par construction ?

Parce que sinon tu aurais vraisemblablement intérêt justement à utiliser une liste....

[tom42]

Oui c'est un tableau mais pour moi une liste et un tableau c'est le même combat dans ce cas là non?
J'ai quand même trouver un algo en n*m mais j'aimerais vraiment faire mieux parce qu'avec 1 millon d'éléments c'est un peu long

[souviron34]

Oui c'est un tableau mais pour moi une liste et un tableau c'est le même combat dans ce cas là non?

Non pas du tout....

• Avec un tableau, le seul autre moyen (qui peut être très rapide), c'est un déplacement mémoire direct (je ne sais pas avec quel langage tu programmes, mais ça se fait sans doute dans tous. En C c'est avec la fonction memmove ) :
  
  
  • stocker l'adresse de l'élément du tableau qu'on supprime
  • déplacer d'un coup le bloc mémoire partant de l'élément suivant jusqu'à la fin à cette adresse
  
  
  
  
• Sinon, si c'est avec une liste :
  
  
  • un element d'une liste est constitué des données, et d'un pointeur vers l'élément suivant et sur l'élément précédent
    
  • donc pour supprimer, il suffit d'ajuster le suivant du précédent et le précédent du suivant (et de libérer ce qui doit l'être de l'élément supprimé).
  
  

[souviron34]

j'avais pas complètement lu. Tu veux décaler vers la droite, c'est à dire insérer.

La même technique que ci-dessus :

avec un tableau, déplacement mémoire de m places (1 opération, mais gros mouvement de mémoire, donc possibilité crash (ça dépend si tu as déjà reservé la mémoire) ou lenteur éventuelle), mas certainement plus rapide que le décalage manuel.

avec une liste : insertion de m éléments, avec ajustement des précédents et suivant à chaque fois (3*m opérations).

[Jean-Marc.Bourguet]

Oui c'est un tableau mais pour moi une liste et un tableau c'est le même combat dans ce cas là non?
J'ai quand même trouver un algo en n*m mais j'aimerais vraiment faire mieux parce qu'avec 1 millon d'éléments c'est un peu long

Plutot que m blocs de 1 element, imagine que tu as a deplacer 1 bloc de m elements...

[tom42]

Merci pour vos réponses. Ca me revient maintenant (désolé mais mes cours d'algo sont loin dériére moi.. )

Cela dit, j'implémente cela avec actionscript de flash alors pour ce qui est des memcpy et des allocations de mémoire, je peux oublier.
Ma structure de donnée est forcemment une table et je ne peux accéder qu'à un un élément à la fois.
Est-ce donc mort pour améliorer la complexité?