从一组嵌套字典中创建键值对列表的最python和最快的方法

Question

我想出了以下解决方案，但它非常丑陋（请参阅原始解决方案）。 我对修订后的解决方案相当满意。 有人有更干净/更快的方式来完成相同的输出吗？

其他要求：

• 必须接受任何值并返回键值对列表。
• 最后一个键必须跟踪键列表，才能使用点语法访问值。
• 必须返回键值对列表或字典。
• 未提供base_key时必须删除前导.。

我修改后的解决方案：

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

我的原始解决方案：

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

输入：

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')

输出：

[('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')]

笔记：

• Alex Martelli提出的发电机解决方案非常流畅。 不幸的是，它似乎比我的第一个和修订的解决方案慢一点。 此外，它返回一个生成器，该生成器仍然需要转换为列表或 poof，它消失了。

时间它的结果 @ 数字=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

除了字典中键的排序是任意的，以及如果需要空键（规范不清楚），可能需要修剪前导.：

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

看起来不错，很紧凑。 例如：

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')))

发出

[('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')]

根据需要。

补充：在Python中，"快速"和"优雅"经常重合 - 但并不总是如此。 特别是，递归速度稍慢，循环中全局变量的查找也是如此。 所以，在这里，拉出所有常用的技巧来消除递归和显式堆栈，以及查找提升，可以得到......：

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

。绝对没有那么优雅，但是...在我的笔记本电脑上，我的原始版本加上最后的list()，在给定的样本v上需要 21.5 微秒;这个更快的版本需要 16.8 微秒。 如果节省这 4.7 微秒（或者更有意义地表达，原始运行时的 22%）比清晰度和可维护性更重要，那么可以选择第二个版本并获得相同的结果（与通常的排序相同）。

OP的"修订版"在样本v上仍然更快，部分原因是在Python 2中用%格式化比更优雅的format略快，部分原因是items比iteritems稍微快一点（同样，只有Python 2）;一些提升可能会进一步减少一些纳秒， 太。