深度优先遍历和广度优先遍历
以前做过一个XQuery的项目，其中对Path式的执行采用了深度优先遍历算法。
现在想想，还可以考虑广度优先遍历。它们的对比如下:
可以把节点A匹配Path子式后得到的节点看作节点A的子节点，如果该Path子式不是最后一个Path子式，
则这些子节点是中间节点。
深度优先遍历
优点:节省内存
一次只保存一个中间节点，只有所有的Path子式都匹配完了的最终结果才会输出。
缺点:重复计算
每个Path子式的输出节点都应该是没有重复节点的，采用深度优先遍历算法时不能判断
当前中间节点是否已经被处理过，只能在生成最终结果时消除重复节点。可能会导致重复计算。
广度优先遍历
优点:避免重复计算
处理一个Path子式，可以得到匹配该Path子式得所有中间节点，也就能够消除重复节点。
缺点:内存消耗
需要消耗内存用于存储中间节点。当中间节点数目过大时可能会耗尽内存
在广度优先遍历算法中存储的中间节点数目是可控的，不会超过Dom树的实际节点数。
但深度优先遍历算法中重复计算的次数是不可控的，可能会对性能有极大的影响。
上面的例子相比而言，还是广度优先遍历更好。
另外，SQL的查询处理也有类似的问题。
为了减少磁盘IO，应减少中间结果的输出。
可以将一个元组做完所有运算后再输出最终结果，
但是选择Distinct选项是个障碍，Distinct要求所有选择结果都出来后才知道哪些是重复的。
阅读(5887) | 评论(0) | 转发(0) |
