Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 4, in liste_croissante
TypeError: '<' not supported between instances of 'str' and 'int'
tu essais de comparer une chaine (i) à un entier (len(l)) ce qui n'est pas faisable. D'ailleurs, pourquoi comparer la 1er valeur à la longueur de la liste ? i ne devrait pas juste être un indice ? (ou on peut même s'en passer)
Cette fonction sera plus rapide si la liste n'est pas en ordre croissant. On sort dès que ça ne marche pas. - def liste_croissante(L): r = 0 while r < len(L)-1: if L[r] > L[r+1]: return False r += 1 return True
Le Tout est souvent plus grand que la somme de ses parties.
Cette fonction sera plus rapide si la liste n'est pas en ordre croissant. On sort dès que ça ne marche pas. - def liste_croissante(L): r = 0 while r < len(L)-1: if L[r] > L[r+1]: return False r += 1 return True
Du point de vue temps, je doute que ça change grand chose. La bonne façon de faire (si une fonction est à coder) est d'utiliser une boucle for et pas while. Non seulement le temps devrait être sensiblement meilleur (un luxe à vrai dire) mais ce sera plus lisible et moins sujet à erreur. En outre il ne faut pas recalculer à chaque tour de boucle la longueur de la liste alors qu'elle n'a pas changé.
Je pensais que le PO n'avais pas droit au for (on en voit souvent de ce genre) Cette version devrait être un peu mieux. Comme je l'ai dit, cette variante sera plus rapide si la liste n'est pas ordonnée car on ne se rend pas jusqu'au bout. - def liste_croissante(L): lg = len(L)-1 for i in range(lg): if L[i] > L[i+1]: return False return True
Le Tout est souvent plus grand que la somme de ses parties.
Je pensais que le PO n'avais pas droit au for (on en voit souvent de ce genre) Cette version devrait être un peu mieux. Comme je l'ai dit, cette variante sera plus rapide si la liste n'est pas ordonnée car on ne se rend pas jusqu'au bout.
C'est aussi le cas de la version qu'il avait proposée qui est équivalente algorithmiquement à ce que tu as écrit.
La version que tu viens de donner :
PierrotLeFou a écrit:
def liste_croissante(L):
lg = len(L)-1
for i in range(lg):
if L[i] > L[i+1]:
return False
return True
me paraît être la seule façon correcte de faire (tu peux laisser len(L)-1 dans le range, ça ne jouera pas sur le temps).
Comme je l'ai dit la boucle while est plus lente que la boucle for et est moins lisible. Le fait de recalculer len(L) à chaque tour de boucle entraîne une pénalisation non négligeable. Voici quelques tests sur une liste croissante de 10 millions de nombres placée dans un fichier :
from time import perf_counter
def estCroissante_for(L):
for i in range(len(L)-1):
if L[i]>L[i+1]:
return False
return True
def estCroissante_while_len(L):
r = 0
while r < len(L)-1:
if L[r] > L[r+1]:
return False
r += 1
return True
def estCroissante_while(L):
r = 0
n=len(L)
while r < n-1:
if L[r] > L[r+1]:
return False
r += 1
return True
def estCroissante_while_noif(L):
r = 0
n=len(L)
m=n-1
while r < m and L[r] <= L[r+1]:
r += 1
return r==n-1
begin_perf = perf_counter()
L=[int(z) for z in open("test10M.in").read().split()]
delta = perf_counter() - begin_perf
print(f"Génération test : {delta:.2f}s")
begin_perf = perf_counter()
print(estCroissante_for(L))
delta = perf_counter() - begin_perf
print(f"for : {delta:.2f}s")
begin_perf = perf_counter()
print(estCroissante_while_len(L))
delta = perf_counter() - begin_perf
print(f"while + len : {delta:.2f}s")
begin_perf = perf_counter()
print(estCroissante_while(L))
delta = perf_counter() - begin_perf
print(f"while : {delta:.2f}s")
begin_perf = perf_counter()
print(estCroissante_while_noif(L))
delta = perf_counter() - begin_perf
print(f"while noif: {delta:.2f}s")
qui affiche
Génération test : 2.13s
True
for : 0.68s
True
while + len : 1.51s
True
while : 1.14s
True
while noif: 0.94s
Comme tu peux l'observer, le simple fait de ne pas mémoriser la longueur entraîne une pénalisation de 25%. Et la boucle for est clairement plus rapide.
On peut essayer de faire mieux que la boucle for ci-dessus. Utiliser all :
def estCroissante_all(L):
return all(L[i]<=L[i+1] for i in range(len(L)-1))
est 40 % moins rapide. Ce qui est coûteux sont les accès aux éléments d'une liste, donc le L[i] et le L[i+1]. Donc une première tentative d'améliorer est
def estCroissante_zip(L):
for a,b in zip(L,L[1:]):
if a>b:
return False
return True
qui donne 0.48s donc 40% meilleur que la simple boucle for. Ce code reste ralenti par le slice qui fait une copie de 10 millions de pointeurs (truc mal fait en Python : on ne peut pas itérer partiellement sans indice sur une séquence autrement que par un slice alors que l'infrastructure C le permet à coût nul).
L'idée serait de s'affranchir complètement des accès par indice et il se trouve qu'ici, on peut le faire :
def estCroissante_for_noindex(L):
it = iter(L)
next(it)
old = L[0]
for a in it:
if old > a:
return False
old = a
return True
ce qui donne un temps de 0.24s autrement dit 65% meilleur que la simple boucle for.
J'avais pensé au all() mais je pensais que c'était trop simple pour l'exercice. Mais avec iter c'est fantastique! Combien de fois j'ai dû faire du slicing pour partir du deuxième élément.
J'ai fait le test suivant: >>> L=[1,2,3,4] >>> it = iter(L) >>> a=next(it);a 1 >>> for i in it: ... print(i) ... 2 3 4 >>> Le next me donne directement le premier élément, je n'ai pas besoin de faire a=L[0]
- Edité par PierrotLeFou 26 novembre 2021 à 19:58:35
Le Tout est souvent plus grand que la somme de ses parties.
Bonsoir, le code que j'avais écrit fonctionne pour toutes les suites sauf pour la liste vide, je ne vois pas comment faire, pourriez vous la modifier ? merci.
Je vous remets la fonction ci-dessous. Elle doit garder la même synthaxe
def liste_croissante(l):
r=0
while r<len(l)-1 and l[r]<=l[r+1] :
r=r+1
return r==len(l)-1
Bonsoir, le code que j'avais écrit fonctionne pour toutes les suites sauf pour la liste vide, je ne vois pas comment faire, pourriez vous la modifier ? merci.
Je vous remets la fonction ci-dessous. Elle doit garder la même synthaxe
def liste_croissante(l):
r=0
while r<len(l)-1 and l[r]<=l[r+1] :
r=r+1
return r==len(l)-1
Ce n'est pourtant pas compliqué, il suffit juste de compléter le return déjà écrit de manière adéquate. L'interdiction de faire un return True est assez factice et se contourne facilement. Comme signalé plus haut, ton code utilise de pratiques à ne pas recommander : le fait de ne pas placer len(l) -1 dans une variable et le fait d'utiliser la lettre minuscule l pour une variable, ce qui se confond trop facilement avec le caractère 1.
Par ailleurs, ton code initial ne me paraît pas naturel et celui qui va tester si r vaut le premier indice interdit (à savoir len(l)) me semble plus conforme à la logique de l'intervalle semi-fermé du range. Si ton début de code était plutôt :
def liste_croissante(l):
r=1
while r<len(l) and l[r-1]<=l[r] :
r=r+1
return ????
for L in [[1], [1,2], [2,1],range(42, 81, 3), range(-42, -81, -3),list(range(10))+[8], []]:
print(L, liste_croissante(L))
avec un return à peine modifié, on aurait une réponse correcte dans tous les cas, je te laisse remplir les points d'interrogation.
le code FAIT le bonheur (pour moi en tous cas)
le code FAIT le bonheur (pour moi en tous cas)
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