Python et list — Les-mathematiques.net The most powerful custom community solution in the world

Python et list

Bonjour,

J'aimerais savoir comment on peut réduire la taille du code suivant si vous voyez ce que je veux dire merci pour le coup de main !
S=0
for i in range(C):
    for X in clusters[ i]:
        print("X", X)
        print("G", G[ i])
        S = S + d2(X,G[ i])
print(S)

Réponses

  • C’est difficile si on ne connaît pas la structure de clusters et de G.
    Essaie peut-être avec zip.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • On doit pouvoir faire quelque chose comme ça :
    S = sum([ d2(X, G[ i]) for i in range(C) for X in clusters[ i] ])
    
    Mais si le but est d'accélérer l'exécution, il faudrait sans doute plutôt regarder du côté de NumPy pour calculer les distances d2(X, G[ i]) « vectoriellement ». Pour ce faire, il faudrait sans doute expliciter d2 avec une ou des fonctions que Numpy peut exécuter sur un couple de vecteurs (ou peut-être directement entre une valeur et chaque composante d'un vecteur : je ne suis pas assez familier de Numpy).
  • Tu peux te passer des crochets :
    S = sum( d2(X, G[ i]) for i in range(C) for X in clusters[ i] )
    
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • En effet, c'est ce que j'allais ajouter car si C est grand, ça doit prendre beaucoup moins de mémoire ainsi (generator expression).
  • Cela dit, si l'occupation mémoire n'est pas un problème, la solution avec list comprehension est un peu plus rapide que celle avec une generator expression sur mon ordinateur :
    >>> import timeit
    >>> timeit.timeit( "sum( [ 0 for i in range(100000) ] )", number=1000)
    5.139831292000963
    >>> timeit.timeit( "sum( 0 for i in range(100000) )", number=1000)
    6.275311594999948
    >>>
    
    (c'est reproductible).
  • Il faudrait tester avec de vraies données. Peut-être que le « compilateur » optimise la présence des zéros.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • J'aimerais vous répondre mais là j'ai un autre problème.
    NameError: name 'self' is not defined

    Je peux vous montrer ce que j'ai fait
    class Kmeans():
        """""
        Input : 
        C : Number of clusters
        X : Training set
        """""
        def __init__(self, C, data, Bool):
            self.C = C
            self.data = data
            self.N = len(X) # Number of points
            self.display = Bool 
        
        def d2(data, G):
            """""
            Input : 
            clusters_label : A numpy vector of size data set and each coordinate is the number of the clusters 
                                whoose the data point belongs.
            G : A set centroids
            
            Output : 
            """""
            
            return np.array([ [np.sum((x-g)**2) for g in G] for x in data])
        
        def Inertia(clusters_label, G):
            """""
            Input : 
            clusters_label : A numpy vector of size data set and each coordinate is the number of the clusters 
                                whoose the data point belongs.
            G : A set centroids
            
            Output : 
            """""
            return 
            
        
        def assignement(G):
            """""
            Input : 
            C : Number of clusters
            X : Training set
            
            Output : Cluster_labels 
            """""
            return np.argmin( d2(data, G), axis = 1)
    
        
        def centroids(clusters_labels, G):
            """""
            Input : 
            C : Number of clusters
            X : Training set
            """""
            Gnew = np.zeros(G.shape)
            for j in range(C):
                if sum(clusters_label == j) == 0:
                    Gnew[j] = G[j]
                else:
                    Gnew[j] = np.mean(data[cluster_label == j, :], axis=0)
            
        def display(clusters_labels, step):
            """""
            Input : 
            C : Number of clusters
            X : Training set
            
            Out : Display step
            """""
            
        def train(self,C,data, G):
            """""
            Input : 
            C : Number of clusters
            data : Training set 
            G : Set of centroids set up as a list of points
            """""
            IB = 0 # Inertia before
            IA = 0 # Intertia after
            step = 0 
            epsilon = 10**(-3) # inertia's variation minimum value.
            
            # Represent the clusters as a list with C lines each lines is a cluster 
            clusters = [[G[ i]] for i in range(C)] # Initialization of the clusters set
            clusters_label = np.zeros(len(data))
            
            while np.abs(IB-IA) > epsilon or step==0 : # While inertia doesn't stagnate 
                #Display step
                if self.display :
                    display(clusters_label, G, step)
                # Training step
                IB = IA # Old interia to compute variation
                IA = Inertia(clusters, G) # Update Inertia
                clusters_labels = assignement(G) # Update clusters
                G = centroids(clusters_labels, G) # Update centroids
                step = step +1 # Update step
                
    


    Et
    class KLoyds(KMeans):
        def __init__(self, C, data, Bool):
            super().__init__(self, C, data, Bool)
        # Initialisation step 
        G = np.random.choice(self.data, self.C)
        self.train(self.C, self.data, G)
    
  • Je n'ai pas lu grand-chose, mais vu l'indentation à la fin, ces deux lignes :
    G = np.random.choice(self.data, self.C)
    self.train(self.C, self.data, G)
    
    ne font pas partie de la méthode KLoyds.__init__(), ce qui est probablement une erreur et la cause du problème (ou d'un des problèmes). Elles sont exécutées lors de la définition de la classe (exécution de l'instruction 'class'). Il n'y a pas de variable 'self' à ce moment-là.
  • Oui il y a quelques erreurs c'est normal je suis en train d'écrire. Ma question est juste sur la problème que j'ai évoqué. Je ne comprends pas l'idée en fait. Pour moi je veux simplement faire hériter Floyds de Kmean et utiliser du coup la méthode mère train. Je pourrais le faire sans créer une sous classe mais j'ai bien envie de le faire comme ça pour apprendre.
  • Il n’empêche que self n’est pas défini. Peut-être que ces deux lignes devaient être décalées d’un alinéa vers la droite.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • @mini_callli

    Tu n'es pas clair car on ne sait même pas sur quelle ligne portait l'erreur dont tu as donné le message. Je crois qu'il faut que tu enlèves l'argument 'self' dans :
    super().__init__(self, C, data, Bool)
    
    Cela dit, je préfèrerais faire :
    KMeans.__init__(self, C, data, Bool)
    
    dans KLoyds.__init__() même si cela répète la classe de base, car il y a des subtilités avec cette façon d'utiliser super() (voir ici et  ; cela fait fort longtemps que j'ai lu ces liens et honnêtement, j'en ai oublié le contenu ; mais j'en ai retenu que super() utilisé ainsi peut réserver de mauvaises surprises).
  • Merci pour vos réponses, j'ai fini d'écrire mon code. Il fonctionne du moins il tourne si je puis dire !

    Comme je n'ai pas compris le problème de classes j'ai utilisé l'écriture
    classifer = Kmeans(2, data, False)
    G = [data[0], data[1]]
    clus, Gn = classifer.train(G)
    

    A présent je vais lire vos réponses.
  • @nicolas.patrois : Décalé d'un alignât vers la droite hum.

    ok je crois que j'avance
    class KLoyds(Kmeans):
        def __init__(self, C, data, Bool):
            super().__init__(self, C, data, Bool)
            self.G = np.random.choice(self.data, self.C) # Initialisation step
        def train(self):
            self.train(self.C, self.G)
    

    A présent il est pas content car TypeError: __init__() takes 4 positional arguments but 5 were given j'ai l'impression que ce n'est pas de me faute parce que j'ai bien quatres arguments même si positional argument est un mot inconnu pour moi.
  • @Brian : Merci pour l'explication c'est bon
    class KLoyds(Kmeans):
        def __init__(self, C, data, Bool):
            Kmeans.__init__(self, C, data, Bool)
            self.G =  [self.data[0], self.data[1]] # Initialisation step
        def train_Loyds(self):
            return self.train(self.G)
    
  • Bilan : super() n'est pas super pour moi :)o.
  • @Brian : Pour en revenir au sujet, j'ai l'impression en vous lisant que travailler avec des listes prends plus de temps que avec des tableaux numpy c'est ça ? Mais on garde les list parce que on ne peut pas tout faire avec numpy right ?
  • Autre question comment on fait pour selectionner $n$ éléments aléatoirement dans un tableau à plusieurs dimensions ? Typiquement dans un tableau de coordonées 2D ?

    Comme je savais pas comment faire j'ai mis
    self.G = [self.data[0], self.data[1]] # Initialisation step

    Mais bien évidement j'aimerais tirer deux points aléatoirement du tableau (500,2) appelé data
  • @mini_calli

    Les listes Python sont très flexibles et faciles à manipuler. On peut mettre n'importe quels objets dedans, y compris d'autres listes. Pour pouvoir gérer sainement le remplacement d'un élément par un autre, la permutation de deux éléments, le tri... il faut que ces opérations puissent être faites en modifiant quelque chose qui occupe très peu de mémoire : un pointeur vers l'objet remplit ce critère. Donc pour accéder à un élément, il faut 1) accéder au pointeur correspondant à l'indice spécifié (se fait en $O(1)$ d'après cette page SO et la FAQ de CPython), 2) lire ce pointeur et 3) le déréférencer, i.e. : lire ce qu'il y a à l'adresse du pointeur : un ou des octets représentant l'objet qui nous intéresse.

    À l'inverse, les tableaux NumPy (à $n$ dimensions) contiennent un paquet d'objets tous du même type, qui prennent tous la même place. Ils peuvent donc a priori être stockés directement et de manière contiguë, ce qui permet d'y accéder plus vite en lecture comme en écriture (adresse de l'élément $L[k_1, \dotsc, k_n]$ du type $(\text{adresse début de } L) + k_1 S_1 + \dotsb + k_n S_n$ où $k_1, \dotsc, k_n$ représentent les indices et $S_1, \dotsc, S_n$ les tailles des « lignes » à chaque niveau, $S_n$ étant la taille d'un élément du tableau). Avec ce système, à l'adresse calculée, on a directement l'objet stocké dans telle ou telle case du tableau. Pas besoin de déréférencer un pointeur.

    NumPy peut sans doute aussi effectuer des opérations simultanément sur divers éléments d'un tableau en utilisant les instructions vectorielles des processeurs actuels, à confirmer toutefois. Bref, NumPy permet d'être plus efficace lorsqu'on manipule des tableaux de nombres qui sont tous du même type (au sein d'un tableau donné). Par contre, cela nécessite un apprentissage. paul18 du forum a l'air de bien connaître et avait posté un exemple ici ainsi que des liens sur la vectorisation (c.-à-d. la façon de traiter les données de type tableau qui permet d'obtenir du code efficace).

    Pour ton accès à un élément aléatoire, je dirais que soit tu utilises random.randint() pour calculer chacun des deux indices, soit tu fais deux appels successifs à random.choice() : le premier renvoie une ligne choisie aléatoirement et le second un élément de cette ligne.
  • Un truc qui peut bien marcher, c’est d’aplatir ton tableau (il y a une méthode pour les tableau de numpy).
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • J'ai un peu modifié mon message précédent : d'après cette page de SO (edit : et la FAQ de CPython), les listes Python sont implémentées comme des tableaux de pointeurs, ce qui est très différent des listes chaînées. L'accès à un élément d'indice donné se fait donc a priori en temps constant, mais l'insertion et la suppression doivent être en $O(n)$, où $n$ est le nombre d'éléments de la liste après la position d'insertion ou de suppression.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!