JAVA—咖啡馆

——欢迎访问rogerfan的博客,常来《JAVA——咖啡馆》坐坐,喝杯浓香的咖啡,彼此探讨一下JAVA技术,交流工作经验,分享JAVA带来的快乐!本网站部分转载文章,如果有版权问题请与我联系。

BlogJava 首页 新随笔 联系 聚合 管理
  447 Posts :: 145 Stories :: 368 Comments :: 0 Trackbacks

05 2008 档案

     摘要: 如果一个图中所有点都是联通的,求最小树可以将图遍历完成,这里的最小是指边最少,跟边长没有关系。

算法利用深度优先遍历,记载每个遍历过的节点,将节点按照遍历顺序记录下来就是所谓的最小树。

关于深度优先遍历请参见深度优先遍历。

不过这里奇怪的是:

假如所有节点之间是双向联通的,只用生成一个数组,装入所有的节点,例如{'a','b','c','d','d'}

然后每两个点之间的线段就是最小树的结果,即a --> b, b --> c, c --> d, d --> e

似乎不用图这样复杂的结构支撑。

不过这里还是给出了按照图来产生最小树的办法。

Graph.mst:返回最小树。

Graph.main:提供简单测试。
  阅读全文
posted @ 2008-05-28 15:58 rogerfan 阅读(609) | 评论 (0)  编辑

     摘要: 当每个任务有前后置关系时,需要找到一种满足前后置关系的路线,将任务完成。

如果将每个任务看成一个节点,任务之间的前后置关系表示为有向图时,这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。

这里的图用邻接矩阵法表示,算法的关键是:

1 找到一个没有后继的顶点

2 在图中删除它,放入结果数组中

3 重复 步骤 1 ,步骤 2 直到图中没有多余的节点。

如果图中出现环装结构,则算法无法进行,因为此时任务之间循环成为前置。
  阅读全文
posted @ 2008-05-28 15:57 rogerfan 阅读(1030) | 评论 (0)  编辑

     摘要: 图的传递闭包是指修正后的邻接矩阵表示的图。(见Graph 图-邻接矩阵法 )

在多个顶点的有向图中,每个顶点可以到按照方向到达一定的节点,这叫图的连通性。有种方法直接告诉我们,图中的两个节点是否可以联通,这里说的是WarShall算法。

WarShall的基本原理是,如果A可以到达B,且C可以到达A,则C可以到达B。通过对邻接矩阵的修正可以做到这点。随然这里举例是将两步可并成一步,但数学上可以证明这种修正可以达到任意步骤。
  阅读全文
posted @ 2008-05-28 15:54 rogerfan 阅读(812) | 评论 (0)  编辑

     摘要: 与传递闭包问题 非常相似的一个问题是,能不能给出一个矩阵,根据矩阵可以以时间代价O(n)的方式得到在一个有向代权图中任意指定端点之间的最短距离。求的这个矩阵的问题被称为每一对端点间的最小距离问题。

这里采用的是Floyd算法,它与WalShall 算法非常相似:

如果A可以到达B,距离为x,且C可以到达A,距离为y,则求得C可以到达B,距离为 z = x + y,z小于如果c到B的原来的距离,则用z更新矩阵,否则c到B距离维持不变。

和最小路径算法类似,这里用一个很大数字INFINITY来表示两个端点之间距离为无穷大的情况,即不通。这里INFINITY=最大的int值(~(1<<31))。

Floyd.main()提供简单的测试。

与WalShall 一样,Floyd算法本身的时间代价为O(n^3)
  阅读全文
posted @ 2008-05-28 15:53 rogerfan 阅读(291) | 评论 (0)  编辑

     摘要: 图中代权的最小树的问题如下:


如果N个城市之间(图中的顶点)要修公路(图中的边)以使所有的城市联通,求怎样修可以使得公路的总长最小?
以上问题中的N个城市之间可以用图中的顶点表示,公路可以图中的边表示,公路的长度用边长表示,公路是双向的。问题就转换为在有N个顶点中的双向代权图中求得一个最小树。这里的代权指的边的长度,这与以前的不代权的最小树生成算法有很大的区别。


算法描述如下:
  阅读全文
posted @ 2008-05-28 15:45 rogerfan 阅读(306) | 评论 (0)  编辑

     摘要: 这里使用的是Dijkstra来计算最短路径。事实上Dijkstra完成时,指定节点到所有节点的最小路径均已求出。

算法简述如下:

准备好两个辅助性数据结构:

1 ParentLength : 用来记录到当前节点之前的父节点,与到当前节点的最小路径

2 Path: 记录指定节点到所有节点的ParentLength。初始化时,所有的ParentLength的父节点都为指定的起始节点,长度都是INFINITY,代表没有联通,距离无穷大。
  阅读全文
posted @ 2008-05-28 15:39 rogerfan 阅读(752) | 评论 (0)  编辑

     摘要: 1 直观印象
在JDK1.5之前的版本中,对于一个Collection类库中的容器类实例,可将任意类型

对象加入其中(都被当作Object实例看待);从容器中取出的对象也只是一个Object实例,需要将其强制转型为期待的类型,这种强制转型的运行时正确性由程序员自行保证。

例如以下代码片断:
  阅读全文
posted @ 2008-05-27 11:47 rogerfan 阅读(262) | 评论 (0)  编辑

     摘要: Java技术自问世时光已经过去了9个年头。作为一名一直关注其成长的记者,曾经一段时间有过这样的想法:“Java技术已经成熟,是不是发展速度该放慢一些了呢”。然而,这种想法错了。近来Java技术的进化相当显著。Java技术正在迎来“又一次革命”的风暴。这就是本文的结论。
  
  “又一次”指的是什么?“革命”指的又是什么?光看结论的话肯定是一头雾水。其实,笔者要讲的并不是变化这样一个事实,而是“促进变化的原动力”。是什么让Java技术发生变化?让我们从这一角度出发,先看一下Java的变化历程。  阅读全文
posted @ 2008-05-27 11:32 rogerfan 阅读(163) | 评论 (1)  编辑

     摘要: 查询语言的改进是JDO2.0规范中的重要环节,本文从较高的层面阐述JDO2.0所提供的一些新功能。由于JDO2.0规范还未进入公开草案状态,目前还没有任何内容敲定下来,一切都还可能面临变化。不过,JDO2.0将会很快进入最后阶段,而这里提到的查询特性是JDO2.0专家组(译者注:David Jordan就是专家组重要成员)花费时间最多,并且相对来说最为稳定。因此,我有足够理由相信,最终规范与这里的描述将会基本一致。

  如果各位读者觉得本文遗漏了某些重要的特性,建议立即到JDO论坛(http://www.jdocentral.com/forums/index.php?showforum=10)去提出并讨论。这里我们需要感谢JDO2.0规范领导人Craig Russell授权给我公开这些JDO2.0查询语言的新特性。
  阅读全文
posted @ 2008-05-27 10:23 rogerfan 阅读(255) | 评论 (1)  编辑

     摘要:   作者注:JDO和CMP方式的EJB目前正在同时向前发展,但采取的是不同的路线。JDO的核心思想是在企业应用软件架构的不同层面中存储传统的Java对象(Plain Old Java Objects,下称POJOs),而CMP方案则基于容器环境,并针对特殊的需求。

  两者之间的异同在规范出台之初便成为众所争论的话题。你可以到JDOCentral.com上看到这类的争论,而在6月中旬即将在旧金山开幕的2003年JavaOne大会上,也会有一些演示和讲解来比较这两种不同的技术。

  在这次JavaOne大会上,3368号技术对话将讨论JDO与Struts(一个著名的Web应用架构设计的开源软件)集成的可行性和实践经验;3236号专题研究JDO与EJB容器的结合;1289号专题将对比使用JDO、JDBC和EJB时,设计模式在开发中的应用。

  在我们的《Java Data Objects》的第17章有一小段话描述使用JDO和CMP的平衡点。--Craig Russell   阅读全文
posted @ 2008-05-27 10:22 rogerfan 阅读(224) | 评论 (0)  编辑

     摘要: JDO的优点:
  
  ● JDO的生命周期状态机(lifecycle state machine)是正确的用法。任何其它的O/R映射工具都应该使用JDO的生命周期或者它的子集(例如:如果不支持事务)。记住,JDO生命周期是为JDO实现服务的。大部分用户不需要了解其中很复杂的内幕。网页Amber生命周期中有些图示。
  
  ● PersistentManager API对如何管理JDO对象的状态有一定的优势和价值。
  阅读全文
posted @ 2008-05-27 10:20 rogerfan 阅读(253) | 评论 (0)  编辑

     摘要: 网上关于JDO的文章已经不少了,关于JDO的优点也讲了很多,我看了一些文章后,自己也研究了一段时间,忽然很想写一个系列文章全面的介绍一下JDO,今天先写下第一篇算是个开头。呵呵,有些内容是我对JDO规范的理解,如果有不对的地方请大家指正。
  
  Java开发人员已经有好几种存取数据库的方法:序列化,JDBC,面向对象映射工具,对象数据库,以及实体EJB。那为什么还要介绍其他的存储架构呢?答案是,上面每一种实现存储的方案都存在一定的限制。JDO正在尝试解决这些限制。  阅读全文
posted @ 2008-05-27 10:19 rogerfan 阅读(255) | 评论 (0)  编辑

     摘要: JDO是Java对象持久化的新的规范。JDO经SunJava Community Process认定。
  
  
  一、历史
  JDO是对象持久化工作的综合成果,试图提供一个对象持久化的完全版本。JDO同时继承于ODMG(对象数据管理小组,标准化对象数据库的一个独立委员会)和对象关系映射工具提供商。
  JSR #000012 approved in July 1999
  1999-8组建的专家小组:包括Sun、Apple、BEA、IBM、Oracle、SAP、WebGain等
  2000-5 完成公开评论草案
  2000-6 在JavaOne上引入
  2001-3 最终草案0.93
  2001-5 最终草案0.96公布
  2001-6 在JavaOne上启动
  2001-11 最终草案0.98  阅读全文
posted @ 2008-05-27 10:18 rogerfan 阅读(221) | 评论 (0)  编辑

     摘要: 在反射的帮助下,我们可以有效的简化这个繁琐的过程,看代码之前我们先补充一点有关类字段的反射API:
●Field[] getDeclaredFields():返回已加载类声明的所有成员变量的Field对象数组,不包括从父类继承的成员变量.
●Field getDeclaredField(String name):返回已加载类声明的所有成员变量的Field对象,不包括从父类继承的成员变量,参数name指定成员变量的名称.
●Field[] getFields():返回已加载类声明的所有public型的成员变量的Field对象数组,包括从父类继承的成员变量
●Field getField(String name):返回已加载类声明的所有成员变量的Field对象,包括从父类继承的成员变量,参数name指定成员变量的名称.  阅读全文
posted @ 2008-05-23 12:52 rogerfan 阅读(371) | 评论 (3)  编辑

     摘要: 文章摘要

Torque项目是Apache的公开源代码项目,主要用于生成访问数据库的资源和java代码、提供使用这些代码访问数据库的运行时(runtime)环境。通过使用Torque,你可以使用面向对象方式访问数据库,不再需要编写任何SQL语句。本文中给大家详细的介绍了如何使用Torque框架访问数据库的整个过程,希望能够指导大家熟练使用Torque。
  阅读全文
posted @ 2008-05-22 11:52 rogerfan 阅读(400) | 评论 (0)  编辑

     摘要: Apache Torque 是一个使用关系数据库作为存储手段的Java应用程序持久化工具。Torque是一个开源项目,由Web应用程序框架
  Jakarta Apache Turbine 发展而来,但现在已完全独立于Turbine。通过JDBC,Torque支持大多数流行的开源商业数据库,包括Oracle、Microsoft SQL Server、IBM DB/2、MySQL以及PostgreSQL。  阅读全文
posted @ 2008-05-22 11:51 rogerfan 阅读(269) | 评论 (0)  编辑

     摘要: Apache Torque是一个使用关系数据库作为存储手段的Java应用程序持久化工具,是 Apache 的公开源代码项目,Torque是一个开源项目,由Web应用程序框架Jakarta Apache Turbine发展而来,但现在已完全独立于Turbine。 Torque 主要包含两部分:一部分是 Generator,它可以使用xml文件,产生应用程序需要的所有数据库资源,包括 sql 和 java 文件;另外一部分是 Runtime,提供使用这些代码访问数据库的运行时环境。  阅读全文
posted @ 2008-05-22 11:33 rogerfan 阅读(1042) | 评论 (0)  编辑

     摘要: Peers
Everything in Peers resolve around Peer classes. A Peer class has a one-to-one mapping to a Database table. You use each table's associated Peer class to do operations on that table. Peer classes are generated for you automatically.

Peer classes have static methods only, so you would never create objects of Peer classes. It is not necessary to have objects on this level because of the one-to-one mapping with a table. Peer methods are thread safe.

Peer classes are ge  阅读全文
posted @ 2008-05-22 11:31 rogerfan 阅读(258) | 评论 (0)  编辑

     摘要: 一般在利用O/R Mapping框架进行开发的时候,有三个基本的单元即关系数据库中的表(Table),Java中的持久对象(PO),定义PO到Table映射的xml文件(Schema)。
首先,Torque包含一个generator用来根据由开发者配置好的Schema来自动生成PO和Table,这就意味着开发者只要定义好Schema,PO和Table就可以自动生成了。
在生成好的PO和Table以后,开发者就可以利用PO来进行对Table的访问了。为了达到这个目的Torque提供了一个运行时环境来保证代码的正确运行。在工程中引入了torque相关的.jar就可以拥有这个运行环境了。  阅读全文
posted @ 2008-05-22 11:29 rogerfan 阅读(881) | 评论 (0)  编辑

     摘要: 目前对于J2EE应用中的Persistence Layer的解决方案很多,其中,最近从Apache Turbine中剥离处理的Torque是一个优秀的ORM(Object Relational Mapping,对象角色建模) 解决方案。

  主流的Persistence Layer解决方案

  随着基于J2EE应用的日益增加,出现了很多Persistence Layer的解决方案。目前主要的解决方案有以下几种:

  ◆ 自己编写基于JDBC API的解决方案;

  ◆ 采用ObjectRational Mapping(ORM)工具或者是采用面向对象的数据库(ODBMS);

  ◆ J2EE/Entity Bean CMP (container-managed persistence);

  ◆ JDO。  阅读全文
posted @ 2008-05-22 11:20 rogerfan 阅读(357) | 评论 (1)  编辑

     摘要: Groovy是一种语言,其语法类似于Java,但比Java更简单。它通常被视为脚本/灵活/动态的语言,但是我不喜欢这类形容词,因为我认为它们只会令人困惑。如果说Java是一位明智的中年男子,那么Groovy就是他十几岁的儿子。Groovy具有父亲的许多特点,但是更为狂野且更为有趣。他们也可以很好地合作。  阅读全文
posted @ 2008-05-22 11:09 rogerfan 阅读(534) | 评论 (0)  编辑

     摘要: 1. 为了方面按列作外循环,想把ArrayList构造成一个二维数组,如下:

......

ArrayList result=GetResult();

int n=result.size();

String[][] myArray=new String[n][]; //定义二维数组

for (int i=0;i {
ArrayList tempArray= (ArrayList)result.get(i);
myArray[i]=(String[])tempArray.toArray();
}

......
  阅读全文
posted @ 2008-05-14 13:40 rogerfan 阅读(1897) | 评论 (0)  编辑