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é).
  
  

[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...

[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]

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

Je me demande s'il ne veut pas un decalage circulaire.

[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é?

[pseudocode]

And now... Ladies and Gentlemen, the big shift in o(n) !

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
/**
 * @param arr le tableau a decaler
 * @param n la longueur du tableau
 * @param r le nombre de decalage a droite
 */
void shift(int[] arr, int n, int r) {
 
	// pour le cas ou r > n
	r=r%n;
	if (r<=0) return;
 
	// creation du tableau "tampon"
	int[] backlog = new int[r];
 
	// remplissage initial du tampon
	for(int i=0;i<r;i++)
		backlog[i]=arr[i];
 
	// boucle d'echanges tableau/tampon
	for(int i=r;i<n+r;i+=r) {
		for(int j=0;j<r;j++) {
			int tmp=arr[(i+j)%n];
			arr[(i+j)%n]=backlog[j];
			backlog[j]=tmp;
		}
	}
}

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

En fait, tu déplaces n/m blocs de m elements !

[souviron34]

ben à ce compte là il y a encore plus simple : (en O(n-pos))


n = taille actuelle du tableau
pos = emplacement où insérer
m = nombre d'éléments à insérer

pour i = (n+m) jusquà i = (pos+m) par incrément de -1, faire

table[i] = table[i-m]

@pseudocode : tu te compliques la vie

[tom42]

En fait je ne voulais pas inserer d'élément mais tous les décaler vers la droite de r.
Je viens d'implémenter l'algo "shift" et ça va plus vite.

Voila merci à tous pour vos réponses

[souviron34]

as you wish...

[pseudocode]

ben à ce compte là il y a encore plus simple : (en O(n-pos))

n = taille actuelle du tableau
pos = emplacement où insérer
m = nombre d'éléments à insérer

pour i = (n+m) jusquà i = (pos+m) par incrément de -1, faire

table[i] = table[i-m]

Hum... ca fait un shift circulaire ca ?

Je viens d'implémenter l'algo "shift" et ça va plus vite.

Je l'ai appelé "shift" comme ca. Ce n'est pas un algo "officiel" standard et reconnu.... juste le résultat de mes 30 secondes de reflexion....

[souviron34]

Hum... ca fait un shift circulaire ca ?

le PO n'a pas parlé d'un shift circulaire du tout, mais de décaler les éléments vers la droite....

[pseudocode]

le PO n'a pas parlé d'un shift circulaire du tout, mais de décaler les éléments vers la droite....

Ah bah, bien sur, si tu fais confiance au posteurs... Comme si les gens savaient ce qu'ils veulent, et qu'ils l'exprimaient clairement.

Heureusement, cette fois ci il y avait du pseudocode () ce qui m'a permis de déchiffrer la veritable question.

si j = card(liste)-1 faire
liste[0] <- liste[card(liste)-1]
sinon
liste[j+1] <- liste[j]
fin si

[tom42]

Pardon souviron34 si je me suis mal exprimé mais c'est bien un "shift circulaire" que je voulais faire.
En tout cas meci et félicitation pour la performance de ce forum.

[pseudocode]

@pseudocode : tu te compliques la vie

Tu ais completement raison. Il y a plus simple, avec juste un décalage.

Il suffit de faire un décalage a droite dans le tableau, en ayant auparavant sauvegardées les valeurs qui vont etre écrasées. Puis de remettre ces valeurs a gauche. exemple avec un décalage de 2 a droite:

Tableau initial
[1|2|3|4|5|6|7|8|9]

On sauve les 2 elements de droite
[1|2|3|4|5|6|7|8|9] ___tmp=[8|9]

On décale les elements du tableau
[ | |1|2|3|4|5|6|7] ___tmp=[8|9]

On recopie les valeurs sauvées a gauche
[8|9|1|2|3|4|5|6|7]

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
 
/**
 * @param arr le tableau a decaler
 * @param n la longueur du tableau
 * @param r le nombre de decalage a droite
 */
private void shift(int[] arr, int n, int r) {
	// cas ou R > N
	r=r%n;
	if (r<=0) return;
 
	// sauvegarde des valeurs qui vont etre écrasées par le décalage
	int[] backlog = new int[r];
	for(int i=0;i<r;i++) backlog[i]=arr[n-r+i];
 
	// decalage des elements du tableau a droite 
	for(int i=n-1;i>=r;i--) arr[i]=arr[i-r];
 
	// recopie des valeurs sauvegardées
	for(int i=0;i<r;i++) arr[i]=backlog[i];
}

[souviron34]

[souviron34]

Et on peut aussi se passer du tampon :

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
 
/**
 * @param arr le tableau a decaler
 * @param n la longueur du tableau
 * @param r le nombre de decalage a droite
 */
private void shift(int[] arr, int n, int r) {
int i, j ;
int tmp ;
int tmp1 ;
 
       // cas ou R > N
       r=r%n;
       if (r<=0) return;
 
	// decalage des elements du tableau a droite 
	for( i=0 ; i < r ; i++ )
	  {
	    j = i + r ;
	    tmp1 = arr[i] ;
 
	    while ( j < n )
	      {
		tmp = arr[j] ;
		arr|j] = tmp1 ;
	        tmp1 = tmp ;
 
		j = j + r ;
	      }
 
	    if ( j >= n )
	      {
		j = j % n ;
		arr[j] = tmp1 ;
	      }
          }
}