计数 JSON 个叶节点

Question

我想计算 JSON 结构中叶节点（即只有那些没有更多子元素的键）节点的数量。

我找不到任何明显的方法可以做到这一点，所以一直在尝试编写一个函数，但我很难找到一个不使用全局变量的函数。

这是我目前拥有的：

def count_leafs(nested):
  is isinstance(nested, Mapping):
    for k, v in nested.items():
      if isinstance(v, Mapping):
        for i_k, i_v in count_leafs(v):
          yield i_k, i_v
      elif isinstance(v, MutableSequence):
        for i_k in v:
          for i_i_k, i_i_v in i_k.items():
            count_leafs(i_i_v)
      else:
        yield k, v
  elif isinstance(nested, MutableSequence):
    for k in nested:
      count_leafs(k)


for k,v in count_leafs(json):
 leaf_count += 1

这并没有真正起作用，因为一些非叶节点被计算在内，并且它没有一直递归到某些结构中。

Answer 1

您的伪代码过于复杂且存在错误。我还建议您编写紧跟 PEP 8 - Style Guide for Python Code 的代码，以便您自己和阅读您编写的代码的其他人。

无论如何，作为测试用例，假设您有一些像这样的 JSON 数据：

json_data = {
    "glossary": {
        "title": "example glossary",
        "answer": 42,
        "boolean": True,
        "nada": None,
        "GlossDiv": {
            "GlossList": {
                "GlossEntry": {
                    "GlossDef": {
                        "GlossSeeAlso": [
                            "GML",
                            "XML"
                        ],
                        "para": "A meta-markup language, used to create markup "
                                "languages such as DocBook."
                    },
                    "GlossSee": "markup",
                    "Acronym": "SGML",
                    "GlossTerm": "Standard Generalized Markup Language",
                    "SortAs": "SGML",
                    "Abbrev": "ISO 8879:1986",
                    "ID": "SGML"
                }
            },
            "title": "S"
        }
    }
}

你可以像这样递归计算叶子数：

from collections import Mapping, MutableSequence

def count_leaves(json_obj):

    def leaf_iterator(json_obj):
        if isinstance(json_obj, Mapping):
            for v in json_obj.values():
                for obj in leaf_iterator(v):
                    yield obj
        elif isinstance(json_obj, MutableSequence):
            for v in json_obj:
                for obj in leaf_iterator(v):
                    yield obj
        else:
            yield json_obj

    return sum(1 for leaf in leaf_iterator(json_obj))

leaf_count = count_leaves(json_data)
print('leaf count: {}'.format(leaf_count))  # -> leaf_count: 14

我将 leaf_iterator() 生成器嵌套在叶子计数函数中，但如果它在更大的上下文中证明有用，也可以在外部定义。其中的代码可以在 Python 3 中进一步简化，方法是使用 Python 3.3 版中引入的 yield from<expression>。

Answer 2

总的来说，我更喜欢非递归解决方案而不是递归解决方案。我的算法是这样工作的：

初始化队列并将json对象放入其中
当队列不为空时循环
从队列中获取一个节点
- 如果是Mapping，则将所有的值加入到队列中，待后续处理
- 如果是一个序列或者一个集合（注意：字符串也是序列--我们需要对其进行测试），我们将所有元素添加到队列中以备后处理
- 如果是上面的none，算一个

代码如下：

from collections import Mapping, Sequence, Set, deque

def count_leaves(nested):
    queue = deque([nested])
    count = 0
    while queue:
        node = queue.popleft()
        if isinstance(node, Mapping):
            queue.extend(node.values())
        elif isinstance(node, (Sequence, Set)) and not isinstance(node, basestring):
            queue.extend(node)
        else:
            count += 1

    return count

计数 JSON 个叶节点

Counting JSON leaf nodes

python

recursion

json

yield

count