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

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，它消失了。

timeit 结果@ 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

除了字典中键的顺序是任意的，以及如果空键需要的话可能需要修剪前导 .s(规范不清楚):

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 中使用 % 格式化比更优雅的 格式稍快，部分原因是 items 比 iteritems 稍快(同样，仅限 Python 2)；并且一些提升也可能会进一步减少一些纳秒。