Partage
  • Partager sur Facebook
  • Partager sur Twitter

[Exercice][Moyen - Avancé] Trouver les VIP

Recherche d'une clique particulière dans un graphe orienté

    19 mars 2011 à 23:28:15

    Salut !

    Je vous propose aujourd'hui de résoudre un problème algorithmique en Python, très largement inspiré d'un chapitre de l'excellent livre Pearls of Functional Algorithm Design de Richard Bird.

    Formulation du problème



    Vous assistez à une soirée où sont présentes un certain nombre de personnes.

    La classe Person


    Une personne se caractérise par son nom, ainsi que la liste des noms des personnes qu'elle connaît. Elle dispose d'une méthode knows, permettant de savoir si elle connaît la personne qui lui est passée en paramètre :

    a.knows(b) retourne :
    • True si la personne a connaît la personne b,
    • False si a ne connaît pas b.

    La relation knows n'est pas symétrique : une personne a peut tout à fait connaitre une personne b alors que b ne connaît pas a.

    Voici le code de la classe Person

    class Person(object):
        def __init__(self, name):
            self.name = name
            self._known = []
    
        def knows(self, other):
            return other.name in self._known
    
        def __str__(self):
            return str(self.name)
    
        def __repr__(self):
            return repr(self.name)
    



    Faites entrer les VIP


    Parmi les gens qui assistent à la soirée, vous avez un certain nombre (strictement positif) de VIP.
    Voici les propriétés des VIP :
    • Un VIP ne connaît que les autres VIP, il ne connait pas de gens ordinaires. (On appelle cela une "clique" en théorie des graphes)
    • Un VIP est connu de tout le monde,


    Ainsi, vous avez dans cette soirée un groupe de VIP qui se connaissent tous entre eux, qui sont connus de tout le monde, mais qui ne connaissent personne en dehors de leur groupe.

    Votre mission, si vous l'acceptez


    Le but de cet exercice, est de rechercher, étant donnée la liste de toutes les personnes assistant à cette soirée, cette clique de VIP.

    Voici une fonction qui crée une liste d'invités pour tester votre algorithme :


    from random import shuffle, randrange, sample
    
    def mk_problem():
        # Création de la clique de VIP (j'avais pas d'inspiration pour les
        # célébrités, et comme je suis en train d'écouter du jazz...)
        c_names = ["Louis Armstrong", "Oscar Peterson", "Billie Holiday", 
                   "Ella Fitzgerald", "Paul Desmond", "Chet Baker",
                   "Dave Brubeck", "Niels E.H. Pedersen", "John Pass",
                   "Quincy Jones"]
        c_clique = [Person(n) for n in c_names]
    
        # Les VIP se connaissent tous entre eux
        for c in c_clique:
            c._known = c_names
    
        # Création d'un certain nombre de gens ordinaires
        n_names = ["Toto", "Titi", "Tata", "Tutu", "Bibi", "Coco", "Papi", "Tati",
                "Dede", "Dudu", "Bobo"]
    
        normal_people = [Person(n) for n in n_names]
     
        # Les gens normaux connaissent tous les VIP
        # ainsi qu'un certain nombre d'autres gens normaux (choisis au hasard).
        for n in normal_people:
            n._known = c_names + sample(n_names, randrange(len(n_names)))
    
        # On mélange le tout
        party = normal_people + c_clique
        shuffle(party)
    
        return party
    



    Votre mission est donc de créer une fonction find_vip qui prend en argument la liste des personnes assistant à la soirée (dans l'exemple : le retour de la fonction mk_problem, et retourne la liste des VIP de cette soirée).

    Le but de cet exercice est de trouver un algorithme efficace permettant de résoudre ce problème (en formulant l'hypothèse qu'il y a une et une seule clique de VIP à cette soirée) en ne se servant que de la méthode knows. L'algorithme naïf est en O(nk) en termes d'utilisation de l'opérateur knows avec n le nombre de personnes assistant à la soirée et k le nombre de VIP. Il est possible de faire BEAUCOUP mieux que ça. Une première amélioration de l'algorithme naïf (tenant compte des contraintes sur les VIP) est en O(n²), et il existe une solution linéaire (en O(n)) à ce problème. ;)

    Voici une seconde fonction de test (python 2 ET 3), permettant de tester les performances de votre fonction avec possibilité de dimensionner le problème :
    • total est le nombre total d'invités à la soirée.
    • vips est le nombre de vips (< total).
    • functions est la liste des fonctions à tester.


    from __future__ import print_function
    from random import shuffle, sample, randrange
    from time import time
    
    def test_function(total, vips, functions):
        print("Building list of {0} vips and {1} normal people".format(vips
                , total - vips))
        
        vip_names = set(range(vips))
        normal_names = set(range(vips, total))
        
        vip = [Person(c) for c in vip_names]
        normal = [Person(p) for p in normal_names]
        
        for v in vip:
            v._known = vip_names
        
        for p in normal:
            p._known = vip_names.union(sample(normal_names, randrange(vips)))
        
        party = vip + normal
        shuffle(party)
       
        for fn in functions:
            print("Running '{0}' :\t".format(fn.__name__), end=" ")
            start = time()
            result = fn(party)
            end = time()
            print("[{0:.6f}s]".format(end-start), end= " ")
            
            result.sort(key=lambda p:p.name)
            print("OK" if result == vip else "FAIL!")
    



    Bon courage !

    Je posterai une première solution en O(n²) dans 24h si personne n'a le courage d'essayer d'ici-là.
    • Partager sur Facebook
    • Partager sur Twitter
    Zeste de Savoir, le site qui en a dans le citron !
      20 mars 2011 à 12:10:55

      Citation : NoHaR



      Ainsi, vous avez dans cette soirée un groupe de VIP qui se connaissent tous entre eux, qui sont connus de tout le monde, mais qui ne connaissent personne en dehors de leur groupe. On appelle cela une "clique".




      Non, ce n'est pas ce qu'on appelle une clique car tu as ajouté une condition très forte, à savoir que les VIP sont connus de tout le monde. Dans ces conditions, le problème est trivial, il suffit de chercher tous les sommets de degré entrant n-1 où n est le nb total de personnes et c'est alors forcément une clique puisque si a et b sont deux tels sommets, par hypothèse sur a et b, a et b se connaissent mutuellement. Trouver tous les sommets de degré n-1 est une opération en n**2 (et pas moins, imagine que tout ton groupe ne soit constitué que de VIP, autrement dit que le graphe soit complet). Quand tu disais linéaire, tu voulais peut-être dire en le nombre d'arêtes mais attention, le nombre d'arêtes peut s'approcher de n*2 donc c'est de la fausse linéarité.


      Sinon, je trouve dommage de cacher un problème d'algorithmique dans un contexte assez lourd de POO.
      • Partager sur Facebook
      • Partager sur Twitter
        20 mars 2011 à 12:13:49

        Oui, il y a une contrainte très forte (ainsi qu'une autre contraite qui veut qu'il y ait nécessairement un groupe de VIP), justement pour garantir l'unicité de cette clique et faire en sorte que le problème ne soit pas NP-complet (rechercher la clique la plus grande). ;)

        Sinon, quand je dis linéaire, c'est bel et bien linéaire en le nombre de sommets (de personnes).

        Citation : candide


        Sinon, je trouve dommage de cacher un problème d'algorithmique dans un contexte assez lourd de POO.



        Si j'ai défini une classe Person moi-même, c'est justement pour que l'on utilise tous la même représentation : la fonction utilise simplement l'opérateur knows de la classe Person, de façon opaque en considérant qu'il s'agit d'une opération élémentaire (les set en Python permettent d'ailleurs d'obtenir une complexité en O(1) sur cette méthode) : nul besoin de connaître la POO pour résoudre cet exo, donc.

        Edit : j'ai précisé l'énoncé (pour ne pas mal définir le terme de clique) ainsi que le sous-titre (recherche d'une clique particulière)

        Edit2 : Puisque tu as donné la solution en O(n2), la voici :

        def vip_gen(persons):
            return (p for p in persons if all(k.knows(p) for k in persons))
        
        def find_vip_quad(persons):
            return list(vip_gen(persons))
        


        Cette solution calcule le résultat sur un problème à 10000 personnes (dont 500 VIP), sur ma machine, en 5.222 secondes.

        Une amélioration directe de cet algorithme permet de le rendre "presque" linéaire, le faisant s'exécuter, sur le même problème, en 0,019 seconde.

        La solution linéaire, quant à elle, prend sur ma machine 0,016 seconde.
        • Partager sur Facebook
        • Partager sur Twitter
        Zeste de Savoir, le site qui en a dans le citron !
          20 mars 2011 à 13:11:27

          def find_vip(party):
              fiesta = party[:]
              for person in fiesta:
                  for otherperson in fiesta[:]:
                      if not person.knows(otherperson): fiesta.remove(otherperson)
              return fiesta
          

          j'ai pas compris comment tester la fonction ...
          • Partager sur Facebook
          • Partager sur Twitter
            20 mars 2011 à 13:17:45

            Merci josmiley, et bien joué. :)

            Pour utiliser la fonction de test :
            test_function(10000, 500, [find_vip_quad, find_vip_josmiley, find_vip_better, find_vip_linear])
            


            Voilà le résultat sur ma machine :

            Building list of 500 vips and 9500 normal people
            Running 'find_vip_quad':           [5.146332s] OK
            Running 'find_vip_josmiley':       [0.401770s] OK
            Running 'find_vip_better':         [0.018467s] OK
            Running 'find_vip_linear':         [0.017028s] OK


            Par contre, en augmentant la proportion de VIP et le nombre de connaissances des gens ordinaires :

            Building list of 5000 vips and 5000 normal people
            Running 'find_vip_quad':           [45.618220s] OK
            Running 'find_vip_josmiley':       [17.350655s] OK
            Running 'find_vip_better':         [0.017984s] OK
            Running 'find_vip_linear':         [0.017059s] OK
            • Partager sur Facebook
            • Partager sur Twitter
            Zeste de Savoir, le site qui en a dans le citron !
              20 mars 2011 à 13:48:26

              Salut, je propose une solution linéaire à cet exercice intéressant.


              Il s'agit de parcourir la liste des personnes une première fois: pour chaque personne, si elle connaît la suivante on continue normalement, sinon on supprime celle-ci (elle n'est forcément pas VIP) et on recommence. La dernière personne de la liste ainsi traitée est forcément un VIP, on n'a plus qu'à renvoyer la liste filtré en fonction des connaissances de ce VIP.
              On utilise entre n+k (meilleur des cas) et 2n (pire des cas) fois la méthode knows, la solution est donc linéaire.

              def vips(party):
              	i,l=0,party[:]
              	while i<len(l)-1:
              		if l[i].knows(l[i+1]): i+=1
              		else : del l[i+1]
              	return filter(l[-1].knows,l)
              


              Building list of 500 vips and 9500 normal people
              Running 'find_vip_quad' :         [3.808000s] OK
              Running 'find_vip_josmiley' :         [0.356000s] OK
              Running 'vips' :         [0.037000s] OK
              • Partager sur Facebook
              • Partager sur Twitter
                20 mars 2011 à 14:00:05

                Effectivement. :)

                Le principe "trouver le premier VIP dont on est sûr, et retourner la liste de ses connaissances" est celui de la fonction "find_vip_better".
                Ici, on cherche le premier VIP "à la brutor" (la première personne connue de toutes les autres que l'on trouvera dans la liste), et on retourne ses connaissances :

                def vip_gen(persons):
                    return (p for p in persons if all(k.knows(p) for k in persons))
                
                def find_vip_better(persons):
                    v = vip_gen(persons).next()
                    return [p for p in persons if v.knows(p)]
                


                La première phase est donc un O(n²) (mais qui termine dès qu'on a trouvé le premier VIP, donc assez rapidement), et la seconde un O(n).

                Voilà le comparatif :

                Building list of 500 vips and 9500 normal people
                Running 'find_vip_quad':           [5.209512s] OK
                Running 'find_vip_josmiley':       [0.279171s] OK
                Running 'find_vip_EMC1':           [0.027112s] OK
                Running 'find_vip_better':         [0.018381s] OK
                Running 'find_vip_linear':         [0.016826s] OK


                Et en corsant un peu le problème :

                Building list of 5000 vips and 5000 normal people
                Running 'find_vip_quad':           [45.551293s] OK
                Running 'find_vip_josmiley':       [18.044011s] OK
                Running 'find_vip_EMC1':           [0.024511s] OK
                Running 'find_vip_better':         [0.017652s] OK
                Running 'find_vip_linear':         [0.018022s] OK


                Ta fonction est donc robuste aux variations en proportion de VIP et en nombre de connaissances des individus lambda.


                Reste à déterminer une solution linéaire qui ne nous oblige pas à connaître un VIP dès le départ. :p
                • Partager sur Facebook
                • Partager sur Twitter
                Zeste de Savoir, le site qui en a dans le citron !
                  20 mars 2011 à 14:56:22

                  ha oué, j'avais zappé que les vips ne connaissaient que les vips ...
                  def find_vip0(party):
                      z = party[:]
                      x = ''
                      while len(z)!=len(x):
                          x = z[:]
                          a = z[0]
                          b = z[1:]
                          z = [i for i in b if a.knows(i)]+[a]
                      return z
                  
                  • Partager sur Facebook
                  • Partager sur Twitter
                    20 mars 2011 à 15:12:12

                    Wow : cette fonction est vachement rapide, bien joué, tu passes en tête !

                    Building list of 500 vips and 9500 normal people
                    Running 'find_vip_EMC1':           [0.026495s] OK
                    Running 'find_vip_better':         [0.018644s] OK
                    Running 'find_vip_linear':         [0.017147s] OK
                    Running 'find_vip_josmiley2':      [0.009718s] OK


                    Par contre, en "corsant" le problème, elle ralentit, et devient en moyenne aussi rapide que les autres.

                    Building list of 5000 vips and 5000 normal people
                    Running 'find_vip_EMC1':           [0.022855s] OK
                    Running 'find_vip_better':         [0.017416s] OK
                    Running 'find_vip_linear':         [0.017006s] OK
                    Running 'find_vip_josmiley2':      [0.020505s] OK
                    
                    Building list of 5000 vips and 5000 normal people
                    Running 'find_vip_EMC1':           [0.022959s] OK
                    Running 'find_vip_better':         [0.018132s] OK
                    Running 'find_vip_linear':         [0.017884s] OK
                    Running 'find_vip_josmiley2':      [0.013481s] OK


                    Super efficace quand il n'y a pas beaucoup de VIP ou peu de relations "knows" entre les individus normaux.


                    • Partager sur Facebook
                    • Partager sur Twitter
                    Zeste de Savoir, le site qui en a dans le citron !
                      20 mars 2011 à 15:16:38

                      Citation : NoHaR


                      Reste à déterminer une solution linéaire qui ne nous oblige pas à connaître un VIP dès le départ. :p




                      ????


                      Une solution linéaire en n n'existe pas puisque si la réunion d'individus est composée uniquement de n VIP, tu auras une clique de <math>\(n^2\)</math> et donc ton algo ne peut pas faire moins. Par contre, il peut être linéaire en n et m ou m est le nombre d'arêtes du graphe des connaissance. Mais bon, rien de difficile, comme j'ai dit, il suffit de chercher les personnes connues de toutes (sauf éventuellment d'elle-même) donc la complexité de l'algo est exactement de n + m, c'est une banale boucle :




                      connait=[
                      [3,5,2,0],
                      [3,5,4,0,1],
                      [3,5,1],
                      [5,0],
                      [3,5,4],
                      [3,1,2,4]
                      ]
                      
                      def vip(n,connait):
                          t=[0]*n
                          for p in connait:
                              for c in p: 
                                  t[c]+=1
                          return [i for i in range(n) if t[i]==n-1]
                      
                      print vip(6,connait)
                      


                      [3, 5]




                      Bien sûr, on peut faire de micro-optimisation, par exemple il est inutile de parcourir une liste d'un individu qui n'apparait pas dans une liste de connaissances déjà rencontrée. En pratique, ça peut bien sûr accélérer mais ça ne change pas la complexité algorithmique.


                      Cette solution est assez laborieuse en Python, le plus efficace est d'utiliser des ensembles :


                      connait=[
                      [3,5,2,0],
                      [3,5,4,0,1],
                      [3,5,1],
                      [5,0],
                      [3,5,4],
                      [3,1,2,4]
                      ]
                      
                      def vip_set(n,connait):
                          z=set(range(n))
                          for i in range(n):
                              z&=set(connait[i])|set([i])
                          return list(z)
                      
                      print vip_set(6,connait)
                      


                      [3, 5]
                      • Partager sur Facebook
                      • Partager sur Twitter
                        20 mars 2011 à 15:18:48

                        @candide : ah bon ? elle n'existe pas ? ;)


                        def find_vip_linear(persons):
                            vip, v = [], None
                            for p in persons:
                                if v is None or not p.knows(v):
                                    vip = [p]
                                    v = p
                                elif v.knows(p):
                                    vip.append(p)
                            return vip
                        


                        L'idée, c'est de se mettre un peu "à la place du videur", et d'intercepter les gens qui "entrent".
                        On prend la première personne qui vient, et on fait l'hypothèse que c'est un VIP. On l'appelle V.
                        Ensuite, à chaque personne P qui entre : si P ne connaît pas V, c'est que V n'est pas un VIP, donc P remplace V, et [P] remplace la "clique" de V.
                        Si P connaît V, et que V connaît P, alors, par hypothèse, P est aussi un VIP, donc on l'ajoute à la clique de V. Sinon, V ne connaît pas P, donc P est forcément un individu lambda et on l'ignore.

                        Une fois que toutes les personnes sont entrées, on est forcément tombé sur un VIP, donc la clique que l'on a construite est forcément la clique de VIP que l'on cherche (à cause des contraintes de l'énoncé sur les VIP).

                        Au final, en termes d'utilisation de l'opérateur knows() (dont l'implémentation par les set est en O(1), je le rappelle, quoiqu'il est possible de faire la même chose avec une LUT) :
                        Pour chaque personne (×N):
                        - évaluation de p.knows(v)
                        - évaluation éventuelle de v.knows(p)

                        On trouve le résultat en 2N utilisation de knows (où N est le cardinal de l'ensemble des sommets). Je sais pas pour toi, mais moi j'appelle ça une complexité linéaire.


                        Bisous. :p
                        • Partager sur Facebook
                        • Partager sur Twitter
                        Zeste de Savoir, le site qui en a dans le citron !
                          20 mars 2011 à 15:50:22

                          Citation : NoHaR


                          Au final, en termes d'utilisation de l'opérateur knows() (dont l'implémentation par les set est en O(1),




                          Eh, non tout le problème est là. Une application known comme tu dis ça s'appelle une matrice d'adjacence, ça a une taille de <math>\(n^2\)</math>. Imagine, comment tu fais pour connaître le graphe des connaissances de ta party :


                          tu prends Toto et tu lui demandes :
                          - Toto, connais-tu TaTa ? Rép : Non
                          - Toto, connais-tu TuTu ? Rép : Oui
                          - Toto, connais-tu Sarko ? Rép : Oui
                          etc

                          et tu recommences avec chacun des individus, ce qui fait n*(n-1) requêtes ce qui est un <math>\(O(n^2)\)</math>.
                          • Partager sur Facebook
                          • Partager sur Twitter
                            20 mars 2011 à 15:54:03

                            Alors déjà : http://wiki.python.org/moin/TimeComplexity .

                            Ensuite, l'énoncé parle bien dès le départ de complexité en termes d'utilisation de l'opérateur knows, ce qui fait que tu pars du principe que tu as déjà créée ta matrice d'adjacence (ou toute représentation valable), donc que tu considères dans le calcul de complexité que la complexité théorique de knows est O(1) de toute façon.
                            • Partager sur Facebook
                            • Partager sur Twitter
                            Zeste de Savoir, le site qui en a dans le citron !
                              20 mars 2011 à 15:58:16

                              @Candide: Tu prends une matrice de taille n*n de booléen que tu remplit avant, tu numérotes les personnes, et knows n'est plus qu'en accés à la dite case : ie constant. Ou dit autrement tu changes la représentation des données et à la place d'une liste de personne connu tu prends un tableau de bolléen. Et de toute facon l'énoncé était en terme d'appel à knows.
                              • Partager sur Facebook
                              • Partager sur Twitter
                              FaQ : Fr | En 1 2 | C++11 | Template || Blog : Deloget | C++|Boost--Dev | C++Next | GotW || Installer Boost
                                20 mars 2011 à 17:35:54

                                Citation : NoHaR


                                Ensuite, l'énoncé parle bien dès le départ de complexité en termes d'utilisation de l'opérateur knows, ce qui fait que tu pars du principe que tu as déjà créée ta matrice d'adjacence (ou toute représentation valable), donc que tu considères dans le calcul de complexité que la complexité théorique de knows est O(1) de toute façon.



                                Oui, dans ces conditions la complexité est linéaire et la solution est assez futée, je dois reconnaître, merci de nous l'avoir fait connaître.

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  20 mars 2011 à 18:08:27

                                  @candide : Je t'en prie.

                                  Pour essayer de faire parler un peu plus les chiffres, et se faire une meilleure idée des performances des solutions proposées, je me suis amusé à benchmarker les 4 algos (celui d'EMC1, le second de josmiley, le "better", et le "linear"), et à tirer les graphes correspondants.

                                  J'ai fait pour cela 5 sessions (en faisant varier N entre 1000 et 15000), avec une population de vip représantant respectivement 90%, 80%, 70%, 60%, et 50% de la population totale.

                                  La méthode knows, dans ces conditions, est l'opérateur in sur les set, qui a bien une complexité moyenne en O(1).

                                  Les relations de connaissance entre individus lambda sont décidées par tirage au sort (chaque individu connait un nombre arbitraire de gens lambda, pris au hasard entre 0 et le nombre de gens lambda de la population).
                                  Dans le cas extrême, (50% vip, N=14000 et plus), il faut avouer que ça fait un peu chauffer le silicium (tellement que l'on a des énormes outliers) vu le nombre extrêmement conséquent de relations entre les individus lambda (c'est une combinatoire...).

                                  Voilà les résultats.

                                  90% de VIP


                                  90%

                                  80% de VIP


                                  80%

                                  70% de VIP


                                  70%

                                  60% de VIP


                                  60%

                                  50% de VIP


                                  50%

                                  Sur ce dernier graphe, j'ai retiré les 2 derniers résultats pour l'algo de EMC1 et le "better", le premier passant directement à 1.4s pour N=14000 (donc le reste du graphe serait ratatiné), et 0.3s pour N=15000, et le second prenant 15 secondes juste pour le cas N=14000, et 27s pour N=15000 (ce qui signifie grosso-modo que le O(n²) de la phase de recherche du premier VIP rattrape le O(n) du reste de l'algo).

                                  On remarque que l'algorithme de josmiley est souvent plus rapide, mais très instable.
                                  Je conjecture que certains pètes en performances sont pris en raison des allocations de liste...

                                  Edit : pour essayer de comprendre l'instabilité de l'algo de josmiley, j'ai essayé un autre cas extrême, c'est à dire un bench avec N variant entre 100 et 3000, avec 10% de VIP.

                                  Image utilisateur

                                  Ça ne vient en fait probablement pas des allocations de mémoire...
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                  Zeste de Savoir, le site qui en a dans le citron !
                                    20 mars 2011 à 20:36:00

                                    non mais mon algo est faut en fait ... ça ne marche pas si les non vip se connaissent tous entre eux.
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      20 mars 2011 à 20:41:21

                                      En fait, tu pourrais expliquer l'idée qu'il y a derrière ton algo ?

                                      Pour un algo "qui ne marche pas", il poutre les 3 autres un coup sur 2, quand même. :p
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                      Zeste de Savoir, le site qui en a dans le citron !
                                        20 mars 2011 à 21:19:24

                                        en gros c'est si 2 personnes ont la même liste d'amis, alors c'est des listes de vip; ce qui n'est pas forcement vrai ...

                                        ce nouveau code fonctionne, reste à tester les perfs.
                                        def find_vip1(party):
                                            z = party[:]
                                            while True:
                                                a = z[0]
                                                b = z[1:]
                                                z = [i for i in b if a.knows(i)]
                                                if all([i.knows(a) for i in z]): return z+[a]
                                        


                                        après lecture de postes précédent, on dirait le même que 'better' mais écrit différement.
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          21 mars 2011 à 0:32:46

                                          Citation : NoHaR


                                          def find_vip_linear(persons):
                                              vip, v = [], None
                                              for p in persons:
                                                  if v is None or not p.knows(v):
                                                      vip = [p]
                                                      v = p
                                                  elif v.knows(p):
                                                      vip.append(p)
                                              return vip
                                          




                                          Une variante de ta méthode qui m'a permis de comprendre plus facilement l'algo. Le code est plus simple mais curieusement les performances un poil moins bonnes. De plus en plus, je trouve assez lourd le for de Python, ya qu'à voir les contorsions que ça m'oblige à faire. Ah ! rien ne vaut le bon vieux C.


                                          def find_vip_candide(persons):
                                              z=iter(persons)     # ces deux lignes juste pour
                                              q=z.next()          # commencer au 2ème terme de la liste
                                              for p in z:
                                                  if not p.knows(q):
                                                      q=z.next()
                                              return [p for p in persons if q.knows(p)]
                                          
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            21 mars 2011 à 0:47:43

                                            @candide: Inutile d'être si modeste.

                                            J'ai testé sur le "bench 70%", je ne vois pas de différence notoire de performances avec mon implémentation. ;)

                                            Image utilisateur

                                            L'algo est un peu différent, mais ça revient bien à choisir un VIP en O(n) itérations maximum puis reconstruire la clique avec une list comprehension en O(n), donc un algo parfaitement linéaire.

                                            Par contre, à quelques instabilités près, la nouvelle implémentation de josmiley est vraiment pas mal non plus. :)
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                            Zeste de Savoir, le site qui en a dans le citron !
                                              21 mars 2011 à 3:00:08

                                              Citation : NoHaR


                                              <image>



                                              Jolis et convaincants ces petits graphiques, c'est du matplotlib, non ?

                                              Citation : NoHaR


                                              Par contre, à quelques instabilités près, la nouvelle implémentation de josmiley est vraiment pas mal non plus. :)




                                              Ça se comprend assez bien puisque son algo peut terminer bien avant d'avoir tout parcouru ce qui n'est pas le cas de ton algo. Mais, dans certains cas (ça dépend du tirage), l'algo de josmiley est presque du quadratique. Pourtant, je suis étonné qu'il rivalise aussi bien avec celui de EMC1. Et l'avantage de l'algo de josmiley c'est qu'il est compréhensible assez rapidement (tout en étant assez élégant) tandis que le tien demande vraiment de se casser la tête pour comprendre que ça marche.
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                21 mars 2011 à 3:04:47

                                                Citation : candide


                                                Jolis et convaincants ces petits graphiques, c'est du matplotlib, non ?



                                                Tout à fait.

                                                Citation : candide


                                                Pourtant, je suis étonné qu'il rivalise aussi bien avec celui de EMC1. Et l'avantage de l'algo de josmiley c'est qu'il est compréhensible assez rapidement (tout en étant assez élégant) tandis que le tien demande vraiment de se casser la tête pour comprendre que ça marche.



                                                Ça doit être avant tout une question d'habitudes, je suppose. J'ai justement le point de vue inverse sur la compréhension des programmes. ;)

                                                Il est aussi possible que l'algorithme de ma fonction me paraisse évident parce que je me suis cassé la tête à lire la preuve formelle de son fonctionnement (sa dérivation depuis l'algorithme naïf) en Haskell dans le livre de Richard Bird (raison pour laquelle, d'ailleurs, j'ai préféré utiliser la métaphore du videur en l'expliquant ici, parce que je la trouvais particulièrement adaptée).
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                Zeste de Savoir, le site qui en a dans le citron !
                                                  19 juillet 2011 à 21:33:24

                                                  J'ai triché...

                                                  Citation : candide

                                                  Une variante de ta méthode qui m'a permis de comprendre plus facilement l'algo. Le code est plus simple mais curieusement les performances un poil moins bonnes. De plus en plus, je trouve assez lourd le for de Python, ya qu'à voir les contorsions que ça m'oblige à faire. Ah ! rien ne vaut le bon vieux C.

                                                  def find_vip_candide(persons):
                                                      z=iter(persons)     # ces deux lignes juste pour
                                                      q=z.next()          # commencer au 2ème terme de la liste
                                                      for p in z:
                                                          if not p.knows(q):
                                                              q=z.next()
                                                      return [p for p in persons if q.knows(p)]
                                                  


                                                  Marrant, j'ai moi aussi modifié la fonction de cette manière, mais en plus lisible (sans contorsions :p ), comme ceci :
                                                  def find_vip_linear2(persons):
                                                      v = persons[0]
                                                      for p in persons[1:]:
                                                          if not p.knows(v):
                                                              v = p
                                                      return [p for p in persons if v.knows(p)]
                                                  


                                                  Je suppose que tu as voulu éviter le persons[:1], qui crée une copie semble-il. Question: créer un itérateur est-il plus performant ? Et où trouve on ce genre d'informations ?

                                                  Citation : nohar

                                                  L'algo est un peu différent, mais ça revient bien à choisir un VIP en O(n) itérations maximum puis reconstruire la clique avec une list comprehension en O(n), donc un algo parfaitement linéaire.


                                                  Il y a globalement un avantage et un inconvénient :
                                                  • Avantage : on ne crée pas de multiples listes de VIP théoriques (ça peut faire mal dans le cas ou les VIP sont en fin de liste)
                                                  • Inconvénient : on parcourt la liste deux fois.

                                                  Pour moi, l'avantage est nettement plus intéressant (stabilité de l'algo).
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    2 juillet 2013 à 16:32:08

                                                    Je sais que le topic est vieux mais je me permet de tenter ma chance.

                                                    Avant de commencer j'aimerais savoir: doit on generer aléatoirement le fait qu'une personne soit VIP soit non?

                                                    from random import choice, shuffle,randint
                                                    from time import time
                                                    
                                                    class VIP:
                                                        liste=[]
                                                        def __init__(self,nom):
                                                            self.nom=nom
                                                            VIP.liste.append(self.nom)
                                                    
                                                        def connaitre(self,pers):
                                                            if isinstance(pers,VIP):
                                                                return True
                                                            elif isinstance(pers,Normal):
                                                                return False
                                                    
                                                    class Normal:
                                                        liste=[]
                                                        def __init__(self,nom):
                                                            self.nom=nom
                                                            Normal.liste.append(self.nom)
                                                    
                                                        def connaitre(self,pers):
                                                            return True
                                                    
                                                    def generer_fete(invités=["Louis Armstrong", "Oscar Peterson", "Billie Holiday",
                                                                   "Ella Fitzgerald", "Paul Desmond", "Chet Baker",
                                                                   "Dave Brubeck", "Niels E.H. Pedersen", "John Pass",
                                                                   "Quincy Jones"]):
                                                        global var
                                                        fete=[]
                                                        
                                                        for n in invités:
                                                            i=randint(0,1)
                                                            if i:
                                                                n=VIP(n)
                                                            else:
                                                                n=Normal(n)
                                                            fete.append(n)
                                                    
                                                        shuffle(fete)
                                                    
                                                        trouvés=False
                                                        
                                                        for i in range(len(fete)-1):
                                                            if not fete[i].connaitre(fete[i+1]):
                                                                var=fete[i+1]
                                                                trouvés=True
                                                                break
                                                    
                                                        if not trouvés:
                                                            for i in range(len(fete)-1,0,-1):
                                                                if not fete[i].connaitre(fete[i-1]):
                                                                    var=fete[i+1]
                                                                    break
                                                    
                                                        return [n.nom for n in fete if not n.connaitre(var)]

                                                    -On parcourt la liste de gauche a droite et dés que fete[x] ne connait pas fete[x+1] on stocke fete[x+1] dans une variable global (oui je sais c'est mal :p) et on arrete le for (car on sait que cette personne est non-vip)

                                                    -si malgré tout on ne trouve personne on refait la même chose mais en sens inverse 

                                                    -ainsi on n'a plus qu'a renvoyer la liste des personnes qui ne connaissent PAS cette personne

                                                    dans le pire des cas on parcourt la liste 3 fois ce qui fait autour des O(3n)

                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                    Si c'était facile, tout le monde le ferait.
                                                      2 juillet 2013 à 16:44:30

                                                      Ça fonctionne pas. Un non-VIP peut très bien ne pas connaître un autre non-VIP.

                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                      Zeste de Savoir, le site qui en a dans le citron !
                                                        2 juillet 2013 à 17:53:24

                                                        autant pour moi je n'avait pas vu :)

                                                        def generer_fete(invités=["Louis Armstrong", "Oscar Peterson", "Billie Holiday",
                                                                       "Ella Fitzgerald", "Paul Desmond", "Chet Baker",
                                                                       "Dave Brubeck", "Niels E.H. Pedersen", "John Pass",
                                                                       "Quincy Jones"]):
                                                            global var
                                                            fete=[choice([Normal,VIP])(n) for n in invités]
                                                        
                                                            shuffle(fete)
                                                        
                                                            trouvés=False
                                                            
                                                            for i in range(len(fete)-1):
                                                                if not fete[i].connaitre(fete[i+1]) and all([n.connaitre(fete[i]) for n in fete]):
                                                                    var=fete[i]
                                                                    trouvés=True
                                                                    break
                                                        
                                                            if not trouvés:
                                                                for i in range(len(fete)-1,0,-1):
                                                                    if not fete[i].connaitre(fete[i-1]) and all([n.connaitre(fete[i]) for n in fete]):
                                                                        var=fete[i]
                                                                        break
                                                                    
                                                            return [n.nom for n in fete if var.connaitre(n)]

                                                        j'ai donc légerement changé l'algorithme:

                                                        -on parcourt la liste de gauche a droite et si l'element a indice i ne connait pas l'element à l'indice i+1 et que i est connu de tout le monde alors on le met dans un variable car on sait que c'est un VIP.(on fait le parcours la liste en sens inverse si on ne trouve pas de VIP genre [Normal, Normal, Normal...VIP,VIP])

                                                        -on renvoit la liste des personnes que la personne "echantillon" connait 



                                                         @Nohar connait fait tu pour voir le temps d'execution sur un grand nombre d'invités ?

                                                        -
                                                        Edité par Smich74 3 juillet 2013 à 10:14:34

                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                        Si c'était facile, tout le monde le ferait.

                                                        [Exercice][Moyen - Avancé] Trouver les VIP

                                                        × 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