32 votes

Accès efficace à des dictionnaires arbitrairement profonds

Supposons que j'ai un multi-niveau de dictionnaire comme ceci

mydict = {
    'first': {
        'second': {
            'third': {
                'fourth': 'the end'
             }
         }
     }
}

J'aimerais y accéder comme ça

test = get_entry(mydict, 'first.second.third.fourth')

Ce que j'ai à ce jour est

def get_entry(dict, keyspec):
    keys = keyspec.split('.')

    result = dict[keys[0]]
    for key in keys[1:]:
       result = dict[key]

    return result

Existe-il des moyens plus efficaces de le faire? Selon %timeit l'exécution de la fonction est de 1,26 nous, lors de l'accès au dictionnaire de la manière standard comme ceci

foo = mydict['first']['second']['third']['fourth']

prend 541ns. Je suis à la recherche de moyens pour couper 800ns gamme si possible.

Merci

13voto

tdelaney Points 7235

J'ai eu 20% de gain de performances en resserrant un peu le code, mais une énorme augmentation de 400% par l'utilisation d'un cache pour le fractionnement des chaînes de caractères. Cela ne fait qu'une différence si vous utilisez le même spec plusieurs fois. Voici un exemple de mise en œuvre et d'un profil de script de test.

test.py

mydict = {
    'first': {
        'second': {
            'third': {
                'fourth': 'the end'
             }
         }
     }
}

# original
def get_entry(dict, keyspec):
    keys = keyspec.split('.')

    result = dict[keys[0]]
    for key in keys[1:]:
       result = result[key]

    return result

# tighten up code
def get_entry_2(mydict, keyspec):
    for key in keyspec.split('.'):
        mydict = mydict[key]
    return mydict

# use a cache
cache = {}
def get_entry_3(mydict, keyspec):
    global cache
    try:
        spec = cache[keyspec]
    except KeyError:
        spec = tuple(keyspec.split('.'))
        cache[keyspec] = spec

    for key in spec:
        mydict = mydict[key]
    return mydict

if __name__ == "__main__":
    test = get_entry(mydict, 'first.second.third.fourth')
    print(test)

profile.py

from timeit import timeit
print("original get_entry")
print(timeit("get_entry(mydict, 'first.second.third.fourth')",
    setup="from test import get_entry, mydict"))

print("get_entry_2 with tighter code")
print(timeit("get_entry_2(mydict, 'first.second.third.fourth')",
    setup="from test import get_entry_2, mydict"))

print("get_entry_3 with cache of split spec")
print(timeit("get_entry_3(mydict, 'first.second.third.fourth')",
    setup="from test import get_entry_3, mydict"))

print("just splitting a spec")
print(timeit("x.split('.')", setup="x='first.second.third.fourth'"))

Le timing de ma machine est

original get_entry
4.148535753000033
get_entry_2 with tighter code
3.2986323120003362
get_entry_3 with cache of split spec
1.3073233439990872
just splitting a spec
1.0949148639992927

Notez que le fractionnement de la spec est relativement onéreuse pour cette fonction. C'est pourquoi la mise en cache permet.

12voto

coldspeed Points 111053

Il n'y a vraiment qu'une seule solution. Reconstruire votre dictionnaire. Mais faire juste une fois.

def recursive_flatten(mydict):
    d = {}
    for k, v in mydict.items():
        if isinstance(v, dict):
            for k2, v2 in recursive_flatten(v).items():
                d[k + '.' + k2] = v2 
        else:
            d[k] = v
    return d

In [786]: new_dict = recursive_flatten(mydict); new_dict
Out[786]: {'first.second.third.fourth': 'the end'}

(Des tests un peu plus)

In [788]: recursive_flatten({'x' : {'y' : 1, 'z' : 2}, 'y' : {'a' : 5}, 'z' : 2})
Out[788]: {'x.y': 1, 'x.z': 2, 'y.a': 5, 'z': 2}

In [789]: recursive_flatten({'x' : 1, 'y' : {'x' : 234}})
Out[789]: {'x': 1, 'y.x': 234}

Tous les accès devient constante de temps à partir d'ici.

Maintenant, il suffit d'accéder à votre valeur à l'aide d' new_dict['first.second.third.fourth']. Devrait fonctionner pour tout arbitraire imbriquée dictionnaire ne pas contenir une auto-référence.

Notez que chaque solution a sa juste part des compromis, ce n'est pas une exception. Sauf si vous êtes de cuisson des millions de requêtes à vos données, telles que le pré-traitement est acceptable, les frais généraux, alors ce qu'il est. Avec les autres solutions, vous êtes seulement de contourner le problème plutôt que d'attaquer ce qui est de traiter avec le dictionnaire de la structure. Otoh, que, si vous allez le faire une fois sur beaucoup de telles structures de données, il ne font pas sens pour prétraiter juste pour une seule requête, dans ce cas, vous préférerez l'un de l'autre des solutions.

11voto

user3483203 Points 28606

J'ai mis à jour la réponse de Comment utiliser un point "." pour accéder aux membres de dictionnaire? pour utiliser une conversion initiale qui sera ensuite travailler pour imbriqués les dictionnaires:

Vous pouvez utiliser la classe suivante pour permettre dot-indexation des dictionnaires:

class dotdict(dict):
    """dot.notation access to dictionary attributes"""
    __getattr__ = dict.get
    __setattr__ = dict.__setitem__
    __delattr__ = dict.__delitem__

Toutefois, cela ne prend en charge la nidification si tous imbriqués les dictionnaires sont également de type dotdict. C'est là que la fonction d'assistance suivante survient:

def dct_to_dotdct(d):
    if isinstance(d, dict):
        d = dotdict({k: dct_to_dotdct(v) for k, v in d.items()})
    return d

Cette fonction doit être exécutée une fois sur votre imbriquée dictionnaire, et le résultat peut ensuite être indexé à l'aide de dot-indexation.

Voici quelques exemples:

In [13]: mydict
Out[13]: {'first': {'second': {'third': {'fourth': 'the end'}}}}

In [14]: mydict = dct_to_dotdct(mydict)

In [15]: mydict.first.second
Out[15]: {'third': {'fourth': 'the end'}}

In [16]: mydict.first.second.third.fourth
Out[16]: 'the end'

Une remarque à propos de la performance: cette réponse est lente par rapport à la norme d'accès de type dictionnaire, je voulais juste présenter une option qui en fait utilisé "point d'accès" à un dictionnaire.

7voto

kabanus Points 11398

Voici une solution similaire à chrisz, mais vous n'avez pas à quoi que ce soit à votre dict a-avant. :

class dictDotter(dict):
    def __getattr__(self,key):
        val = self[key]
        return val if type(val) != dict else dictDotter(val)

et juste x=dictDotter(originalDict) qui vous permettra d'avoir arbitraire dot obtenir (`x.d'abord.la seconde...). Je note c'est deux fois plus lent que chrisz solution, et le son est 9 fois plus lent que le vôtre (sur ma machine, environ).

Donc, si vous insistez pour faire ce travail @tdelaney semble avoir fourni le seul véritable amélioration de la performance.

Une autre option qui fait mieux que ce que vous avez (en termes de temps d'exécution):

class dictObjecter:
    def __init__(self,adict):
        for k,v in adict.items():
            self.__dict__[k] = v
            if type(v) == dict: self.__dict__[k] = dictObjecter(v)

qui vont faire un objet de votre dict, de sorte que la notation point est d'habitude. Cela permettra d'améliorer les temps d'exécution à 3 fois ce que vous avez, pas mal, mais au prix d'aller sur vos dict, et de le remplacer par autre chose.

Voici le total de tests de code:

from timeit import timeit

class dictObjecter:
    def __init__(self,adict):
        for k,v in adict.items():
            self.__dict__[k] = v
            if type(v) == dict: self.__dict__[k] = dictObjecter(v)

class dictDotter(dict):
    def __getattr__(self,key):
        val = self[key]
        return val if type(val) != dict else dictDotter(val)

def get_entry(dict, keyspec):
    keys = keyspec.split('.')

    result = dict[keys[0]]
    for key in keys[1:]:
        result = result[key]

    return result

class dotdict(dict):
    """dot.notation access to dictionary attributes"""
    __getattr__ = dict.get
    __setattr__ = dict.__setitem__
    __delattr__ = dict.__delitem__

def dct_to_dotdct(d):
    if isinstance(d, dict):
        d = dotdict({k: dct_to_dotdct(v) for k, v in d.items()})
    return d

x = {'a':{'b':{'c':{'d':1}}}}
y = dictDotter(x)
z = dct_to_dotdct(x)
w = dictObjecter(x)
print('{:15} : {}'.format('dict dotter',timeit('y.a.b.c.d',globals=locals(),number=1000)))
print('{:15} : {}'.format('dot dict',timeit('z.a.b.c.d',globals=locals(),number=1000)))
print('{:15} : {}'.format('dict objecter',timeit('w.a.b.c.d',globals=locals(),number=1000)))
print('{:15} : {}'.format('original',timeit("get_entry(x,'a.b.c.d')",globals=locals(),number=1000)))
print('{:15} : {:.20f}'.format('best ref',timeit("x['a']['b']['c']['d']",globals=locals(),number=1000)))

Je fournis le dernier de recherche comme le meilleur de référence.Les résultats sur un ordinateur Windows Ubuntu sous-système:

dict dotter     : 0.0035500000003594323
dot dict        : 0.0017939999997906853
dict objecter   : 0.00021699999979318818
original        : 0.0006629999998040148
best ref        : 0.00007999999979801942

de sorte que le est objectivé dict est 3 fois plus lent que régulièrement une recherche dans le dictionnaire - donc, si la vitesse est importante, pourquoi voudriez-vous cela?

2voto

Ramazan POLAT Points 475

J'ai eu le même besoin, j'ai donc créé le Prodict.

Pour votre cas, vous pouvez le faire en une seule ligne:

mydict = {
    'first': {
        'second': {
            'third': {
                'fourth': 'the end'
             }
         }
     }
}
dotdict = Prodict.from_dict(mydict)
print(dotdict.first.second.third.fourth) # "the end"

Après cela, utilisez dotdict comme un dict, parce que c'est une sous-classe de dict:

dotdict.first == dotdict['first'] # True

Vous pouvez aussi ajouter des touches de façon dynamique avec la notation point:

dotdict.new_key = 'hooray'
print(dotdict.new_key) # "hooray"

Il fonctionne même si les nouvelles clés sont imbriqués les dictionnaires:

dotdict.it = {'just': 'works'}
print(dotdict.it.just)  # "works"

Enfin, si vous définissez vos clés à l'avance, vous bénéficiez de la saisie semi-automatique et automatique de conversion de type:

class User(Prodict):
    user_id: int
    name: str

user = User(user_id="1", "name":"Ramazan")
type(user.user_id) # <class 'int'>
# IDE will be able to auto complete 'user_id' and 'name' properties

Mise à JOUR:

C'est le résultat du test pour le même code écrit par @kabanus:

x = {'a': {'b': {'c': {'d': 1}}}}
y = dictDotter(x)
z = dct_to_dotdct(x)
w = dictObjecter(x)
p = Prodict.from_dict(x)

print('{:15} : {}'.format('dict dotter', timeit('y.a.b.c.d', globals=locals(), number=10000)))
print('{:15} : {}'.format('prodict', timeit('p.a.b.c.d', globals=locals(), number=10000)))
print('{:15} : {}'.format('dot dict', timeit('z.a.b.c.d', globals=locals(), number=10000)))
print('{:15} : {}'.format('dict objecter', timeit('w.a.b.c.d', globals=locals(), number=10000)))
print('{:15} : {}'.format('original', timeit("get_entry(x,'a.b.c.d')", globals=locals(), number=10000)))
print('{:15} : {:.20f}'.format('prodict getitem', timeit("p['a']['b']['c']['d']", globals=locals(), number=10000)))
print('{:15} : {:.20f}'.format('best ref', timeit("x['a']['b']['c']['d']", globals=locals(), number=10000)))

Et les résultats:

dict dotter     : 0.04535976458466595
prodict         : 0.02860781018446784
dot dict        : 0.019078164088831673
dict objecter   : 0.0017378700050722368
original        : 0.006594238310349346
prodict getitem : 0.00510931794975705289
best ref        : 0.00121740293554022105

Comme vous pouvez le voir, sa performance est entre "dict dotter" et "point dict". Toute amélioration de la performance suggestions seront appréciées.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X