Partage
  • Partager sur Facebook
  • Partager sur Twitter

[Python] fonction croissante

    25 novembre 2021 à 19:00:56

    Bonjour, je dois écrire une fonction qui renvoie True si la liste est croissante.

    Je l'ai alors écrite mais elle ne fonctionne pas sur les listes contenant des chaines.Pourriez-vous la corriger svp?

    def liste_croissante(l):
        i=l[0]
        k=0
        while i<len(l) and l[k]<=l[k+1] :
                i=i+1
                k=k+1
        return i==len(l)



    • Partager sur Facebook
    • Partager sur Twitter
      25 novembre 2021 à 19:19:31

      le message d'erreur est clair 

      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)

      • Partager sur Facebook
      • Partager sur Twitter
        25 novembre 2021 à 20:10:14

        def liste_croissante(l):
            r=0
            while l[r]<=l[r+1] :
                    r=r+1
            return r==len(l)

        J'ai modifié pour la fonction ci-dessus mais maintenant elle ne fonctionne plus pour les listes numériques, puisqu'on sort de l'intervalle :(

        • Partager sur Facebook
        • Partager sur Twitter
          25 novembre 2021 à 20:40:45

          Si r est l'indice qui permet de comparer 2 éléments successifs de la liste sa valeur ne doit pas dépasser len(l) - 1.

          Le premier code que vous avez posté n'était pas si mauvais vous vous êtes planté de variable.

          • Partager sur Facebook
          • Partager sur Twitter
            25 novembre 2021 à 20:58:29

            Ahhh oui !

            J'ai donc réécrit :

            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

            Est-ce correct ? Merci :)

            • Partager sur Facebook
            • Partager sur Twitter
              25 novembre 2021 à 21:26:08

              bonjour, ce code peut s'écrire en une ligne:

              liste_croissante = lambda liste: sorted(liste) == liste

              facon pratique pour savoir si une liste est croissant



              • Partager sur Facebook
              • Partager sur Twitter

              le code FAIT le bonheur (pour moi en tous cas)

                25 novembre 2021 à 21:28:03

                Oui bien-sûr mais puisque je dois écrire une fonction qui vérifie que la liste est croissante, je n'ai pas le droit d'utiliser 'sorted()' :)
                • Partager sur Facebook
                • Partager sur Twitter
                  25 novembre 2021 à 21:29:44

                  ah bah alors ton code est trés bien!:)
                  • Partager sur Facebook
                  • Partager sur Twitter

                  le code FAIT le bonheur (pour moi en tous cas)

                    26 novembre 2021 à 3:05:12

                    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
                    • Partager sur Facebook
                    • Partager sur Twitter

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

                      26 novembre 2021 à 16:15:18

                      PierrotLeFou a écrit:

                      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é.
                      • Partager sur Facebook
                      • Partager sur Twitter
                        26 novembre 2021 à 18:09:08

                        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
                        • Partager sur Facebook
                        • Partager sur Twitter

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

                          26 novembre 2021 à 18:51:42

                          PierrotLeFou a écrit:

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

                          La version du PO teste r<len(l)-1 and l[r]<=l[r+1]. ça ne testera tout que si la liste est ordonnée.
                          • Partager sur Facebook
                          • Partager sur Twitter
                            26 novembre 2021 à 18:54:06

                            PierrotLeFou a écrit:

                            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.





                            • Partager sur Facebook
                            • Partager sur Twitter
                              26 novembre 2021 à 19:45:05

                              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

                              • Partager sur Facebook
                              • Partager sur Twitter

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

                                26 novembre 2021 à 20:50:29

                                PierrotLeFou a écrit:

                                Le next me donne directement le premier élément, je n'ai pas besoin de faire a=L[0]


                                Effectivement, je l'ai vu après.
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  5 décembre 2021 à 20:22:35

                                  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



                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    5 décembre 2021 à 20:31:00

                                    A priori, si la liste est vide, ça retourne False. Ce qui me semble correct.
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      5 décembre 2021 à 20:57:27

                                      Oui c'est ce que j'obtiens avec cette fonction-ci mais le professeur veut que l'appel de la fonction sur [] renvoie True :/
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        5 décembre 2021 à 22:50:34

                                        Tester explicitement la longueur de la liste et retourner True si elle est nulle avant les autres instructions devrait marcher...
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          6 décembre 2021 à 1:14:40

                                          Le code que je proposais le 26 nov devrait fonctionner également pour une liste vide.
                                          • Partager sur Facebook
                                          • Partager sur Twitter

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

                                            6 décembre 2021 à 9:32:56

                                            Le problème c'est que je n'ai le droit d'inclure ni 'return True' ou 'return False' dans la fonction, ni 'print()'
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              6 décembre 2021 à 11:00:42

                                              LilililiMimimimi a écrit:

                                              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.



                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                6 décembre 2021 à 14:37:57

                                                LilililiMimimimi a écrit:

                                                Le problème c'est que je n'ai le droit d'inclure ni 'return True' ou 'return False' dans la fonction, ni 'print()'


                                                Dans ce cas, il faut faire un peu de logique: vous savez que A ou B sera vrai si A et si A est faux, ce sera B.

                                                Ici le A est la condition r==len(l)-1, reste à trouver B.

                                                • Partager sur Facebook
                                                • Partager sur Twitter

                                                [Python] fonction croissante

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