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"
