Самый быстрый способ создания JSON для отражения древовидной структуры в Python/Django с использованием mptt

Какой самый быстрый способ в Python (Django) создать JSON на основе набора запросов Django. Обратите внимание, что разбор его в шаблоне, предложенный здесь, не является вариантом.

Фон состоит в том, что я создал метод, который перебирает все узлы в дереве, но уже очень медленно при преобразовании около 300 узлов. Первая (и, вероятно, худшая) идея, которая мне пришла в голову, - создать json как-то "вручную". См. Код ниже.

#! Solution 1 !!#
def quoteStr(input):
    return "\"" + smart_str(smart_unicode(input)) + "\""

def createJSONTreeDump(user, node, root=False, lastChild=False):
    q = "\""

    #open tag for object
    json = str("\n" + indent + "{" +
                  quoteStr("name") + ": " + quoteStr(node.name) + ",\n" +
                  quoteStr("id") + ": " + quoteStr(node.pk) + ",\n" +
                )

    childrenTag = "children"
    children = node.get_children()
    if children.count() > 0 :
        #create children array opening tag
        json += str(indent + quoteStr(childrenTag) + ": [")
        #for child in children:
        for idx, child in enumerate(children):
            if (idx + 1) == children.count():
                //recursive call
                json += createJSONTreeDump(user, child, False, True, layout)
            else:
                //recursive call
                json += createJSONTreeDump(user, child, False, False, layout)
        #add children closing tag
        json += "]\n"

    #closing tag for object
    if lastChild == False:
        #more children following, add ","
        json += indent + "},\n"
    else:
        #last child, do not add ","
        json += indent + "}\n"
    return json

Древовидная структура, которую нужно визуализировать, представляет собой дерево с mptt, где вызов .get_children() возвращает все дочерние элементы a node.

Модель выглядит так же просто, как это, mptt заботится обо всем остальном.

class Node(MPTTModel, ExtraManager):
    """
    Representation of a single node
    """ 
    name = models.CharField(max_length=200)
    parent = TreeForeignKey('self', null=True, blank=True, related_name='%(app_label)s_%(class)s_children')

Ожидаемый JSON результат, созданный таким образом в шаблоне var root = {{ jsonTree|safe }}

Изменить: Основываясь на этом, я создал следующий код (определенно лучший код), но чувствует себя немного быстрее.

Решение 2:

def serializable_object(node):
    "Recurse into tree to build a serializable object"
    obj = {'name': node.name, 'id': node.pk, 'children': []}
    for child in node.get_children():
        obj['children'].append(serializable_object(child))
    return obj

import json
jsonTree = json.dumps(serializable_object(nodeInstance))

Решение 3:

def serializable_object_List_Comprehension(node):
    "Recurse into tree to build a serializable object"
    obj = {
        'name': node.name,
        'id': node.pk,
        'children': [serializable_object(ch) for ch in node.get_children()]
    }
    return obj

Решение 4:

def recursive_node_to_dict(node):
    result = {
        'name': node.name, 'id': node.pk
    }
    children = [recursive_node_to_dict(c) for c in node.get_children()],
    if children is not None:
        result['children'] = children
    return result

from mptt.templatetags.mptt_tags import cache_tree_children
root_nodes = cache_tree_children(root.get_descendants())
dicts = []
for n in root_nodes:
    dicts.append(recursive_node_to_dict(root_nodes[0]))
    jsonTree = json.dumps(dicts, indent=4)

Решение 5 (используйте select_related to pre_fetch, в то время как не уверены, правильно ли он используется)

def serializable_object_select_related(node):
    "Recurse into tree to build a serializable object, make use of select_related"
    obj = {'name': node.get_wbs_code(), 'wbsCode': node.get_wbs_code(), 'id': node.pk, 'level': node.level, 'position': node.position, 'children': []}
    for child in node.get_children().select_related():
        obj['children'].append(serializable_object(child))
    return obj

Решение 6 (улучшенное решение 4, использующее кеширование дочерних узлов):

def recursive_node_to_dict(node):
    result = {
        'name': node.name, ''id': node.pk,
         #notice the use of node._cached_children instead of node.get_children()
        'children' : [recursive_node_to_dict(c) for c in node._cached_children]
    }

Вызывается через:

from mptt.templatetags.mptt_tags import cache_tree_children
subTrees = cache_tree_children(root.get_descendants(include_self=True))
subTreeDicts = []
for subTree in subTrees:
    subTree = recursive_node_to_dict(subTree)
    subTreeDicts.append(subTree)
jsonTree = json.dumps(subTreeDicts, indent=4)
#optional clean up, remove the [ ] at the beginning and the end, its needed for D3.js
jsonTree = jsonTree[1:len(jsonTree)]
jsonTree = jsonTree[:len(jsonTree)-1]

Ниже вы можете увидеть результаты профилирования, созданные с помощью cProfile, как это было предложено MuMind, настроив представление Django для запуска автономного метода profileJSON(), который, в свою очередь, вызывает различные решения для создания вывода JSON.

def startProfileJSON(request):
    print "startProfileJSON"
    import cProfile
    cProfile.runctx('profileJSON()', globals=globals(), locals=locals())
    print "endProfileJSON"

Результаты:

Решение 1: 3350347 функциональных вызовов (3130372 примитивных вызовов) за 4.969 секунд (подробности)

Решение 2: 2533705 вызовы функций (2354516 примитивных вызовов) за 3.630 секунд (подробности)

Решение 3: 2533621 вызовы функций (2354441 примитивных вызовов) за 3,684 секунды (подробности)

Решение 4: 2812725 вызовов функций (2466028 примитивных вызовов) за 3,840 секунды (подробности)

Решение 5: 2536504 вызовов функций (2357256 примитивных вызовов) за 3,779 секунды (подробности)

Решение 6 (Улучшенное решение 4): 2593122 вызовы функций (2299165 примитивных вызовов) за 3,663 секунды (details)

Обсуждение:

Решение 1: реализация собственной кодировки. плохая идея

Решение 2 + 3: в настоящее время самый быстрый, но все же болезненно медленный

Решение 4: выглядит многообещающим с кешированием дочерних элементов, но выполняет аналогичные и в настоящее время производит недействительный json, поскольку дети помещаются в double []:

"children": [[]] instead of "children": []

Решение 5: использование select_related не имеет значения, тогда как, вероятно, используется неверно, поскольку node всегда имеет ForeignKey для своего родителя, и мы анализируем от root к child.

Обновление: решение 6: оно выглядит как самое чистое решение для меня, используя кеширование дочерних узлов. Но работает только аналогично решению 2 + 3. Что для меня странно.

Есть ли еще идеи для улучшения производительности?

Ответы

Ответ 1

Я подозреваю, что самым большим замедлением является то, что это сделает 1 запрос базы данных за node. Выделение json является тривиальным по сравнению с сотнями обращений к вашей базе данных.

Вы должны кэшировать дочерние элементы на каждом node, чтобы эти запросы могли выполняться все сразу. django-mptt имеет функцию cache_tree_children(), с которой вы можете сделать это.

import json
from mptt.templatetags.mptt_tags import cache_tree_children

def recursive_node_to_dict(node):
    result = {
        'id': node.pk,
        'name': node.name,
    }
    children = [recursive_node_to_dict(c) for c in node.get_children()]
    if children:
        result['children'] = children
    return result

root_nodes = cache_tree_children(Node.objects.all())
dicts = []
for n in root_nodes:
    dicts.append(recursive_node_to_dict(n))

print json.dumps(dicts, indent=4)

Пользовательская кодировка json, в то время как в некоторых сценариях может быть небольшое ускорение, я бы очень обескуражила, так как это будет много кода, и это легко получить очень неправильно.

Ответ 2

Ваша обновленная версия выглядит так, что будет очень мало накладных расходов. Я думаю, что было бы немного более эффективным (и более читаемым тоже!), Чтобы использовать понимание списка:

def serializable_object(node):
    "Recurse into tree to build a serializable object"
    obj = {
        'name': node.name,
        'children': [serializable_object(ch) for ch in node.get_children()]
    }
    return obj

Кроме того, все, что вы можете сделать, это профилировать его, чтобы найти узкие места. Напишите некоторый автономный код, который загружает и сериализует ваши 300 узлов, а затем запускает его с помощью

python -m profile serialize_benchmark.py

(или -m cProfile, если это работает лучше).

Можно увидеть 3 различных потенциальных узких места:

  • Доступ к DB (.get_children() и .name). Я не уверен, что происходит под капотом, но у меня был такой код, который делает запрос БД для каждого node, добавляя потрясающий накладные расходы. Если это ваша проблема, вы можете настроить это, чтобы выполнить "нетерпеливую нагрузку", используя select_related или что-то подобное.
  • служебный вызов функции (например, serializable_object). Просто убедитесь, что ncalls для serializable_object выглядит как разумное число. Если я понимаю ваше описание, оно должно быть в районе 300.
  • Сериализация в конце (json.dumps(nodeInstance)). Не является вероятным виновником, так как вы сказали, что это всего лишь 300 узлов, но если вы видите, что это занимает много времени выполнения, убедитесь, что у вас есть скомпилированные ускорения для JSON, работающих должным образом.

Если вы не можете много узнать из профилирования, сделайте усеченную версию, которая, скажем, рекурсивно вызывает node.name и node.get_children(), но не сохраняет результаты в структуре данных и не видит, как это сравнивается.

Обновление: В решении 3 и 2192 в решении 5 есть 2192 вызовов execute_sql, поэтому я считаю, что чрезмерные запросы БД являются проблемой и что select_related не сделал ничего такого, как он использовал выше. Глядя на проблема django-mptt # 88: Разрешить select_related в методах модели предлагает вам использовать его более или менее правильно, но у меня есть мои сомнения и get_children vs. get_descendants могут иметь огромное значение.

Также существует тонна времени, затрачиваемого на copy.deepcopy, что вызывает недоумение, потому что вы не вызываете его напрямую, и я не вижу его вызванного из кода MPTT. Что такое tree.py?

Если вы много работаете с профилированием, я настоятельно рекомендую действительно гладкий инструмент RunSnakeRun, который позволяет вам см. данные вашего профиля в действительно удобной форме сетки и быстрее осмыслить данные.

В любом случае, еще одна попытка упорядочить сторону БД:

import weakref
obj_cache = weakref.WeakValueDictionary()

def serializable_object(node):
    root_obj = {'name': node.get_wbs_code(), 'wbsCode': node.get_wbs_code(),
            'id': node.pk, 'level': node.level, 'position': node.position,
            'children': []}
    obj_cache[node.pk] = root_obj
    # don't know if the following .select_related() does anything...
    for descendant in node.get_descendants().select_related():
        # get_descendants supposedly traverses in "tree order", which I think
        # means the parent obj will always be created already
        parent_obj = obj_cache[descendant.parent.pk]    # hope parent is cached
        descendant_obj = {'name': descendant.get_wbs_code(),
            'wbsCode': descendant.get_wbs_code(), 'id': descendant.pk,
            'level': descendant.level, 'position': descendant.position,
            'children': []}
        parent_obj['children'].append(descendant_obj)
        obj_cache[descendant.pk] = descendant_obj
    return root_obj

Обратите внимание, что это больше не является рекурсивным. Это происходит итеративно через узлы, теоретически после того, как их родители были посещены, и все это используют один большой вызов MPTTModel.get_descendants(), так что, надеюсь, это хорошо оптимизировано и кэширует .parent и т.д. (Или, может быть, есть более прямой способ получить у родительского ключа?). Он создает каждый объект без детей, а затем "прививает" все значения родителям.

Ответ 3

Организуйте данные в вложенные словари или списки, затем вызовите метод json:

import json   
data = ['foo', {'bar': ('baz', None, 1.0, 2)}]
json.dump(data)

Ответ 4

Немного поиграв с этим, я обнаружил, что решения были слишком медленными, потому что сам mptt сканирует кеш несколько раз на get_children.

Воспользовавшись тем фактом, что mptt возвращает строки в правильном порядке, чтобы легко создавать деревья, я сделал следующее:

def flat_tree_to_dict(nodes, max_depth):
    tree = []
    last_levels = [None] * max_depth
    for n in nodes:
        d = {'name': n.name}
        if n.level == 0:
            tree.append(d)
        else:
            parent_dict = last_levels[n.level - 1]
            if 'children' not in parent_dict:
                parent_dict['children'] = []
            parent_dict['children'].append(d)
        last_levels[n.level] = d
    return tree

Для моего набора данных это выполняется на 10 раз быстрее, чем другие решения, потому что он O (n), только один раз повторяя данные.

Я использую его следующим образом:

json.dumps(flat_tree_to_dict(Model.objects.all(), 4), indent=4)