12
\$\begingroup\$

Problem: We read a complex json-file which grants us a tree in terms of a python "dict of dicts". We're then requested to retrieve a specific path from the tree, represented by a list of elements. The list (i.e. the path) may have any, arbitrary length.

Simple Example:

# The dict-tree:
d = {"a":{"1":{"aa":"a2", "aaa":"a3"}},
     "b":{"2":{"bb":"b2", "bbb":"b3"}},
     "c":{"3":{"cc":"c2", "ccc":"c3"}},
     "d":{"4":{"dd":"d2", "ddd":"d3"}},
     "e":{"5":{"ee":"e2", "eee":"e3"}}
     }

# The path ..
p = ["b", "2", "bb"] # --> "b2"

Solution (to be improved): Now, a naive solution could be to simply return d[p[0]][p[1]][p[2]]. However this obviously fails for any path-length not equal to three. Thus, I wrote two functions as shown below,

# Recursive approach
def get_val_from_path_1(d, p):
    if len(p)>1 and p[0] in d:
        return get_val_from_path_1(d[p[0]], p[1:])
    if p[0] in d:
        return d[p[0]]
    return None

# Iterative approach
def get_val_from_path_2(d, p):
    tmp = d
    for s in p:
        if not s in tmp:
            return None
        tmp = tmp[s]
    return tmp

A (very) simple time-consumption test can be run on my repl.it, which suggests that the iterative approach (no.2) is significantly faster than the recursive (no.1).

Preferably, I would really like a simpler approach, without any need of loops, however, any suggestions that improves performance, readability and/or code-line-usage are most appreciated.

EDIT: The question was intended for Python-3.x. I do not edit the label, because it is discussed in the comments of the below answer(s).

\$\endgroup\$
21
\$\begingroup\$

Recursive Approach Review

In this method you are performing too many look-ups.

First, you are looking up the 0th value of p two or three times. List indexing does take time, so it may be faster to store p[0] in a local variable, to avoid repeatedly indexing into the list.

Second, you are performing a dictionary looking ups two or three times. While dictionary look-ups are fast, ideally \$O(1)\$ in time, they do take time. p[0] in d is a dictionary lookup without retrieving the looked up value; d[p[0]] is a dictionary lookup that retrieves the value.

The first and second if statements do effectively the same things. They check p[0] in d, and if true, they retrieve d[p[0]]. We can extract this common functionality, perform it once, and then, depending on len(p), perform the recursion. Additionally, we'll use dict.get(p[0], None) to perform a single dictionary lookup, using the value from a single list index operation:

def get_val_from_path_1(d, p):
    d = d.get(p[0], None)
    if d is not None and len(p) > 1:
        return get_val_from_path_1(d, p[1:])
    return d

Note: I used d is not None, instead of simply testing if d is "truthy", so that if a subkey is requested of a "falsy" value (0, False, ""), the dictionary lookup will happen in the recursive call, and an exception will be raised similar to the original code.

EDIT: As mentioned by RootTwo in the comments, it is "safer" to use a sentinel object, in case None is an actual value contained in the JSON object. Although if None values are contained in the JSON object, it is ambiguous as to whether the key does not exist, or exists with the value None:

def get_val_from_path_1(d, p):
    sentinel = object()
    d = d.get(p[0], sentinel)
    if d == sentinel:
        return None
    if len(p) > 1:
        return get_val_from_path_1(d, p[1:])
    return d

Iterative Approach Review

This code begins with tmp = d, which is odd as d is never used in the remainder of the code. The temporary variable can be removed.

Similar to the Recursive Approach, you are using a double dictionary lookup. s in tmp followed by tmp[s]. Again, using tmp.get(s, None) would perform the dictionary lookup once, and return None if the key was not present.

def get_val_from_path_2(d, p):
    for s in p:
        d = d.get(s, None)
        if d is None:
            break
    return d

EDIT: A sentinel can be used here as well, with the same ambiguity disclaimer:

def get_val_from_path_2(d, p):
    sentinel = object()
    for s in p:
        d = d.get(s, sentinel)
        if d is sentinel:
            return None
    return d

Which approach is better?

EDIT: Clarifications added at based on comments by Konrad.

Gloweye attempts to make the case that "recursive is the way to go". I disagree.

First off, Python does not do tail call optimization. If it did, it would close the performance gap with the iterative approach, but with the current recursive implementation, the iterative method would still win.

In each recursive call, the p[1:] is being passed to the p argument. This is building a brand-new list, and copying the elements to the new list. With n items in the original list, n-1 elements are copied the first time, n-2 are copied the second, n-3 the third, and so on, making this an \$O(n^2)\$ time algorithm.

Gloweye's approach is a constant factor worse, since *args[1:] in addition to constructing the list slice must "splat" the items into the argument list, which then gets unsplatted back to args tuple in the next call. I should stress it is not that much worse; it is still only \$O(n^2)\$.

Both Gloweye's and the current recursive approach, passing p[1:] as the argument in the recursive call, can be corrected from \$O(n^2)\$ to \$O(n)\$ by replacing the list slicing with an iterator. Since the recursive argument has changed from a list to an iterator, a second function would be needed to implement this change.

If tail call optimization was present, and the list was not being repeatedly sliced and recreated each step, such as by using an iterator to walk down the list of keys, then things would be better (as in \$O(n)\$). Tail call optimization works by updating the arguments for the next call, and jumping to the top of the function, which turns the recursion into a simple loop.

So why not just use a loop?

One last optimization is to stop checking for the existence of the keys (or even a None default or sentinel value); these checks slow the loop down. Instead, unconditionally lookup and retrieve the values. Rely on Python's blazingly fast exception handling to efficiently recover from non-existent keys.

Also, use meaningful variable names. d and p are far too obscure.

Finally, use """docstrings""" to document how to use the function.

def get_val_from_path(json_object, key_path):
    """
    Retrieve a value from a JSON object, using a key list to
    navigate through the JSON object tree.

    Parameters:
       json_object (JSON): An object return from json.loads()
       key_path (Iterable[str]): A list of keys forming the key path.

    Returns:
       The value found at the given key path, or `None` if
       any of the keys in the path is not found.
    """

    try:
        for key in key_path:
            json_object = json_object[key]

        return json_object

    except KeyError:
        return None

Optionally, use Gloweye's *args method signature for slightly friendlier calls, without the [] noise.

def get_val_from_path(json_object, *key_path):
    ...

get_val_from_path(d, "b", "2", "bb")  # --> "b2"
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ From a static typing POV you may want key_path (List[str]): to be key_path (Iterable[str]):. It may still not work with Iterators or Generators. \$\endgroup\$ – Peilonrayz Oct 28 '19 at 18:19
  • \$\begingroup\$ Python has suggested using alternate forms for typing for a while. This can be seen in how generic PEP 3107 is. It's normally best not to assume much when it comes to typing, as PyCharm likely would see the typing in the docstring and I would think Sphinx and a custom middleware would also likely see it, to name two. If you want standard Python 2.7 compatibility then you can use type comments. \$\endgroup\$ – Peilonrayz Oct 28 '19 at 19:05
  • 5
    \$\begingroup\$ It might be safer to use a sentinel object instead of None in the call to d.get(). In case None is a possible value in the nested dictionaries. \$\endgroup\$ – RootTwo Oct 29 '19 at 4:21
  • 1
    \$\begingroup\$ Eh, that's a pretty reasonable argument against my recursive preference. I mostly just assumed that the performance wasn't that important - my own experience with this type of "deep" indexing never got beyond ~10 depth, and it'll be fast regardless. +1. \$\endgroup\$ – Gloweye Oct 29 '19 at 11:05
  • 2
    \$\begingroup\$ @magnus: For the record, Python's exception handling is slow(er than using e.g. dict.get or in). But Python's try...except clause is really fast (almost negligible) if there is no exception. \$\endgroup\$ – Graipher Oct 29 '19 at 13:47
12
\$\begingroup\$

Use a library.

In particular, glom does an admirable job of this, and is actively developed.

>>> d = {"a":{"1":{"aa":"a2", "aaa":"a3"}},
...      "b":{"2":{"bb":"b2", "bbb":"b3"}},
...      "c":{"3":{"cc":"c2", "ccc":"c3"}},
...      "d":{"4":{"dd":"d2", "ddd":"d3"}},
...      "e":{"5":{"ee":"e2", "eee":"e3"}}
...      }
>>> import glom
>>> glom.glom(d, 'b.2.bb')
'b2'
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

The simplest approach I can think of is to use a reduce and let it handle the boring stuff for us:

from functools import reduce

def get_value_by_path(container, path):
    return reduce(dict.__getitem__, path, container)

get_value_by_path(d, ["d", "4", "ddd"])
# 'd3'

As for performance, I tested it on your repl.it link and it seems to run in about 2 seconds with your test data. So maybe not the fastest approach, but not the slowest either, and the least complex one IMO.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Thematically, I would say recursive is the way to go. Especially if you ever find yourself writing a language that does tail-call optimization well, it's superior. (Python sadly doesn't. It involves replacing the top frame on the stack with a new frame, which stops you from getting...StackOverflow. Well, to be 100% accurate, Python will toss a RecursionError in your face before that happens, but it's a fitting thought.)

I would however, also recommend using python *args notation and slicing to parse it a tad more easily:

def get_value_by_path(container, *args):
    if not args:
        return container
    return get_value_by_path(container[args[0]], *args[1:])

value = get_value_by_path(d, "b", "2", "bb")
# "b2"
value = get_value_by_path(d, "b", "2")
# {"bb":"b2", "bbb":"b3"}
value = get_value_by_path(d, "b")
# {"2":{"bb":"b2", "bbb":"b3"}}

This has the advantage that it will also work for lists, if you just give indices, whereas an in check like you have would stop that. If there's a wrong index/key somewhere, this way will throw a KeyError, exactly like all builtin indexing operations.

If you care more about SLOC (Source Lines of Code) than readability, you could use the 1liner:

def ugly_get_value_by_path(container, *args):
    return ugly_get_value_by_path(container[args[0]], *args[1:]) if args else container
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I agree with AJNeufeld that any recursive solution has (sometimes) serious caveats in Python. But I ultimately agree more with you: this problem is fundamentally recursive, and an iterative solution won’t be as direct, intuitive and elegant as a recursive one. At best it’ll be a good approximation. Slicing is a real performance issue (regardless of paradigm), but a recursive solution can solve that just as well as an iterative solution. \$\endgroup\$ – Konrad Rudolph Oct 29 '19 at 15:01
  • \$\begingroup\$ Regarding the slicing, I was assuming this isn't that performance critical. A more performance-friendly implementation could build a simple tuple and then pass it along with an index. \$\endgroup\$ – Gloweye Oct 30 '19 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.