Permuter 2 variables

Bonjour,

Je voulais vous poser une question concernant les variables et la permutation de celles-ci. En effet, je débute dans la programmation et je me suis lancé dans l'apprentissage de Python depuis environ 2 mois et j'essaie de progresser de la meilleure façon que possible

Aujourd'hui je poste donc car j'ai une question qui peut paraitre idiote pour certains d'entre vous mais il me faut une réponse

En Python je sais comment ce passe la permutation de deux variables (a, b = b, a) mais en algo et autre langage de prog' il faut utiliser une troisième variable et c'est là que je me posai la question :

dans quelle 'limite' une variable change (désolé je ne sais pas comment formuler cette question) ? ; c'est à dire que

a = 3 b = 5 c = a

a = b b = c

et là, moi je pensais qu'en réaffectant la variable a, la valeur de c changerai, en cooccurrence elle deviendrait celle de b.

(désolé je suis crevé, j'ai du mal à formuler mes questions ^^)

Pouvez-vous m'expliquer comment ça fonctionne en fait ?

Merci

a = 3 , a vaut 3

b = 5 , b vaut 5

c = a , c vaut 3 puisque a vaut 3

a = b , a vaut 5 puisque b vaut 5

b = c , b vaut 3 puisque c vaut 3

Ce sont 3 cases mémoire différente. Le signe '=' fait une affectation, soit une recopie de la valeur, une seule fois, rien de plus.

En python, c'est un poil particulier : tu as deux types d'objets : les objets mutables (les listes, dictionnaires, …), et les objets immutables. Et contrairement à la plupart des langages compilés, une variables en python n'est qu'une étiquette collée sur un objet, et ne représente pas son espace mémoire.

Le concept est pas trop mal expliqué par S&M ici ( Attention, la page d’accueil du blog est NSFW).

Pour ton exemple

1
2
3
4
5

a = 3
b = 4
c = 5
a = b
b = c

Tu te retrouve avec a = 4, b = 5 et c = 5. Comme les entiers sont des immutables, de nouveaux objets sont créés à chaque fois.

En faisant

1
2
3
4
5

a = [1, 1, 1]
b = [2, 2, 2]
c = [3, 3, 3]
a = b
b = c

Tu as toujours a = [2, 2, 2], b = [3, 3, 3] et c = [3, 3, 3]. Par contre si après ça tu fait

1
2
3
4

print(c) # [3, 3, 3]
c[0] = 56
print(c) # [56, 3, 3]
print(b) # [56, 3, 3]

là tu as modifié b.

Je comprends mieux

merci pour vos explications

Salut,

mais en algo et autre langage de prog' il faut utiliser une troisième variable

Ça dépend, si on travaille sur des objets munis de deux opérateurs $+$ et $-$ réciproques, une permutation de a et de b peut se coder tout simplement :

1
2
3

a = a+b
b = a-b
a = a-b

Joli celle là @dri1, je connaissais pas cette tournure et elle est assez élégante

Et il me semble qu'il existe toujours une solution pour permuter circulairement en place pour un nombre quelconque de variables. J'avais lu un article dans Pour la science, et j'ai trouvé un gentil monsieur qui a eu la bonne idée de le scanner et le laisser trouver par le robot de Google : l'article en question.

J'aime bien aussi mais en pratique une variable supplémentaire est préférable, dans un langage tel que le C le dépassement de représentation de la valeur est si vite arrivée.

Le problème de dépassement se contourne facilement, en fait. Avec deux valeurs de même signe proches des extrêmes, cette version fonctionnera sans problème :

1
2
3

a = a-b
b = a+b
a = b-a

Mais bon, une troisième variable reste pratique dans plein de cas, c'est plus pour le côté un peu élégant de la chose (le seul cas utile, c'est éventuellement sur des gros objets dont la copie en mémoire pourrait être problématique).

Pour éviter tout dépassement, il reste la solution d'utiliser un xor (^) à la place de l'addition/soustraction, mais ça reste amha moins lisible qu'une variable temporaire.

Disons qu'à part pour l'élégance de la solution, dans un vrai programme il est préférable de passer par une variable intermédiaire pour des raisons de simplicité, à moins que le langage n'offre la permutation des éléments comme en Python.

Ça dépend ce qu'on appelle simplicité. Je trouve ça beaucoup plus simple de faire une permutation sur les deux variables considérées directement. On évite un intermédiaire, c'est plus simple dans ce sens. Après on fait plus de calculs dans certains cas.

Et sinon, pour ma culture, y a d'autres langages que le Python qui proposent ce genre de mécanismes ?

Je trouve ça beaucoup plus simple de faire une permutation sur les deux variables considérées directement. On évite un intermédiaire, c'est plus simple dans ce sens. Après on fait plus de calculs dans certains cas.

Si je mets la solution de @drien ou à base de XOR pour permuter deux variables dans un programme sans mettre de commentaires, les gens ne vont pas identifier le rôle de ces instructions. La solution avec une variable intermédiaire est connue de tout programmeur et est donc identifié immédiatement comme tel.

Cette remarque n'est valable que dans les langages n'ayant pas d'opérateurs similaires à celui de Python qui est à privilégier quand c'est disponible.

Je vois pas le rapport entre simplicité et compréhension du code ? Tu parles de la facilité de lecture alors ?

C'est plus simple à comprendre, à identifier son rôle dans un tas de code, etc. Le terme simple ne se réduit pas à "ce qui a le moins d'éléments en jeu".

Si en Python on préconise la permutation via l'affectation multiple aussi bien pour des questions de performance que de style, pourquoi ne pas en faire autant avec le XOR en C ? Ce n'est qu'une question d'habitude finalement.

Je dirais que c'est parce que l'affectation multiple fait partie de Python, tout dév Python sérieux est censé savoir que ça existe. Et de fait, voir un truc comme a, b = b, a ça n'a rien de choquant et c'est parfaitement explicite et compréhensible au premier coup d'oeil. C'est idiomatique du langage donc c'est la solution retenue.

Par contre si en C on voit ça : a ^= (b ^= (a ^= b)), c'est incompréhensible sans commentaire, y a pas que l'habitude qui rentre en jeu pour moi. Même si tout dév C sérieux est censé connaitre les opérateurs bit à bit, la ligne ci-dessus n'a rien d'explicite en elle-même. Après on peut dire que les one-liners chelous sont idiomatiques, à voir

Si tu parles bien de l'affectation multiple, c'est possible dans pas mal de langages : Lua, Perl, Go, OCaml, et sûrement pas mal d'autres.

Pourquoi pas ?

Mais si on oubli le one-liner et que l'on pose ça simplement :

1
2
3
4
5
6
7
8
9

// Permutation classique :
c = a;
a = b;
b = c;

// Permutation optimale :
a ^= b;
b ^= a;
a ^= b;

Celui qui lit ça pour la première fois va devoir décortiquer rapidement ces trois dernières lignes pour comprendre ce qu'elles font, mais les fois suivantes ce sera acquis et parfaitement logique, non ? Que peut-on faire d'autre d'utile avec seulement 2 variables et 3 XOR ?

Le commentaire "permutation optimale" m'a fait me poser la question de si c'était bien le cas (vu tout ce que savent faire nos compilateurs aujourd'hui) et visiblement, la réponse est non, dans certains cas en tout cas : http://stackoverflow.com/a/36910

Du coup je pense réellement qu'il y a plus d'inconvénients que d'avantages à utiliser ça : c'est plus chiant pour un lecteur qui bloquera là-dessus (au moins la première fois, et une fois c'est déjà trop si y a pas de gain réel), et c'est plus chiant pour certains compilateurs qui ne sauront pas transformer la permutation en op assembly pour swapper, si disponible… Ça + le :

On modern CPU architectures, the XOR technique is considerably slower than using a temporary variable to do swapping. One reason is that modern CPUs strive to execute instructions in parallel via instruction pipelines. In the XOR technique, the inputs to each operation depend on the results of the previous operation, so they must be executed in strictly sequential order. If efficiency is of tremendous concern, it is advised to test the speeds of both the XOR technique and temporary variable swapping on the target architecture.

sur Wikipedia.

L'explication présente sur le wikipédia est totalement fausse. Seuls les anciens CPU (single Issue ou sans renommage de registres avec Physical Register File) exécutent réellement les MOV en parallèle.

La vraie raison est tout simplement que la permutation s'effectue directement dans l'unité de renommage de registre, sans copier/déplacer physiquement les données : cela prend un seul cycle sur un CPU multiple Issue avec un Physical Registre File. Du moins, si on code la permutation avec des instructions MOV ou XCHG (de préférence XCHG, merci).