Optimiser code Complément A Deux

Signaler
-
 gmatg -
Salut à tous, j'ais fais un algorithme en python qui permet de faire du complément à deux sur les nombres binaires.
Avez vous une solution pour l'optimiser ?
Merci à vous

nbr = "11110000" [::-1]
end, reverse = 0, ""

for i in nbr:
  if end == 1 and "0" in i:
    j = "1"
  else:
    j = "0"

  if "1" in i and end == 0:
    end += 1
    j = i

  reverse += j
print(reverse[::-1])

6 réponses

Messages postés
419
Date d'inscription
vendredi 25 septembre 2015
Statut
Membre
Dernière intervention
20 octobre 2020
200
Bonjour,
le code me semble assez optimisé, je ne pense pas qu'il soit possible de réduire sa complexité.

Vous pouvez cependant faire certaines opérations plus rapidement, mais je ne pense pas que la différence de temps soit perceptible.

"0" in i
peut être remplacé par
i == "0"
. Un test d'égalité est plus rapide qu'une recherche dans une chaine de caractère.
j = i
peut être remplacé par
j = "1"
. Ça évite d'évaluer la valeur de i alors qu'elle a déjà été testé juste avant.
end += 1
peut être remplacé par
end = 1
. Ça évite une addition inutile.
D'ailleurs end pourrait être remplacer par un booléen et remplacer
if end == 1:
par
if end:
et
if end == 0:
par
if not end:
. Je pense que c'est légèrement plus optimisé comme ça.
Les conditions pourraient aussi sûrement être un peu réarrangées pour éviter de modifier j à la fois à la ligne et 8 et la ligne 12 lors d'une seule itération, et aussi utiliser des else pour éviter de tester 2 fois la valeur de end et i alors qu'ils n'ont que 2 valeurs possibles (donc si i vaut "1" alors il ne peut pas valoir "0", pas la peine de tester une deuxième fois).

Ça c'est ce que je vois en me basant sur votre code actuel, mais on pourrait aussi tirer parti des optimisations de python.
La première étape de l'algo revient à chercher le premier 1 dans la chaine, donc on pourrait utiliser la fonction index pour faire ça plus rapidement.
Pour changer les 1 en 0 et les 0 en 1 sur le reste de la chaine, je pense que c'est plus rapide d'utiliser un générateur que l'on met dans la fonction join plutôt que de faire une boucle et de concaténer les éléments un par un.

Mais encore une fois, c'est vraiment histoire de s'entrainer à optimiser au maximum chaque instruction, vous ne verrez probablement aucune différence ^^'
Super !! avec vos idées d'optimisation, on arrive à quelque chose de pas mal !
Merci de votre aide
Génial !! De bonne idées d'optimisation
Merci de votre aide

Du coup ca donne ca : c'est bien nan ?

nbr = "11110000" [::-1]
end, reverse = False, ""

for i in nbr:
  if end and i == "0":
    j = "1"
  else:
    j = "0"

  if "1" in i and not end:
    end = True
    j = "1"

  reverse += j
print(reverse[::-1])
Messages postés
477
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
28 octobre 2020
66
Bonjour gmatg,

Plus court :

nb, inb = '00000100', ''
#On inverse les bits
for c in (nb): inb += str(1-int(c))
#On ajoute 1 et on reconverti en binaire
c2 = bin(int(inb, 2)+1).lstrip('0b')
print(c2)
Salut, ta technique est pas mal mais je préfère la mienne, que je cherche à améliorer Si tu as des idées pour améliorer mon code, je suis preneur :)
A bientot
Messages postés
477
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
28 octobre 2020
66 > gmatg
Je pensais que tu voulait optimiser .... :-)

Mon code est optimisé puisqu'il est plus court et plus concis que le tiens, il n'a que 4 lignes
>
Messages postés
477
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
28 octobre 2020

oui je sais :--) mais j'ai envie de garder ma technique, tout en l'optimisant. Il y a pas moyen de supprimer le
else: j = "0"    
? et aussi enlever le slicing
[::-1]
?
Merci à vous pour votre aide
Messages postés
477
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
28 octobre 2020
66
je vais jeter un œil ...


enlever le slicing [::-1] : non, il n'y a pas plus court pour inverser la chaine, ou alors comme ça:
nbr = ''.join(reversed('11110000'))

mais ca ne change pas grand chose ... ou alors comme j'ai fait (ligne 3 de mon code)

Comme ça, alors:

nbr = "11110000" [::-1]
first_1, reverse = True, ''
for i in nbr:
	if(i == '0'):
		reverse += i
	else:
		if(first_1):
			first_1 = False
			reverse += i
		else:
			reverse += '0'
print(reverse[::-1])
Messages postés
477
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
28 octobre 2020
66
Bonjour Gmatg,

Erreur dans mon code précédent, c'est plutôt comme ça:

nbr = "11111100" [::-1]
c2, first_1 = '', False
for c in nbr:
	if((first_1 and c == '1') or (not first_1 and c == '0')):
		c2 += '0'
	elif((first_1 and c == '0') or (not first_1 and c == '1')):
		if(not first_1 and c == '1'): first_1 = True
		c2 += '1'
c2 = c2[::-1]
print(c2)


Evitons le nom de variable reverse, c'est déjà un mot clé de Python ...
Salut, ton code me parait pas mal, mais du coup le miens sera plus optimiser (la logique des deux codes reste très similaires). Eh du coup je ne trouve toujours pas de moyens pour optimiser mon script.
A bientôt et merci pour ton aide
Messages postés
477
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
28 octobre 2020
66 > gmatg
AH ?

Moi, je trouve que le mien est plus optimisé:

il est plus compact, 1 seul test if ... elif

plus de J='0'' ou '1', plus de variables inutiles

Il est plus lisible car il traite les 4 combinaisons possibles avec first_1 et c

Après, je ne sais pas ce que tu entends par optimisé , mais bon, tu fais bien comme tu veux ..
>
Messages postés
477
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
28 octobre 2020

Ouai ouai je vois. En tout cas, merci pour votre aide et je referme le sujet ici
Merci encore