python - 如何在此递归函数中更快地查找列表

Question

我有一个递归函数，它创建一个 json 对象

def add_to_tree(name, parent, start_tree):
    for x in start_tree:
        if x["name"] == parent:
            x["children"].append({"name":name, "parent":parent, "children":[]})
        else:
            add_to_tree(name, parent, x["children"])

它是从另一个函数调用的

def caller():
    start_tree = [{"name":"root", "parent":"null", "children":[]}] # basic structure of the json object which holds the d3.js tree data
    for x in new_list:
        name = x.split('/')[-2]
        parent = x.split('/')[-3]
        add_to_tree(name, parent, start_tree)

new_list 是包含这种形式的链接的列表

/root/A/
/root/A/B/
/root/A/B/C/
/root/A/D/
/root/E/
/root/E/F/
/root/E/F/G/
/root/E/F/G/H/
...

除运行时间随输入大小呈指数增长外，一切正常。通常 new_list 有大约 500k 个链接，这些链接的深度可以超过 10 个，因此 add_to_tree() 函数中涉及很多循环和查找。

关于如何让它更快的任何想法？

Answer 1

每次添加新条目时，您都在搜索整棵树。随着树的生长，这是非常低效的；你可以很容易地以这种方式进行 O(N^2) 次搜索；对于每个新元素，再次搜索整棵树。

您可以使用字典将名称映射到特定的树条目，以实现快速 O(1) 查找；这可以让你避免每次都遍历树。它可以像 treeindex[parent] 一样简单。然而，这将占用更多内存，并且您可能需要处理将父项添加到子项之后的情况(使用队列)。

但是，由于您的输入列表似乎已排序，您可以递归地处理您的列表或使用堆栈并利用您刚刚找到父级这一事实。如果您的路径比上一个条目长，它将成为该条目的子项。如果路径相等或更短，它将成为前一个节点或该节点的父节点的同级条目，因此返回或弹出堆栈。

例如，对于这三个元素:

/root/A/B/
/root/A/B/C/
/root/A/D/

/root/A/B/C 不必从根开始搜索树中的 /root/A/B，它是 以前的已处理条目。这将是此递归迭代的父调用，或堆栈的顶部。只需直接添加到该父级即可。

/root/A/D 是 parent 的 sibling ；该路径比 /root/A/B/C/ 短，因此返回或弹出堆栈的该条目。长度等于/root/A/B/，所以是直系兄弟；再次返回或弹出堆栈。现在您将处于 /root/A 级别，而 /root/A/D/ 是一个子级。添加并继续您的流程。