Подсчет узлов узла 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

В целом, я предпочитаю нерекурсивные решения по рекурсивным. Мой алгоритм работает следующим образом:

1. Инициализировать очереди и поместить объект JSON в него
2. Loop, пока очередь не пуста
3. Получить один узел из очереди
   • Если это Сопоставление, добавьте все значения в очередь для последующей обработки.
   • Если это последовательность или набор (будьте осторожны: строки тоже чередуются - нам нужно протестировать против них), мы добавляем все элементы в очередь для последующей обработки
   • Если это не ни один из вышеперечисленных, рассчитывать

Вот код:

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 

Answer 2

Ваш псевдокод чрезмерно сложный и багги. Я также предлагаю вам написать код, который следует за 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, используя yield from<expression>, который был представлен в версии 3.3 на Python.