DFS搜索树的优化
本文最后更新于 481 天前,其中的信息可能已经有所发展或是发生改变。

其实没啥特别大的优化,只是这两个点在搜索比较大的树的时候,可能会有一些性能优势。

这是以前的方法 : DFS遍历多叉树实现XML转JSON

第一处优化:

注意在循环中(Go函数第5行):

self.CNodeChild = [N for N in self.CNodeChild if bool(N.getchildren())]

这里为了找子节点是否都是叶子节点用了Python的列表推导。

可是这个效率并不高,因为如果这个节点的子节点非常多而都不是叶子节点的时候,会浪费大量的资源。

于是这里我将它改做一个循环:

for node in self.childNode:
    if len(node.getchildren()) != 0:
        break

这样在遇到一个子节点不为叶子节点时会立刻跳出循环,而且Python的列表推导式虽然优雅,但是好像效率不是很高(嘴炮)。

第二处优化:

在循环中,我们可以加入一个标志位,还有一个指针,弄清楚到底时在哪里退出了循环(也就是第一个遇到的非叶子子节点是谁),这样可以使mergeNode函数中少对当前子节点做一次遍历。

于是循环改做:

childNodePointer = 0
haveChild = False
for node in self.childNode:
    if len(node.getchildren()) != 0:
        haveChild = True
        break
    childNodePointer += 1

这样会减少一部分运算量。

我的详细分析(包括整个过程的,在知乎的这个地方,有兴趣的可以去看一下)

桂小方的回答 – 如何用 python 解析三层结构 XML?

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇