Optimiser code Complément A Deux Fermé

Question

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

quent217 · Answer

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 ^^'

gmatg · Answer

Super !! avec vos idées d'optimisation, on arrive à quelque chose de pas mal !
Merci de votre aide

gmatg · Answer

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

Phil_1857 · Answer

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)

Phil_1857 · Answer

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

Phil_1857 · Answer

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

gmatg · Answer

j'ai réussi à faire ca, et je pense que je peux enlever le booléen, quelqu'un a une idée ?

nbr2 = "11110000" [::-1]
end, first = False, ""

for i in nbr2:
  if i == "1" and not end:
    end = True
    first = "1" + first
    continue

if end and i == "0":
    first = "1" + first
  else: 
    first = "0" + first

print(first)

Optimiser code Complément A Deux

7 réponses

Discussions similaires