Most pythonic and fastest way to create a list of key value pairs from a set of nested dictionaries?

Question

I have come up with the following solution, but it was quite ugly (see original solution). I'm fairly happy with the revised solution. Anybody have a cleaner / faster way to accomplish the same output?

Other requirements:

• Must accept any value and return a list of key value pairs.
• The final key must track the list of keys to access the value with dot syntax.
• must return a list of key value pairs or a dictionary.
• must remove leading . when no base_key is supplied.

My revised solution:

def create_nested_kvl(v, base_key=None):
    kvl = []
    if not isinstance(v, dict):
        kvl.append((base_key,v))
    else:
        def iterate(v, k):
            for ki, vi in v.items():
                ki = '%s.%s' % (k, ki) if k else ki
                iterate(vi, ki) if isinstance(vi, dict) else kvl.append((ki, vi))
        iterate(v, base_key)
    return kvl

My Original Solution:

def create_nested_kvl(v, base_key=''):
    """ Creates a list of dot syntax key value pairs from a nested dictionary.
    :param      v: The value suspected to be a nested dictionary.
    :param      k: Base key
    :return:    [(k,v)]
    :rtype:     list
    """
    if not isinstance(v, dict):
        return [(base_key,v)]

    kvl = []
    def iterate(v, k):
        for kd, vd in v.items():
            v = vd
            kd = '%s.%s' % (k, kd) if k else kd
            kvl.append((kd, v))

    iterate(v, base_key)
    for k, v in kvl:
        if isinstance(v, dict):
            iterate(v, k)
            kvl.remove((k,v))
    return kvl

input:

v = {'type1':'type1_val',
     'type2':'type2_val',
     'object': {
          'k1': 'val1',
          'k2': 'val2',
          'k3': {'k31': {
                     'k311': 'val311',
                     'k322': 'val322',
                     'k333': 'val333'
                     },
                'k32': 'val32',
                'k33': 'val33'}}}

create_nested_kvl(v, 'base')

output:

[('base.type1', 'type1_val'),
 ('base.type2', 'type2_val'),
 ('base.object.k2', 'val2'),
 ('base.object.k1', 'val1'),
 ('base.object.k3.k33', 'val33'),
 ('base.object.k3.k32', 'val32'),
 ('base.object.k3.k31.k311', 'val311'),
 ('base.object.k3.k31.k333', 'val333'),
 ('base.object.k3.k31.k322', 'val322')]

Notes:

• The generator solution presented by Alex Martelli is very slick. Unfortunately, it appears to be a tad slower than my first and revised solution. Also, it returns a generator which still needs to be converted to a list or poof, its gone.

timeit results @ number=1000000:

generator : 0.911420848311 (see alex's answer)
original  : 0.720069713321
revised   : 0.660259814902

best      : 0.660259814902 
* as Alex pointed out, my late night rounding skills are horrific.
It's 27% faster not twice as fast (my bad).

Answer 1

Apart from ordering of keys in dicts being arbitrary, and the possible need to trim leading .s if that's needed for empty keys (spec unclear):

def create_nested_kvl(v, k=''):
    if isinstance(v, dict):
        for tk in v:
            for sk, sv in create_nested_kvl(v[tk], tk):
                yield '{}.{}'.format(k, sk), sv
    else:
        yield k, v

seems nice and compact. E.g:

v = {'type1':'type1_val',
     'type2':'type2_val',
     'object': {
          'k1': 'val1',
          'k2': 'val2',
          'k3': {'k31': {
                     'k311': 'val311',
                     'k322': 'val322',
                     'k333': 'val333'
                     },
                'k32': 'val32',
                'k33': 'val33'}}}

import pprint
pprint.pprint(list(create_nested_kvl(v, 'base')))

emits

[('base.object.k3.k31.k311', 'val311'),
 ('base.object.k3.k31.k333', 'val333'),
 ('base.object.k3.k31.k322', 'val322'),
 ('base.object.k3.k33', 'val33'),
 ('base.object.k3.k32', 'val32'),
 ('base.object.k2', 'val2'),
 ('base.object.k1', 'val1'),
 ('base.type1', 'type1_val'),
 ('base.type2', 'type2_val')]

as required.

Added: in Python, "fast" and "elegant" often coincide -- but not always so. In particular, recursion is slightly slower and so are lookups of globals in loop. So, here, pulling all the usual tricks for recursion elimination w/an explicit stack, and lookup hoisting, one can get...:

def faster(v, k='', isinstance=isinstance):
    stack = [(k, v)]
    result = []
    push, pop = stack.append, stack.pop
    resadd = result.append
    fmt = '{}.{}'.format
    while stack:
        k, v = pop()
        if isinstance(v, dict):
            for tk, vtk in v.iteritems():
                push((fmt(k, tk), vtk))
        else:
            resadd((k, v))
    return result

...definitely not as elegant, but... on my laptop, my original version, plus a list() at the end, takes 21.5 microseconds on the given sample v; this faster version takes 16.8 microseconds. If saving those 4.7 microseconds (or, expressed more meaningfully, 22% of the original runtime) is more important than clarity and maintainability, then one can pick the second version and get the same results (net as usual of ordering) that much faster.

The OP's "revised version" is still faster on the sample v, partly because formatting with % is slightly faster in Python 2 than the more elegant format, and partly because items is slightly faster (again, Python 2 only) than iteritems; and some hoisting might further shave some nanoseconds off that one, too.