创建JSON以使用mptt在Python/Django中反映树结构的最快方法

Question

Python(Django)中基于Django查询集创建JSON的最快方法是什么.请注意,在此处提议的模板中解析它不是一个选项.

背景是我创建了一个循环遍历树中所有节点的方法,但在转换大约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到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]

下面你可以看到按照MuMind的建议使用cProfile创建的分析结果,设置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: 2530705函数调用(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.这对我来说很奇怪.

有没有更多关于性能改进的想法？

Answer 1

我怀疑到目前为止最大的减速是每个节点将进行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编码,虽然它可能在某些情况下提供轻微的加速,但我强烈反对,因为它将是很多代码,并且它很容易变得非常错误.

Answer 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个不同的潜在瓶颈:

• 数据库访问(.get_children()和.name) - 我不确定究竟发生了什么,但是我有这样的代码,它为每个节点进行数据库查询,增加了巨大的开销.如果这是您的问题,您可以将其配置为使用select_related或类似的东西进行"急切加载" .
• 函数调用开销(例如serializable_object本身) - 只需确保ncalls serializable_object看起来像一个合理的数字.如果我理解你的描述,它应该在300附近.
• 最后序列化(json.dumps(nodeInstance)) - 因为你说它只有300个节点,所以不是一个可能的罪魁祸首,但是如果你确实看到这会占用大量的执行时间,请确保你已经为JSON编译了加速版本正常工作.

如果你无法从分析中得到多少,那么制作一个精简版本,比如递归调用node.name,node.get_children()但不会将结果存储在数据结构中,看看它是如何比较的.

更新:execute_sql解决方案3中有2192个调用,解决方案5中有2192个调用,因此我认为过多的数据库查询是一个问题,并且select_related没有像上面那样使用它.纵观Django的MPTT问题#88:模型方法允许select_related建议你使用它更多或更少的权利,但我有我的怀疑,以及get_children对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等等(或者可能有更直接的方法来获取父键？) .它最初创建的每个obj都没有子项,然后将所有值"移植"给父母.