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
@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 ...
Le Tout est souvent plus grand que la somme de ses parties.
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.
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.
Le Tout est souvent plus grand que la somme de ses parties.
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])
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
Le Tout est souvent plus grand que la somme de ses parties.
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à.
@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
Le Tout est souvent plus grand que la somme de ses parties.
@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.
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()
Le Tout est souvent plus grand que la somme de ses parties.
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
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
Le Tout est souvent plus grand que la somme de ses parties.
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')
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
Le Tout est souvent plus grand que la somme de ses parties.
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.
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
Le Tout est souvent plus grand que la somme de ses parties.
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.
Le Tout est souvent plus grand que la somme de ses parties.
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.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères