IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Calcul scientifique Python Discussion :

Algorithme pour préparation de matrice creuse


Sujet :

Calcul scientifique Python

  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    avril 2010
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2010
    Messages : 22
    Points : 20
    Points
    20
    Par défaut Algorithme pour préparation de matrice creuse
    Bonjour, j'ai un dictionnaire de synonyme que je représente sous la forme d'un... dictionnaire Python. C'est à dire :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    d
    {'abasourdi' : ['étonné', 'hébété'],
    'abondant' : ['riche', 'copieux', 'luxuriant'],
    ...
    }
    Afin de pouvoir travailler efficacement dessus, je souhaiterais transformer ce dictionnaire en :
    1- un tuple ordonné d'entrées, donc ici quelque chose comme names = ('abasourdi', 'abondant', etc...)
    2- une matrice creuse où M(i,j) == 1 si et seulement si le mot names[j] apparaît dans la liste des synonymes du mot names[i]

    J'ai donc tenté de construire les trois listes I,J,V qui représentent cette matrice au format COO; c'est donc les indices de valeurs non nulle de ma matrice au format (row, column, value) avec value=1

    Voici le bout de code qui effectue cette tâche :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    keys = tuple(sorted(d.keys()))
    Nentries = len(keys)
    indices = range(Nentries)
     
    # Construction of I,J,V vectors in COO format
     
    I = []; J = []; V = [];
     
    for (name, syno_list) in d.items():
        rank_key = keys.index(name)
        rank_values = [keys.index(n) for n in syno_list]
        if len(rank_values)>0: # This should always be the case, but we check
            I.append(rank_key*len(rank_values))
            J.append(rank_values)
            V.append([1]*len(rank_values))
    Le problème ? Avec un dictionnaire qui contient Nentries = 36 178 entrées, c'est très lent !

    Avez-vous des idées pour optimiser cela ?

    Merci d'avance et bonne journée

    D.

  2. #2
    Membre régulier
    Inscrit en
    juillet 2013
    Messages
    73
    Détails du profil
    Informations forums :
    Inscription : juillet 2013
    Messages : 73
    Points : 111
    Points
    111
    Par défaut
    Bonjour,

    Est-ce que vous pouvez communiquer le fichier contenant les données ?

  3. #3
    Membre à l'essai
    Profil pro
    Inscrit en
    avril 2010
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2010
    Messages : 22
    Points : 20
    Points
    20
    Par défaut
    Bonjour charliemtx,
    merci pour l'intérêt porté à ma requête

    Le fichier zip contenant les données peut être téléchargé ici : https://grammalecte.net/download/fr/thesaurus-v2.3.zip
    Il s'agit du fichier "thes_fr.dat"

    Voici mon script complet :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-
    """
    Created on Fri Apr  9 00:09:39 2021
     
    @author: donutman
    """
     
    from scipy import sparse
    from numpy import savez
     
    def print_entry(name, syno_list):
        print("- %s : %s" %  (name, ' - '.join(syno_list) ) )
     
     
     
    filein = './data/step0/thes_fr.dat'
    fileout1 = './data/step1/thesaurus_matrix'
    fileout2 = './data/step1/thesaurus_entries'
     
    d = {} # empty dictionnary
    name = ""
    syno_list = []
     
     
    # STEP 1 : we read the input file and parse the data in a dictionnary structure
    print('''
    ******************************
     
          STEP 1
          
    ******************************
    ''')
     
    with open(filein, mode='rt', encoding='utf-8') as f:
        next(f) # we skip first line
        for line in f:
            line = line.rstrip('\n')
            if not line.startswith('('): # we read a new entry !
                # First, we need to add the previous entry into our dictionnary
                # But only if name is not empty !
                if not name=="":
                    #print_entry(name, syno_list)
                    d[name] = syno_list
                    syno_list = []
     
                (name, _) = line.split('|')
            else:
                syno_list_tmp = line.split('|')
                del syno_list_tmp[0]
                syno_list = syno_list + syno_list_tmp
     
    # Now that we read all the entries we need to add the last entry
    d[name] = syno_list
     
     
     
    # STEP 2 : we go through the dictionnary and delete synonyms that are NOT
    # an entry of the dictionnary itself (self consistency check)
     
    print('''
    ******************************
     
          STEP 2
          
    ******************************
    ''')
     
    d2 = {}
     
    for (name, syno_list) in d.items():
        syno_list_2 = [syno for syno in syno_list if syno in d.keys()]
        deleted_words = set(syno_list).symmetric_difference(set(syno_list_2))
     
        if len(deleted_words)>0:
            #print('****')
            #print('l1 : %s' % ' - '.join(syno_list))
            #print('l2 : %s' % ' - '.join(syno_list_2))
            print('- Deleted entries for "%s" : %s' % ( name, " - ".join(deleted_words) ))
        d2[name] = syno_list_2
     
     
    # STEP 3 : Now we want to convert all that in a sparse matrix
    # This step is a little bit slow and might be in some way optmized...
    print('''
    ******************************
     
          STEP 3
          
    ******************************
    ''')
     
     
    keys = tuple(sorted(d2.keys()))
    Nentries = len(keys)
    indices = range(Nentries)
     
    # Construction of I,J,V vectors in COO format
     
    I = []; J = []; V = [];
     
    for (name, syno_list) in d2.items():
        rank_key = keys.index(name)
        rank_values = [keys.index(n) for n in syno_list]
        if len(rank_values)>0: # This should always be the case, but we check
            I.extend([rank_key]*len(rank_values))
            J.extend(rank_values)
            V.extend([1]*len(rank_values))
     
     
    M = sparse.coo_matrix((V, (I,J)), shape=(Nentries, Nentries), dtype=bool)
     
     
    sparse.save_npz(fileout1, M)
    savez(fileout2, names=keys)
    Quelques remarques additionnelles :
    STEP1 lit les données de thes_fr.dat et stocke tout dans un dictionnaire python
    STEP2 supprime les synonymes qui ne sont pas eux-mêmes des entrées du dictionnaire (on voit à ce propos passer un certain nombre de mots mal orthographiés)
    STEP3 transforme tout ça sous la forme d'une matrice creuse

    Par rapport à mon post initial, j'ai remplacé les .append() par .extend() qui fusionnent les listes (c'est plus proche de ce que je souhaite faire).
    In fine, j'arrive bien à mes fins mais je me demandais s'il n'était pas possible de faire plus simple et plus malin en Python...

    Par exemple, j'aurais peut-être pu pré-allouer les vecteur I,J,V... je ne sais pas trop...

    Merci pour tout avis sur la qualité du code

    D.

  4. #4
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    juin 2008
    Messages
    17 735
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 17 735
    Points : 30 621
    Points
    30 621
    Par défaut
    Salut,

    Citation Envoyé par DonutMan Voir le message
    Avec un dictionnaire qui contient Nentries = 36 178 entrées, c'est très lent !
    Ça prend combien de temps? Et qu'espérez vous comme durée?

    A priori, c'est une opération que vous allez faire une seule fois (puisque le dictionnaire initial évolue peu).

    Sauvegarder le résultat dans un fichier dans un format approprié (json, pickle) et le relire plutôt que le recalculer pourrait être une solution qui permettra de valider ce que vous pensez faire avec cette structure là (optimiser pourra venir plus tard, mais il vaut mieux le faire lorsque l'algo et le code seront un peu stables).

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  5. #5
    Membre chevronné

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    mars 2013
    Messages
    1 116
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : mars 2013
    Messages : 1 116
    Points : 2 094
    Points
    2 094
    Par défaut
    C'est normal que votre step 3 soit très long avec un algorithme pareil !
    Toute la lenteur se trouve là :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    for (name, syno_list) in d.items():
        rank_key = keys.index(name)
        rank_values = [keys.index(n) for n in syno_list]
    Votre dictionnaire contient 36178 entrées. Vous faites donc déjà autant d'appel à la fonction index. Puis ensuite pour chaque synonyme de chaque mots, vous réappeler cette méthode index. Donc au total vous appelez environ 450 000 fois cette fonction ! Mais vous vous rendez compte qu'à chaque appel de cette fonction, Python va parcourir tout votre dico, pour trouver le mot chercher (et donc sa position) ? Une fonction de recherche par définition c'est déjà pas super rapide (comparer à si vous deviez chercher la définition d'un mot dans un dictionnaire, c'est une tache tout aussi complexe pour python que pour vous), mais alors là, l'appeler autant de fois ...

    Donc :
    1) Les synonymes étant aussi des clés du dictionnaires on n'a pas besoin de recalculer tout ces index ! On calcule ceux des clés du dictionnaire, on les stocke, et quand on a besoin d'un index sur un synonyme et bien c'est le même que sur la clé (c'est le principe de ce genre de matrice)
    2) Si on les stocke dès le départ, et bien on peut meme s'affranchir de faire une recherche d'index pour chaque mot : juste on les prends dans l'ordre, et on mémorise son index associé dans un dico.

    Ca donne ca, qui s'éxécute en moins d'une seconde

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    keys = tuple(sorted(d2.keys()))
    Nentries = len(keys)
    positions = { k:i for i,k in enumerate(keys) }  #### La ligne de prétraitement super importante qui stocke tous les indices pour ne pas avoir à les recalculer à chaque fois
     
    # Construction of I,J,V vectors in COO format
     
    I = []; J = [];
     
    for rank_key in range(Nentries):
        name = keys[rank_key]
        syno_list = d2[name]
        nb_syno = len(syno_list)
        if nb_syno>0: # This should always be the case, but we check
            I.extend([rank_key]*nb_syno)
            J.extend( positions[syno] for syno in syno_list )
     
     
    V = [1]*len(I) 
    M = scipy.sparse.coo_matrix((V, (I,J)), shape=(Nentries, Nentries), dtype=bool)

    Et j'ai également sorti le calcul de V, car il n'a absolument pas d'intérêt de le calculer à cout d'extend successif : c'est juste un vecteur rempli de 1 qui a la meme taille que I et J.

    Pour les autres step je n'ai pas regardé si le code était améliorable (certainement), vu que la lenteur vient uniquement du step 3.

  6. #6
    Membre à l'essai
    Profil pro
    Inscrit en
    avril 2010
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2010
    Messages : 22
    Points : 20
    Points
    20
    Par défaut
    Bonjour,
    super, merci beaucoup pour cette astuce !
    En effet, c'est désormais quasi instantané.

    Bonne soirée à tous

    D.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algorithme de Cuthill McKee pour transformer une matrice creuse en matrice bande
    Par Domi1966 dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 08/04/2020, 17h44
  2. [Lazarus] Un conteneur pour matrices creuses
    Par JP CASSOU dans le forum Lazarus
    Réponses: 4
    Dernier message: 21/06/2018, 23h44
  3. Algorithme pour générer des matrices
    Par senacle dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 13/12/2007, 14h32
  4. Code pour matrice creuse (sparse matrix)
    Par Xavier dans le forum C++Builder
    Réponses: 1
    Dernier message: 02/11/2007, 17h41
  5. Algorithme pour chiffres significatifs en Assembleur
    Par lutin2003 dans le forum Assembleur
    Réponses: 5
    Dernier message: 09/09/2004, 10h47

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo