Accélérer l'appariement des chaînes en objets en Python

Question

J'essaie de trouver un moyen efficace pour lier ensemble les lignes de données contenant les entiers de points, et de les stocker comme des objets Python. Les données se compose d' X et Y des points de coordonnées, représenté sous forme de chaînes séparées par des virgules. Les points doivent être appariés, comme en (x_1, y_1), (x_2, y_2), ... etc. et ensuite stockée sous la forme d'une liste d'objets, où chaque point est un objet. La fonction ci-dessous get_data génère cet exemple de données:

def get_data(N=100000, M=10):
    import random
    data = []
    for n in range(N):
        pair = [[str(random.randint(1, 10)) for x in range(M)],
                [str(random.randint(1, 10)) for x in range(M)]]
        row = [",".join(pair[0]),
               ",".join(pair[1])]
        data.append(row)
    return data

Le code d'analyse que j'ai maintenant est:

class Point:
    def __init__(self, a, b):
        self.a = a
        self.b = b

def test():
    import time
    data = get_data()
    all_point_sets = []
    time_start = time.time()
    for row in data:
        point_set = []
        first_points, second_points = row
        # Convert points from strings to integers
        first_points = map(int, first_points.split(","))
        second_points = map(int, second_points.split(","))
        paired_points = zip(first_points, second_points)
        curr_points = [Point(p[0], p[1]) \
                       for p in paired_points]
        all_point_sets.append(curr_points)
    time_end = time.time()
    print "total time: ", (time_end - time_start)

Actuellement, il faut compter près de 7 secondes pour 100 000 points, ce qui semble très inefficace. Une partie de l'inefficacité semble provenir de la base de calcul de first_points, second_points et paired_points - et la transformation de ces objets.

Une autre partie de l'inefficacité semble être la construction d' all_point_sets. En prenant de l' all_point_sets.append(...) ligne semble faire le code à partir de ~7 secondes à 2 secondes!

Comment cela peut-il être accéléré? merci.

SUIVI Merci pour tous les grands suggestions - ils sont tous utiles. mais même avec toutes les améliorations, c'est encore d'environ 3 secondes à 100 000 entrées. Je ne suis pas sûr pourquoi, dans ce cas, il n'est pas juste à l'instant, et si il existe une autre représentation qui en ferait l'instant. Serait-ce codage en Cython changer les choses? Quelqu'un pourrait-il offrir un exemple de cela? merci encore.

Answer 1

Lorsque vous traitez avec la création de grands nombres d'objets, souvent la plus importante de l'amélioration de la performance, vous pouvez utiliser est de transformer le garbage collector off. Chaque "génération" des objets, le garbage collector parcourt tous les objets en direct à la mémoire, à la recherche d'objets qui font partie de cycles, mais ne sont pas indiquées par des objets vivants, sont donc éligibles pour la mémoire de la remise en état. Voir Doug Helmann de PyMOTW GC article pour certaines informations (plus peut être trouvé avec google et une certaine détermination). Le garbage collector est exécuté par défaut de toutes les 700 ou si les objets créés-mais-pas-remise en état, avec les générations suivantes de course un peu moins souvent (j'ai oublié les détails).

À l'aide d'un tuple à la place d'un Point de classe peut vous faire économiser du temps (à l'aide d'un namedtuple est quelque part entre les deux), et intelligent déballage peut vous faire économiser du temps, mais le plus gros gain peut être obtenu en tournant la gc hors tension avant de votre création de lots d'objets que vous savez n'avez pas besoin d'être gc souhaitez, et puis de le rallumer par la suite.

Un peu de code:

def orig_test_gc_off():
    import time
    data = get_data()
    all_point_sets = []
    import gc
    gc.disable()
    time_start = time.time()
    for row in data:
        point_set = []
        first_points, second_points = row
        # Convert points from strings to integers
        first_points = map(int, first_points.split(","))
        second_points = map(int, second_points.split(","))
        paired_points = zip(first_points, second_points)
        curr_points = [Point(p[0], p[1]) \
                       for p in paired_points]
        all_point_sets.append(curr_points)
    time_end = time.time()
    gc.enable()
    print "gc off total time: ", (time_end - time_start)

def test1():
    import time
    import gc
    data = get_data()
    all_point_sets = []
    time_start = time.time()
    gc.disable()
    for index, row in enumerate(data):
        first_points, second_points = row
        curr_points = map(
            Point,
            [int(i) for i in first_points.split(",")],
            [int(i) for i in second_points.split(",")])
        all_point_sets.append(curr_points)
    time_end = time.time()
    gc.enable()
    print "variant 1 total time: ", (time_end - time_start)

def test2():
    import time
    import gc
    data = get_data()
    all_point_sets = []
    gc.disable()
    time_start = time.time()
    for index, row in enumerate(data):
        first_points, second_points = row
        first_points = [int(i) for i in first_points.split(",")]
        second_points = [int(i) for i in second_points.split(",")]
        curr_points = [(x, y) for x, y in zip(first_points, second_points)]
        all_point_sets.append(curr_points)
    time_end = time.time()
    gc.enable()
    print "variant 2 total time: ", (time_end - time_start)

orig_test()
orig_test_gc_off()
test1()
test2()

Quelques résultats:

>>> %run /tmp/flup.py
total time:  6.90738511086
gc off total time:  4.94075202942
variant 1 total time:  4.41632509232
variant 2 total time:  3.23905301094

Answer 2

Le simple fait de courir avec Pypy fait une grande différence

 $ python pairing_strings.py 
total time:  2.09194397926
$ pypy pairing_strings.py 
total time:  0.764246940613
 

désactiver gc n'a pas aidé pour pypy

 $ pypy pairing_strings.py 
total time:  0.763386964798
 

namedtuple pour Point aggrave

 $ pypy pairing_strings.py 
total time:  0.888827085495
 

en utilisant itertools.imap et itertools.izip

 $ pypy pairing_strings.py 
total time:  0.615751981735
 

Utilisation d'une version mémorisée de int et d'un itérateur pour éviter le zip

 $ pypy pairing_strings.py 
total time:  0.423738002777 
 

Voici le code avec lequel j'ai fini.

 def test():
    import time
    def m_int(s, memo={}):
        if s in memo:
            return memo[s]
        else:
            retval = memo[s] = int(s)
            return retval
    data = get_data()
    all_point_sets = []
    time_start = time.time()
    for xs, ys in data:
        point_set = []
        # Convert points from strings to integers
        y_iter = iter(ys.split(","))
        curr_points = [Point(m_int(i), m_int(next(y_iter))) for i in xs.split(",")]
        all_point_sets.append(curr_points)
    time_end = time.time()
    print "total time: ", (time_end - time_start)
 

Answer 3

Je voudrais

• utiliser numpy tableaux pour ce problème (Cython serait une option, si ce n'est toujours pas assez rapide).
• stocker les points comme un vecteur non pas comme simple Point des cas.
• s'appuyer sur les analyseurs existants
• (si possible) d'analyser les données une seule fois et de le stocker dans un format binaire comme hdf5 pour d'autres calculs, qui sera l'option la plus rapide (voir ci-dessous)

Numpy a des fonctions intégrées pour lire des fichiers texte, par exemple loadtxt. Si vous avez les données stockées dans un tableau structuré, vous n'avez pas nécessairement besoin de la convertir en un autre type de données. Je vais utiliser les Pandas qui est une bibliothèque de construire au-dessus de numpy. Il est un peu plus pratique pour la manipulation et le traitement de données structurées. Pandas a son propre analyseur de fichier read_csv.

Pour le moment, j'ai écrit les données dans un fichier, comme dans l'original de votre problème (il est basé sur votre get_data):

import numpy as np
import pandas as pd

def create_example_file(n=100000, m=20):
    ex1 = pd.DataFrame(np.random.randint(1, 10, size=(10e4, m)),
                       columns=(['x_%d' % x for x in range(10)] +
                                ['y_%d' % y for y in range(10)]))
    ex1.to_csv('example.csv', index=False, header=False)
    return

C'est le code que j'ai utilisé pour lire les données dans un pandas.DataFrame:

def with_read_csv(csv_file):
    df = pd.read_csv(csv_file, header=None,
                     names=(['x_%d' % x for x in range(10)] +
                            ['y_%d' % y for y in range(10)]))
    return df

(Notez que je suppose, qu'il n'y a pas d'en-tête de votre fichier et j'ai donc dû créer les noms de colonne.)

La lecture des données est rapide, il devrait être plus efficace en terme de mémoire (voir à cette question) et les données sont stockées dans une structure de données vous pouvez continuer à travailler dans un rapide, vectorisé façon:

In [18]: %timeit string_to_object.with_read_csv('example.csv')
1 loops, best of 3: 553 ms per loop

Il y a un nouveau C en fonction de l'analyseur dans une branche de développement qui prend 414 ms sur mon système. Votre test prend 2.29 s sur mon système, mais il n'est pas vraiment comparable, car les données ne sont pas lues à partir d'un fichier et que vous avez créé l' Point des cas.

Si vous avez lu une fois dans les données que vous pouvez stocker dans un hdf5 le fichier:

In [19]: store = pd.HDFStore('example.h5')

In [20]: store['data'] = df

In [21]: store.close()

La prochaine fois vous avez besoin des données vous pouvez le lire à partir de ce fichier, qui est vraiment très rapide:

In [1]: store = pd.HDFStore('example.h5')

In [2]: %timeit df = store['data']
100 loops, best of 3: 16.5 ms per loop

Toutefois, il ne sera applicable, si vous avez besoin des mêmes données plusieurs fois.

À l'aide de numpy base de tableaux de grands ensembles de données présente des avantages lorsque vous sont en train de faire d'autres calculs. Cython ne serait pas nécessairement plus rapide si vous pouvez utiliser vectorisé numpy fonctions et de l'indexation, il sera plus rapide si vous avez vraiment besoin d'itération (voir aussi cette réponse).

Answer 4

Méthode la plus rapide, à l'aide de Numpy (accélération d'environ 7x):

import numpy as np
txt = ','.join(','.join(row) for row in data)
arr = np.fromstring(txt, dtype=int, sep=',')
return arr.reshape(100000, 2, 10).transpose((0,2,1))

Comparaison des performances:

def load_1(data):
    all_point_sets = []
    gc.disable()
    for xs, ys in data:
        all_point_sets.append(zip(map(int, xs.split(',')), map(int, ys.split(','))))
    gc.enable()
    return all_point_sets

def load_2(data):
    txt = ','.join(','.join(row) for row in data)
    arr = np.fromstring(txt, dtype=int, sep=',')
    return arr.reshape(100000, 2, 10).transpose((0,2,1))

load_1 s'exécute dans 1.52 secondes sur ma machine, load_2 s'exécute dans de 0,20 secondes, 7 fois l'amélioration. Le gros inconvénient ici est que il faut que vous (1) connaître les longueurs de tout à l'avance, et (2) que chaque ligne contient exactement le même nombre de points. Cela est vrai pour votre get_data de la production, mais peut ne pas être vrai pour le vrai jeu de données.

Answer 5

J'ai obtenu une amélioration de 50% par l'aide de tableaux, et un support d'objet que paresseusement des constructions d'objets Point lors de l'accès. J'ai aussi "fendue" le Point de l'objet pour mieux l'efficacité du stockage. Cependant, un tuple serait probablement mieux.

La modification de la structure de données peut également aider, si c'est possible. Mais ce ne sera jamais instantanée.

from array import array

class Point(object):
    __slots__ = ["a", "b"]
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __repr__(self):
        return "Point(%d, %d)" % (self.a, self.b)

class Points(object):
    def __init__(self, xs, ys):
        self.xs = xs
        self.ys = ys

    def __getitem__(self, i):
        return Point(self.xs[i], self.ys[i])

def test3():
    xs = array("i")
    ys = array("i")
    time_start = time.time()
    for row in data:
        xs.extend([int(val) for val in row[0].split(",")])
        ys.extend([int(val) for val in row[1].split(",")])
    print ("total time: ", (time.time() - time_start))
    return Points(xs, ys)

Mais lorsque de grandes quantités de données, j'avais l'habitude d'utiliser numpy N dimensions des tableaux (ndarray). Si l'original de la structure de données peut être modifié alors qui serait susceptible d'être le plus rapide de tous. Si elle pouvait être structuré de manière à lire x,y paires dans linéairement puis remodeler le ndarray.