深度优先遍历和广度优先遍历

简介: 深度优先遍历和广度优先遍历以前做过一个XQuery的项目,其中对Path式的执行采用了深度优先遍历算法。现在想想,还可以考虑广度优先遍历。它们的对比如下:可以把节点A匹配Path子式后得到的节点看作节点A的子节点,如果该Path子式不是最后一个Path子式,则这些子节点是中间节点。
深度优先遍历和广度优先遍历

以前做过一个XQuery的项目,其中对Path式的执行采用了深度优先遍历算法。
现在想想,还可以考虑广度优先遍历。它们的对比如下:

可以把节点A匹配Path子式后得到的节点看作节点A的子节点,如果该Path子式不是最后一个Path子式,
则这些子节点是中间节点。


深度优先遍历
优点:节省内存
  一次只保存一个中间节点,只有所有的Path子式都匹配完了的最终结果才会输出。
缺点:重复计算
  每个Path子式的输出节点都应该是没有重复节点的,采用深度优先遍历算法时不能判断
当前中间节点是否已经被处理过,只能在生成最终结果时消除重复节点。可能会导致重复计算。

广度优先遍历
优点:避免重复计算
  处理一个Path子式,可以得到匹配该Path子式得所有中间节点,也就能够消除重复节点。
缺点:内存消耗
  需要消耗内存用于存储中间节点。当中间节点数目过大时可能会耗尽内存

在广度优先遍历算法中存储的中间节点数目是可控的,不会超过Dom树的实际节点数。
但深度优先遍历算法中重复计算的次数是不可控的,可能会对性能有极大的影响。
上面的例子相比而言,还是广度优先遍历更好。

另外,SQL的查询处理也有类似的问题。

为了减少磁盘IO,应减少中间结果的输出。
可以将一个元组做完所有运算后再输出最终结果,
但是选择Distinct选项是个障碍,Distinct要求所有选择结果都出来后才知道哪些是重复的。
相关文章
|
数据安全/隐私保护 网络架构
CentOS8 Kibana8.x 安装遇到的问题解决
CentOS8 Kibana8.x 安装遇到的问题解决
701 0
CentOS8 Kibana8.x 安装遇到的问题解决
|
设计模式 Java
好好的“代码优化”是怎么一步步变成“过度设计”的(上)
好好的“代码优化”是怎么一步步变成“过度设计”的(上)
453 4
|
域名解析 安全 应用服务中间件
手把手教你安装WordPress详细教程(图文)
如果还有不了解宝塔面板怎么使用的小伙伴,可以看下我总结的系列教程,保证从新手变老鸟:
1502 0
手把手教你安装WordPress详细教程(图文)
|
SQL 关系型数据库 MySQL
MySql数据库中的视图,索引与数据库sql脚本如何导入与导出---(详细介绍)
MySql数据库中的视图,索引与数据库sql脚本如何导入与导出---(详细介绍)
550 0
|
小程序 容器
【微信小程序】-- WXML 模板语法 - 条件渲染 -- wx:if & hidden (十一)
【微信小程序】-- WXML 模板语法 - 条件渲染 -- wx:if & hidden (十一)
|
10月前
|
弹性计算 运维 监控
云产品评测:云服务诊断 — ECS实例健康状态与诊断功能体验
作为一名运维工程师,我日常管理和维护云资源,确保服务稳定运行。阿里云的云服务诊断功能提供了便捷的方式实时了解和优化ECS实例的健康状态。通过健康状态功能,我能够查看CPU、内存等指标,及时发现并解决性能瓶颈,提升了约30%的工作效率。诊断功能则帮助我快速定位复杂问题,减少了40%的诊断时间,并提供详细的优化建议。尽管功能已很强大,但仍建议进一步细化诊断结果和增加自定义告警选项,以提升使用体验。我非常推荐此工具给其他运维人员。
242 22
|
11月前
|
机器学习/深度学习 供应链 算法
量子计算:从理论到实践的跨越
量子计算基于量子力学原理,利用量子比特的叠加态和纠缠特性,展现出远超经典计算机的计算能力。本文从基本概念、发展历程、应用场景及未来挑战四个方面,全面介绍量子计算从理论到实践的跨越,展望其在优化问题、量子化学、机器学习等领域的广泛应用前景。
|
8月前
|
机器学习/深度学习 算法 PyTorch
从零开始深度学习:全连接层、损失函数与梯度下降的详尽指南
在深度学习的领域,全连接层、损失函数与梯度下降是三块重要的基石。如果你正在踏上深度学习的旅程,理解它们是迈向成功的第一步。这篇文章将从概念到代码、从基础到进阶,详细剖析这三个主题,帮助你从小白成长为能够解决实际问题的开发者。
|
存储 算法 数据可视化
云上大数据分析平台:解锁数据价值,驱动智能决策新篇章
实时性与流式处理:随着实时数据分析需求的增加,云上大数据分析平台将更加注重实时性和流式处理能力的建设。通过优化计算引擎和存储架构等技术手段,平台将能够实现对数据流的高效处理和分析,为企业提供实时决策支持。通过优化计算引擎和存储架构等技术手段,平台将能够实现对数据流的高效处理和分析,为企业提供实时决策支持。
1362 8
|
前端开发 JavaScript 开发工具
跨域联姻:React.NET——.NET应用与React的完美融合,解锁前后端高效协作新姿势。
【8月更文挑战第28天】探索React.NET,这是将热门前端框架React与强大的.NET后端无缝集成的创新方案。React以其组件化和虚拟DOM技术著称,能构建高性能、可维护的用户界面;.NET则擅长企业级应用开发。React.NET作为桥梁,使.NET应用轻松采用React构建前端,并优化开发流程与性能。通过直接托管React组件,.NET应用简化了部署流程,同时支持服务器端渲染(SSR),提升首屏加载速度与SEO优化。
425 1