Самый быстрый способ создания 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)