`
E-Hunter
  • 浏览: 11678 次
  • 性别: Icon_minigender_1
  • 来自: 青岛
社区版块
存档分类
最新评论

复合对象解析为XML的顺序表算法

    博客分类:
  • Java
阅读更多

上两个图,说明复合对象的关系以及XML表示的方法:

简单来说就是Root中有objectA跟objectB,objectB中包含objectC,objectC中又包含了objectA,即引用了objectA。




    注意看objectC这个节点中,reference属性使用相对路径表示出了objectA的位置。
大家从上面两个图应该了解这是个什么情况了。

    那么先说一下树形结构的解决方案,当然是构建多叉树,然后开始对树进行遍历,效率是很低的~~

    那么再说下我的解决方案:
    看图:

    Root伴随着一个长度为1的数组,第一个元素为0,表示这是根节点,objectA伴随着长度为2的数组,表示它是Root的第一个节点,objectB和objectC应该也很好理解了吧。
这样,当把Root解析为XML时,发现objectC引用了ObjectA,那么怎样获得reference的值呢?因为这是一个顺序表,所以我们去遍历它。首先取得objectA的标志性数组{0,1}那么先查找数组第一个元素为0的元素,在绝对路径上加上“Root”,得到“/Root”,然后开始搜索第二个元素为1的节点,找到后加到绝对路径上就得到“/Root/objectA”了。

    另外需要说明的是,再设计这个算法的时候,我不确定xml是否必须只有一个根节点,所以采用了现在的思路,如果能够确定只有一个根节点的话,那么就可以稍作更改了,总的思路就是这样的,至于在具体实现中,采用数组还是ArrayList,还是HashMap,大家就随意了。我刚刚构思出这个算法,也没有通过实际的例子与树形结构的算法进行性能比较,但是顺序表查找快是无需置疑的,所以我感觉这个算法还是应该很有效率的,欢迎大家拍砖~~

 

分享到:
评论
2 楼 E-Hunter 2010-08-22  
恩恩~楼上所言极是,所以后来我才又发表了《复合对象解析为XML的顺序表算法的改进》,改掉了这个算法中的一些缺陷。另外,由于时间关系我还没有来得及进行实际测试的相关工作,编码过程中所遇到的一些其他问题,会陆续在博客中发表,与大家进行交流~
1 楼 zozoh 2010-08-22  
这个算法有两个关键:

  1. 什么是对象的 ID
  2. 如何根据对象反查出对象的 ID // 在 refer A 时,你需要知道 A 的 ID
 
楼主给出的答案是
 
  1. ID 就是一个数组,表示一条路径
  2. 循环遍历索引表
 
我的问题是:
 
  1. ID 为什么是一个数组而不是一个整数呢?
  2. 至少要用散列吧

我的详细建议:

如果,每输出一个节点,都将这个对象放到一个数组里
ids[i] = obj;
i++

并且将 i 为这个对象的 ID,如果你知道了一个对象的ID,则可以很快拿到这个对象的实例引用

那么其他对象 refer 这对象时,如果获得这个对象的ID呢?
因此你还需要一个这个对象的反查索引:
ids[i] = obj;
indexes.add(obj, i);
i++

根据一个对象,获取其 ID
int objId = indexes.get(obj);

如果采用 HashMap,则对象的 hashCode() 方法给出的散列值是效率的关键,但是效果最差也比遍历索引表要快很多
因为它是对基于 hasCode 的散列表进行二分查找

无论从 POJO 到 XML,还是从 XML 到 POJO,大体都可以用这种思路

相关推荐

    hibernate源码分析过程

    Hibernate 的基本映射包括 id 算法、复合主键、数据版本并发性控制等。id 算法可以是整型自增、sql server 等数据库的 identity、Oracle 的 sequence、hilo(高低位)算法、uuid、guid、程序赋值等。复合主键可以...

    2017年阿里Java基础面试题文档 Java知识分享

    - **树**:层次结构的数据表示形式,通常用于文件系统、XML解析等。 - **图**:由顶点和边组成的复杂数据结构,用于模拟复杂的网络结构。 #### 十一、String与StringBuffer的区别 - **String**:不可变字符串,即...

    快学 scala 中文版 带完整目录

    10.1 为什么没有多重继承 135 10.2 当作接口使用的特质 137 10.3 带有具体实现的特质 138 10.4 带有特质的对象 139 10.5 叠加在一起的特质 140 10.6 在特质中重写抽象方法 141 10.7 当作富接口使用的特质 142 ...

    HIBERNATE - 符合Java习惯的关系数据库持久化

    通过将Java对象模型映射到关系型数据库表上,Hibernate为数据持久化提供了强大的支持,同时保持了代码的简洁性和可维护性。 #### 二、权限与配置 在部署Hibernate之前,必须确保具备适当的权限,并进行正确的配置...

    2021-2022计算机二级等级考试试题及答案No.18700.docx

    17. 作用域顺序:在Web开发中,作用域从大到小为application > session > request > pageContext。 18. 赋值语句:在C/C++或类似的编程语言中,x++=y++这样的复合赋值语句可能导致未定义行为,因为它涉及到了两个...

    2021-2022计算机二级等级考试试题及答案No.13674.docx

    在一个表中,可以设置一个复合主键(由多个字段组成),但通常建议仅使用单一字段作为主键以简化设计。因此,正确答案是**B. 主关键字段中不许有重复值和空值**。 ### 3. 二分查找的应用 二分查找算法适用于有序...

    前端面试宝典V3.0.docx

    - **引用计数算法**:每个对象都有一个引用计数,当引用计数为 0 时,对象会被回收。 #### 进程与线程的关系 - **进程**:是操作系统分配资源的基本单位。 - **线程**:是进程内的执行单元,一个进程可以有多个线程...

    WebKit分析报告2

    - **DOM解析基本算法**:将HTML文档转换为DOM树的过程。 #### WebKit DOM代码解析流程 - **解析HTML文档**:生成DOM树。 - **解析CSS样式表**:生成样式规则。 - **合并DOM树和样式规则**:生成渲染树。 ### ...

    2021-2022计算机二级等级考试试题及答案No.4807.docx

    以下是根据题目内容解析的一些重要知识点: 1. C 语言特性:C 语言允许 main 函数在文件的任何位置,每行可以写多条语句,但通常为了可读性,每行只写一条。C 语言没有内置的输入/输出语句,输入/输出通过标准...

    中级程序员必备面试题.txt

    而`LinkedHashSet`则是基于哈希表与双向链表实现,保证了元素插入顺序。 #### 用JDBC编写带有事务处理的代码示例 使用JDBC进行数据库操作时,事务管理是非常重要的。以下是一个简单的示例: ```java Connection ...

    2021-2022计算机二级等级考试试题及答案No.13774.docx

    - **知识点**: 在Python中,使用文件对象的 `write()` 方法可以向文件写入字符串。 - **正确答案**: B. 90,87,93 ### 17. IE 浏览器功能 - **知识点**: 使用IE浏览器,收藏夹功能允许用户保存网页链接。 - **正确...

Global site tag (gtag.js) - Google Analytics