Partage
  • Partager sur Facebook
  • Partager sur Twitter

Optimisation algo

Sujet résolu
    18 décembre 2021 à 18:40:59

    Bonjour,

    J'ai réé un algorithme permettant de compter sur n'importe quel base (avec n'importe quels caractères). 

    Cependant je n'en suis pas entièrement satisfait, je le trouve mal optimiser.

    J’attends donc simplement vos retours sur celui-ci, des propositions d'amélioration etc...

    Comportement:

    Le code:

    def compter(pas: int, char: list) -> list:
    	"""
    	Fonction récursive qui compte à partir 
    	d'un nombre de pas demander et d'une chaine de caractère
    	"""
    
    	#le résultat sera stoker dans cette liste
    	result = list()
    
    	#condition d'arrêt de la fonction récursive
    	if pas < len(char):
    		
    		for i in range(pas+1):
    			result.append(str(char[i]))
    	else:
    		# la récursivité commence ici:
    		#donc si le nombre de pas à effectuer est supérieur aux nombres de caractères,
    		#On ajoute récursivement les nombres
    		result.append(compter(pas-1, char))
    		result.append(str(compter(pas//len(char), char)[-1]) + str(char[pas%len(char)]))
    
    		# Pour avoir une liste propre
    		# sans ça, ça donnerait ça:
    		# >>> compter(2, [0,1])
    		# [['0', '1'], '10']
    		
    		result = result[0] + [result[1]]
    
    	return result

    Merci d'avance !:D

    • Partager sur Facebook
    • Partager sur Twitter
      18 décembre 2021 à 18:48:04

      Bonjour,

      Peux tu être plus clair sur le terme "compter" ?

      • Partager sur Facebook
      • Partager sur Twitter

      Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
      La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)

        18 décembre 2021 à 18:58:11

        En fait, par compter j'entends incrémenté 1 n fois dans une base donné.

         Ex:

        compter(3, [0,1])

        3 -> nombre d'itération

        [0,1] -> les caractères utilisé, ici une base binaire

        résultat: ["0","1","10","11"]

        compter(6, [i for i in range(10)])

        6 itération sur base décimale: ["0","1","2","3","4","5","6"]

        Je sais pas si c'est très clair, je galère pour expliquer:euh:

        • Partager sur Facebook
        • Partager sur Twitter
          18 décembre 2021 à 19:40:38

          Une mouture non récursive devrait être plus rapide.
          • Partager sur Facebook
          • Partager sur Twitter
            18 décembre 2021 à 19:50:00

            Le problème c'est que je ne vois pas comment faire
            • Partager sur Facebook
            • Partager sur Twitter
              18 décembre 2021 à 23:03:33

              La taille de la liste des chiffres est une base B. Si on convertit le nombre en base B, on obtient une suite de chiffres qui utilisés comme index...
              • Partager sur Facebook
              • Partager sur Twitter
                19 décembre 2021 à 2:17:56

                La base n'est pas donnée de façon symbolique dans ton exemple. Si je veux une base 16, qu'est-ce que j'écris?
                [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] ou "0123456789ABCDEF"

                Voici une petite esquisse, on peut mettre dans des variables les len(...)
                On fait comme à la petite école, on compte sur nos doigts avec une "retenue"
                # La vraie longueur serait log(pas) / log(len(base)) + 1
                resultat = [0 for _ in range(pas)]
                while pas:
                    carry = 1
                    digit = len(resultat) - 1
                    while carry:
                        resultat[digit] += carry
                        carry = resultat[digit] // len(base)
                        resultat[digit] %= len(base)
                        digit -= 1
                    # Je suppose que base est en caractères.
                    liste.append(''.join(base[resultat[i]] for i in range(digit, len(resultat))))
                    pas -= 1

                edit:
                Indices:
                J'affiche après l'incrémentation alors que je devrais le faire avant.
                Le nombre de digits affichés n'est pas correct, il faut garder la plus petite valeur de digit et s'en servir pour la conversion.

                -
                Edité par PierrotLeFou 19 décembre 2021 à 3:06:33

                • Partager sur Facebook
                • Partager sur Twitter

                Le Tout est souvent plus grand que la somme de ses parties.

                  19 décembre 2021 à 11:44:54

                  ebdm13 a écrit:

                  def compter(pas: int, char: list) -> list:
                  	"""
                  	Fonction récursive qui compte à partir 
                  	d'un nombre de pas demander et d'une chaine de caractère
                  	"""
                  
                  	#le résultat sera stoker dans cette liste
                  	result = list()
                  
                  	#condition d'arrêt de la fonction récursive
                  	if pas < len(char):
                  		
                  		for i in range(pas+1):
                  			result.append(str(char[i]))
                  	else:
                  		# la récursivité commence ici:
                  		#donc si le nombre de pas à effectuer est supérieur aux nombres de caractères,
                  		#On ajoute récursivement les nombres
                  		result.append(compter(pas-1, char))
                  		result.append(str(compter(pas//len(char), char)[-1]) + str(char[pas%len(char)]))
                  
                  		# Pour avoir une liste propre
                  		# sans ça, ça donnerait ça:
                  		# >>> compter(2, [0,1])
                  		# [['0', '1'], '10']
                  		
                  		result = result[0] + [result[1]]
                  
                  	return result




                  A cause des limitations de la récursivité en Python, tu ne pourras pas compter au-delà de 1000 sinon, c'était pas mal tenté.

                  Ton problème est fondamentalement d'écrire les n premiers entiers dans une base donnée. Il suffit donc d'écrire un programme de conversion dans une base (ce dont Python ne dispose pas nativement), et de procéder exactement comme l'a expliqué mps.

                  On peut aussi voir la question d'un point de vue «combinatoire». Il s'agit de trouver le suivant dans l'ordre lexicographique sur un alphabet donné. Par exemple, en base 3 

                  • le suivant de [1, 2, 0, 1, 2, 2, 2] est [1, 2, 0, 2, 0, 0, 0]
                  • le suivant de [2, 2, 2, 2, 2, 2, 2] est [1, 0, 0, 0, 0, 0, 0, 0]

                  Il suffit donc de coder une fonction suivant  (ce qui revient à gérer l'addition de 1 à un nombre d'où la retenue qu'utilise pierrot) et pour chaque liste obtenue, d'écrire le nombre correspondant :

                  def suivant(L, N):
                      n=len(L)
                      k=n-1
                      while k>=0 and L[k]==N-1:
                          k-=1
                      if k<0:
                          return [1]+n*[0]
                      L[k]+=1
                      L[k+1:]=(n-k-1)*[0]
                      return L
                  
                  def compter(n, alpha):
                      L=[0]
                      for i in range(n):
                          print(''.join(alpha[i] for i in L))
                          L=suivant(L, len(alpha))
                  
                  compter(10, alpha=["1", "A", "4", "Z"])
                  
                  

                  J'ai utilisé des slices mais on peut s'en passer. Ce code affiche les 10 premiers nombres (j'ai repris un de tes exemples)

                  1
                  A
                  4
                  Z
                  A1
                  AA
                  A4
                  AZ
                  41
                  4A

                  On doit aussi pouvoir parvenir au même résultat en utilisant la fonction product du module itertools.


                  -
                  Edité par PascalOrtiz 19 décembre 2021 à 14:16:19

                  • Partager sur Facebook
                  • Partager sur Twitter
                    19 décembre 2021 à 14:57:02

                    Je ne suis pas sûr de l'intérêt de la fonction, mais pour le fun je propose avec product :
                    import itertools
                    import math
                    
                    def my_product(length, digits):
                        digits = list(map(str, digits))
                        results, firsts = digits[:length], digits[1:]
                        for magnitude in range(1, math.ceil(math.log(length, len(digits)))):
                            for sequence in itertools.product(firsts, *[digits] * magnitude):
                                results.append(''.join(sequence))
                        return results[:length]
                    
                    print(my_product(10, ["Foo", "Bar", "Baz"]))

                    -
                    Edité par ЯК 19 décembre 2021 à 15:08:59

                    • Partager sur Facebook
                    • Partager sur Twitter
                      19 décembre 2021 à 15:14:36

                      C'est pas de la triche avec itertools ?
                      Ca me retourne le cerveau à chaque fois cet exercice car je sais que les solutions peuvent être simples et je galère à en retrouver une :
                      def test(a=5, b='abc'):
                      	ids = [0]
                      	c = len(b)
                      	for x in range(a+1):
                      		for i, z in enumerate(ids):
                      			if z == c:
                      				try:
                      					ids[i] = 0
                      					ids[i+1] += 1
                      				except:
                      					ids.append(1)
                      		print(''.join(b[index] for index in ids[::-1]), ids)
                      		ids[0] += 1

                      Pas trouvé plus simple...

                      >>> test(8,["1", "A", "4", "Z"])
                      1 [0]
                      A [1]
                      4 [2]
                      Z [3]
                      A1 [0, 1]
                      AA [1, 1]
                      A4 [2, 1]
                      AZ [3, 1]
                      41 [0, 2]

                      @PascalOrtiz

                      Il faut que tu rajoutes +1 à n ! ;) Regarde le comportement en exemple.

                      -
                      Edité par ErispoeLeNarvalo 19 décembre 2021 à 15:19:10

                      • Partager sur Facebook
                      • Partager sur Twitter
                        19 décembre 2021 à 18:30:14

                        Je ne crois pas qu'on puisse s'en sortir sans que la base soit en symbolique (caractêres);
                        -
                        def convert(n, base):
                            b = len(base)
                            s = ""
                            while n:
                                s = base[n%b] + s
                                n //= b
                            return s or base[0]
                        def compte(pas, base):
                            liste = []
                            for c in range(pas):
                               liste.append(convert(c, base))
                            return liste
                        print(compte(4, "01"))
                        print(compte(6, "0123456789"))
                        print(compte(13, "abcd"))
                        -
                        ['0', '1', '10', '11']                                                                                                  
                        ['0', '1', '2', '3', '4', '5']                                                                                          
                        ['a', 'b', 'c', 'd', 'ba', 'bb', 'bc', 'bd', 'ca', 'cb', 'cc', 'cd', 'da']
                        • Partager sur Facebook
                        • Partager sur Twitter

                        Le Tout est souvent plus grand que la somme de ses parties.

                          19 décembre 2021 à 18:35:47

                          ErispoeLeNarvalo a écrit:

                          C'est pas de la triche avec itertools ?


                          Sans doute pour le lycéen (?) qui a l'exo à faire mais product fait presque ce qui est demandé donc c'est naturel de l'utiliser.

                          ErispoeLeNarvalo a écrit:

                          def test(a=5, b='abc'):
                          	ids = [0]
                          	c = len(b)
                          	for x in range(a+1):
                          		for i, z in enumerate(ids):
                          			if z == c:
                          				try:
                          					ids[i] = 0
                          					ids[i+1] += 1
                          				except:
                          					ids.append(1)
                          		print(''.join(b[index] for index in ids[::-1]), ids)
                          		ids[0] += 1

                          Pas trouvé plus simple...


                          Ton code est simple et efficace, tu passes le test de 20 millions :

                          def test(a=5, b='abc'):
                              ids = [0]
                              c = len(b)
                              L=[]
                              for x in range(a+1):
                                  for i, z in enumerate(ids):
                                      if z == c:
                                          try:
                                              ids[i] = 0
                                              ids[i+1] += 1
                                          except:
                                              ids.append(1)
                                  L.append(''.join(b[index] for index in ids[::-1]))
                                  ids[0] += 1
                              return L
                                  
                          L=(test(20*10**6, "0123456789"))
                          print(L[-1])

                          Tu passes le test en 30s sur ma machine et surtout, avec une conso mémoire très raisonnable.

                          ErispoeLeNarvalo a écrit:

                          @PascalOrtiz

                          Il faut que tu rajoutes +1 à n ! ;) Regarde le comportement en exemple.

                          En effet, il commence à compter à zéro.

                          ЯК a écrit:

                          Je ne suis pas sûr de l'intérêt de la fonction, mais pour le fun je propose avec product :

                          import itertools
                          import math
                          
                          def my_product(length, digits):
                              digits = list(map(str, digits))
                              results, firsts = digits[:length], digits[1:]
                              for magnitude in range(1, math.ceil(math.log(length, len(digits)))):
                                  for sequence in itertools.product(firsts, *[digits] * magnitude):
                                      results.append(''.join(sequence))
                              return results[:length]
                          
                          print(my_product(10, ["Foo", "Bar", "Baz"]))

                          Si n n'est pas trop grand, le programme est rapide. Mais dès qu'on dépasse la dizaine de millions, la conso mémoire s'affole et freeze le PC. Exemple :

                          import itertools
                          import math
                           
                          def my_product(length, digits):
                              digits = list(map(str, digits))
                              results, firsts = digits[:length], digits[1:]
                              for magnitude in range(1, math.ceil(math.log(length, len(digits)))):
                                  for sequence in itertools.product(firsts, *[digits] * magnitude):
                                      results.append(''.join(sequence))
                              return results[:length]
                           
                          
                          L=my_product(20*10**7+1, list("0123456789"))
                          
                          
                          
                          print(L[-1])
                          

                          Si on mettait un compteur pour arrêter quand n est atteint, peut-être que ça irait jusqu'au bout.

                          Voici un autre code, basé sur la même idée :

                          from math import log
                          from itertools import product
                          
                          def compter(n, alpha):
                              B=len(alpha)
                              r=1+int(log(n)//log(B))
                              
                              # Génère les B**r premiers entiers à partir de 0
                              p=product(alpha, repeat=r+1)
                          
                              a=0
                              b=B
                          
                              L=[]
                              cpt=0
                              for k in range(r):
                                  for i in range(a, b):
                                      z="".join(next(p)[-(k+1):])
                                      L.append(z)
                                      cpt+=1
                                      if cpt>n:
                                          return L
                                  a=b
                                  b=10*a
                              return L
                           
                          L=compter(20*10**6, list("0123456789"))
                          print(L[-1])


                          Bien qu'utilisant itertools, il faut un peu retravailler le code pour obtenir ce que l'on veut. Mais c'est relativement rapide (8s sur ma machine).

                          En fait, on peut faire mieux sans itertools :

                          from math import log
                          
                          
                          def compter(n, alpha):
                              if n == 0:
                                  return [alpha[0]]
                              B = len(alpha)
                              r = 1 + int(log(n) // log(B))
                          
                              L = list(alpha[1:])
                              R = list(alpha)
                              cpt = B
                              if n < B:
                                  return R[:n + 1]
                              for i in range(r):
                                  temp = []
                                  for c in L:
                                      for i in alpha:
                                          temp.append(c + i)
                                          cpt += 1
                                          if cpt > n:
                                              R.extend(temp)
                                              return R
                          
                                  L = temp
                                  R.extend(temp)
                              return R
                          
                          
                          R = compter(20 * 10**6, "0123456789")
                          print(len(R), R[-1])


                          qui s'exécute en moins de 4s (EDIT : code corrigé suite test de ErispoeLeNarvalo).

                          PierrotLeFou a écrit:

                          Je ne crois pas qu'on puisse s'en sortir sans que la base soit en symbolique (caractêres);
                          -
                          def convert(n, base):
                              b = len(base)
                              s = ""
                              while n:
                                  s = base[n%b] + s
                                  n //= b
                              return s or base[0]
                          def compte(pas, base):
                              liste = []
                              for c in range(pas):
                                 liste.append(convert(c, base))
                              return liste
                          print(compte(4, "01"))
                          print(compte(6, "0123456789"))
                          print(compte(13, "abcd"))
                          -
                          ['0', '1', '10', '11']                                                                                                  
                          ['0', '1', '2', '3', '4', '5']                                                                                          
                          ['a', 'b', 'c', 'd', 'ba', 'bb', 'bc', 'bd', 'ca', 'cb', 'cc', 'cd', 'da']



                          Ton code est plus efficace que je ne pensais (les divisions sont coûteuses) :

                          def convert(n, base):
                              b = len(base)
                              s = ""
                              while n:
                                  s = base[n%b] + s
                                  n //= b
                              return s or base[0]
                          def compte(pas, base):
                              liste = []
                              for c in range(pas):
                                 liste.append(convert(c, base))
                              return liste
                          
                          L=(compte(20*10**6, "0123456789"))
                          
                          print(len(L), L[-1])

                          Ça met 18s sur ma machine.

                          EDIT

                          Et avec la fonction que j'avais donné au début, c'est pas si mal, contrairement à ce que je pensais :

                          def suivant(L, N):
                              n=len(L)
                              k=n-1
                              while k>=0 and L[k]==N-1:
                                  k-=1
                              if k<0:
                                  return [1]+n*[0]
                              L[k]+=1
                              L[k+1:]=(n-k-1)*[0]
                              return L
                           
                          def compter(n, alpha):
                              R=[]
                              L=[0]
                              for i in range(n+1):
                                  R.append(''.join(alpha[i] for i in L))
                                  L=suivant(L, len(alpha))
                              return R
                           
                          
                          L=(compter(20*10**6, "0123456789"))
                          
                          print(len(L), L[-1])

                          Exécution en moins de 25 s.

                          -
                          Edité par PascalOrtiz 19 décembre 2021 à 22:06:57

                          • Partager sur Facebook
                          • Partager sur Twitter
                            19 décembre 2021 à 19:49:42

                            Et ceci?
                            -
                            def compte(pas, base):
                                num = [0]
                                lg = 1
                                b = len(base)
                                liste = []
                                while pas:
                                    liste.append(''.join(base[c] for c in num))
                                    carry = 1
                                    i = lg-1
                                    while carry:
                                        num[i] += carry
                                        carry = 0
                                        if num[i] >= b:
                                            num[i]=0
                                            if i>0:
                                                carry = 1
                                                i -= 1
                                            else:
                                                num.insert(0, 1)
                                                lg += 1
                                                carry = 0
                                    pas -= 1
                                return liste
                            print(compte(4, "01"))
                            print(compte(12, "0123456789"))
                            print(compte(13, "abcd"))
                            -
                            ['0', '1', '10', '11']                                                                                                  
                            ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11']                                                          
                            ['a', 'b', 'c', 'd', 'ba', 'bb', 'bc', 'bd', 'ca', 'cb', 'cc', 'cd', 'da']
                            • Partager sur Facebook
                            • Partager sur Twitter

                            Le Tout est souvent plus grand que la somme de ses parties.

                              19 décembre 2021 à 20:11:26

                              Si n n'est pas trop grand, le programme est rapide. Mais dès qu'on dépasse la dizaine de millions, la conso mémoire s'affole et freeze le PC.

                              Que serait Python sans thrashing.
                              Bon c'est vrai que ma proposition abuse un peu en essayant de produire 99999999 éléments quand seulement 20M sont nécessaires. xD

                              Mais ce problème de thrashing finira toujours par arriver alors que le déclenchement d'une erreur serait salvateur. C'est pour ça que je désactive toujours le swap.

                              Voilà qui est sûrement mieux :

                              import itertools
                              import math
                              
                              def my_product(length, digits):
                                  digits = list(map(str, digits))
                                  results, firsts = digits[:length], digits[1:]
                                  length, magnitude = length - len(results), 0
                                  while length:
                                      magnitude += 1
                                      for sequence in itertools.product(firsts, *[digits] * magnitude):
                                          if length:
                                              results.append(''.join(sequence))
                                              length -= 1
                                          else: break
                                  return results
                              
                              ls = my_product(20000000, range(10))
                              print(len(ls), ls[-1])

                              -
                              Edité par ЯК 19 décembre 2021 à 21:48:50

                              • Partager sur Facebook
                              • Partager sur Twitter
                                19 décembre 2021 à 20:46:26

                                @PascalOrtiz

                                Re,

                                La vache vos codes sont carrément plus rapides ! o_O
                                J'comprends difficilement comment ça fonctionne, va falloir que je dorme plus de 2h par nuit...

                                Par contre :

                                >>> R=compter(8, "0123456789")
                                >>> print(len(R), R[-1])
                                
                                11 10

                                Bof, bof ! ^^

                                -
                                Edité par ErispoeLeNarvalo 19 décembre 2021 à 21:02:17

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  19 décembre 2021 à 21:49:46

                                  ErispoeLeNarvalo a écrit:

                                  @PascalOrtiz

                                  Re,

                                  La vache vos codes sont carrément plus rapides ! o_O
                                  J'comprends difficilement comment ça fonctionne, va falloir que je dorme plus de 2h par nuit...

                                  Par contre :

                                  >>> R=compter(8, "0123456789")
                                  >>> print(len(R), R[-1])
                                  
                                  11 10

                                  Bof, bof ! ^^


                                  Oui je savais que ça ne marchait pas (corner case), je corrigerai.

                                  PierrotLeFou a écrit:

                                  Et ceci?

                                  def compte(pas, base):
                                      num = [0]
                                      lg = 1
                                      b = len(base)
                                      liste = []
                                      while pas:
                                          liste.append(''.join(base[c] for c in num))
                                          carry = 1
                                          i = lg-1
                                          while carry:
                                              num[i] += carry
                                              carry = 0
                                              if num[i] >= b:
                                                  num[i]=0
                                                  if i>0:
                                                      carry = 1
                                                      i -= 1
                                                  else:
                                                      num.insert(0, 1)
                                                      lg += 1
                                                      carry = 0
                                          pas -= 1
                                      return liste
                                  
                                  
                                  L=(compte(20*10**6, "0123456789"))
                                  print(len(L), L[-1])

                                  S'exécute en 19 s. Je ne pense pas ça joue trop ici (car les listes dont courtes et que l'insertion est rare) mais le num.insert(0, 1) est algorithmiquement hérétique.

                                  J'ai essayé de reprendre ton code en le simplifiant et en supprimant ce qui me paraissait lent mais, curieusement, ton code reste plus rapide :

                                  def compter(n, alpha):
                                      R=[]
                                      L=[0]
                                      m=len(alpha)-1
                                      append=R.append
                                      join=''.join
                                      for i in range(n+1):
                                          append(join(alpha[i] for i in L))
                                          for k in range(len(L)-1, -1, -1):
                                              if L[k]==m:
                                                  L[k]=0
                                              else:
                                                  break
                                          else:
                                              L.append(0)
                                          L[k]+=1
                                  
                                      return R
                                  
                                  
                                  n=20*10**6
                                  L=(compter(n, "0123456789"))
                                  
                                  print(len(L), L[-1])

                                  qui s'exécute en 21 s.

                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    19 décembre 2021 à 21:53:30

                                    Oups, my bad - Error 418 !

                                    -
                                    Edité par ЯК 19 décembre 2021 à 21:55:08

                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      19 décembre 2021 à 23:49:42

                                      PierrotLeFou a écrit:

                                      Et ceci?
                                      -

                                      def compte(pas, base):
                                          num = [0]
                                          lg = 1
                                          b = len(base)
                                          liste = []
                                          while pas:
                                              liste.append(''.join(base[c] for c in num))
                                              carry = 1
                                              i = lg-1
                                              while carry:
                                                  num[i] += carry
                                                  carry = 0
                                                  if num[i] >= b:
                                                      num[i]=0
                                                      if i>0:
                                                          carry = 1
                                                          i -= 1
                                                      else:
                                                          num.insert(0, 1)
                                                          lg += 1
                                                          carry = 0
                                              pas -= 1
                                          return liste
                                      





                                      Travailler directement avec les caractères est plus rapide que passer par des indices :

                                      def suivant(mot, alpha, alpha0):
                                          n=len(mot)
                                          k=n-1
                                          while k>=0 and mot[k]==alpha[-1]:
                                              k-=1
                                              
                                          if k<0:
                                              return alpha[1]+alpha0*(n)
                                          
                                          i=alpha.index(mot[k])
                                          c=alpha[i+1]
                                      
                                          return mot[:k]+c+alpha0*(n-k-1)
                                      
                                      n=20*10**6
                                      mot="0"
                                      R=[mot]
                                      for _ in range(n):
                                          mot=suivant(mot, "0123456789", "0")
                                          R.append(mot)
                                          
                                      print(len(R), R[-1])
                                      

                                      qui met 13,5 s au lieu de 19 s.

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        20 décembre 2021 à 3:08:55

                                        @PascalOrtiz:
                                        Et ton code fonctionne avec un ensemble de symboles non conventionel telle que "acfk"
                                        Est-ce que le fait que alpha0 soit passé en paramètre est plus rapide que l'évaluer au début de la fonction?

                                        Mes tests ne montrent pas de différence significative.

                                        edit:
                                        Ça fonctionne encore plus vite si on en fait un itérateur.
                                        -
                                        from time import perf_counter
                                        def suivant(count, base):
                                            base0 = base[0]
                                            mot =base0    
                                            n=1
                                            while count >   0:
                                                count -= 1
                                                yield mot
                                                k = n - 1
                                                while k>=0 and mot[k]==base[-1]:
                                                    k-=1
                                                if k<0:
                                                    mot = base[1]+base0*(n)
                                                    n += 1
                                                else:
                                                    i=base.index(mot[k])
                                                    c=base[i+1]
                                                    mot = mot[:k]+c+base0*(n-k-1)
                                        #
                                        count = 20*10**6
                                        R=[]
                                        begin=perf_counter()
                                        for mot in suivant(count, "0123456789"):
                                            R.append(mot)
                                        print(round(perf_counter()-begin, 3),"secondes")
                                        #print(R)
                                        #print(len(R), R[-1])

                                        -
                                        Edité par PierrotLeFou 20 décembre 2021 à 4:54:34

                                        • Partager sur Facebook
                                        • Partager sur Twitter

                                        Le Tout est souvent plus grand que la somme de ses parties.

                                          20 décembre 2021 à 10:04:36

                                          PierrotLeFou a écrit:

                                          @PascalOrtiz:
                                          Et ton code fonctionne avec un ensemble de symboles non conventionel telle que "acfk"
                                          Est-ce que le fait que alpha0 soit passé en paramètre est plus rapide que l'évaluer au début de la fonction?

                                          Mes tests ne montrent pas de différence significative.

                                          Tu as raison, ce 3e paramètre n'est pas utile.

                                          PierrotLeFou a écrit:

                                          edit:

                                          Ça fonctionne encore plus vite si on en fait un itérateur.


                                          Pas testé intensément mais l'avantage semble limité (entre 1% et 2%)
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            20 décembre 2021 à 15:06:32

                                            Tout d’abord, Merci pour toutes vos réponses (je m'attendais pas à en recevoir autant).

                                            Les solutions avec itertools ne sont pas exactement ce que je souhaite, mais c'est une solutions qui marche.

                                            La solution avec la fonction suivante n'est pas non-plus exactement ce que je cherche.

                                            Sinon, j'ai adoré toutes vos solutions.

                                            Je propose donc une autre solution, j’aimerai également avoir votre avis et vos conseils sur celui ci:

                                            def compter_nr(pas: int, char: list) -> list:
                                            
                                            	char = list(map(str, char))
                                            	result = ([i for i in char] * (pas//len(char))) + char[:pas%len(char)]
                                            
                                            	for i in range(len(char)-1,len(result)):
                                            
                                            		#appliquer la modif du nb d'avant sur l'actuel	
                                            		if len(result[i-1]) > len(result[i]):
                                            
                                            			result[i] = result[i-1][:len(result[i-1])-len(result[i])] + result[i]
                                            
                                            		if char[-1] in result[i]:
                                            
                                            			i_last_char = None
                                            			
                                            			for b in range(len(result[i])):
                                            				if result[i][-(b+1)] != char[-1] :
                                            					break
                                            				else:
                                            					i_last_char = len(result[i])-(b+1)
                                            
                                            			if i_last_char != None and i != len(result)-1:
                                            				
                                            				if i_last_char:
                                            					result[i+1] = result[i][:i_last_char-1] + char[char.index(result[i][i_last_char-1])+1] + char[0]*len(result[i][i_last_char:])
                                            				
                                            				else:
                                            					result[i+1] = char[1] + char[0]*len(result[i])
                                            	
                                            	return result


                                            PS: J'ai du mal à comprendre vos code, a cause de mes connaissances limitées notamment en math (je connais les logarithmes uniquement de nom), et en python(je ne maitrise pas itertools ni les itérateurs). Malgré ça j’essaye de me renseigner pour mieux comprendre vos codes.

                                            -
                                            Edité par ebdm13 20 décembre 2021 à 15:25:23

                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              20 décembre 2021 à 15:43:48

                                              @PascalOrtiz:
                                              J'obtiens 14.113 secondes pour ta version contre 12.823 secondes pour la mienne avec itérateur.

                                              un peu moins de 9% de gain.

                                              -
                                              Edité par PierrotLeFou 20 décembre 2021 à 15:46:36

                                              • Partager sur Facebook
                                              • Partager sur Twitter

                                              Le Tout est souvent plus grand que la somme de ses parties.

                                                20 décembre 2021 à 19:14:55

                                                ebdm13 a écrit:

                                                PS: J'ai du mal à comprendre vos code, a cause de mes connaissances limitées notamment en math (je connais les logarithmes uniquement de nom), et en python(je ne maitrise pas itertools ni les itérateurs). Malgré ça j’essaye de me renseigner pour mieux comprendre vos codes.

                                                Je tire un peu la couverture à moi mais je pense que mon code est le plus simple à comprendre, n'étant pas bon en python ni en math j'ai codé comme si je faisais la manip à la main.

                                                La liste qui apparait dans le code suivant correspond à l'ordre des index qu'il faut prendre en commençant par la fin de la liste, ex : 'ba' -> b est  à l'index 1 et a l'index 0 de 'abc', donc on a : ba [0, 1]

                                                >>> test(15,'abc')
                                                a [0]
                                                b [1]
                                                c [2]
                                                ba [0, 1]
                                                bb [1, 1]
                                                bc [2, 1]
                                                ca [0, 2]
                                                cb [1, 2]
                                                cc [2, 2]
                                                baa [0, 0, 1]
                                                bab [1, 0, 1]
                                                bac [2, 0, 1]
                                                bba [0, 1, 1]
                                                bbb [1, 1, 1]
                                                bbc [2, 1, 1]
                                                bca [0, 2, 1]



                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  20 décembre 2021 à 20:12:38

                                                  Effectivement ton code est plus simple, j'ai souvent du mal à pensée simple et je complique souvent trop les choses.

                                                  J'ai un tout petit peut modifié ton code à ma sauce (j'ai pratiquement rien changé):

                                                  def test(a=20, b='0123456789'):
                                                      ids = [0]
                                                      c = len(b)
                                                      result = list()
                                                      
                                                      for _ in range(a+1):
                                                          for i in range(len(ids)):
                                                              if ids[i] == c:
                                                                  
                                                                  try:
                                                                      ids[i] = 0
                                                                      ids[i+1] += 1
                                                                  except IndexError:
                                                                      ids.append(1)
                                                          
                                                          result.append(''.join(b[index] for index in ids[::-1]))
                                                          ids[0] += 1
                                                  
                                                      return result



                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    20 décembre 2021 à 20:33:29

                                                    Je pense que le bon compromis, performance pas trop mauvaise et code facile à comprendre, c'est la solution qui construit la liste en convertissant chaque nombre en sa représentation.
                                                    def useless(length, digits):
                                                        digits = list(map(str, digits))
                                                        base, results = len(digits), []
                                                        for number in range(length):
                                                            tmp = []
                                                            while number:
                                                                tmp.append(digits[number % base])
                                                                number //= base
                                                            results.append(''.join(reversed(tmp)))
                                                        return results

                                                    -
                                                    Edité par ЯК 20 décembre 2021 à 20:40:51

                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      20 décembre 2021 à 21:19:51

                                                      En effet, c'est un bon compromis.

                                                      Bon, je pense que le sujet et clos.

                                                      Encore Merci pour votre participation

                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        20 décembre 2021 à 22:47:56

                                                        ebdm13 a écrit:

                                                        Je propose donc une autre solution, j’aimerai également avoir votre avis et vos conseils sur celui ci:

                                                        def compter_nr(pas: int, char: list) -> list:
                                                        
                                                        	char = list(map(str, char))
                                                        	result = ([i for i in char] * (pas//len(char))) + char[:pas%len(char)]
                                                        
                                                        	for i in range(len(char)-1,len(result)):
                                                        
                                                        		#appliquer la modif du nb d'avant sur l'actuel	
                                                        		if len(result[i-1]) > len(result[i]):
                                                        
                                                        			result[i] = result[i-1][:len(result[i-1])-len(result[i])] + result[i]
                                                        
                                                        		if char[-1] in result[i]:
                                                        
                                                        			i_last_char = None
                                                        			
                                                        			for b in range(len(result[i])):
                                                        				if result[i][-(b+1)] != char[-1] :
                                                        					break
                                                        				else:
                                                        					i_last_char = len(result[i])-(b+1)
                                                        
                                                        			if i_last_char != None and i != len(result)-1:
                                                        				
                                                        				if i_last_char:
                                                        					result[i+1] = result[i][:i_last_char-1] + char[char.index(result[i][i_last_char-1])+1] + char[0]*len(result[i][i_last_char:])
                                                        				
                                                        				else:
                                                        					result[i+1] = char[1] + char[0]*len(result[i])
                                                        	
                                                        	return result



                                                        Code que je trouve compliqué mais qui montre que tu n'as pas des connaissances en Python aussi limitées que tu le laisses entendre :). Le code semble fonctionner. Maintenant, si tu expliquais l'algorithme ...

                                                        ebdm13 a écrit:

                                                        PS: J'ai du mal à comprendre vos code, a cause de mes connaissances limitées notamment en math (je connais les logarithmes uniquement de nom), et en python(je ne maitrise pas itertools ni les itérateurs). 


                                                        itertools n'est pas important ici, tu peux ignorer. Les itérateurs, il n'y a rien besoin de savoir dans les codes qui t'ont été proposés. Pour les maths, il faut juste savoir comment le logarithme permet de trouver le nombre de chiffres d'un entier dans une base donnée, c'est juste une formule (mais ça peut se faire facilement sans logarithme avec une simple boucle while, exo classique).

                                                        ErispoeLeNarvalo a écrit:

                                                        Je tire un peu la couverture à moi mais je pense que mon code est le plus simple à comprendre, n'étant pas bon en python ni en math j'ai codé comme si je faisais la manip à la main.

                                                        Comme je t'avais dit ton code est très simple et court, bravo ! Je n'avais pas porté assez d'attention à ton code, en particulier à cause des noms de variables (pour moi peu parlants comme test, idx, x, etc), de l'utilisation d'exceptions (qui me semblaient inutiles ici).

                                                        Je viens d'y passer un petit moment pour essayer de comprendre comment ça marche. En fait ton code fait de manière plutôt simple ce que Pierrot et moi parlions dans ce message : tu calcules le suivant du nombre courant en ajoutant 1 manuellement (avec gestion de la retenue) sauf que tu te donnes la possibilité d'écrire la base comme chiffre. Par exemple, si en base 10, j'écris 2029 sous la forme [9, 2, 0, 2], pour rajouter 1 tu écris [10, 2, 0, 2] et tu propages la retenue.

                                                        Si je reprends ton code :

                                                        def test(a=5, b='abc'):
                                                            ids = [0]
                                                            c = len(b)
                                                            for x in range(a+1):
                                                                for i, z in enumerate(ids):
                                                                    if z == c:
                                                                        try:
                                                                            ids[i] = 0
                                                                            ids[i+1] += 1
                                                                        except:
                                                                            ids.append(1)
                                                                print(''.join(b[index] for index in ids[::-1]), ids)
                                                                ids[0] += 1

                                                        je peux facilement en extraire une fonction suivant (j'ai mis juste des noms qui me paraissent plus parlants) :

                                                        def suivant(digits, base):
                                                            digits[0] += 1
                                                            for i, d in enumerate(digits):
                                                                if d == base:
                                                                    digits[i] = 0
                                                                    try:
                                                                        digits[i+1] += 1
                                                                    except:
                                                                        digits.append(1)
                                                        
                                                        def test(n, alpha='0123456789'):
                                                            R=[alpha[0]]
                                                            digits = [0]
                                                            base = len(alpha)
                                                            for _ in range(n):
                                                                suivant(digits, base)
                                                                R.append(''.join(alpha[index] for index in digits[::-1]))
                                                            return R
                                                        
                                                        R=test(112)
                                                        print(R)


                                                        Le code est super simple et marche très bien mais il n'est pas optimal car la plupart du temps tu testes pour rien si le chiffre courant est la base : par exemple, quand tu ajoutes +1 à 2021, comme 1+1=2 , tu ne vas pas regarder à chaque chiffre pour savoir s'il vaut 10. De même, si tu rajoutes 1 à 2029, à partir du 2e chiffre (à savoir 3), tu n'as pas besoin de regarder derrière s'il y a une retenue à propager. Voilà pourquoi Pierre et moi avons utilisé une boucle while (ou un for/break).

                                                        J'avais écrit dans le message déjà cité un code équivalent, que je récris en faisant apparaître une fonction suivant :

                                                        def suivant(L, m):
                                                            for k in range(len(L)-1, -1, -1):
                                                                if L[k]==m:
                                                                    L[k]=0
                                                                else:
                                                                    break
                                                            else:
                                                                L.append(0)
                                                            L[k]+=1
                                                        
                                                        def compter(n, alpha):
                                                            R=[]
                                                            L=[0]
                                                            m=len(alpha)-1
                                                            for i in range(n+1):
                                                                R.append(''.join(alpha[i] for i in L))
                                                                suivant(L, m)
                                                            return R
                                                        
                                                        n=42
                                                        L=(compter(n, "0123456789"))
                                                        
                                                        print(len(L), L[-1])
                                                        

                                                        Il y a une différence entre nos deux codes, c'est que tu inverses les chiffres à la fin de l'opération et moi dès le départ. Et aussi qu'au lieu de lever une exception comme tu as fais (bonne idée à propos), je surveille si la retenue dépasse le début du nombre.

                                                        ЯК a écrit:

                                                        Je pense que le bon compromis, performance pas trop mauvaise et code facile à comprendre, c'est la solution qui construit la liste en convertissant chaque nombre en sa représentation.

                                                        def useless(length, digits):
                                                            digits = list(map(str, digits))
                                                            base, results = len(digits), []
                                                            for number in range(length):
                                                                tmp = []
                                                                while number:
                                                                    tmp.append(digits[number % base])
                                                                    number //= base
                                                                results.append(''.join(reversed(tmp)))
                                                            return results
                                                        Oui, c'est la solution assez naturelle (et encore, je ne suis pas sûr que quelqu'un d'inexpérimenté la voit si facilement) et évoquée par mps et en outre assez courte. Du point de vue performance (24 s), ça reste assez moyen (la génération ne tient pas compte des résultats précédents et la division est une opération processeur coûteuse).

                                                        -
                                                        Edité par PascalOrtiz 20 décembre 2021 à 22:50:56

                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          22 décembre 2021 à 2:16:58

                                                          Merci pour tous ces précieux conseilles.

                                                          J'ai ajouter des explications à mon code, dites-moi si ce n'est pas assez clair ou si vous avez des suggestion d'amélioration.

                                                          Mercie !

                                                          def compter_nr(pas: int, char: list) -> list:
                                                          	"""
                                                          	Principe:
                                                          	La base de cette algorithme, est le principe selon lequelle
                                                              si l'on prend une liste avec des nombres qui ce suivent,
                                                              ex: 0,1,2,3,4,5,6,7,8,9,10,11,12
                                                              on remarque que si on prend le dernier caractère de chaque élément et
                                                              qu'on en fait une liste, cela donne l'enchainement des caractères définis dans la base x fois.
                                                              ex: avec une base="0123456789"
                                                              0,1,2,3,4,5,6,7,8,9,10,11,12 -> 0,1,2,3,4,5,6,7,8,9,0,1,2
                                                          
                                                              Puis, pour que cette liste représente bien ces nombres, ex: 0(le 2ème) -> 10
                                                              On va regarder si dans l'élément sélectionner de la liste, il y a le dernier caractère de la base: ici 9.
                                                              Si c'est le cas, alors il faut tout simplement remplacer le caractère de l'élément suivant avant le 9 par le caractère qui le suit
                                                              dans la base. Seulement, si l'on prend 9 par exemple, il n'y a aucun caractère devant lui dans l'élément.
                                                              Donc, si tous les caractères de cet élément sont le même que celui du dernier de la base, il faut donc ajouter
                                                              le 2ème caractère de la base avant les autres caractères de l'élément et remplacer ses autres caractères par le premier 
                                                              caractère de la base. Ainsi, 0 -> 10.
                                                              Mais si vous avez bien suivi, l'élément d'après, ici: 1,ne sera donc pas changé.
                                                              Il faut donc ajouter le radical ajouter de l'élément précédent sur celui-ci.
                                                              """
                                                          	char = list(map(str, char))
                                                              # On défini result sur la liste des derniers caractères: 0,1,2,3,4,5,6,7,8,9,0,1 etc... (en base d?imal) 
                                                          	result = ([i for i in char] * (pas//len(char))) + char[:pas%len(char)]
                                                          
                                                          	for i in range(len(char)-1,len(result)):
                                                          
                                                          		#appliquer la modif du nb d'avant sur l'actuel	
                                                          		if len(result[i-1]) > len(result[i]):
                                                          
                                                          			result[i] = result[i-1][:len(result[i-1])-len(result[i])] + result[i]
                                                          
                                                          		if char[-1] in result[i]:
                                                          
                                                          			i_last_char = None
                                                          			
                                                                      # boucle qui permet de définir l'indice du caractère pour lequel il faudra changer
                                                                      # le caractère suivant de cette élément
                                                                      # ex: 909; indice = 2, puisqu'il faut arriver à 910
                                                                      for b in range(len(result[i])):
                                                          				if result[i][-(b+1)] != char[-1] :
                                                          					break
                                                          				else:
                                                          					i_last_char = len(result[i])-(b+1)
                                                          
                                                          			if i_last_char != None and i != len(result)-1:
                                                          				
                                                                          # pour changer l'élément si il n'y a déjà un caractère devant 
                                                                          # ex: 1099 -> 1100
                                                          				if i_last_char:
                                                          					result[i+1] = result[i][:i_last_char-1] + char[char.index(result[i][i_last_char-1])+1] + char[0]*len(result[i][i_last_char:])
                                                          				
                                                                          # pour changer l'élément si il n'y a pas un caractère devant
                                                                          # ex: 999->1000
                                                          				else:
                                                          					result[i+1] = char[1] + char[0]*len(result[i])
                                                          	
                                                          	return result



                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            22 décembre 2021 à 3:20:18

                                                            Je comprend tes explications car je suis familier avec le problème, mais je ne sais pas ce que comprendrait quelqu'un qui ne l'a jamais abordé.
                                                            Comment expliquer que lorsqu'on atteint le dernier symbole de la base pour une position donnée et qu'on veut passer au suivant, il faut revenir au premier.
                                                            Et ensuite, passer à la position précédent dans cette suite? Et s'il n'y a pas de précédente?
                                                            En fait, virtuellement, on peut supposer que les positions précédentes sont égales au "zéro" de cette base (le premier symbole)
                                                            En décimal, 9 = 00000009, et 0 + 1 donne 1.
                                                            On fait passer le 9 à 0 et à cause de cela, on passe au second symbole et on le fait passer de 0 à 1
                                                            C'est ce que j'appelle un "compteur circulaire" ("ring counter" en anglais)
                                                            On pourrait imaginer une série de roulettes marquées avec les symboles.
                                                            On commence par faiere avancer celle de droite d'un symbole.
                                                            Quand on a fait le tour, on entraine la roulette suivante d'une position.
                                                            Si celle-ci a également fait le tour, on passe à la troisième, etc.
                                                            • Partager sur Facebook
                                                            • Partager sur Twitter

                                                            Le Tout est souvent plus grand que la somme de ses parties.

                                                              22 décembre 2021 à 11:03:23

                                                              PierrotLeFou a écrit:

                                                              Je comprend tes explications car je suis familier avec le problème, mais je ne sais pas ce que comprendrait quelqu'un qui ne l'a jamais abordé.
                                                              Comment expliquer que lorsqu'on atteint le dernier symbole de la base pour une position donnée et qu'on veut passer au suivant, il faut revenir au premier.
                                                              Et ensuite, passer à la position précédent dans cette suite? Et s'il n'y a pas de précédente?
                                                              En fait, virtuellement, on peut supposer que les positions précédentes sont égales au "zéro" de cette base (le premier symbole)
                                                              En décimal, 9 = 00000009, et 0 + 1 donne 1.
                                                              On fait passer le 9 à 0 et à cause de cela, on passe au second symbole et on le fait passer de 0 à 1
                                                              C'est ce que j'appelle un "compteur circulaire" ("ring counter" en anglais)
                                                              On pourrait imaginer une série de roulettes marquées avec les symboles.
                                                              On commence par faiere avancer celle de droite d'un symbole.
                                                              Quand on a fait le tour, on entraine la roulette suivante d'une position.
                                                              Si celle-ci a également fait le tour, on passe à la troisième, etc.

                                                              Je ne savais pas que ce système avait un nom, mais j'imaginais exactement ça.
                                                              Merci pour ces explications plus précises.

                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              Optimisation algo

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              • Editeur
                                                              • Markdown