récursif n-ième enfant dict.get() - efficacité ?

Question

J'ai besoin d'extraire certaines valeurs de grands dictionnaires imbriqués. Par paresse, j'ai décidé d'écrire une fonction qui s'appelle récursivement jusqu'à ce que le dernier enfant soit trouvé, ou que la feuille soit vide.

Comme il y a des dictionnaires qui sortent et qu'à chaque nouvel appel, un nouveau dictionnaire est construit, je me demande quelle est l'efficacité de cette méthode.

Des suggestions ?

def recursive_dict_get(item, string, default=False):
    if not isinstance(item, dict):
        return default

    print "called with ", item, "and string", string
    if "." in string:
        attrs = string.split(".")
        parent = attrs.pop(0)
        rest = ".".join(attrs)
        result = item.get(parent, None)
        if result is None:
            return default
        else:
            return recursive_dict_get(item.get(parent, default), rest, default)
    else:
        return item.get(string, default)

---

foo = {
            "1": {
                "2": {
                    "3": {
                        "4":{
                            "5": {
                                "6": {
                                    "7": "juice"
                                }
                            }
                        }
                    }
                }
            }
        }

print recursive_dict_get(foo, "1.2.3.4.5.6.7", False)
print "*" * 3       
print recursive_dict_get(foo, "1.2.3.4.5.6", False)
print "*" * 3
print recursive_dict_get(foo, "1.3", False)

Answer 1

Une suggestion que j'ai faite est de donner split() un deuxième argument. Vous pouvez faire quelque chose de plus simple comme :

parent, rest = string.split(".", 1)

En dehors de cela, je ne vois pas de problèmes immédiats avec le code.

Vous pouvez également le faire sans récursion :

def recursive_dict_get(item, string, default=False):
    for s in string.split('.'):
        if (isinstance(item, dict) and s in item):
            item = item[s]
        else:
            return default
    return item

Answer 2

Oui, votre implémentation est assez inefficace, même si elle ne construit pas de nouveaux dictionnaires, mais renvoie plutôt potentiellement beaucoup de dictionnaires existants. Quoi qu'il en soit, vous pourriez adapter la réponse acceptée à Accès aux éléments d'un dictionnaire imbriqué en python via une liste de clés a réduire le site votre fonction d'accès à une seule ligne de code. Cela ressemble à ce à quoi J.F. Sebastian (@jfs) faisait allusion dans son commentaire . Mon point de vue sur la question serait le suivant :

def nonrecursive_dict_get(item, key_string, default=False):
    return reduce(lambda d, k: d.get(k, default), key_string.split('.'), item)

print "*" * 3, 'using nonrecursive_dict_get()'
print nonrecursive_dict_get(foo, "1.2.3.4.5.6.7")
print "*" * 3
print nonrecursive_dict_get(foo, "1.2.3.4.5.6")
print "*" * 3
print nonrecursive_dict_get(foo, "1.3")

Mise à jour :

Lorsque l'efficacité est une préoccupation, la meilleure chose à faire est souvent d'effectuer une analyse comparative des différentes approches. En voici un que j'ai utilisé un certain nombre de fois :

global_setup = """
    foo = {
            "1": {
                "2": {
                    "3": {
                        "4": {
                            "5": {
                                "6": {
                                    "7": "juice"
                                     }
                                 }
                             }
                         }
                     }
                 }
          }
"""

testcases = {
"jay":
    { 'setup' : """
        def recursive_dict_get(item, string, default=False):
            if not isinstance(item, dict):
                return default
            if "." in string:
                attrs = string.split(".")
                parent = attrs.pop(0)
                rest = ".".join(attrs)
                result = item.get(parent, None)
                if result is None:
                    return default
                else:
                    return recursive_dict_get(item.get(parent, default), rest, default)
            else:
                return item.get(string, default)
                """,
      'code' : """
        recursive_dict_get(foo, "1.2.3.4.5.6.7", False)
        recursive_dict_get(foo, "1.2.3.4.5.6", False)
        recursive_dict_get(foo, "1.3", False)
        """,
    },

"martineau":
    { 'setup' : """
        def nonrecursive_dict_get(nested_dict, key_string, default=False):
            return reduce(lambda d, k: d.get(k, default), key_string.split('.'), nested_dict)
            """,
      'code' : """
        nonrecursive_dict_get(foo, "1.2.3.4.5.6.7", False)
        nonrecursive_dict_get(foo, "1.2.3.4.5.6", False)
        nonrecursive_dict_get(foo, "1.3", False)
        """,
    },

"J.F. Sebastian":
    { 'setup' : """
        # modified to support 'default' keyword argument
        def quick_n_dirty(nested_dict, key_string, default=False):
            reduced = reduce(dict.get, key_string.split('.'), nested_dict)
            return default if reduced is None else reduced
            """,
      'code' : """
        quick_n_dirty(foo, "1.2.3.4.5.6.7", False)
        quick_n_dirty(foo, "1.2.3.4.5.6", False)
        quick_n_dirty(foo, "1.3", False)
        """,
    },

"arshajii":
    { 'setup' : """
        def recursive_dict_get(item, string, default=False):
            for s in string.split('.'):
                if (isinstance(item, dict) and s in item):
                    item = item[s]
                else:
                    return default
            return item
            """,
      'code' : """
        recursive_dict_get(foo, "1.2.3.4.5.6.7", False)
        recursive_dict_get(foo, "1.2.3.4.5.6", False)
        recursive_dict_get(foo, "1.3", False)
        """,
    },

"Brionius":
    { 'setup' : """
        def getVal(d, keys, default):
            keys = keys.split(".")
            for key in keys:
                try:
                    d = d[key]
                except KeyError:
                    return default
            return d
            """,
      'code' : """
        getVal(foo, "1.2.3.4.5.6.7", False)
        getVal(foo, "1.2.3.4.5.6", False)
        getVal(foo, "1.3", False)
        """,
    },
}

import sys
from textwrap import dedent
import timeit
N = 100000
R = 3

# remove leading whitespace from all code fragments
global_setup = dedent(global_setup)
for testcase in testcases.itervalues():
    for label, fragment in testcase.iteritems():
        testcase[label] = dedent(fragment)

timings = [(name,
            min(timeit.repeat(testcases[name]['code'],
                              setup=global_setup + testcases[name]['setup'],
                              repeat=R, number=N)),
           ) for name in testcases]

longest_name = max(len(t[0]) for t in timings)

print('fastest to slowest timings:\n'
      '  ({:,d} calls, best of {:d} repetitions)\n'.format(N, R))

ranked = sorted(timings, key=lambda t: t[1])  # sort by speed (fastest first)
for timing in ranked:
    print("{:>{width}} : {:.6f} secs ({rel:>8.6f}x)".format(
          timing[0], timing[1], rel=timing[1]/ranked[0][1], width=longest_name))

Sortie :

fastest to slowest timings:
  (100,000 calls, best of 3 repetitions)

J.F. Sebastian : 1.287209 secs (1.000000x)
      Brionius : 1.420099 secs (1.103239x)
      arshajii : 1.431521 secs (1.112112x)
     martineau : 2.031539 secs (1.578251x)
           jay : 7.817713 secs (6.073384x)

Comme vous pouvez le constater, la suggestion de J.F. Sebastian est la plus rapide, même avec la modification que j'ai apportée pour la rendre identique aux autres.

Answer 3

Voici un autre moyen :

def getVal(d, keys, default):
    keys = keys.split(".")  # You can avoid this first step if you're willing to use a list like ["1", "2", "3"...] as an input instead of a string like "1.2.3..."
    for key in keys:
        try:
            d = d[key]
        except KeyError:
            return default
    return d

Je peux le profiler si vous le souhaitez - faites-le moi savoir. Gardez à l'esprit qu'il est inutile d'optimiser si vous n'avez pas rencontré ou si vous avez des raisons de croire que vous allez rencontrer un goulot d'étranglement.