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

17

Какой самый быстрый способ в 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 ( ) возвращает всех дочерних узлов узла.

Модель выглядит так же просто, как это, 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 секунды ( подробности )

Обсуждение:

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

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

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

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

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

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

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

    
задан Thomas Kremmel 23.05.2017 в 12:30
источник
  • вы прошли через docs.djangoproject.com/en/dev/topics/serialization? –  Samy Vilar 23.09.2012 в 23:13
  • Спасибо за подсказку. Я прошел через него, но не мог обдумать его рекурсивную сериализацию. Но ваш намек заставил меня искать сериализацию + дерево + джанго, и первый удар - это вопрос, который выглядит так, как будто это решение того, что я ищу. stackoverflow.com/questions/5597136/... .. Попробует! –  Thomas Kremmel 23.09.2012 в 23:20
  • Похоже, что ваше основное узкое место в первой версии вышеприведенного кода будет многократно добавляться к строке, которая, как известно, является очень неэффективной операцией, поскольку она должна постоянно перераспределять непрерывные блоки памяти. Добавление строк в список и выполнение «.join (штук) в конце будет намного лучше. –  Mu Mind 23.09.2012 в 23:37
  • Спасибо за подсказку. Попробуем завтра. Время отдохнуть. –  Thomas Kremmel 23.09.2012 в 23:42
  • Из всех узлов в вашей базе данных, сколько вы фактически сбрасываете JSON с помощью этого метода? –  Winston Ewert 24.09.2012 в 17:50

4 ответа

18

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

Вы должны кэшировать дочерние элементы на каждом узле, чтобы эти запросы могли выполняться одновременно. 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, в то время как в некоторых сценариях может быть небольшое ускорение, я бы очень обескуражил, так как это будет много кода, и это легко получить очень неправильно .

    
ответ дан craigds 24.09.2012 в 00:11
  • Спасибо. Не могли бы вы проверить решение 4 в моем коде и предложить, как предотвратить двойные списки для детей? Дети в настоящее время упакованы в два [] вместо одного. –  Thomas Kremmel 24.09.2012 в 11:37
  • сделано. у него была конечная запятая, питон счастливо превратился в кортеж: s –  craigds 25.09.2012 в 06:52
  • Спасибо. Я использовал ваш код, так как он самый элегантный, и немного переписал его. См. Решение 6 выше. Важно использовать node._cached_children вместо node.get_children (), чтобы использовать кеширование, выполняемое cache_tree_children. Во всяком случае, код не работает лучше, чем решение 2, что странно для меня, так как ваш аргумент с ударом db только один раз убедительно. Любая идея, почему она не работает лучше? –  Thomas Kremmel 25.09.2012 в 10:38
8

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

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 различных потенциальных узких места:

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

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

Обновление: Есть 2192 вызовов execute_sql в решении 3 и 2192 в решении 5, поэтому я думаю, что чрезмерные запросы к БД являются проблемой и что 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 и т. Д. (Или, возможно, есть более прямой способ получить у родительского ключа?). Он создает каждый объект без детей, а затем «прививает» все значения родителям.

    
ответ дан Mu Mind 24.09.2012 в 00:09
  • Спасибо! Я проверил ускорения, и они, кажется, там, используя Python2.7: из _json import scanstring как c_scanstring. –  Thomas Kremmel 24.09.2012 в 09:29
1

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

import json   
data = ['foo', {'bar': ('baz', None, 1.0, 2)}]
json.dump(data)
    
ответ дан Samy Arous 23.09.2012 в 23:55
  • Если я правильно понимаю, это то, что я делаю в решении2. См. Обновление к моему вопросу выше. –  Thomas Kremmel 24.09.2012 в 09:11
0

Немного поиграв с этим, я обнаружил, что решения были слишком медленными, потому что сам 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)
    
ответ дан Roger Collins 09.01.2018 в 22:42