Composite模式和树形结构的讨论

总共有 12 回复／ 1 页

banq

悄悄话
发表文章: 9528
注册时间: 2002年08月03日 17:08

Composite模式和树形结构的讨论	2005年11月22日 15:55
标签列表 composite模式(20) visitor模式(10) 设计模式(166) 框架(52)

最近在使用Jdon框架做JiveJdon3，碰到一个老问题，主题帖和回帖之间是树形结构关系，现在碰到两种方案：

1. 采取Composite模式封装复杂的树形结构，这样外界要访问一个主题贴需要树形遍历时，由Composite内部来树形算法来遍历，外界只要告诉要怎样的结果即可。
优点：封装了树形结构的遍历算法，外界客户端无需自行进行帖子的树形结构相关判断代码。
缺点：对树形结构的操作有各种各样，而且以后可能有新增新的操作，这可能涉及修改Composite模式的Component接口。
Composite模式：http://www.jdon.com/designpatterns/composite.htm

这种采取Composite模式封装树形结构遍历的方法，为防止新增新的操作改动接口，可引入访问者模式，下面这篇文章谈到了用C++实现Composite模式+Visitor模式解决树形结构封装算法:
http://members.home.nl/r.f.pels/articles/misc/C++PatternsAndTreesSeparatingKnowledge.html
它主要讨论了如何分离树形结构的不同类的对象和用户界面的树形结构表现这两个方面。

2.不采取Composite模式进行树形结构封装，就象原来Jive一样，给每个主题贴提供一个TreeWalker对象，这样外界如果要遍历这个主题贴时，自己通过TreeWalker去遍历树形结构。
优点：比较符合模型编程，ForumThread主题贴是一个模型，里面提供一个自身树形结构遍历，非常开放，外界客户端有新的操作，只要得到模型ForumThread就可以了。
缺点：TreeWalker提供的树形结构遍历方法有限，有可能不能满足新的操作或新的功能的需要。

有过这方面考虑的人可一同讨论一下。

banq

悄悄话
发表文章: 9528
注册时间: 2002年08月03日 17:08

Re: Composite模式和树形结构的讨论

2005年11月23日 14:38

这条题目其实应该算非常难的一道题，涉及到GoF模式中两个较不常用的模式，而且又解决了日常编程中经常碰到的对象树形结构问题，请真正大牛的人来解决这个实际问题吧。我原意洗耳恭听。是显示您真正水平的时候了。

whatavery

悄悄话
发表文章: 14
注册时间: 2005年11月25日 16:17

Re: Composite模式和树形结构的讨论

2005年11月25日 16:56

在这里回复是不是也太不知天高地厚了，因为和banq老师的水平差的不是一点半点了。

我认为TreeWalker是优于Composite，我在用Composite的时候更倾向于那种隐性的树模式。至使连有些客户并在UI上并看不出来。但是这种替代结构我一直不敢特别肯定他的整和/扩展程度，而需要结合其他模式如Visitor，Adapter等来扩展。

所谓替代结构，如
Polymorphism把if/switch Refactoring掉
Iterator把for Refactoring掉
Composite把纯tree Refactoring掉
等等

对于这些很纯的tree，我认为类似于TreeModel/DefaultTreeModel这种封装型的才是最好扩展的。而Composite在增加系统复杂度的情况下实现，表面上看结构是清楚的，但效率和扩展度，都没直接的tree封装来的痛快。

因为和banq老师差的水平太多，所以只提供一个投票性的意见，我是第一次发帖子。谢谢banq老师写了那么多精彩的文章，其实我回帖不是目的，只是来景仰一下banq老师

鲁中正气

悄悄话
发表文章: 50
注册时间: 2005年06月13日 17:33

Re: Composite模式和树形结构的讨论

2005年11月26日 20:40

所谓替代结构，如
Iterator把for Refactoring掉
Composite把纯tree Refactoring掉

好！好！口诀阿。
不过，Polymorphism把if/switch Refactoring掉
除了Polymorphism还可以用其他方式吧

banq

悄悄话
发表文章: 9528
注册时间: 2002年08月03日 17:08

Re: Composite模式和树形结构的讨论

2005年11月29日 16:10

whatavery这方面是有一定研究。

TreeWalker/TreeModel和Composite相比，要简单直接多。

Composite模式是一种内敛式样或者趋向闭合的模式，该模式是将以前在客户端中实现的代码强制收回，这对一个Open开放结构有所伤害。

因此，一般使用Composite模式都要结合Visitor模式，但是，
使用Composite+Visitor模式带来缺点是：对访问者进行了一定限制，例如可能只是需要一个帖子集合，必须将将这段代码变成一个访问者类。

但是，如果单纯使用TreeWalker/TreeModel，TreeModel中只封装了常见的树操作，万一有新的特殊树操作，需要更改TreeModel接口，而且TreeWalker客户端会拥有自己对树结构遍历的代码，需要增加新功能或维护时，都需要维护者对这个树了解，可维护和可拓展差。

现在，我采用的方案是：TreeWalker/TreeModel和Composite+Visitor两个结合，我通过TreeWalkerService以服务形式向外提供常见的树操作，而TreeWalkerService内部的实现是通过Composite+Visitor实现的。当在组件层以后需要有新的树结构操作时，使用Composite+Visitor实现。

也就是说：Composite+Visitor在组件层封装了树形结构，这样在组件层各处就没有零星散落的涉及树形结构操作的代码，如果你需要将这组树形结构数据转化为XML，那么做一个Visitor方法即可。如果在表现层需要操作树形结构，只能通过TreeWalkerService了。

这样做到通用和定制，简单和复杂实现一定的统一。
以上只是个人观点，欢迎讨论。

banq

悄悄话
发表文章: 9528
注册时间: 2002年08月03日 17:08

Re: Composite模式和树形结构的讨论

2005年11月30日 18:26

在IBM发现早在2002年就有老外进行这方面研究，并且提出深度优先访问器，这些估计在Junit中得到了很好的实现。

文章连接:深度优先访问器和中断的分派

看来，使用Composite+Visitor对树的访问是不错，问题难题还是如何在Model/Service这样数据模型的构件系统中实现啊。

对于一个数据模型，我们使用parentID和currentID两个字段表示这同一个数据模型不同对象之间的父子关系；而使用Composite模式，两个重要的子类，Leaf（叶）和Branch（枝）必须首先确定。

这两者之间就存在一定衔接距离，衔接的功能是：必须根据parentID和currentID这个简单的信息，找出一颗树中的Leaf和Branch，然后装入Composite供Visitor访问。

这个衔接功能实际是树的算法，我们需要在内存中（缓存）中首先根据parentID和currentID建立一颗完整的树，这样就能从这个树中获知leaf和Branch，从而使用Composite实现树的操作方法封装。

这是一点思考，望能获得whatavery等高手交流指导。

whatavery

悄悄话
发表文章: 14
注册时间: 2005年11月25日 16:17

Re: Composite模式和树形结构的讨论

2005年12月01日 01:13

看来banq老师对Composite+Visitor还是很欣赏的，感觉banq老师肯定倾向于用Composite+Visitor模式的。

但banq老师实在是对Composite要求太高了，Composite是实现了递归树的模型，但我理解老师想要把Composite当节点用，这肯定无法满足需求了。

（因为水平和banq老师相去太远，理解老师的意思可能不到位，希望老师见谅）老师的意思要是细化到节点，对节点进行封装，从而跳出Composite的约束。节点无非三种：Root，Branch，Leaf。但都可以归结为Branch（Root，Leaf视为特殊节点），这样就可以细化到节点了，而节点对象需要有一个有ID到另一Branch对象的映射过程的对象，所以已经产生两个对象：1，Branch对象 2，Finder对象。

Branch对象，持有自身的parentID和currentID，聚合Finder对象。
Finder对象，返回Branch对象的collection（子），或返回Branch对象（父）。

且Finder对象自身递归。

这样就由递归树的模型细化到了递归节点的模型。

老师对Composite要求过于严格了。

对于效率我一般倾向于primitive，所以我觉得这个模型 ID-对象-ID-映射-对象也许可行。

banq老师，我说实话，我发的帖子真向您表示尊敬，至于讨论，我还不够资格。

呵呵，至于看贴的高手就不要笑话我了，我只是初学者。

banq

悄悄话
发表文章: 9528
注册时间: 2002年08月03日 17:08

Re: Composite模式和树形结构的讨论

2005年12月01日 10:22

whatavery太谦虚了，能有人一起讨论这样一个吃力不讨好的设计非常难得。

你只使用两个对象抽象：Branch对象和Finder对象是一种思路，非常不错，有时间我会按照这种思路仔细考虑一下。

我目前思考方向是这样的：根据Composite模式定义，需要两个重要子类，第一是复合类Composite，相当于Branch，另外一个是非复合类，单个对象，相当于Leaf，所以，我的代码非常类似"深度优先访问器和中断的分派"一文中"清单 1. 带访问器的二叉树"的代码。

在Jive中有一个LongTree，它使用 leftChildren和rightSiblings两个primitive数组来保存Branch二叉树的特点，然后它根据这两个数组可以得到任何一个节点的子集合，相当于实现你的Finder对象功能。

我就使用LongTree的这两个数组算法，生成Composite模式需要的Leaf和Branch对象，LongTree使用这个两个数组是直接实现TreeWalker（TreeModel），我是用来既实现treeWalker，又用来实现Composite+Visitor。

whatavery

悄悄话
发表文章: 14
注册时间: 2005年11月25日 16:17

Re: Composite模式和树形结构的讨论

2005年12月01日 16:07

banq老师对LongTree到Composite过程中，使不使用Strategy/Builder有什么看法?

banq

悄悄话
发表文章: 9528
注册时间: 2002年08月03日 17:08

Re: Composite模式和树形结构的讨论

2005年12月01日 16:30

说的好，Strategy/Builder都要使用，首先内存中要建立一个二叉树数据结构，这里使用到Builder模式，我将longTree的add方法分解到Builder中。

从这个二叉树中延伸出两种算法策略Strategy：一个遍历提供getChildern等方法treeWalker；另外一个是Leaf和Branch节点的获得，奠定Composite基础。

设计时，我们先穷尽其复杂性，到真正实现时，简化一下，避免让人眼花缭乱。

我现在总结一下通过Composite+Visitor访问的具体功能：删除帖子、显示树形结构帖子、将帖子转为XML格式。

目前这三个功能方法使用Composite+Visitor好像显示不太多好处，如果有更多树形操作代码，就能显示出来。

banq

悄悄话
发表文章: 9528
注册时间: 2002年08月03日 17:08

Re: Composite模式和树形结构的讨论

2005年12月02日 11:34

其实我们讨论到现在，相当于已经把一个普通通用常用的问题用模式语言表达出来，据此可以形成一套解决树形结构访问的应用框架了。最重要的是：树形结构问题基本方向搞清楚，以后再碰到此类问题，可以向这个方向去再深入研究。

模式语言相关的连接地址：

模式采掘、体系结构设计和应用框架开发

banq

悄悄话
发表文章: 9528
注册时间: 2002年08月03日 17:08

Re: Composite模式和树形结构的讨论

2005年12月02日 11:41

另外我想说的是：本主题涉及到数据结构+模式语言的解决方案，可是我们高等教育中只讲数据结构，不讲模式语言，导致出现大量左撇子，重视数据结构数据库，不重视软件可维护性可拓展性和重用性。这也是我曾经提出“设计模式”应该是程序基础教育一部分的原因。

另外一个对模式疑问的讨论：
懂模式又咋样？不还是一个技工吗？

shanghaimin

悄悄话
发表文章: 45
注册时间: 2007年05月29日 04:44

re:Composite模式和树形结构的讨论

2007年05月30日 00:05

In Macro level, Design pattern is a fundamental methodology to make big application extendable,testable,maintainable.
while in Micro level, the fundamental methodology is the well-known algorithms which can improve the system performance.

But the real big distribution real-time project needs another cornorstone, Parallel Programming.

这个主题有 12 回复／ 1 页