Discussion :

[coyotte507]

Salut,

j'ai deux questions sur l'opérateur "décalages de bits".

Je sais qu'on peut l'utiliser sur un entier unique, mais est-ce que l'on pourrait l'utiliser carrément sur une zone mémoire pour par exemple décaler les cases d'un tableau?

Sinon, si c'est possible, de quelle facon augmente le temps pris par cette action? Est-ce de l'ordre de n, log(n)...? Par exemple, dans la vie réelle, si j'ai un jeu de cartes, quand je met une carte au milieu (et que je décale les autres cartes donc), ca ne dépend du nombre de cartes que très faiblement.

Merci de vos réponses

[droggo]

Dio,

Par exemple, dans la vie réelle, si j'ai un jeu de cartes, quand je met une carte au milieu (et que je décale les autres cartes donc), ca ne dépend du nombre de cartes que très faiblement.

Mais imagine que les cartes soient disposées dans une série de cases, ce qui t'obligerait à en décaler la moitié avant d'en insérer une.
Penses-tu qu'il en serait de même ?

[coyotte507]

Si je prend par exemple les 7 lettres de scrabble côte à côte, il me suffit de pousser celle du milieu vers la gauche (ca décalera les autres en même temps) et d'en mettre une autre au milieu.

Ta réponse veut dire que ca prend un temps linéaire?

[DavidDeharbe]

L'opérateur << ou >> ne fonctionne pas sur des positions arbitraires en mémoire. Tu ne peux donc pas décaler un ensemble de valeurs en temps constant (du moins sur les architectures classiques).

Une insertion dans un tableau demande de décaler, dans le pire des cas, tous les éléments du tableau. Chaque décalage a un coût constant, donc c'est linéaire. Il est également parfois nécessaire de ré-allouer un nouveau bloc de mémoire plus grand si l'insertion provoque une augmentation du tableau à une taille supérieure à celle allouée. En ce cas, il est de plus nécessaire de copier le contenu entier du tableau de l'ancien bloc vers le nouveau bloc et de libérer la mémoire occupée par l'ancien bloc.

Une structure de données linéaire permettant de faire des insertions en temps constant est la liste chaînée.

David.
--

[coyotte507]

D'accord merci. Ca me servirait donc à rien de savoir comment décaler un bloc de plus de 32 bits.