Partage
  • Partager sur Facebook
  • Partager sur Twitter

[Exercice] trouver les dix plus grands nombres

sans utiliser sort...

    4 août 2011 à 16:10:09

    Bonjour,

    Je vous propose de résoudre ce petit problème (pas bien dur) :

    Nous devons trouver les dix plus grands nombres dans un iterable sans faire appel à la fonction sort() ou sorted().

    En pratique, cet algo peut se révéler très utile, par exemple dans le cas ou il y a énormément de valeurs à filtrer (fichier de log par exemple), car ce ne sera pas forcément évident de tout stocker en mémoire pour trier (on parle de complexité mémoire)...

    Donc pour simuler ce contexte, je vous propose d'utiliser un générateur, comme ceci :
    from random import randint
    
    # génère n entiers compris entre a et b
    def gen(n, a, b):
        for i in range(n):
            yield randint(a, b)
    
    # ou bien, pour ceux qui préfèrent les 'one-liner'
    gen = lambda n, a, b: (randint(a,b) for i in range(n))
    


    Ensuite, nous allons créer une fonction dix_maxi(), et l'appeler comme ceci :
    dix_maxi(gen(n, start, stop))
    


    Cette fonction doit nous renvoyer une liste (ou ce que vous voulez) contenant les dix plus grands nombres générés. Les nombres retournés ne doivent pas forcément être ordonnés, faites ce que vous voulez de ce coté là.

    Dans un second temps, vous devez essayer de rendre votre fonction générique, afin de pouvoir renvoyer les N éléments maximums. Essayez de faire en sorte que votre fonction soit un minimum performante même avec de grandes valeurs de N.

    Astuce :
    certains modules de la lib standard peuvent vous aider (je ne dis pas lesquels, ce serait trop facile)


    PS : prière de mettre les réponses en secret, pour que tout le monde puisse réfléchir.

    [edit] : Ajout de la possibilité de faire une fonction générique, ainsi qu'un petit mot sur la complexité.
    • Partager sur Facebook
    • Partager sur Twitter
    Anonyme
      4 août 2011 à 17:07:58

      Bon j'ai pas fais gaffe aux noms de fonctions.

      Je l'ai fais en POO, ça m'aide dans mon organisation.

      Pour les puristes, j'aurais pu hériter de list et utiliser super(), mais je voulais garder quelque-chose d'accessible pour les débutants en POO.

      from random import randint
      
      class Conteneur(object):
          def __init__(self, ma_liste):
              self.c = []
              self.liste = ma_liste
              self.compteur = 0
          def retirer(self):
              maxi = max(self.liste)
              index = self.liste.index(maxi)
              pop = self.liste.pop(index)
              return pop
          def ajouter(self):
              value = self.retirer()
              if value not in self.c:
                  self.c.append(value)
                  self.compteur += 1
          def __repr__(self):
              return repr(self.c)
      
      def main(a, b, n_randint, n_maxi):
          liste = [randint(a, b) for i in range(n_randint)]
          c = Conteneur(liste)
          while c.compteur != n_maxi:
              c.ajouter()
          print(c)
      
      main(1, 500, 30, 10)
      


      Pour les puristes

      from random import randint
      
      class Conteneur(list):
          def __init__(self, ma_liste):
              super(Conteneur, self).__init__(self)
              self.liste = ma_liste
              self.compteur = 0
          def retirer(self):
              maxi = max(self.liste)
              index = self.liste.index(maxi)
              pop = self.liste.pop(index)
              return pop
          def ajouter(self):
              value = self.retirer()
              if value not in self:
                  self.append(value)
                  self.compteur += 1
          def __str__(self):
              return repr(self)
      
      def main(a, b, n_randint, n_maxi):
          liste = [randint(a, b) for i in range(n_randint)]
          c = Conteneur(liste)
          while c.compteur != n_maxi:
              c.ajouter()
          print(c)
      
      main(1, 500, 30, 10)
      
      • Partager sur Facebook
      • Partager sur Twitter
        4 août 2011 à 17:45:49

        Euhm, j'ai pas bien compris fred1599, tu fais à la fois de l'encapsulation et de l'héritage ?
        • Partager sur Facebook
        • Partager sur Twitter
        yjltg.
          4 août 2011 à 17:57:26

          @ fred1599 :
          Merci pour ta participation. :)

          Je ne sais pas pourquoi tu l'as fait en POO, ça alourdit le code, mais enfin libre à toi.

          Une petite explication sur ton algo à l'attention des lecteurs ne serait pas de refus ;) .

          3 points ont retenus mon attention : si je comprends bien, tu parcours la liste 10 fois et tu extrais le maximum. Donc en fait, tu dois parcourir 10 fois la liste.

          1. Maintenant, imagine que tu doive récupérer les 1000 plus grandes valeurs d'une liste de 1000000 d'éléments. A ce moment là, ton approche ne sera plus du tout adaptée.

          2. Deuxième problème: j'ai donné l'exemple d'un fichier de log et de contraintes mémoire. Il est bien connu que l’accès au disque est particulièrement couteux en termes de temps. Donc le fait de devoir relire à chaque fois toutes les données va encore enfoncer les performances.

          3. Tu profites d'avoir tes données dans une liste pour appliquer ta methode en supprimant à chaque fois l'élément trouvé. Imagine toi que cette liste soit en lecture seule : à ce moment, ton approche n'est plus valable.

          C'est vrai que ce n'est pas inclus dans les contraintes explicites de l'exo, mais il serait intéressant de prendre cela en compte. Je te suggère d'utiliser le générateur que j'ai proposé ci-dessus, ça te poussera sûrement à coder un algo différent ;) .

          EDIT : Ajout du 3e point.
          • Partager sur Facebook
          • Partager sur Twitter
          Anonyme
            4 août 2011 à 17:58:59

            Citation

            Euhm, j'ai pas bien compris fred1599, tu fais à la fois de l'encapsulation et de l'héritage ?



            Encapsulation? Quelle est la définition d'encapsulation pour toi?

            De l'héritage, oui pour la 2ème solution

            • Partager sur Facebook
            • Partager sur Twitter
              4 août 2011 à 19:31:52

              Bref, peu importe. Voici ma solution:
              def maximums(liste, n=10):
                  liste = iter(liste)
                  bar = [next(liste) for _ in range(n)]
                  # on prend les dix premiers elements comme liste de maximums.
                  while True:
                      indice, minimum = min(enumerate(bar), key=lambda a:a[1])
                      # on prend ensuite le plus petit element de la liste des maximums
                      try:
                          i = next(liste)
                      except StopIteration:
                          break
                      if i> minimum:
                          bar[indice] = i
                      # et on le compare avec l'element courant de la liste.
                  return bar
              


              Et désolé pour les noms, j'avais pas beaucoup d'inspiration.
              • Partager sur Facebook
              • Partager sur Twitter
              yjltg.
                4 août 2011 à 20:07:20

                def maximums(iterable,n=10):
                    out = []
                    it = iterable[:]
                    while it and len(out)<10: out.append(it.pop(it.index(max(it))))
                    return out
                
                • Partager sur Facebook
                • Partager sur Twitter
                  4 août 2011 à 20:08:24

                  Bonjour, merci pour l'exercice, voici ma solution j'ai été obligé de créer une liste (liste1) je n'ai pas su faire autrement:

                  from random import randint
                  
                  def dix_maxi(iterable):
                      
                      l1,l2 = list(),list()
                      [l1.append(x) for x in iterable]
                      maxi = max(l1)
                      for _ in range(10):
                          for x in l1:
                              if x == maxi:
                                  if not x in l2:
                                      l2.append(x)
                                  l1.remove(x)
                          maxi = max(l1)
                      l2.reverse()
                      return l2
                  
                  gen = lambda n,a,b: (randint(a,b) for i in range(n))
                              
                  print(dix_maxi(gen(20,10,100)))
                  


                  Edit : excellente la solution Josmiley, j'ai honte maintenant.
                  En plus j'ai fais n'importe quoi je vais recommencer.
                  • Partager sur Facebook
                  • Partager sur Twitter
                    4 août 2011 à 20:22:47

                    en plus court mais je pense moins efficace que le précédent ...
                    def maximums(iterable,n=10):
                        it = iterable[:]
                        return [it.pop(it.index(max(it))) for i in range(10) if len(it)]
                    
                    • Partager sur Facebook
                    • Partager sur Twitter
                    Anonyme
                      4 août 2011 à 20:41:11

                      Voilà la mienne nettement plus efficace que la 1ère

                      from random import randint
                      
                      gen = lambda n, a, b: (randint(a,b) for i in range(n))
                      
                      def maxi(liste):
                          liste = set(liste)
                          for i in range(10):
                              if liste:
                                  m = max(liste)
                                  liste.remove(m)
                                  yield m
                      
                      print [i for i in maxi(gen(10000,1,1000000))]
                      
                      • Partager sur Facebook
                      • Partager sur Twitter
                        4 août 2011 à 23:33:27

                        WoW ! Déjà plein de réponses, à ce que je vois. Ça fait plaisir ! :)

                        @ quelqun_dautre :
                        C'est vraiment très bien, comme tu as fait. Tu prends en compte mes remarques 2. et 3. ci-dessus.
                        Maintenant, ton code est toujours en O(nk) (k = taille de la liste, n = nombre d'éléments à extraire), on peut faire mieux avec une astuce. ;)

                        Au passage, c'est intéressant de noter les contorsions que tu es obligé de faire pour récupérer l'index de max sans traverser 2 fois la liste (avec index()). Cela montre une certaine limitation du langage, me semble il.

                        @ josmiley :
                        Très bon code, clair et concis. :) J'ai testé le premier code, et je suis très impressionné par les performances, alors que ton algo me semble aussi en O(nk).

                        Maintenant, si on cherche par exemple les 500 plus grands nombres, les performances s'effondrent un peu.

                        Petite correction (premier code) : tu déclare n=10, mais tu utilise la constante 10 à la place de n dans le code.

                        @ fred1599 :
                        Tres bonne idée, que d'utiliser un set(). Au niveau complexité, c'est une excellente solution, à laquelle je n'avais pas pensé. ;)

                        Le seul cas ou ce ne sera pas adapté est le cas d'une contrainte mémoire, par exemple si on lit séquentiellement un fichier de plusieurs To., le set() risque de saturer la mémoire.

                        EDIT : Non, en fait c'est une fausse bonne idée, car tu vas supprimer les doublons, comme signalé plus bas par PsycoPy. La solution serait d'utiliser un dictionnaire, ou un Counter(), ou autre...


                        Il existe une technique pour améliorer l'approche de quelqun_dautre et josmiley. Réfléchissez bien... ;)
                        • Partager sur Facebook
                        • Partager sur Twitter
                          5 août 2011 à 1:07:33

                          Merde j'ai loupé ça, demain je pond un truc!

                          Juste comme ça direct un tas, non?

                          Bel exo Yoch.

                          • Partager sur Facebook
                          • Partager sur Twitter
                          Zeste de Savoir, le site qui en a dans le citron !
                            5 août 2011 à 9:03:27

                            Citation : GurneyH

                            Juste comme ça direct un tas, non?


                            Yes ! :magicien:

                            J'attends encore un peu avant de poster ma solution...
                            • Partager sur Facebook
                            • Partager sur Twitter
                              5 août 2011 à 10:29:04

                              Voilà ma solution.

                              Bon j'ai utilisé sort(), mais pas pour trier la séquence dans laquelle on cherche les maximums. En fait c'est la liste des maximums que je trie. L'argument pour ne pas utiliser sort() est que la séquence d'intérêt peut être très grande, et on aurait un problème de complexité mémoire. Quand on veut extraire n éléments, il me semble raisonnable d'utiliser sort() sur une liste de n éléments, voire 2n éléments (c'est ce que fait mon algo).

                              Certains considèrerons peut être que c'est de la triche, mais je pense rester dans l'esprit du problème original.

                              Du coup, comme complexité (à vérifier...), si on cherche n éléments maximums dans une séquence de longueur k :
                              - mémoire : 2n
                              - temporelle : 2k(1+log(2n))

                              def extract_best( tmp, best, n ) :
                                  best.extend(tmp)
                                  best.sort()
                                  return best[-n:]
                              
                              def n_maxi( seq, n = 10 ) :
                                  best = []
                                  tmp = []
                                  for i in seq :
                                      tmp.append(i)
                                      if len(tmp) == n :
                                          best = extract_best(tmp, best, n)
                                          tmp = []
                                  best = extract_best(tmp, best, n)
                                  return best
                              
                              print n_maxi(gen(1000000,-1000000, 1000000), 1000)
                              
                              • Partager sur Facebook
                              • Partager sur Twitter
                              Anonyme
                                5 août 2011 à 10:50:45

                                f = lambda it, n: list(set(it))[-n:]
                                


                                Bon, C'est peut-être un peu de la triche... :-°
                                Mais ça marche plutôt bien et ça évite de modifier la liste de départ.

                                [edit] le défaut c'est que ça supprime les doublons.
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  5 août 2011 à 11:13:07

                                  Citation : quark

                                  Certains considèrerons peut être que c'est de la triche, mais je pense rester dans l'esprit du problème original.


                                  Non, c'est très bien je trouve. Si on s'en tient à l'énoncé stricto-sensu, on pourrait par exemple recoder sort() :p

                                  Sinon, ton approche est vraiment intéressante. On peut simplifier, mais la tienne est nettement plus performante (beaucoup moins d'appels à sort) :
                                  def n_maxi( seq, n = 10 ) :
                                      best = []
                                      for i in seq :
                                          best.append(i)
                                          if len(best) > n:
                                              best = sorted(best)[1:]
                                      return best
                                  


                                  En fait, on peut réécrire ton approche comme ceci, il me semble (on peut très facilement jouer sur la complexité mémoire, cf. ligne 5) :
                                  def n_maxi( seq, n = 10 ) :
                                      best = []
                                      for i in seq :
                                          best.append(i)
                                          if len(best) == 2 * n:
                                              best = sorted(best)[-n:]
                                      return sorted(best)[-n:]
                                  


                                  Pour la complexité temporelle, je crois que c'est moins que ça. Je dirais un truc comme (un horreur simplifiée par Maxima) : <math>\(\frac{{k}^{2}\,ln\left( 2\,n\,ln\left( 2\,n\right) \right) }{2\,n}\)</math>.

                                  A confirmer par un matheux, parce que c'est pas tout à fait mon truc... :-°

                                  EDIT :

                                  Citation : PsycoPy

                                  [edit] le défaut c'est que ça supprime les doublons.


                                  Ah oui, merci, j'avais pas fait gaffe effectivement.

                                  Je propose une solution de rechange ci-dessus.
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                  Anonyme
                                    5 août 2011 à 11:21:35

                                    vraiment très intéressant ce qu'on peut voir comme solution pour un exercice où on a tendance à utiliser une méthode naïve.

                                    J'aime bien la solution de quark, mais contrôle-t-il les doublons dans son résultat final?
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      5 août 2011 à 11:31:27

                                      Citation : yoch


                                      Pour la complexité temporelle, je crois que c'est moins que ça. Je dirais un truc comme (un horreur simplifiée par Maxima) : <math>\(\frac{{k}^{2}\,ln\left( 2\,n\,ln\left( 2\,n\right) \right) }{2\,n}\)</math>.



                                      Je ne pense pas que ton expression soit correcte (pourquoi k est il au carré?), et en fait la complexité de mon algo (pas ta version modifiée qui diminue un peu la complexité temporelle) serait plutôt <math>\(k(1+2(1+\log(2n)))\)</math>, mais je ne suis pas vraiment sur...

                                      Quoi qu'il en soit la méthode est rapide et se comporte bien si on augmente k et/ou n.

                                      @fred1599 : ma méthode peut renvoyer des doublons dans le résultat final. L'énoncé initial ne précise pas qu'on ne doit pas en renvoyer, et dans certaines applications il peut être utile d'avoir ces doublons. Après il doit être possible de les éliminer, mais ça pose des problèmes dans des cas particuliers, par exemple si la liste initiale contient k fois le même nombre...
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        5 août 2011 à 12:41:52

                                        Je viens de découvrir que python fournissait un tas, je partais pour en coder un. :-°

                                        Je n'ai pas fait de tests, mais ça me semble un peu lent.
                                        from random import randint
                                        import heapq
                                        
                                        N = 1000
                                        MAX = 10000
                                        
                                        def gen(n, a, b):
                                            for i in range(n):
                                                yield randint(a, b)
                                        
                                        def dix_maxi(g):
                                            hp, res = [], []
                                            for value in g:
                                                heapq.heappush(hp, -value)
                                        
                                            for _ in range(10):
                                                res.append(-heapq.heappop(hp))
                                        
                                            return res
                                        
                                        
                                        print dix_maxi(gen(N, 0, MAX))
                                        


                                        edit: en fait, non ça semble très correct niveau temps, testé avec cette fonction
                                        def n_maxi(g, n = 10):
                                            hp, res = [], []
                                            for value in g:
                                                heapq.heappush(hp, -value)
                                        
                                            for _ in range(n):
                                                res.append(-heapq.heappop(hp))
                                        
                                            return res
                                        


                                        Les perfs sont convenables même avec de grandes valeurs de N.
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                        Zeste de Savoir, le site qui en a dans le citron !
                                          5 août 2011 à 15:50:18

                                          Citation : fred1599

                                          J'aime bien la solution de quark


                                          Moi aussi, c'est ma préférée pour l'instant :) (avec la mienne).

                                          Citation : quark

                                          Je ne pense pas que ton expression soit correcte (pourquoi k est il au carré?), et en fait la complexité de mon algo (pas ta version modifiée qui diminue un peu la complexité temporelle) serait plutôt <math>\(k(1+2(1+\log(2n)))\)</math>, mais je ne suis pas vraiment sur...


                                          Oui, j'ai un peu gaffé. Maintenant, je trouve : <math>\(2\,k\,ln\left( 2\,n\right) +k\)</math> avec mon 2e algo (légèrement différent du tien).

                                          Citation : quark

                                          Quoi qu'il en soit la méthode est rapide et se comporte bien si on augmente k et/ou n.


                                          Tout à fait.

                                          @ GurneyH :
                                          Aïe, si proche... :p

                                          Ce que tu fais, c'est l’équivalent d'un semi-heapsort (1e partie + extraction des N premières valeurs). L'ennui, c'est que la complexité mémoire n'est pas terrible, comme mentionné maintes fois plus haut.


                                          Mon code :



                                          Avant de proposer ma solution, je vais expliquer ma démarche :

                                          Certaines personnes ont essayé - et à juste titre ;) - d'utiliser une liste de N éléments pour enregistrer les N éléments les plus grands au cours de l'énumération de tous les éléments de l'iterable (une seule passe). La difficulté majeure est qu'a chaque élément, on doit vérifier s'il est supérieur au minimum de notre liste, ce qui donne une complexité temporelle en O(NM) (N pour le nombre d'éléments à retourner, M pour la taille de la liste).

                                          Si on disposait d'une structure "auto-triée", on pourrait alors se contenter de comparer chaque valeur avec le premier élément de la liste, et ainsi passer en O(M). Bien sûr, l'insertion dans une telle structure a aussi un coût qu'il faut évaluer.

                                          En fait, nul besoin d'avoir une structure totalement "auto-triée", il suffit que le premier élément soit toujours la plus petite valeur. Autrement dit, un tas peut parfaitement faire l'affaire :magicien: . [en principe, un set du C++ aussi pourrait faire l'affaire, mais je crois qu'un set ne respecte pas systématiquement l'ordre en python, détrompez moi si je dis une bêtise]

                                          L'opération d'insertion dans un tas a une complexité de O(log(N)), donc on se retrouve au final avec une complexité de O(M*log(N)).

                                          Mon code :
                                          from heapq import *
                                          
                                          def n_premiers(generator, n=10):
                                              result = []
                                              for elt in iter(generator):
                                                  if len(result) < n:
                                                      heappush(result, elt)
                                                  elif elt > result[0]:
                                                      heapreplace(result, elt)
                                              return [heappop(result) for i in range(10)]
                                          


                                          Vous pouvez vérifier que les performances ne se dégradent pas vraiment même avec de grosses valeurs de N.

                                          En espérant que cet exo vous a plu.
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            5 août 2011 à 16:22:50

                                            Bien vu!

                                            Une fois la correction sous les yeux c'est évident, comme toujours. :-°
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                            Zeste de Savoir, le site qui en a dans le citron !
                                              5 août 2011 à 17:43:11

                                              Pour moi la solution ne me semble pas si évidente (bon j'ai pas un grand niveau en python mais la il est plutôt question d'algo).
                                              D'abord faire le test sur la longueur de result à chaque tour de boucle pourrait être optimisé.
                                              Ensuite et surtout l'algo ne fonctionne pas me semble t'il.
                                              On compare toujours l'élément en cours avec le premier de la liste, mais je ne vois pas ce qui garanti que c'est lui le plus petit de cette liste ?



                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                5 août 2011 à 17:45:21

                                                Citation : mac.aque


                                                On compare toujours l'élément en cours avec le premier de la liste, mais je ne vois pas ce qui garanti que c'est lui le plus petit de cette liste ?


                                                Au moment de l'insertion dans le tas, le plus petit élément se retrouve en première position.
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                Zeste de Savoir, le site qui en a dans le citron !
                                                  5 août 2011 à 17:59:51

                                                  A ok, j'avais pas compris le que heapq n'était pas une simple pile, dsl.
                                                  Le cas le plus défavorable est donc celui d'une liste triée par ordre croissant.
                                                  [edit]En fait faut voir puisque l'insertion sur le tas sera a priori plus favorable, mais avec la suppression du minimum en O(log(n)) également...[/edit]
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                  Anonyme
                                                    5 août 2011 à 18:58:30

                                                    Faut-il que la liste retournée soit triée (du plus grand au plus petit) ?

                                                    Si oui, il n'y a que les algos de josmiley et GurneyH qui sont juste... :-°
                                                    Si non, alors je vous fais un benchmark. ;)
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      5 août 2011 à 19:00:33

                                                      Citation : Yoch


                                                      Les nombres retournés ne doivent pas forcément être ordonnés


                                                      ;)
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                      Zeste de Savoir, le site qui en a dans le citron !
                                                      Anonyme
                                                        5 août 2011 à 19:56:11

                                                        Ok, la prochaine fois j'ouvrirai les yeux...



                                                        Voici le benchmark promis. Je n'ai laissé que les algos qui passent la validation.
                                                        Amusez-vous à changer les paramètres val_min, val_max, it_size et n
                                                        # -*- coding:utf-8 -*-
                                                        
                                                        from __future__ import print_function
                                                        
                                                        
                                                        # -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
                                                        # quelqun_dautre :
                                                        def quelqun_dautre_nmax(liste, n=10):
                                                            liste = iter(liste)
                                                            bar = [ next(liste) for _ in range(n) ]
                                                            while True:
                                                                indice, minimum = min(enumerate(bar), key=lambda a:a[1])
                                                                try:
                                                                    i = next(liste)
                                                                except StopIteration:
                                                                    break
                                                                if i> minimum:
                                                                    bar[indice] = i
                                                            return bar
                                                        
                                                        
                                                        # -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
                                                        # quark :
                                                        def quark_extract_best( tmp, best, n ) :
                                                            best.extend(tmp)
                                                            best.sort()
                                                            return best[-n:]
                                                        
                                                        def quark_nmax( seq, n = 10 ) :
                                                            best = []
                                                            tmp = []
                                                            for i in seq :
                                                                tmp.append(i)
                                                                if len(tmp) == n :
                                                                    best = quark_extract_best(tmp, best, n)
                                                                    tmp = []
                                                            best = quark_extract_best(tmp, best, n)
                                                            return best
                                                        
                                                        
                                                        # -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
                                                        # josmiley :
                                                        def josmiley_nmax(iterable, n=10):
                                                            it = iterable[:]
                                                            return [ it.pop(it.index(max(it))) for i in range(n) if len(it) ]
                                                        
                                                        
                                                        # -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
                                                        # GurneyH :
                                                        import heapq
                                                        
                                                        def GurneyH_nmax(g, n):
                                                            hp, res = [], []
                                                            for value in g:
                                                                heapq.heappush(hp, -value)
                                                        
                                                            for _ in range(n):
                                                                res.append(-heapq.heappop(hp))
                                                        
                                                            return res
                                                        
                                                         
                                                        # -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
                                                        # yoch :
                                                        import heapq
                                                        
                                                        def yoch_nmax(generator, n=10):
                                                            result = []
                                                            for elt in iter(generator):
                                                                if len(result) < n:
                                                                    heapq.heappush(result, elt)
                                                                elif elt > result[0]:
                                                                    heapq.heapreplace(result, elt)
                                                            return [ heapq.heappop(result) for i in range(len(result)) ]
                                                        
                                                        
                                                        
                                                        
                                                        # -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
                                                        # -*-*-*-*-*-*-*-*-*-*-*-*-*- Benchmark -*-*-*-*-*-*-*-*-*-*-*-*-*-*-
                                                        # -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
                                                        if __name__ == "__main__":
                                                            from random import randint
                                                            from timeit import Timer
                                                            
                                                            gen = lambda a, b, n: [ randint(a, b) for _ in range(n) ]
                                                        
                                                            val_min = 1     # Valeur minimal contenu dans l'itérable.
                                                            val_max = 10000 # Valeur maximal contenu dans l'itérable.
                                                            it_size = 5000  # Taille de l'itérable.
                                                        
                                                            n = 500         # Nombre de valeurs à extraire de l'itérable.
                                                        
                                                            repeat = 100    # see help(Timer.timeit) 
                                                        
                                                            iterable = list(gen(val_min, val_max, it_size))
                                                            
                                                            players = [ # Proprio des algos (ça sonne bien en plus... 
                                                                "quelqun_dautre",
                                                                "quark",
                                                                "josmiley",
                                                                "GurneyH",
                                                                "yoch"
                                                            ]
                                                        
                                                            # La réponse attendu :
                                                            resp = iterable[:]
                                                            resp.sort()
                                                            resp = resp[-n:]
                                                            
                                                            # Validation des algos :
                                                            discalified = []
                                                            for i, name in enumerate(players[:]):
                                                                if resp != sorted(list(eval(name + "_nmax(iterable[:], n)"))):
                                                                    print("L'algo de", name, "est incorrect !")
                                                                    discalified.append(name)
                                                                else:
                                                                    print("L'algo de", name, "est correct.")
                                                        
                                                            print("\nBenchmark")
                                                            setup = "from __main__ import heapq, {}_nmax, iterable, n"
                                                            stmt = "_ = list({}_nmax(iterable[:], n))"
                                                            ls = []
                                                            for name in players:
                                                                if name in discalified:
                                                                    continue # on ne teste pas les algos erronés
                                                                t = Timer(stmt.format(name), setup.format(name))
                                                                print(name, end=" : ")
                                                                t = t.timeit(repeat)
                                                                print(t, " seconde", 's' if t > 1 else '', sep='')
                                                                ls.append((t, name))
                                                            ls.sort()
                                                        
                                                        
                                                            print("\nPodium")
                                                            for t, name in ls:
                                                                print("{} : {} seconde{}".format(
                                                                    name.center(15), t,
                                                                    's' if t > 1 else ''))
                                                        
                                                        #EOF#
                                                        
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          5 août 2011 à 21:56:55

                                                          Citation : yoch

                                                          En fait, nul besoin d'avoir une structure totalement "auto-triée", il suffit que le premier élément soit toujours la plus petite valeur. Autrement dit, un tas peut parfaitement faire l'affaire



                                                          Héhé, c'est la solution que je voulais poster hier, mais je n'ai pas eu le temps...

                                                          C'est la méthode qu'utilise postgresql pour traiter un ORDER BY + LIMIT, et ça fonctionne très bien.
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            5 août 2011 à 22:48:01

                                                            J'ai juste modifié la solution de yoch pour éviter des faire un test inutile à chaque boucle :
                                                            import heapq
                                                            
                                                            def nmax(generator, n=10):
                                                                result = []
                                                                for elt in iter(generator[:n]):
                                                                    heapq.heappush(result, elt)
                                                                for elt in iter(generator[n:]):
                                                                    if elt > result[0]:
                                                                        heapq.heapreplace(result, elt)
                                                                return result
                                                            

                                                            Le gain est sensible au benchmark.
                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                              6 août 2011 à 9:42:31

                                                              On peut utiliser l'opérateur [] sur un générateur ? ce serait nouveau XDDDD

                                                              Ça marche dans ton exemple parce que "generator" est une liste en fait.

                                                              import heapq
                                                              from itertools import *
                                                              
                                                              def nmax(generator, n=10):
                                                                  it = iter( generator )
                                                              
                                                                  result = list(islice( it, n ))
                                                                  if not result: 
                                                                      return result
                                                                  heapq.heapify(result)
                                                              
                                                                  for elt in g:
                                                                      if elt > result[0]:
                                                                          heapq.heapreplace(result, elt)
                                                              
                                                                  return result
                                                              

                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              [Exercice] trouver les dix plus grands nombres

                                                              × 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.
                                                              • Editeur
                                                              • Markdown