3
votes

Je dois comparer les données de chaque ligne d'un Pandas DataFrame avec les données du reste des lignes, existe-t-il un moyen d'accélérer le calcul?

Disons que j'ai un pandas DataFrame (chargé à partir d'un fichier csv) avec cette structure (le nombre de colonnes var et err n'est pas fixe et varie d'un fichier à l'autre):

import numpy as np
import pandas as pd

def couple_already_tested(index1, index2, dataframe):
    return (((dataframe['SET_A'] == index1) & (dataframe['SET_B'] == index2)).any()) | (((dataframe['SET_A'] == index2) & (dataframe['SET_B'] == index1)).any())

def check_dominance(set_a, set_b, index_i, index_j, dataframe):
    length = dataframe.shape[0]
    if np.all(set_a >= set_b):
        print("FOUND DOMINANT CONFIGURATION A > B")
        dataframe.loc[length+1] = [index_i,index_j,'A']
    elif np.all(set_b >= set_a):
        print("FOUND DOMINANT CONFIGURATION B > A")
        dataframe.loc[length+1] = [index_i,index_j,'B']
    else:
        dataframe.loc[length+1] = [index_i,index_j,'none']

df = pd.read_csv('test.csv', sep=';')
dom_table_df = pd.DataFrame(columns=['SET_A','SET_B','DOMINANT_SET'])
df_length = df.shape[0]
var_num = df.shape[1]-1 

a = None
b = None

for i in range(0, df_length):
    a = df.iloc[i, 0:var_num].values
    for j in range(0, df_length):
        if j == i:
            continue
        b = df.iloc[j, 0:var_num].values
        if couple_already_tested(i,j,dom_table_df):
            print("WARNING: configuration", i, j, "already compared, skipping")
        else:
            print("Comparing configuration at row", i, "with configuration at row", j)
            check_dominance(a, b, i, j, dom_table_df)

print(dom_table_df)

Supprimons les colonnes err_ds_j et err_mean pour le bien de cette question. Je dois effectuer une comparaison automatique des valeurs de chaque ligne, avec les valeurs des autres lignes; à titre d'exemple: je dois comparer la première ligne avec la deuxième ligne, puis avec la troisième, puis avec la quatrième, et ainsi de suite, puis je dois prendre la deuxième ligne et la comparer avec la première, puis avec la troisième un, et ainsi de suite pour le reste du DataFrame.

Pour approfondir le problème, je veux voir si pour chaque couple de lignes, toutes les valeurs "var_i" de l'une d'entre elles sont supérieures ou égales à les valeurs correspondantes de l'autre ligne. Si cela est satisfait, la ligne avec les valeurs les plus élevées est appelée DOMINANT, et j'ajoute une ligne dans un autre DataFrame, avec cette structure:

   SET_A SET_B DOMINANT_SET
1      0     1            B
2      0     2         none
3      0     3            A
4      0     4            A
5      0     5            B
6      0     6         none
7      0     7         none
8      1     2            A
9      1     3            A
10     1     4            A
11     1     5         none
12     1     6            A
13     1     7         none
14     2     3            A
15     2     4         none
16     2     5            B
17     2     6            B
18     2     7            B
19     3     4            B
20     3     5            B
21     3     6            B
22     3     7            B
23     4     5            B
24     4     6         none
25     4     7         none
26     5     6            A
27     5     7         none
28     6     7            B

Où les valeurs SET_A et SET_B sont des indices de le csv DataFrame, et DOMINANT_SET me dit lequel des deux est l'ensemble dominant (ou s'il n'y en a pas, il est simplement assigné à "aucun"). J'ai trouvé la troisième colonne utile car elle m'aide à éviter la comparaison des lignes que j'ai déjà comparées de manière opposée (par exemple: comparer la ligne 1 avec la ligne 0 est inutile, car j'ai déjà comparé 0 et 1 précédemment).

Donc, pour ce fichier csv, la sortie produite devrait être (et est en fait, avec mon code):

SET_A; SET_B; DOMINANT_SET
0;     1;     B
...

J'ai déjà tout écrit du code pour ce problème particulier, et cela fonctionne très bien avec certains ensembles de données de test (100 lignes échantillonnées à partir d'un ensemble de données réel).

Voici un extrait du code pertinent:

var_0; var_1; var_2;
32;    9;     41;
47;    22;    41;
15;    12;    32;
3;     4;     4;
10;    9;     41;
43;    21;    45;
32;    14;    32;
51;    20;    40;

Le problème est que, n'étant pas aussi compétent en python et en pandas (je les apprends depuis environ un mois et demi), ce code est bien sûr terriblement lent (pour les ensembles de données avec, comme , 1000 à 10000 lignes) car j'utilise des itérations dans mon algorithme. Je sais que je peux utiliser quelque chose appelé vectorisation, mais en lisant à ce sujet, je ne suis pas tout à fait sûr que ce soit bon pour mon cas d'utilisation.

Alors, comment pourrais-je accélérer les calculs?

p >


5 commentaires

voir si drop_duplicates est utile pour vous


Merci pour vos commentaires, mohanys, j'ai modifié ma question avec vos suggestions et je vais examiner drop_duplicates dès maintenant.


Merci encore pour la suggestion et pour votre temps, malheureusement drop_duplicates pourrait ne pas convenir à mon problème, car mon problème est probablement dans la boucle for, qui est une boucle imbriquée (corrigez-moi si je me trompe, mais la complexité devrait être O (n ^ 2), ce qui est terrible avec un jeu de données de 10000 lignes).


Note latérale: Selon la définition, deux lignes peuvent être dominantes l'une par rapport à l'autre en même temps si elles sont égales, mais l'algorithme ne produira que A dans ce cas.


Merci pour la tête Armali! Il s'agit en fait d'un oubli, mais qui n'a pas d'incidence sur toute l'analyse.


3 Réponses :


1
votes

Ce n'est pas un changement majeur de l'algorithme, mais vous pouvez enregistrer plus de la moitié des cycles de boucle ainsi que les tests pour j == i et couple_already_tested si vous choisissez la plage pour j de manière adéquate, de sorte que les boucles principales deviennent:

for i in range(0, df_length):
    a = df.iloc[i, 0:var_num].values
    for j in range(i+1, df_length): # we can skip the range from 0 to i
        b = df.iloc[j, 0:var_num].values
        #print("Comparing configuration at row", i, "with configuration at row", j)
        check_dominance(a, b, i, j, dom_table_df)


1 commentaires

Whoa! Cela accélère définitivement le processus dans une certaine mesure, merci! J'essaierai également de rechercher des moyens de paralléliser des parties de la boucle afin de l'accélérer davantage.



1
votes

Une autre accélération (étonnamment) significative peut être accomplie en préallouant le DataFrame de sortie plutôt qu'en ajoutant une ligne après l'autre. Nous pouvons calculer le nombre de lignes résultant comme

  • (df_length 2 - df_length ) ÷ 2

Afin de déterminer le numéro de ligne où insérer le jeu de données de sortie actuel, nous pouvons maintenant maintenir un compteur au lieu de dataframe.shape [0] . Cela donne:

dom_table_df = pd.DataFrame(index=np.arange(1, 1+(df_length**2-df_length)/2).astype('i'),
                            columns=['SET_A', 'SET_B', 'DOMINANT_SET'])
length = 0  # counter of already filled rows
for i in range(0, df_length):
    a = df.iloc[i, 0:var_num].values
    for j in range(i+1, df_length): # we can skip the range from 0 to i
        b = df.iloc[j, 0:var_num].values
        #print("Comparing configuration at row", i, "with configuration at row", j)
        length += 1
        if np.all(a >= b):
            #print("FOUND DOMINANT CONFIGURATION A > B")
            dom_table_df.loc[length] = [i, j, 'A']
        elif np.all(b >= a):
            #print("FOUND DOMINANT CONFIGURATION B > A")
            dom_table_df.loc[length] = [i, j, 'B']
        else:
            dom_table_df.loc[length] = [i, j, 'none']


2 commentaires

hmmm, pourquoi ne pas mettre les 3 réponses en une seule?


Parce que chaque pièce est une optimisation discrète à part entière.



1
votes

Une autre accélération peut être accomplie en remplaçant .iloc []. values ​​ ainsi que .loc [] par .values ​​[] , mais avec .loc [] nous devons ajuster l'indice, car .values ​​ prend un indice de base zéro, qui est différent de notre dom_table_df basé sur 1. index .

dom_table_df = pd.DataFrame(index=np.arange(1, 1+(df_length**2-df_length)/2).astype('i'),
                            columns=['SET_A', 'SET_B', 'DOMINANT_SET'])
length = 0  # counter of already filled rows
for i in range(0, df_length):
    a = df.values[i, 0:var_num]
    for j in range(i+1, df_length): # we can skip the range from 0 to i
        b = df.values[j, 0:var_num]
        #print("Comparing configuration at row", i, "with configuration at row", j)
        if np.all(a >= b):
            #print("FOUND DOMINANT CONFIGURATION A > B")
            dom_table_df.values[length] = [i, j, 'A']
        elif np.all(b >= a):
            #print("FOUND DOMINANT CONFIGURATION B > A")
            dom_table_df.values[length] = [i, j, 'B']
        else:
            dom_table_df.values[length] = [i, j, 'none']
        length += 1


1 commentaires

Ok, c'est vraiment fou, celui-ci, ainsi que les deux autres suggestions, m'ont fait parcourir un ensemble de données de 1000 lignes en 2 minutes au lieu de 12 heures. Je ne sais vraiment pas comment vous remercier assez!