Quel est l'objet le plus rapide (pour accéder) de type struct en Python?

Question

Je suis de l'optimisation de code dont le principal goulot d'étranglement est en cours d'exécution à travers et de l'accès à une liste très importante des struct-comme des objets. Actuellement, je suis en utilisant namedtuples, pour des raisons de lisibilité. Mais certains rapide analyse comparative de l'utilisation de 'timeit" montre que ce n'est vraiment pas la bonne manière d'aller là où la performance est un facteur:

Nommé tuple avec a, b, c:

>>> timeit("z = a.c", "from __main__ import a")
0.38655471766332994

Classe à l'aide d' __slots__, avec a, b, c:

>>> timeit("z = b.c", "from __main__ import b")
0.14527461047146062

Dictionnaire avec les touches a, b, c:

>>> timeit("z = c['c']", "from __main__ import c")
0.11588272541098377

Tuple avec trois valeurs, à l'aide d'une clé constante:

>>> timeit("z = d[2]", "from __main__ import d")
0.11106188992948773

Liste avec trois valeurs, à l'aide d'une clé constante:

>>> timeit("z = e[2]", "from __main__ import e")
0.086038238242508669

Tuple avec trois valeurs, à l'aide d'une clé locale:

>>> timeit("z = d[key]", "from __main__ import d, key")
0.11187358437882722

Liste avec trois valeurs, à l'aide d'une clé locale:

>>> timeit("z = e[key]", "from __main__ import e, key")
0.088604143037173344

Tout d'abord, est-il quelque chose à propos de ces petits timeit tests qui permettraient de rendre non valide? J'ai couru chacun plusieurs fois, afin de s'assurer qu'aucun système aléatoire de l'événement avait jeté au loin, et les résultats sont presque identiques.

Il semblerait que les dictionnaires offrent le meilleur équilibre entre les performances et la lisibilité, avec des classes de venir en seconde. C'est malheureux, car, pour ma part, j'ai aussi besoin de l'objet de la séquence-comme; d'où mon choix de namedtuple.

Les listes sont sensiblement plus rapide, mais constante, les touches sont difficile à maintenir; je dois créer un groupe de l'indice de constantes, c'est à dire KEY_1 = 1, KEY_2 = 2, etc. qui n'est pas idéal.

Suis-je coincé avec ces choix, ou est-il une autre solution que j'ai manqué?

Answer 1

Une chose à garder à l'esprit est que namedtuples sont optimisés pour l'accès des n-uplets. Si vous changez d'accesseur pour être a[2] au lieu de a.c, vous verrez des performances similaires à la n-uplets. La raison en est que le nom des accesseurs sont effectivement traduire dans les appels à soi-même[idx], afin de payer à la fois l'indexation et la recherche par nom prix.

Si votre modèle d'utilisation est telle que l'accès par nom est commun, mais l'accès en tant que tuple n'est pas le cas, vous pourriez écrire un petit équivalent à namedtuple qui fait des choses de la manière opposée: la diffère de l'indice de recherches pour l'accès par nom. Cependant, vous aurez à payer le prix de l'indice des recherches alors. Par exemple, voici une rapide mise en œuvre:

def makestruct(name, fields):
    fields = fields.split()
    import textwrap
    template = textwrap.dedent("""\
    class {name}(object):
        __slots__ = {fields!r}
        def __init__(self, {args}):
            {self_fields} = {args}
        def __getitem__(self, idx): 
            return getattr(self, fields[idx])
    """).format(
        name=name,
        fields=fields,
        args=','.join(fields), 
        self_fields=','.join('self.' + f for f in fields))
    d = {'fields': fields}
    exec template in d
    return d[name]

Mais les temps sont très mauvais en __getitem__ doit être appelé:

namedtuple.a  :  0.473686933517 
namedtuple[0] :  0.180409193039
struct.a      :  0.180846214294
struct[0]     :  1.32191514969

c'est à dire, la même performance en __slots__ classe pour l'attribut d'accès (sans surprise - qu'est ce que c'est), mais d'énormes pénalités en raison de la double recherche dans des index d'accès. (Il convient de noter que __slots__ n'a pas vraiment d'une grande aide en termes de vitesse. Il permet d'économiser la mémoire, mais le temps d'accès est sur la même sans eux.)

Une troisième option serait de dupliquer les données, par exemple. sous-classe de la liste et de stocker les valeurs dans les attributs et les listdata. Cependant, vous n'avez pas réellement obtenir la liste des performances équivalentes. Il y a une grande vitesse de frapper juste en ayant sous-classé (qui en vérifie pur python surcharges). Ainsi struct[0] encore faut environ 0,5 s (comparativement à 0,18 pour les matières premières de la liste) dans ce cas, et vous ne double l'utilisation de la mémoire, de sorte que cela peut ne pas être en vaut la peine.

Answer 2

Un couple de points et des idées:

1) Vous êtes timing d'accéder au même indice de nombreuses fois dans une rangée. Votre programme utilise probablement aléatoire ou linéaire d'accès, ce qui aura un comportement différent. En particulier, il n'y aura plus de CPU cache. Vous pourriez obtenir des résultats légèrement différents à l'aide de votre programme actuel.

2) OrderedDictionary est écrit comme un wrapper autour de dict, ergo il sera plus lent qu' dict. C'est une non-solution.

3) Avez-vous essayé les deux un style nouveau et vieux style de classes? (nouveau style de classes héritent de object; style ancien classes n')

4) Avez-vous essayé d'utiliser psyco ou Unladen Swallow?

5) est-ce que votre boucle intérieure pour modifier les données ou tout simplement y avoir accès? Il pourrait être possible de transformer les données de la manière la plus efficace possible avant d'entrer dans la boucle, mais l'utilisation de la forme la plus commode ailleurs dans le programme.

Answer 3

Je serais tenté soit (a) d’inventer une sorte de cache spécifique à une charge de travail, et de décharger le stockage et la récupération de mes données sur un processus semblable à celui de memcachedb, afin d’améliorer l’évolutivité plutôt que les performances seules, ou (b) de réécrire sous la forme d’une extension C, avec stockage de données natif. Un type de dictionnaire ordonné peut-être.

Vous pouvez commencer par ceci: http://www.xs4all.nl/~anthon/Python/ordereddict/

Answer 4

Vous pouvez faire vos classes séquence comme par l'ajout d' __iter__, et __getitem__ méthodes, afin de les rendre séquence de type (indexable et itératif.)

Serait une OrderedDict travail? Il existe plusieurs implémentations disponibles, et il est inclus dans le Python31 collections module.