Partage
  • Partager sur Facebook
  • Partager sur Twitter

Optimisation algo

Sujet résolu
    22 décembre 2021 à 15:13:09

    ebdm13 a écrit:

    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



    Merci d'avoir rajouté ces explications, c'est plus clair maintenant : ton algorithme construit dans result[i] la représentation en base len(char) du successeur de chaque nombre courant à partir de sa représentation dans result[i-1]. La technique que tu utilises est très compliquée et je te félicite d'avoir réussi à créer un programme qui fonctionne et qui fonctionne même relativement rapidement en 13.7 s sur ma machine pour n=20 millions en base 10.

    En réalité, j'avais proposé ICI cette même méthode avec le code suivant :

    def suivant(mot, alpha):
        n=len(mot)
        alpha0=alpha[0]
        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)
    
    def compter(n, alpha="0123456789"):
        mot="0"
        R=[mot]
        for _ in range(n):
            mot=suivant(mot, alpha)
            R.append(mot)
        return R
    
    n=20*10**6
    R=compter(n)
    
         
    print(len(R), R[-1])

    qui s'exécute en 13 s. J'espère que tu vois les équivalences de code entre le tien et le mien.

    Il y a une autre méthode qui n'a pas été évoquée me semble-t-il et qui pourrait être rapide mais j'ai la flemme de l'écrire. Il suffit générer les nombres par colonnes, en commençant par la colonne des unités. Par exemple, en base 10, pour écrire les nombres jusqu'à 2038

    • on écrit 203 blocs de "0123456789" et on complète (ça donne les unités)
    • on écrit 20 blocs de 100 blocs de la forme "0...01...1...9...9", les points de suspension montrant des blocs de 10 chiffres tous égaux (ça donnera les chiffres des dizaines)
    • etc jusqu'à la 4e colonne
    Tout ceci peut être très rapide car il faut juste concaténer des blocs de caractères avec les opérateurs + et *. Une fois les colonnes obtenues (mais qu'il faudrait je pense écrire bout à bout, en une seule chaîne), il faut transposer en lignes (ce qui doit pouvoir se faire assez efficacement avec des slices) et supprimer les zéros en début de ligne ce qui doit pouvoir se faire efficacement encore avec des slices car on devrait pouvoir connaître le nombre de zéros dominants. Si quelqu'un à le courage de le coder ... L'idée est simple mais si on veut un code rapide, il faudra sans doute faire attention aux détails.

    -
    Edité par PascalOrtiz 22 décembre 2021 à 15:17:27

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

      @PascalOrtiz: peux-tu me dire si j'ai bien compris?
      Pour les unités, je répète chaque digit 1 fois jusqu'à ce que j'obtienne le bon nombre de digits.
      Pour les "dizaines" (deuzaines en base 2?) je répète len(base) fois chaque gdigits et je recommence
      Pour les centaines, je répète len(base)**2 fois chaque digits jusqu'à ce que j'aie le bon nombre de digits
      Le nombre de digits se calcule encore avec le log en base "base" du compte:
      nombre_digits = log(compte) / log(len(base)) + 1  ajusté correctement .. avec round() ?.
      Une fois la chaîne générée, on pourrait faire:
      nombre = nombre[:-1].lstrip(base[0])+nombre[-1]
      Ça pourrait ressembler à ceci une fois la grille générée.
      for i in range(compte):
          nombre = ""
          for d in range(nombre_digits - 1, -1, -1):
              nombre += grille[i][d]
              liste.append(nombre[:-1].lstrip(base[0])+nombre[-1])
      Reste plus qu'à générer la grille ... :)
      • Partager sur Facebook
      • Partager sur Twitter

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

        22 décembre 2021 à 18:34:34

        @PascalOrtiz

        Effectivement ton programme est basé sur le même principe. (avec tout ces messages, je n'ai pas eu le temps de tous les lires avec attention).

        Après, je m'étais mis la contrainte de n'utiliser qu'une seule fonction ce qui est limitant.

        Pour l'autre méthode qui générer les nombres par colonnes j'y avais vaguement pensé, mais j'ai préféré utilisé celle-ci.

        Pour revenir à ton programme je n'ai pas pensé à utiliser une boucle while, mais je pense qu'au niveaux perf, c'est la même chose que ma boucle for. Voir plus rapide.

        -
        Edité par ebdm13 22 décembre 2021 à 18:52:12

        • Partager sur Facebook
        • Partager sur Twitter
          22 décembre 2021 à 19:15:01

          Si j'ai bien compris l'algo de PascalOrtiz, pour 20 millions, j'ai 8 digits et 20 millions de lignes, ce qui fait 160 millions d'entrées dans ma grille.
          J'aurai 8 chaînes de 20 millions de caractères.
          En faisant du slicing, on pourrait prendre le nombre de digits pour chacun de la ligne précédente et multiplier par la longueur de la base.
          C'est obscur? ...
          Pour les dizaines, j'aurais 10 fois le '0' soit 10 fois [:1]
          Pour les centaines, j'aurai 10 fois [:10]
          Pour les milliers, j'aurai 10 fois [:100]
          etc.
          Ça suppose de traiter la première ligne différemment
          On refait ça pour chaque digit de la base et on doit multiplier la chaîne par un nombre pas trop gros et couper avec le slicing.

          • Partager sur Facebook
          • Partager sur Twitter

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

            23 décembre 2021 à 1:00:50

            PierrotLeFou a écrit:

            Si j'ai bien compris l'algo de PascalOrtiz, pour 20 millions, j'ai 8 digits et 20 millions de lignes, ce qui fait 160 millions d'entrées dans ma grille.
            J'aurai 8 chaînes de 20 millions de caractères.
            En faisant du slicing, on pourrait prendre le nombre de digits pour chacun de la ligne précédente et multiplier par la longueur de la base.
            C'est obscur? ...
            Pour les dizaines, j'aurais 10 fois le '0' soit 10 fois [:1]
            Pour les centaines, j'aurai 10 fois [:10]
            Pour les milliers, j'aurai 10 fois [:100]
            etc.
            Ça suppose de traiter la première ligne différemment
            On refait ça pour chaque digit de la base et on doit multiplier la chaîne par un nombre pas trop gros et couper avec le slicing.

            Oui, c'est ça.

            J'ai écrit un code qui implémente cet algorithme (et encore, des détails manquent) et le temps semble très décevant (30 s contre 4s pour l'algo le plus rapide). En réalité, en y regardant de plus près, le temps de génération du tableau (cols ci-dessous) est très rapide (0,3 s) et tout le reste est passé à transposer le tableau. Il faudrait essayer Numpy qui transpose très vite mais il est assez mauvais avec des tableaux de caractères unicodes. Je mets le code ci-dessous :

            n=20*10**6
            n+=1
            
            bdigits="0123456789"
            base=len(bdigits)
            
            cols=[]
            
            nch=len(str(n))
            s=1
            
            for i in range(nch):
                sbloc=base*s
                nblocs=n//sbloc
                r=n%sbloc
                bloc="".join([d*s for d in bdigits])
                cols.append(nblocs*bloc+bloc[:r])
                s*=base
            
            cols=(''.join(cols))
            
            # Transposition 
            R=["".join(cols[k+q*n] for q in range(nch))[::-1] for k in range(n)]
            print(len(R), R[-1])



            • Partager sur Facebook
            • Partager sur Twitter
              23 décembre 2021 à 3:04:53

              Si on met les 160 millions de caractères dans une seule chaîne et qu'on joue avec le slicing, on accélère beaucoup.
              J'ai des temps de l'ordre de 3.4 secondes.
              -
              from time import perf_counter
              n=20*10**6
              d = len(str(n))
              grid = 'a'*(n*d)
              begin=perf_counter()
              liste = [grid[i: n*d: n] for i in range(n)]
              print(round(perf_counter()-begin, 3),"secondes")
              print(len(liste[0]), liste[0])

              edit:
              Voici ma version complète. Je génère la grille différemment.
              Les performances ne sont pas trop mauvaises malgré le lstrip(). Environ 5 secondes sur mon ordi.
              -
              from time import perf_counter
              base = "0123456789"
              n = 20*10**6
              d = len(str(n))
              b = len(base)
              p = 1   #Puissance de la base
              grille = (base * ((n+b-1)//b))[:n]
              grille0 = grille
              for _ in range(1, d):
                  pb = p*b   # Puissance suivante de la base
                  m = (n+pb-1) // pb   # Multiplicateur pour le nombre d'occurences
                  # Ici, les performances diminuent pour la dernière puissance, on en génère trop
                  grille0 = (''.join(grille0[i: i+p]*b for i in range(0, pb, p))*m)[:n]
                  grille += grille0
                  p = pb
              begin=perf_counter()
              nd = n*(d-1)
              b0 = base[0]
              # Les performances diminuent à cause du lstrip()
              liste = [grille[nd+i::-n].lstrip(b0) or b0 for i in range(n)]
              print(round(perf_counter()-begin, 3),"secondes")
              print(liste[0], liste[-1])

              -
              Edité par PierrotLeFou 23 décembre 2021 à 7:34:03

              • Partager sur Facebook
              • Partager sur Twitter

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

                23 décembre 2021 à 10:20:49

                PierrotLeFou a écrit:

                Si on met les 160 millions de caractères dans une seule chaîne et qu'on joue avec le slicing, on accélère beaucoup.
                J'ai des temps de l'ordre de 3.4 secondes.
                -
                from time import perf_counter
                n=20*10**6
                d = len(str(n))
                grid = 'a'*(n*d)
                begin=perf_counter()
                liste = [grid[i: n*d: n] for i in range(n)]
                print(round(perf_counter()-begin, 3),"secondes")
                print(len(liste[0]), liste[0])

                edit:
                Voici ma version complète. Je génère la grille différemment.
                Les performances ne sont pas trop mauvaises malgré le lstrip(). Environ 5 secondes sur mon ordi.
                -
                from time import perf_counter
                base = "0123456789"
                n = 20*10**6
                d = len(str(n))
                b = len(base)
                p = 1   #Puissance de la base
                grille = (base * ((n+b-1)//b))[:n]
                grille0 = grille
                for _ in range(1, d):
                    pb = p*b   # Puissance suivante de la base
                    m = (n+pb-1) // pb   # Multiplicateur pour le nombre d'occurences
                    # Ici, les performances diminuent pour la dernière puissance, on en génère trop
                    grille0 = (''.join(grille0[i: i+p]*b for i in range(0, pb, p))*m)[:n]
                    grille += grille0
                    p = pb
                begin=perf_counter()
                nd = n*(d-1)
                b0 = base[0]
                # Les performances diminuent à cause du lstrip()
                liste = [grille[nd+i::-n].lstrip(b0) or b0 for i in range(n)]
                print(round(perf_counter()-begin, 3),"secondes")
                print(liste[0], liste[-1])

                -
                Edité par PierrotLeFou il y a environ 1 heure


                Merci de ta contribution Pierre que je rappelle ci-dessous :

                from time import perf_counter
                base = "0123456789"
                n = 20*10**6
                d = len(str(n))
                b = len(base)
                p = 1   #Puissance de la base
                grille = (base * ((n+b-1)//b))[:n]
                grille0 = grille
                for _ in range(1, d):
                    pb = p*b   # Puissance suivante de la base
                    m = (n+pb-1) // pb   # Multiplicateur pour le nombre d'occurences
                    # Ici, les performances diminuent pour la dernière puissance, on en génère trop
                    grille0 = (''.join(grille0[i: i+p]*b for i in range(0, pb, p))*m)[:n]
                    grille += grille0
                    p = pb
                nd = n*(d-1)
                b0 = base[0]
                # Les performances diminuent à cause du lstrip()
                liste = [grille[nd+i::-n].lstrip(b0) or b0 for i in range(n)]
                print(liste[0], liste[-1])



                Sur ma machine ton code s'exécute bien plus vite que la précédente version, j'en suis à environ 6.5s. Je suppose que ta boucle for génère les colonnes et que la fin du code (ton triple slice) transpose la grille.

                Remarques en vrac :

                • Le triple slice est en effet une bonne idée
                • Très bonne idée que de supprimer les zéros avec lstrip.  Effectivement, c'est assez coûteux mais cela s'explique par le grand nombre de chaînes à traiter. Toutefois, même sans le lstrip, le temps (4.25s) ne serait pas meilleur que le meilleur temps actuel (qui est de 3,5 s mesuré avec perf_counter)
                • La construction de la grille est chez moi un peu plus longue avec ta méthode (0.750 s contre 0.250s mesuré avec time en console)
                • Comme tu l'as noté, la construction de la grille peut être améliorée en traitant à part la dernière colonne mais l'engorgement n'est pas vraiment là.
                • Partager sur Facebook
                • Partager sur Twitter
                  24 décembre 2021 à 4:33:52

                  @PascalOrtiz: j'ai repris mon code en m'inspirant de ton algo.
                  Je pense que ce qui me coutait cher est ma façon de générer le "bloc" avec le slicing. Multiplier un caractère est plus rapide.

                  Et multiplier une évaluation force à refaire l'évaluation à chaque tour.
                  -
                  from time import perf_counter
                  base = "0123456789"
                  n = 20*10**6
                  d = len(str(n))
                  b = len(base)
                  p = 1   #Puissance de la base
                  grille=""
                  begin=perf_counter()
                  for _ in range(d):
                      pb = p*b   # Puissance suivante de la base
                      m = n//pb
                      r=n%pb
                      bloc=''.join(c*p for c in base)
                      grille += bloc *m+bloc[:r]
                      p = pb
                  print(round(perf_counter()-begin, 3), "secondes")
                  begin=perf_counter()
                  nd = n*(d-1)
                  b0 = base[0]
                  # Les performances diminuent à cause du lstrip()
                  liste = [grille[nd+i::-n].lstrip(b0) or b0 for i in range(n)]
                  print(round(perf_counter()-begin, 3),"secondes")
                  print(len(grille))
                  print(len(liste))
                  print(liste[0], liste[-1])
                  -
                  0.225 secondes                                                                                                          
                  5.184 secondes                                                                                                          
                  160000000                                                                                                               
                  20000000                                                                                                                
                  0 19999999

                  -
                  Edité par PierrotLeFou 24 décembre 2021 à 4:52:13

                  • Partager sur Facebook
                  • Partager sur Twitter

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

                    24 décembre 2021 à 11:50:07

                    PierrotLeFou a écrit:

                    @PascalOrtiz: j'ai repris mon code en m'inspirant de ton algo.
                    Je pense que ce qui me coutait cher est ma façon de générer le "bloc" avec le slicing. Multiplier un caractère est plus rapide.

                    Et multiplier une évaluation force à refaire l'évaluation à chaque tour.
                    -

                    from time import perf_counter
                    base = "0123456789"
                    n = 20*10**6
                    d = len(str(n))
                    b = len(base)
                    p = 1   #Puissance de la base
                    grille=""
                    begin=perf_counter()
                    for _ in range(d):
                        pb = p*b   # Puissance suivante de la base
                        m = n//pb
                        r=n%pb
                        bloc=''.join(c*p for c in base)
                        grille += bloc *m+bloc[:r]
                        p = pb
                    print(round(perf_counter()-begin, 3), "secondes")
                    begin=perf_counter()
                    nd = n*(d-1)
                    b0 = base[0]
                    # Les performances diminuent à cause du lstrip()
                    liste = [grille[nd+i::-n].lstrip(b0) or b0 for i in range(n)]
                    print(round(perf_counter()-begin, 3),"secondes")
                    print(len(grille))
                    print(len(liste))
                    print(liste[0], liste[-1])




                    Merci pour ce code (je l'ai récrit entre balises). Il s'exécute sur ma machine en 0.15+5.85 = 6s. Tu peux légèrement accélérer la génération de la grille en utilisant une liste au lieu d'une expression génératrice qui sont plutôt lentes en Python. Il est étonnant de voir combien la génération de la grille est rapide par rapport à sa transposition. Il y a une autre façon de transposer un tableau 2D t, c'est d'utiliser zip(*t), d'où le code suivant :

                    from time import perf_counter
                    
                    base = "0123456789"
                    n = 20*10**6
                    d = len(str(n))
                    b = len(base)
                    p = 1   #Puissance de la base
                    grille=[]
                    
                    begin=perf_counter()
                    for _ in range(d):
                        pb = p*b   # Puissance suivante de la base
                        m = n//pb
                        r=n%pb
                        bloc=''.join([c*p for c in base])
                        grille.append(bloc *m+bloc[:r])
                        p = pb
                    grille.reverse()
                    print(round(perf_counter()-begin, 3), "secondes")
                    begin=perf_counter()
                    
                    R=[''.join(line).lstrip("0") for line in zip(*grille)]
                    R[0]=base[0]
                    print(round(perf_counter()-begin, 3),"secondes")
                    
                    print(len(R), R[-1])


                    Le temps d'exécution est de l'ordre de 0.13+5.67=5.80 s. Cela m'oblige à modifier ta génération de la grille (ce n'est plus une unique chaîne mais une liste de chaînes). J'inverse l'ordre de la liste pour éviter d'avoir à la faire pour chaque chaîne.

                    Le lstrip a un coût en effet, de plus de 2 secondes (1/3 du temps de transposition). Comme le nombre de zéros dominants est connu (des puissances de la base), un slice serait peut-être plus rapide mais cela nécessite de fractionner le code pour traiter par lots de nombres ayant le même nombre de zéros dominants. Je dirais qu'en fait il est plus simple et peut-être plus rapide de générer au départ plusieurs grilles n'ayant pas de zéros dominants (il y aura peu de grilles : le nombre de chiffres de n). On n'annulera pas complètement le coût du lstrip mais on devrait l'atténuer.

                    • Partager sur Facebook
                    • Partager sur Twitter
                      24 décembre 2021 à 18:49:52

                      On essaie d'optimiser quelque chose qui n'est pas la meilleure solution au départ, mais bon, j'apprend des choses ...
                      Sur mon ordi, ma méthode au total est meilleure.
                      Dans les deux cas, je fais un lstrip()
                      Avec une liste et zip:
                      0.066 secondes                                                                                                          
                      5.79 secondes                                                                                                           
                      8                                                                                                                       
                      20000000                                                                                                                
                      0 19999999                                                                                                               
                      Avec une seule chaîne et slicing:
                      0.228 secondes                                                                                                          
                      5.093 secondes                                                                                                          
                      160000000                                                                                                               
                      20000000                                                                                                                
                      0 19999999                                                                                                               
                      Si j'exclus le 0, il y a 9 nombrres avec 1 chiffre, 90 nombres avec 2 chiffres, 900 nombres avec 3 chiffres, etc.
                      Je vais essayer de jouer là dessus en ajustant le slicing. Je devrais pouvoir faire sauter le lstrip()
                      • Partager sur Facebook
                      • Partager sur Twitter

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

                        24 décembre 2021 à 19:12:56

                        PierrotLeFou a écrit:

                        On essaie d'optimiser quelque chose qui n'est pas la meilleure solution au départ, mais bon, 

                        Nous sommes bien d'accord :).

                        Finalement, j'ai essayé d'écrire ce dont je parlais ci-dessus, voici ce que ça donne :

                        from math import log
                        from time import perf_counter
                        from string import ascii_lowercase as lower
                        
                        
                        def make_cols(n, base):
                        
                            bdigits = ("0123456789" + lower)[:base]
                            if n < base:
                                return list(bdigits[:n + 1])
                        
                            n += 1
                            nch = 1 + int(log(n) // log(base))
                        
                            cols = []
                            s = 1
                            R = [[] for _ in range(nch)]
                        
                            for i in range(nch):
                                sbloc = base * s
                                nblocs = n // sbloc
                                r = n % sbloc
                                bloc = "".join([d * s for d in bdigits])
                                col = nblocs * bloc + bloc[:r]
                                p = s
                                for j in range(i + 1, nch + 1):
                                    pp = p * base
                                    R[j - 1].append(col[p:pp])
                                    p = pp
                                s *= base
                        
                            R = [reversed(z) for z in R]
                            R[0] = [bdigits]
                            return R
                        
                        
                        def compter(n, base):
                        
                            begin = perf_counter()
                            t = make_cols(n, base)
                            print(round(perf_counter() - begin, 3), "secondes")
                            return [''.join(bloc) for blocs in t for bloc in zip(*blocs)]
                        
                        
                        base = 10
                        n = 20 * 10**6
                        
                        begin = perf_counter()
                        R = compter(n, base)
                        print(round(perf_counter() - begin, 3), "secondes")
                        
                        print(len(R), R[-1])
                        

                        qui affiche

                        0.164 secondes
                        3.635 secondes
                        20000001 20000000

                        on n'est plus très loin du temps le plus court obtenu.

                        EDIT Note au passage que même si cet algo ne semble pas la meilleure solution, à la différence  de la solution optimale, la partie la plus coûteuse de l'algo est parallélisable et donc cette solution est potentiellement plus rapide sur un multicoeur.



                        .

                        -
                        Edité par PascalOrtiz 24 décembre 2021 à 19:24:00

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

                          Je n'ai pas pu faire mieux que ton algo. :)
                          Mais j'ai sauvé le temps du lstrip(), du moins je pense:
                          -
                          from time import perf_counter
                          base = "0123456789"
                          n = 20*10**6
                          d = len(str(n-1))
                          b = len(base)
                          p = 1   #Puissance de la base
                          grille=""
                          begin=perf_counter()
                          for _ in range(d):
                              pb = p*b   # Puissance suivante de la base
                              m = n//pb
                              r=n%pb
                              bloc=''.join(c*p for c in base)
                              grille += bloc *m+bloc[:r]
                              p = pb
                          print(round(perf_counter()-begin, 3), "secondes")
                          begin=perf_counter()
                          liste=[base[0]]
                          p=1
                          nd=n*(d-1)
                          nm=nd-n
                          for _ in range(d):
                              pb=min(p*b, n)
                              if nm < 0: nm = 0
                              liste.extend([grille[nd+i: nm: -n] for i in range(p, pb)])
                              nm -= n
                              p=pb
                          print(round(perf_counter()-begin, 3),"secondes")
                          print(len(grille))
                          print(len(liste))
                          print(liste[0], liste[-1])
                          -
                          0.207 secondes                                                                                                          
                          4.268 secondes                                                                                                          
                          160000000                                                                                                               
                          20000000                                                                                                                
                          0 19999999

                          -
                          Edité par PierrotLeFou 24 décembre 2021 à 21:19:15

                          • Partager sur Facebook
                          • Partager sur Twitter

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

                            25 décembre 2021 à 0:53:23

                            Intéressant, tu fais le slice et la suppression des zéros en même temps. 

                            Juste un point : il y a sans doute des corrections à faire car il reste des zéros dominants et la numérotation au début semble incorrecte, par exemple pour n=105 :

                            from time import perf_counter
                            base = "0123456789"
                            n = 105
                            d = len(str(n-1))
                            b = len(base)
                            p = 1   #Puissance de la base
                            grille=""
                            begin=perf_counter()
                            for _ in range(d):
                                pb = p*b   # Puissance suivante de la base
                                m = n//pb
                                r=n%pb
                                bloc=''.join(c*p for c in base)
                                grille += bloc *m+bloc[:r]
                                p = pb
                            print(round(perf_counter()-begin, 3), "secondes")
                            begin=perf_counter()
                            liste=[base[0]]
                            p=1
                            nd=n*(d-1)
                            nm=nd-n
                            for _ in range(d):
                                pb=min(p*b, n)
                                if nm < 0: nm = 0
                                liste.extend([grille[nd+i: nm: -n] for i in range(p, pb)])
                                nm -= n
                                p=pb
                            print(round(perf_counter()-begin, 3),"secondes")
                            print(len(grille))
                            print(len(liste))
                            print(liste[0], liste[-1])
                            print(*liste, sep='\n')

                            qui affiche :

                            0.0 secondes
                            0.0 secondes
                            315
                            105
                            0 104
                            0
                            00
                            00
                            00
                            00
                            00
                            00
                            00
                            00
                            00
                            010
                            011
                            012
                            013
                            014
                            015
                            016
                            017
                            018
                            019
                            020
                            021
                            022
                            023
                            024
                            025
                            026
                            027
                            028
                            029
                            030
                            031
                            032
                            033
                            034
                            035
                            036
                            037
                            038
                            039
                            040
                            041
                            042
                            043
                            044
                            045
                            046
                            047
                            048
                            049
                            050
                            051
                            052
                            053
                            054
                            055
                            056
                            057
                            058
                            059
                            060
                            061
                            062
                            063
                            064
                            065
                            066
                            067
                            068
                            069
                            070
                            071
                            072
                            073
                            074
                            075
                            076
                            077
                            078
                            079
                            080
                            081
                            082
                            083
                            084
                            085
                            086
                            087
                            088
                            089
                            090
                            091
                            092
                            093
                            094
                            095
                            096
                            097
                            098
                            099
                            100
                            101
                            102
                            103
                            104
                            




                            • Partager sur Facebook
                            • Partager sur Twitter
                              25 décembre 2021 à 2:45:51

                              Pas évident à visualiser ... le jeu des indices. C'est comme descendre en diagonale.
                              Je ne faisais pas les choses de la bonne façon. Le code suivant devrait être correct ...

                              P.S. Joyeux Noël!
                              -
                              from time import perf_counter
                              base = "0123456789"
                              n = 105 # 20*10**6
                              d = len(str(n-1))
                              b = len(base)
                              p = 1   #Puissance de la base
                              grille=""
                              begin=perf_counter()
                              for _ in range(d):
                                  pb = p*b   # Puissance suivante de la base
                                  m = n//pb
                                  r=n%pb
                                  bloc=''.join(c*p for c in base)
                                  grille += bloc *m+bloc[:r]
                                  p = pb
                              print(round(perf_counter()-begin, 3), "secondes")
                              begin=perf_counter()
                              liste=[base[0]]
                              p=1
                              nd=0
                              for _ in range(d):
                                  pb=min(p*b, n)
                                  liste.extend([grille[nd+i: 0: -n] for i in range(p, pb)])
                                  p=pb
                                  nd += n
                              print(round(perf_counter()-begin, 3),"secondes")
                              print(len(grille))
                              print(len(liste))
                              print(liste[1], liste[-1])
                              print(*liste)

                              -
                              S'il existait une variante de zip qui pourrait "zipper" N-1   éléments, on pourrait placer les colonnes à l'envers et supprimer la dernière séquence de 0 comme suit:
                              999999999988888888887777777777666666666655555555554444444444333333333322222222221111111111
                              987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321
                              On aurait: 99, 98, ... , 10, 9, 8, ..., 2, 1
                              Il suffirait de placer les colonnes dans le bon ordre pour avoir les nombres sans faire de reverse.
                              On ferait un reverse sur toute la liste à la fin.

                              -
                              Edité par PierrotLeFou 25 décembre 2021 à 7:55:07

                              • Partager sur Facebook
                              • Partager sur Twitter

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

                                25 décembre 2021 à 8:57:47

                                PierrotLeFou a écrit:

                                Pas évident à visualiser ... le jeu des indices. C'est comme descendre en diagonale.
                                Je ne faisais pas les choses de la bonne façon. Le code suivant devrait être correct ...



                                Joyeux Noël à toi aussi ! Cette fois la sortie est correcte et le temps est aussi excellent, joli travail.

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  26 décembre 2021 à 7:40:33

                                  Faute de ne pas avoir battu de record ... j'ai pu générer la liste à partir de la grille en une seule ligne.
                                  -
                                  from time import perf_counter
                                  base = "0123456789"
                                  n = 20*10**6
                                  d = len(str(n-1))
                                  b = len(base)
                                  p = 1
                                  grille = [[] for _ in range(d)]
                                  begin=perf_counter()
                                  for i in range(d):
                                      pb = p*b
                                      m = n//pb
                                      r=n%pb
                                      bloc=''.join(c*p for c in base)
                                      grille[i] = (bloc *m+bloc[:r])
                                      p = pb
                                  print("grille:", round(perf_counter()-begin, 3), "secondes")
                                  begin=perf_counter()
                                  liste = [base[0]] + [''.join(s) for i in range(d) for s in zip(*(grille[i-t][b**i:min(b**(i+1), n)] for t in range(i+1)))]
                                  print("liste:", round(perf_counter()-begin, 3), "secondes")
                                  print(len(grille))
                                  print(len(liste))
                                  print(*liste[:5], "...", *liste[-5:])
                                  -
                                  grille: 0.068 secondes                                                                                                  
                                  liste: 4.165 secondes                                                                                                   
                                  8                                                                                                                       
                                  20000000                                                                                                                
                                  0 1 2 3 4 ... 19999995 19999996 19999997 19999998 19999999
                                  • Partager sur Facebook
                                  • Partager sur Twitter

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

                                    26 décembre 2021 à 9:42:40

                                    Prochaine étape : paralléliser la génération de la grille :)
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      26 décembre 2021 à 15:13:52

                                      Je suppose que ça se fait avec les thread. Je n'ai pas encore fait de thread en Python.
                                      J'ai trouvé plusieurs tutoriels sur le sujet, en as-tu un bon?
                                      J'ai un processeur 4 coeurs "multi-threading" du côté hardware.
                                      Ne pourrait-on pas générer la liste en parallèle également? Je suppose que c'est moins évident de rassembler les   morceaux d'une liste avec les thread.
                                      • Partager sur Facebook
                                      • Partager sur Twitter

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

                                        26 décembre 2021 à 17:16:27

                                        PierrotLeFou a écrit:

                                        Je suppose que ça se fait avec les thread. Je n'ai pas encore fait de thread en Python.
                                        J'ai trouvé plusieurs tutoriels sur le sujet, en as-tu un bon?
                                        J'ai un processeur 4 coeurs "multi-threading" du côté hardware.
                                        Ne pourrait-on pas générer la liste en parallèle également? Je suppose que c'est moins évident de rassembler les   morceaux d'une liste avec les thread.


                                        Les threads en Python ne permettent pas d'exploiter les multi-coeurs. Il te faut utiliser le module standard multiprocessing. Pour faire un produit de matrices parallélisé, j'avais utilisé la méthode map d'un objet de type Pool, je ne peux t'en dire plus je ne l'ai plus en tête mais j'ai le vague souvenir que c'était très simple à utiliser. Avec un quadcore, le temps avait été divisé autour de 3,5 je crois.
                                        • 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