Permuter deux variables sans en utiliser une troisième

Le contenu de ce billet ne me pose aucun soucis, mais il serait peut-être utile de préciser que ces deux méthodes "sans variables temporaires" sont toutes les deux plus lentes et moins lisibles que la méthode de départ, et qu’elles sont surtout là pour la culture ou pour faire des énigmes, qu’on ne conseille pas de les utiliser en pratique.

Existe-t-il des langages (utilisé !) sans XOR ? C’est une instruction processeur, ça m’étonne qu’une langage ne la propose pas de base.

Haskell peut-être ?

Est-il possible de modifier l’algorithme 1 pour éviter le bug ? Je pense que oui, en utilisant $a - b$ ou $b - a$.

Moi ma question, c’est à quoi ça sert de permuter 2 variables ? Ça vous arrive souvent d’en avoir besoin ?

En vrai, non. C’est pas un besoin que je rencontre couramment. Sauf pour implémenter la suite de Fibonacci en entretien d’embauche, mais ça fait des années qu’on ne m’a pas demandé ce genre de choses…

La première et la quatrième colonnes sont égales.

Dans le tableau du billet, non. Mais elles devraient, en effet.

Merci pour vos retours.

Plus lente, je ne suis pas sur pour la méthodes avec les XOR (C++ implémente celle avec variable temporaires donc je suppose que tu as raison sur ce point). Mais elle gagne surement en consommation mémoire ce qui peut etre intérressant pour un micro-système. Pour la lisibilité, on est bien d’accord.

Ce billet n’a à mon sens qu’un interet théorique, et je ne saurais parler de ce qu’il se fait en pratique, que je ne connais pas suffisamment.

C’est pas mal utilisé dans des algorithmes de tri par comparaison.

Oups! Oui c’est corrigé, merci.

(La correction sur un billet l’enlève de la première page apparement (C’est compréhensible))

C’est un besoin relativement courant par exemple pour trier un tableau.

En tout cas, suffisamment courant pour avoir une instruction processeur dédiée (XCHG) ou que C++ implémente une fonction standard pour le faire de manière performante. (std::swap)

Si on veut échanger des valeurs dans un tableau stocké en mémoire, on veut vraiment éviter les versions sans temporaire qui vont faire plus de lecture et écriture dans le tableau que nécessaire, là où un registre temporaire va coûter très peu cher. (Les segments du tableau autour de ces deux indices sont dans le cache, mais il faut consulter le cache, y propager les écritures, etc.)

Mais [la méthode avec des XOR] gagne sûrement en consommation mémoire ce qui peut être intéressant pour un micro-système.

Bof, d’une part la différence est minime, d’autre part la méthode avec des XOR a un code plus compliqué, donc tu risques de perdre en taille de code ce que tu gagnes en taille de pile.

La différence la plus sensible dans la vraie vie c’est que si on utilise une de ces méthodes, on écrit du code trop compliqué et nos collaborateurs ont envie de se venger.

A noter que la méthode "a + b" peut poser des soucis d’overflow aussi dans certains langages:

Billet sympa, j’ignorais ces méthodes pour éviter les variables temporaires.
Est-ce que la solution la plus optimale de ce problème devra se construire en assembleur ?

Tout dépend ce que tu appelles « optimal ».

Si c’est la lecture/facilité de compréhension, le passage par une variable temporaire est optimal. Si c’est en espace mémoire, je dirais que l’instruction processeur est optimale. Si c’est en vitesse d’exécution, je ne saurais dire qui est optimal.

Plus d’info swap (en).

Dans les années 70, je programmais en assembleur pour IBM 360.
Cette machine disposait de 16 registres pour y faire les opérations.
Dans ce contexte, la permutation par XOR était rapide et économique en ressources mémoire.
C’est une méthode générique pour permuter les contenus de deux registres sans aucune restriction, ni utiliser un troisième registre.

Ce n’est pas le cas des méthodes basées sur l’addition ou la soustraction qui ne fonctionnent pas toujours du fait des limitations de l’arithmétique en nombres entiers.

Je ne comprend pas pourquoi ont dis que la méthode basées sur l’addition ou la soustraction ne marche pas toujours.

Selon moi, c’est faux.

int a = rand(), b = rand();

if( a > b) {
  a = a - b;
  b = a + b;
  a = b - a;
} else {
  a = b - a;
  b = b - a;
  a = a + b;
}

Cette méthode semble convenir dans tous les cas pour moi, tant que a et b sont du même type bien-sûr.

Si a est positif et que b est négatif, a - b peut dépasser. Mais y a moyen de s’arranger je pense. En faisant a = a + b (correct car a positif et b négatif), puis b = a - b on a a + b dans a et a dans b, donc a = a - b permet d’obtenir le résultat. De même on adapte si b est positif et a négatif.

Ou alors pour éviter le bloc conditionnel, si a est plus grand que b, tu permutes a et b avec la méthode XOR puis tu appliques la formule des additions et soustractions !

Sinon (je sais que ça existe en python) On peut faire une manière ultra élégante : a, b = b, a Et tadam

Mais sinon c’est un manière mathématique jolie de faire (même si à pas utiliser car, comme dit plus haut, il y a quelques contraintes)

C’est évoqué en intro du billet, mais on notera tout de même que cette solution n’échappe pas à la valeur temporaire.

Quand tu écris b, a, tu crées un tuple temporaire référençant ces deux valeurs, que tu déconstruis ensuite en l’assignant aux variables a et b.

@entwanne j’ai pas réussi à retrouver l’évocation ^^' Pour la tulpe je suis partagé, car pour moi pour créer un tulpe, il aurait fallu rajouter les parenthèse (puis de toutes manières en assembleur faire une inversion aussi simplement que a<=>b prend une variable temporaire donc on fera pas mieux 😂)

C’est la virgule l’opérateur qui crée un tuple et non les parenthèses (à l’exception du tuple vide qui s’écrit ()).

>>> (1)
1
>>> (1,)
(1,)
>>> 1,
(1,)
>>> ()
()

Ça crée une variable temporaire sémantiquement en Python. Ça ne veut pas dire qu’effectivement, l’interpréteur crée une variable temporaire.

Bon bah j’aurais appris qqc 😁, merci

Un flip est un pattern tellement récurrent qu’il est effectivement optimisé via l’opcode ROT_TWO, implémenté de la façon suivante, autrement dit avec deux temporaires au lieu d’un seul. Quand on commence à regarder un langage qui fonctionne avec une VM, je ne suis pas sûr que regarder les temporaires effectivement créées ou non par l’implémentation est pertinent de toute façon. Ce n’est qu’un détail, ce qui est standardisé est que ça doit conceptuellement se comporter comme si on construisait et déconstruisait un tuple et donc qu’on utilise une construction temporaire (que ce soit un vrai objet Python ou un jeu de pointeurs pour l’émuler, on s’en fout).

Pour exemple :

>>> def flip():
...   a=1
...   b=2
...   a, b = b, a
... 
>>> import dis
>>> dis.dis(flip)
  2           0 LOAD_CONST               1 (1)
              2 STORE_FAST               0 (a)

  3           4 LOAD_CONST               2 (2)
              6 STORE_FAST               1 (b)

  4           8 LOAD_FAST                1 (b)
             10 LOAD_FAST                0 (a)
             12 ROT_TWO
             14 STORE_FAST               0 (a)
             16 STORE_FAST               1 (b)
             18 LOAD_CONST               0 (None)
             20 RETURN_VALUE

ROT_TWO ne permute pas deux variables nommées, mais elle échange les deux valeurs en haut de la pile de valeurs de la machine virtuelle Python. C’est une instruction courante parce qu’on parle d’un jeu d’instruction bytecode à pile, plutôt qu’à registre, donc il y a plein de petits opcodes pour permuter, dupliquer et effacer les valeurs sur la pile — dont celle-ci (mais aussi ROT_THREE, ROT_FOUR, DUP_TOP_TWO etc., dont on conviendra qu’elles ne sont presque jamais utilisées directement par les utilisateurs dans le programme source). On peut remarquer au passage que le consensus actuel est plutôt que les machines à registre sont plus efficaces (au détriment de la taille du code), et qu’elles n’ont pas besoin de ce genre de primitives.

L’avantage de l’écriture Python, c’est qu’elle permet de swapper à peu près n’importe quoi.

Il n’empêche que, quand cela convient, il est plus simple d’écrie trois instructions XOR en assembleur que d’exécuter plusieurs milliers d’instructions depuis Python en utilisant des tuples.