如何在与现有记录集成时使用递归嵌套字典

Question

我正在将 Open Street Map 中的一些 XML 数据解析为 JSON（稍后将上传到数据库）。它很大，所以我正在使用 iterparse。我有一些标签看起来像这样

<tag 'k'=stringA:stringB:stringC 'v'=value>

我想解析成

{stringA: {stringB: {stringC: value} } }

我已经用丑陋的硬编码做到了。但是，我想创建一个使用递归来解决相同问题的函数，以防 'k' 属性值包含任意多个 ':'.

我创造了这个

def nestify(l):
    """Takes a list l and returns nested dictionaries where each element from
    the list is both a key to the inner dictionary and a value to the outer, 
    except for the last element of the list, one which is only a value.
    For best understanding, feed w = [ 'a', 'b', 'c', 'd', 'e', 'f', 'v'] to the
    function and look at the output."""
    n = len(l)
    if n==2:
        key = l[0]
        value = l[1]
    else:
        key = l[0]
        value = nestify(l[1:])

    return {key:value}

有效。（您必须先将键和值放入列表中。）但不是真的，因为它总是会创建一个新字典。我需要它尊重以前的数据并进行整合。例如，如果我的解析器遇到

<tag 'k'=a:b:c 'v'=1 />

然后在同一个元素中

<tag 'k'=a:d:e 'v'=2 />

我需要它来制作

{a: {'b': {'c' : 1}, 'd' : {'e' : 2}}}

而不是

{a: {'b' : {'c' : 1}}}

{a: {'d' : {'e' : 2}}}

我试过这个代码：

def smart_nestify(l, record):
n = len(l)
if n==2:
    key = l[0]
    value = l[1]
else:
    key = l[0]
    value = smart_nestify(l[1:], key)
if key not in record:
    return {key:value}                   
else:
    record[key] = value
    return record

但它仍然会覆盖并且 returns 只会覆盖最新的记录。这是为什么？我该如何修复此代码？

Answer 1

有时只使用迭代比递归更好。这是迭代答案。

g_values = dict()
def make_nested(l):
    """
    l is the array like you have for nestify
    e.g., ['a',  'b', 'c', 1 ] or ['a', 'd', 'e', 2]
    """
    global g_values
    value = l[-1] ; l = l[:-1]
    last_dict = None
    for x in l[:-1]:
        mp_temp = last_dict if last_dict is not None or g_values
        last_dict = mp_temp.get(x)
        if last_dict is None:
            mp_temp[x] = dict()
            last_dict = mp_temp[x]
    last_dict[l[-1]] = value

虽然我没有测试，但你也可以递归地尝试这样的事情：

def make_nested(values, l):
    if len(l == 2):
        values[l[0]] = l[1]
        return
    mp = values.get(l[0])
    if mp is None:
        values[l[0]] = dict()
        make_nested(values[l[0]], l[1:])
    else:
        make_nested(mp, l[1:])

Answer 2

这是一个 "smarter" nestify，它将列表 l 合并到字典 record:

def smarter_nestify(l, record):
    if len(l) == 2:
        return {l[0]: l[1]}
    key = l.pop(0)
    record[key] = smarter_nestify(l, record.get(key, {}))
    return record

每次通过递归，它从列表中弹出第一个元素 l.pop(0) 并合并字典下一级的值 record.get(key, {}).

你可以像这样用两个列表来调用它：

l = ['a', 'b', 'c', 1]
record = smarter_nestify(l, {})

l = ['a', 'd', 'e', 2]
record = smarter_nestify(l, record)
print record

如何在与现有记录集成时使用递归嵌套字典

how to use recursion to nest dictionaries while integrating with existing records

python

recursion

json

dictionary

openstreetmap