重定向

此博客已停止更新,新址: http://blog.scicooking.net


2007年11月22日星期四

fork()子进程和父进程共享的资源

子进程和父进程共享很多资源,除了打开文件之外,很多父进程的其他性质也由子进程继承:

• 实际用户ID、实际组ID、有效用户ID、有效组ID。

• 添加组ID。

• 进程组ID。

• 对话期ID。

• 控制终端。

• 设置-用户-ID标志和设置-组-ID标志。

• 当前工作目录。

• 根目录。

• 文件方式创建屏蔽字。

• 信号屏蔽和排列。

• 对任一打开文件描述符的在执行时关闭标志。

• 环境。

• 连接的共享存储段。

• 资源限制。

父、子进程之间的区别是:

• fork的返回值。

• 进程ID。

• 不同的父进程ID。

• 子进程的tms_utime,tms_stime,tms_cutime以及tms_ustime设置为0。

• 父进程设置的锁,子进程不继承。

• 子进程的未决告警被清除。

• 子进程的未决信号集设置为空集。

2007年11月3日星期六

让Eclipse显示JVM当前内存使用量

更新:Eclipse 有对应的选项...
Windows -> Preferences... -> General
勾选 Show heap status 即可。

让Eclipse显示JVM当前内存使用量:

1、在Eclipse根目录下建立一个文件,文件名options,文件内容org.eclipse.ui/perf/showHeapStatus=true

2、用这条命令启动Eclipse:

E:\eclipse3.1\eclipse.exe -debug options -vm javaw.exe

或者直接右键Eclipse的快捷方式,在"目标"中填入这行。

3、启动Eclipse,就可以看到下面的状态栏会显示当前JVM内存使用量,另外还可以强制进行垃圾收集。

4、可以使用 eclipse.ini 替代命令行参数,每个参数名或者参数值单独一行

-debug
options
-showsplash
org.eclipse.platform
--launcher.XXMaxPermSize
256
-vmargs
-Xms64m
-Xmx256m

可以更改 JVM 堆和栈的大小.
如果在 eclipse.ini 中用 -vm 参数,必须些全路径指定 java.exe 或者 javaw.exe

2007年7月10日星期二

非常有创意的捐血慈善广告


非常有创意的捐血慈善广告。
将播放器的进度条模拟成抽血的血管。
当5秒之后视频中的护士和你道谢后拿起这个血管。
广告形式中的文案也很具有煽动性。
“对你来说只是一个短暂时刻,但对我们来说可能意味着一个生命。”


2007年7月2日星期一

Zend Framework 1.0.0 发布

framework.zend.com

Zend Framework NEWS
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

=RELEASE 1.0.0 / 30-Jun-2007 / based on revision 5541 =
- Zend_Cache
ZF-1583 Zend_Cache_Backend_APC should be Zend_Cache_Backend_Apc
ZF-1606 Zend_Cache does not allow using ZendPlatform cache backend
- Zend_Controller
ZF-778 _redirect() needs to use absolute URIs?
ZF-1439 Request_Http Should check REDIRECT_URL before REQUEST_URI
ZF-1444 allow to set noController globally
ZF-1456 Incorrect behavior in ViewRenderer when exception is thrown
ZF-1485 Prevent unnecessary ViewRenderer instanciation
ZF-1493 default controller class is different from class for specific modules
ZF-1495 when useDefaultControllerAlways is true, a bad view can be selected
ZF-1503 ViewRenderer calls methods not in Zend_View_Interface
ZF-1553 ViewRenderer by postdispatch not disabled by invokeArgs setting
ZF-1571 Wrong method call in zend.controller.plugins.html examples
ZF-1572 Missing parameter in zend.controller.actionhelpers.html example code
ZF-1640 Wrong example in 7.5.5. Base URL and subdirectories
ZF-1642 Can't overwrite headers with setHeader
ZF-1643 Zend_Controller Unit Tests failing
ZF-1649 Plugin broker should attempt to catch plugin exceptions
ZF-1650 Add stack order to plugin broker
ZF-1654 ViewRenderer and finding view scripts
- Zend_Db
ZF-884 SQLite: result set contains correlation names in keys
ZF-1518 Silent failure from describeTable() when schema is wrong
ZF-1563 QuoteInto doesn't work with Sqlite
- Zend_Db_Adapter_Db2
ZF-1648 Fixed DB2 Util tests that get the schema used to qualify a name
- Zend_Db_Table
ZF-1634 The findParentBy() fails to extract the correct class
ZF-1625 Mistakes in Relationships code examples
ZF-1645 createRow() should omit identity columns from data
- Zend_Debug
ZF-1602 Data not in UTF-8 is stripped by htmlentities()
- Zend_Filter / Zend_Validate
ZF-1641 PCRE UTF-8 Support Unavailable on Some Platforms
ZF-1646 Cache result check for UTF-8 and Unicode support in PCRE
- Zend_Gdata
ZF-1644 Order of parameters in FeedLink and EntryLink is not optimal
ZF-1653 author and published-min/published-max missing from Gdata_Query
- Zend_Loader
ZF-1512 loadClass() fails when $dirs contains '.'
- Zend_Log
ZF-1627 Incorrect example in the manual for Zend_Log_Writer_Db
- Zend_Mail
ZF-1622 Safe-Mode Warning in Zend_Mail while sending mails with mail()
- Zend_Memory
ZF-1261 AccessController.php missing require_once for the class it implements
- Zend_Pdf
ZF-1657 Zend_Pdf_Filter interface violates coding standard
- Zend_Registry
ZF-1613 Zend_Registry::setClassName() should load specified class
- Zend_Search_Lucene
ZF-1561 Wrong returned result in comparison to Luke toolbox
ZF-1655 Common_TextNum analyzer skips zeroz, 8 and 9
- Zend_Session
ZF-1610 Zend_Session::rememberMe() can not modify the session cookie lifetime
- Zend_Translate
ZF-1635 Wrong translate() and isTranslated() translation check
ZF-1647 Typo in Zend_Translate documentation
- Zend_View
ZF-1542 FormLabel View Helper silently ignores third parameter
ZF-1568 Zend_View_Helper_FormCheckbox values
- Zend_XmlRpc_Client
ZF-1566 Class 'Zend_Xml_Rpc_Value_Exception' not found
ZF-1637 fatal error if server does not return a response
- Total of 46 issues resolved; for a detailed list, see the changelog
in the issue tracker at http://framework.zend.com/issues

2007年5月29日星期二

Zend Framework 1.0.0 RC1 released

1.0第一个候选版本,55
下个版本将会在六月中旬放出来。

Download it from http://framework.zend.com/

This is the home stretch toward 1.0! Everyone has worked very hard for
many months, and we are very close to finishing what we set out to do
with Zend Framework 1.0. This Release Candidate is intended to show the
complete set of features Zend Framework 1.0 has. Following the final
1.0 release, Zend Framework will continue to grow and improve, but there
will be a great emphasis on maintaining backward-compatibility. That
has been the mission of Zend Framework from the beginning, to provide a
professional web framework with quality and stability.

There are a few noteworthy additions in this release, but some of these
impact backward-compatibility:

- Zend_Controller has a new feature called the ViewRenderer, which makes
it very easy to design controller actions. See docs for the new usage;
there is a section in the Controller Migration section for updating your
MVC applications.

- Zend_Gdata has a new object-oriented usage, making this client very
similar to the interface of Gdata clients for other programming
languages. However, support for Google Calendar is unfinished and
remains in the incubator.

- Zend_Db statement classes now have a consistent interface and common
classes and exceptions across all database adapters; however, binding
query parameters and results to PHP variables by reference has a bug
(logged as ZF-1440).

- Zend_Filter_Input is a new class with an old name. This provides a
solution for declaring rules to filter and validate groups of data, and
it serves as a "cage" from which only values that pass your validation
rules can be retrieved.

- Zend_Service_StrikeIron is a new web service client in the incubator.

There have been 90 issues fixed in this release since 0.9.3. See the
changelog for a list of issues addressed in Release 1.0.0RC1:
http://framework.zend.com/changelog

The next release will be in mid-June, and it will likely be a second
release candidate.

2007年3月31日星期六

Blogger: 使用Picasa Web Albums


picasa相册空间已经自动升级到1G.
Blogger使用picasa相册作为存储空间了吗?测试一下.

原文:
http://buzz.blogger.com/2007/03/blogger-and-picasa-web-albums.html

2007年3月22日星期四

A4纸折CD套

Double CD case


A4纸折CD套(放两张)

注意:
1.第一步很关键,线要对齐,不要误差太大了
2.第三步折两个小折角的时候要保持两边的距离相等,这样后面对得齐
3.第三步时可以把你的光盘的一条边(切线)紧贴中线,另一端头作为折小折角时的参考,这样可以较精确地控制CD套的大小(自己体会一下吧)
4.第五步中是把d的那个直角沿水平线平行放入b的"小套子”中
注:A3纸折CD套是A4的二分之一适合放小的CD-R。

2007年3月18日星期日

ANNOUNCE: Zend Framework 0.9.0 发布

下载地址:http://framework.zend.com/

这是首个beta版本发布。这是Zend Framework项目的一个里程碑,因为beta状态确定了Zend Framework 1.0 的特性,我们会采用向后兼容和接口的稳定。

2007年3月7日星期三

人的性格是不是基因决定的

◇◇新语丝(www.xys.org)(xys.dxiong.com)(xys.3322.org)(xys.xlogit.com)◇◇

人的性格是不是基因决定的?

·方舟子·

国内第一部武侠动画片正在热播,有人认为该片“内容低级,充满了暴力、
情色、脏口、恐吓、威胁”,孩子们长期观看,“会产生很严重的不良影响”,
因此请求停播该片。但有一位被称为“童话大王”的儿童文学作家对此很不以为
然,对记者表示:“我认为一个孩子怎么样,基本上是遗传基因决定的。后天环
境对孩子的影响有多大我不是很清楚,但是父母是怎样的,一个孩子基本上就应
该是怎样的了。”

如果不是记者转述有误的话,“童话大王”的这个评论是自相矛盾的。既然
他不清楚环境的影响有多大,又何以能够断言一个孩子的性格基本上是遗传基因
决定的呢?

“童话大王”的观点,是属于所谓遗传决定论。一个人的性格是基本上先天
决定的,还是受环境的影响后天使然的,曾经是一个争论不休的问题。遗传决定
论向来被认为是反动的、保守的,环境决定论则被认为是进步的、开明的。争论
虽然激烈,在以前却缺乏严谨而客观的科学研究,或者是出于社会偏见,或者是
出于美好的愿望。近二十年来,才有了比较可靠的科学研究,可以对基因、环境
对人的性格的影响下一个结论。

在遗传学上,要研究基因与环境的关系,可以设计一个简单的实验:让有着
相同的基因组的个体(也就是所谓克隆)控制在不同的环境中生长,比较其结果。
同卵孪生子有着相同的基因组,是很好的实验材料,但是我们却无法拿人来做这
种控制实验,只能进行调查统计。

这有两种办法。一种是比较同卵孪生子和异卵孪生子的异同。同卵孪生子是
由同一个受精卵分裂发育来的,他们的基因组相同,遗传相似程度达到100%。
异卵孪生子则是两个(或更多个)卵分别被两个(或更多个)精子受精产生的不
同受精卵分别发育而来的,虽然他们在同一时间位于同一子宫,但是他们的遗传
相似程度与同一对父母在不同时间生下的两个孩子是一样的,平均为50%。如果
某种行为特征在同卵孪生子之间的相似程度并不比异卵孪生子高,那么我们可以
认为这种特征的遗传程度很弱。反之,如果同卵孪生子在某种行为特征的相似程
度高于异卵孪生子,那么它就很可能是受到遗传影响的。

另一种方法是比较出生后不久就被分开在不同家庭抚养的同卵孪生子和在同
一个家庭抚养的同卵孪生子。这个办法的依据是认为在不同家庭抚养的孪生子有
不同的生长环境,因此其相似性就可认为是由于有相同的基因导致的。这个依据
并不完全可靠,因为孪生子在被分开抚养之前,至少已有九个月的时间是处于相
同的环境中的(母亲的子宫),而且在不同的家庭抚育,并不等于其生长环境就
完全不同,其中完全有可能有很相同的环境因素。

不管采用哪一种方法,都不能只比较个案,而必须对大量的孪生子做调查、
统计。在世界上,已有多项这种调查,其中最大的一项是美国明尼苏答大学的研
究人员负责的,他们共研究了8000多对同卵孪生子和异卵孪生子,包括130多对
在不同的家庭长大的同卵孪生子。他们之所以能找到这么多被分开抚育的同卵孪
生子,得益于美国历史上一个悲惨的时期:上个世纪三、四十年代的经济大萧条
迫使许多贫苦家庭把刚出生的孪生子分开送人抚养。以后很可能再难以有这样的
研究机会。

研究者对孪生子进行了深入具体的面试,以了解其生活环境,对社会、宗教、
哲学问题的看法,并用一系列心理测试判断其职业兴趣、思维能力和性格倾向。
结果表明,同卵孪生子的性格相似程度明显大于异卵孪生子。明尼苏答大学的研
究结果是,一起长大的同卵孪生子的相关性平均为0.46(0表示两个人没有一点
相似之处,1表示两个人完全相同),分开长大的同卵孪生子,这一数字为0.45。
这说明同卵孪生子的性格相关程度,与他们是否在相同还是不同的环境长大无关。
分开长大的异卵孪生子的性格相关程度平均为0.26,大约是同卵孪生子的一半,
这与他们的遗传相似程度是同卵孪生子的一半相符。从同卵孪生子和异卵孪生子
得到的相关性可以用于计算遗传差异与性格差异的相关性。平均来说,大约50%
的性格差异是由于遗传差异导致的,或者说,遗传因素对性格的影响大约占了一
半。遗传学家把这个数字称为遗传率。如果性状差异是完全由遗传差异引起的,
遗传率为1,如果性状差异与遗传差异毫无关系,遗传率为0。其他的类似研究的
结果,所得到的性格遗传率,一般在0.2-0.5之间。

由此可见,遗传决定论和环境决定论都是错误的,遗传因素和环境因素对性
格的影响大约同等重要。两个人的遗传差异越大,环境越不同,性格差异也就会
越大。而两个人的性格相似主要是由于相似的遗传因素引起的,环境的影响很小。
但是我们必须记住,遗传因素和环境因素实际上是无法截然分开的,而是混杂在
一起、交互发生作用的,从这个意义上说,区分影响性格的因素有多少属于遗传
的影响,有多少属于环境的影响,是不可能的。简单地说,遗传、环境,以及经
常被忽视的随机因素,都对人性有重要的影响。

达尔文曾经深刻地指出,那些顽固地坚持遗传决定论、认为一切都是天生注
定的人,实际上是在推卸社会责任:“如果穷人的惨状不是自然法则而是我们的
制度导致的,那么我们的罪过就会很大。”“童话大王”本人的童话作品也曾经
遭受批评,认为它们不适合儿童阅读,会对儿童的生长产生不良影响。这也许可
以解释为什么他明知自己并不了解后天环境的影响有多大,却要断言儿童的性格
基本上是遗传基因决定的。暴力动画片、另类童话是否会对儿童产生不良影响当
然可以讨论,但是不应该因此一概否定儿童的成长会受不良环境的影响。编导、
作家在向儿童推销自己的作品时,还是要多一点社会责任感。

2007.2.28

(《经济观察报》2007.3.5.)

(XYS20070305)

◇◇新语丝(www.xys.org)(xys.dxiong.com)(xys.3322.org)(xys.xlogit.com)◇◇

http://xys.3322.org/xys/netters/Fang-Zhouzi/jingji/gene.txt

Christianism 基督教历史常识

基督教Christian分三种:
东正教Orthodox(From Greek orthodoxos, "of the right opinion")
天主教Catholicism,即罗马天主教
新教Protestantism,也俗称基督教(狭义)

上面这三种和犹太教、伊斯兰教都是信上帝God的,同源于犹太教。

最初,犹太教的人陆续编出了Bible这本书,说上帝对犹太人如何如何好,因为犹太是上帝的“选民”,不是选举的人,而是选中的人,只要信主,死后可以上天堂。书中并预测未来会有救世主降临。
大概公元1年左右,有人宣称救世主出现了,就是耶稣。并且,关于他的书层出不穷,也编入Bible中,称为 New Testament 新约,顺手把以前的Bible叫做旧约Old Testament。这就是基督教。在新约中,上帝不再只关注犹太人,而是愿意普渡众生。所有人只要信主就可以上天堂。这个新约没有门槛,所以很快传播开来了。特别是耶稣只反对不受信用的人,不反抗当时的罗马统治,深得罗马人的喜爱。当然,犹太人反对这个说法。
600年后,阿拉伯半岛麦加城的穆罕默德创办了伊斯兰教。教义古兰经中,耶稣只是29个先知之一,而穆罕默德是最大的且最后的先知。
基督教发展之后,分成东西两派,就是东正教和天主教。都赞美圣母玛丽亚并崇拜上帝。后来天主教中出现了新教,把圣母放到一边,只关心耶稣。所以这个教也称作 “耶稣教”。当时美洲是欧洲人流放犯人的地方,这派中一些教徒在欧洲被欺负得活不下去了,又不想改变信仰,听说海外有块新大陆,就乘五月花May Flower号船偷渡到这里来(1620年),在当地印地安人的帮助之下安了家,所以在收获的季节举办了“感恩节”Thanks Giving.当然,也许还有许多偷渡死掉的,我们就不知道了。
也就是因为先到这里的是一些新教坚贞分子,所以这个教派在美洲传输开来。美国可能有60%的人信仰这个教派。

http://xys.3322.org/forum/db/14.html

2007年1月22日星期一

FireBug 控制台函数说明

原文地址:http://www.joehewitt.com/software/firebug/docs.php
FireBug 是一个非常实用的JavaScript以及DOM查看调试工具,是 Firefox 的一个插件。使用 FireBug 调试 AJAX 应用非常方便,终于可以告别 alert 时代了!

Console Logging 函数

FireBug 为所有 Web 页面提供了一个 console 对象。这个对象有以下函数:

Logging 基础

console.log("message" [,objects]) - 将一个字符串打印到控制台。字符串可以包含任何“String Formatting”小节描述的模式。字符串后面的对象应该用来取代之前字符串中的模式。(译者注:大家用过C里面 printf 吧,效果基本是一样的。)

Logging 等级

通常根据不同的等级来区分Logging的严重程度是很有帮助的。FireBug 提供了4个等级。为了达到视觉分离的效果,这些函数与 log 不同的地方就是它们在被调用的时候会自动包含一个指向代码行数的链接。

console.debug("message" [,objects]) - 记录一个 debug 消息。
console.info("message" [,objects]) - 记录一个信息.
console.warn("message" [,objects]) - 记录一个警告.
console.error("message" [,objects]) - 记录一个错误.

断言

断言是一条确保代码规则的非常好的途径。console 对象包含了一系列各种类型的断言函数,并且允许你编写自己的断言函数。

console.assert(a, "message" [,objects]) - Asserts that an a is true.
console.assertEquals(a, b, "message" [,objects]) - Asserts that a is equal to b.
console.assertNotEquals(a, b, "message" [,objects]) - Asserts that a is not equal to b.
console.assertGreater(a, b, "message" [,objects]) - Asserts that a is greater than b.
console.assertNotGreater(a, b, "message" [,objects]) - Asserts that a is not greater than b.
console.assertLess(a, b, "message" [,objects]) - Asserts that a is less than b.
console.assertNotLess(a, b, "message" [,objects]) - Asserts that a is not less than b.
console.assertContains(a, b, "message" [,objects]) - Asserts that a is in the array b.
console.assertNotContains(a, b, "message" [,objects]) - Asserts that a is not in the array b.
console.assertTrue(a, "message" [,objects]) - Asserts that a is equal to true.
console.assertFalse(a, "message" [,objects]) - Asserts that a is equal to false.
console.assertNull(a, "message" [,objects]) - Asserts that a is equal to null.
console.assertNotNull(a, "message" [,objects]) - Asserts that a is not equal to null.
console.assertUndefined(a, "message" [,objects]) - Asserts that a is equal to undefined.
console.assertNotUndefined(a, "message" [,objects]) - Asserts that a is not equal to undefined.
console.assertInstanceOf(a, b, "message" [,objects]) - Asserts that a is an instance of type b.
console.assertNotInstanceOf(a, b, "message" [,objects]) - Asserts that a is not an instance of type b.
console.assertTypeOf(a, b, "message" [,objects]) - Asserts that the type of a is equal to the string b.
console.assertNotTypeOf(a, b, "message" [,objects]) - Asserts that the type of a is not equal to the string b.

测量(Measurement)

下面的一些函数可以让你方便的测量你的一些代码。

console.trace() - 记录执行点的堆栈信息。
console.time("name") - 根据 name 创建一个唯一的计时器。
console.timeEnd("name") - 根据 name 停止计时器,并且记录消耗的时间,以毫秒为单位。
console.count("name") - 记录该行代码执行的次数。

字符串格式化

所有 console 的 logging 函数都可以通过以下模式格式化字符串:

%s - 将对象格式化为字符串。
%d, %i, %l, %f - 将对象格式化为数字。
%o - 将对象格式化成一个指向 inspector 的超链接。
%1.o, %2.0, etc.. - 将对象格式化成包含自己属性的可交互的表格。
%.o - 将对象格式化成具有自身属性的一个数组。
%x - 将对象格式化成一个可交互的 XML 树形结构。
%1.x, %2.x, etc.. - 将对象格式化成一个可交互的 XML 数型结构,并且展开 n 层节点。

如果你需要一个真实的 % 符号,你可以通过一个转移符号就像这样 "\%"。

命令行函数

内建的命令行函数可以通过以下命令行使用:

$("id") - document.getElementById() 的简写。(译者注:跟 prototype.js 学来的吧?)
$$("css") - 返回一个符合 CSS 选择器的元素数组。
$x("xpath") - 返回一个符合 XPath 选择器的元素数组。
$0 - 返回最近被检查(inspected)的对象。
$1 - 返回最近被检查(inspected)的下一个对象。
$n(5) - 返回最近被检查的第n个对象。
inspect(object) - 将对象显示在 Inspector 中。
dir(object) - 返回一个对象的属性名数组。(译者注:跟 Python 学的?)
clear() - 清除控制台信息。

分类算法:在数据库中存储层次数据

在数据库中存储层次数据


作者:Gijs Van Tulder 翻译:ShiningRay @ NirvanaStudio


无论你要构建自己的论坛,在你的网站上发布消息还是书写自己的cms [1]程序,你都会遇到要在数据库中存储层次数据的情况。同时,除非你使用一种像XML [2]的数据库,否则关系数据库中的表都不是层次结构的,他们只是一个平坦的列表。所以你必须找到一种把层次数据库转化的方法。


存储树形结构是一个很常见的问题,他有好几种解决方案。主要有两种方法:邻接列表模型和改进前序遍历树算法


在本文中,我们将探讨这两种保存层次数据的方法。我将举一个在线食品店树形图的例子。这个食品店通过类别、颜色和品种来组织食品。树形图如下:



本文包含了一些代码的例子来演示如何保存和获取数据。我选择PHP [3]来写例子,因为我常用这个语言,而且很多人也都使用或者知道这个语言。你可以很方便地把它们翻译成你自己用的语言。


邻接列表模型(The Adjacency List Model)

我们要尝试的第一个--也是最优美的--方法称为"邻接列表模型"或称为"递归方法"。它是一个很优雅的方法因为你只需要一个简单的方法来在你的树中进行迭代。在我们的食品店中,邻接列表的表格如下:



如你所见,对每个节点保存一个"父"节点。我们可以看到"Pear [4]"是"Green"的一个子节点,而后者又是"Fruit"的子节点,如此类推。根节点,"Food",则他的父节点没有值。为了简单,我只用了"title"值来标识每个节点。当然,在实际的数据库中,你要使用数字的ID。


显示树


现在我们已经把树放入数据库中了,得写一个显示函数了。这个函数将从根节点开始--没有父节点的节点--同时要显示这个节点所有的子节点。对于这些子节点,函数也要获取并显示这个子节点的子节点。然后,对于他们的子节点,函数还要再显示所有的子节点,然后依次类推。


也许你已经注意到了,这种函数的描述,有一种普遍的模式。我们可以简单地只写一个函数,用来获得特定节点的子节点。这个函数然后要对每个子节点调用自身来再次显示他们的子节点。这就是"递归"机制,因此称这种方法叫"递归方法"。


<?php
// $parent 是我们要查看的子节点的父节点
// $level 会随着我们深入树的结构而不断增加,
// 用来显示一个清晰的缩进格式
function display_children($parent, $level) {
// 获取$parent的全部子节点
$result = mysql_query('SELECT title FROM tree ' . 'WHERE parent="' . $parent . '";');

// 显示每个节点
while ($row = mysql_fetch_array($result)) {
// 缩进并显示他的子节点的标题
echo str_repeat(' ',$level).$row['title']."\n";

// 再次调用这个函数来显着这个子节点的子节点
display_children($row['title'], $level+1);
}
}
?>


要实现整个树,我们只要调用函数时用一个空字符串作为 $parent 和 $level = 0: display_children('',0); 函数返回了我们的食品店的树状图如下:


Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork


注意如果你只想看一个子树,你可以告诉函数从另一个节点开始。例如,要显示"Fruit"子树,你只要 display_children('Fruit',0);


The Path to a Node节点的路径


利用差不多的函数,我们也可以查询某个节点的路径如果你只知道这个节点的名字或者ID。例如,"Cherry"的路径是"Food"> "Fruit">"Red"。要获得这个路径,我们的函数要获得这个路径,这个函数必须从最深的层次开始:"Cheery"。但后查找这个节点的父节点,并添加到路径中。在我们的例子中,这个父节点是"Red"。如果我们知道"Red"是"Cherry"的父节点。


<?php
// $node 是我们要查找路径的那个节点的名字
function get_path($node) {
// 查找这个节点的父节点
$result = mysql_query('SELECT parent FROM tree ' . 'WHERE title="' . $node . '";');
$row = mysql_fetch_array($result);

// 在这个array [5] 中保存数组
$path = array();

// 如果 $node 不是根节点,那么继续
if ($row['parent']!='') {
// $node 的路径的最后一部分是$node父节点的名称
$path[] = $row['parent'];

// 我们要添加这个节点的父节点的路径到现在这个路径
$path = array_merge(get_path($row['parent']), $path);
}

// 返回路径
return $path;
}
?>


这个函数现在返回了指定节点的路径。他把路径作为数组返回,这样我们可以使用print_r(get_path('Cherry')); 来显示,其结果是:


Array
(
[0] => Food
[1] => Fruit
[2] => Red
)


不足


正如我们所见,这确实是一个很好的方法。他很容易理解,同时代码也很简单。但是邻接列表模型的缺点在哪里呢?在大多数编程语言中,他运行很慢,效率很差。这主要是"递归"造成的。我们每次查询节点都要访问数据库。


每次数据库查询都要花费一些时间,这让函数处理庞大的树时会十分慢。


造成这个函数不是太快的第二个原因可能是你使用的语言。不像Lisp这类语言,大多数语言不是针对递归函数设计的。对于每个节点,函数都要调用他自己,产生新的实例。这样,对于一个4层的树,你可能同时要运行4个函数副本。对于每个函数都要占用一块内存并且需要一定的时间初始化,这样处理大树时递归就很慢了。


改进前序遍历树

现在,让我们看另一种存储树的方法。递归可能会很慢,所以我们就尽量不使用递归函数。我们也想尽量减少数据库查询的次数。最好是每次只需要查询一次。


我们先把树按照水平方式摆开。从根节点开始("Food"),然后他的左边写上1。然后按照树的顺序(从上到下)给"Fruit"的左边写上2。这样,你沿着树的边界走啊走(这就是"遍历"),然后同时在每个节点的左边和右边写上数字。最后,我们回到了根节点"Food"在右边写上18。下面是标上了数字的树,同时把遍历的顺序用箭头标出来了。



我们称这些数字为左值和右值(如,"Food"的左值是1,右值是18)。正如你所见,这些数字按时了每个节点之间的关系。因为"Red"有3和6 两个值,所以,它是有拥有1-18值的"Food"节点的后续。同样的,我们可以推断所有左值大于2并且右值小于11的节点,都是有2-11的 "Food"节点的后续。这样,树的结构就通过左值和右值储存下来了。这种数遍整棵树算节点的方法叫做"改进前序遍历树"算法。


在继续前,我们先看看我们的表格里的这些值:



注意单词"left"和"right"在SQL中有特殊的含义。因此,我们只能用"lft"和"rgt"来表示这两个列。(译注--其实Mysql 中可以用"`"来表示,如"`left`",MSSQL中可以用"[]"括出,如"[left]",这样就不会和关键词冲突了。)同样注意这里我们已经不需要"parent"列了。我们只需要使用lft和rgt就可以存储树的结构。


获取树


如果你要通过左值和右值来显示这个树的话,你要首先标识出你要获取的那些节点。例如,如果你想获得"Fruit"子树,你要选择那些左值在2到11的节点。用SQL语句表达:


SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;


这个会返回:



好吧,现在整个树都在一个查询中了。现在就要像前面的递归函数那样显示这个树,我们要加入一个ORDER BY子句在这个查询中。如果你从表中添加和删除行,你的表可能就顺序不对了,我们因此需要按照他们的左值来进行排序。


SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;


就只剩下缩进的问题了。


要显示树状结构,子节点应该比他们的父节点稍微缩进一些。我们可以通过保存一个右值的一个栈。每次你从一个节点的子节点开始时,你把这个节点的右值添加到栈中。你也知道子节点的右值都比父节点的右值小,这样通过比较当前节点和栈中的前一个节点的右值,你可以判断你是不是在显示这个父节点的子节点。当你显示完这个节点,你就要把他的右值从栈中删除。要获得当前节点的层数,只要数一下栈中的元素。


<?php
function display_tree($root) {
// 获得$root节点的左边和右边的值
$result = mysql_query('SELECT lft, rgt FROM tree ' . 'WHERE title="' . $root . '";');
$row = mysql_fetch_array($result);

// 以一个空的$right栈开始
$right = array();

// 现在,获得$root节点的所有后序
$result = mysql_query('SELECT title, lft, rgt FROM tree ' .
'WHERE lft BETWEEN '.$row['lft'].' AND '.
$row['rgt'].' ORDER BY lft ASC;');

// 显示每一行
while ($row = mysql_fetch_array($result)) {
// 检查栈里面有没有元素
if (count($right)>0) {
// 检查我们是否需要从栈中删除一个节点
while ($right[count($right)-1]<$row['rgt']) {
array_pop($right);
}
}

// 显示缩进的节点标题
echo str_repeat(' ',count($right)).$row['title']."\n";

// 把这个节点添加到栈中
$right[] = $row['rgt'];
}
}
?>


如果运行这段代码,你可以获得和上一部分讨论的递归函数一样的结果。而这个函数可能会更快一点:他不采用递归而且只是用了两个查询


节点的路径


有了新的算法,我们还要另找一种新的方法来获得指定节点的路径。这样,我们就需要这个节点的祖先的一个列表。


由于新的表结构,这不需要花太多功夫。你可以看一下,例如,4-5的"Cherry"节点,你会发现祖先的左值都小于4,同时右值都大于5。这样,我们就可以使用下面这个查询:


SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;


注意,就像前面的查询一样,我们必须使用一个ORDER BY子句来对节点排序。这个查询将返回:



+-------+
| title |
+-------+
| Food |
| Fruit |
| Red |
+-------+


我们现在只要把各行连起来,就可以得到"Cherry"的路径了。


有多少个后续节点?How Many Descendants


如果你给我一个节点的左值和右值,我就可以告诉你他有多少个后续节点,只要利用一点点数学知识。


因为每个后续节点依次会对这个节点的右值增加2,所以后续节点的数量可以这样计算:


descendants = (right - left - 1) / 2


利用这个简单的公式,我可以立刻告诉你2-11的"Fruit"节点有4个后续节点,8-9的"Banana"节点只是1个子节点,而不是父节点。


自动化树遍历


现在你对这个表做一些事情,我们应该学习如何自动的建立表了。这是一个不错的练习,首先用一个小的树,我们也需要一个脚本来帮我们完成对节点的计数。


让我们先写一个脚本用来把一个邻接列表转换成前序遍历树表格。


<?php
function rebuild_tree($parent, $left) {
// 这个节点的右值是左值加1
$right = $left+1;

// 获得这个节点的所有子节点
$result = mysql_query('SELECT title FROM tree '.
'WHERE parent="'.$parent.'";');

while ($row = mysql_fetch_array($result)) {
// 对当前节点的每个子节点递归执行这个函数
// $right 是当前的右值,它会被rebuild_tree函数增加
$right = rebuild_tree($row['title'], $right);
}

// 我们得到了左值,同时现在我们已经处理这个节点我们知道右值的子节点
mysql_query('UPDATE tree SET lft='.$left.', rgt='.
$right.' WHERE title="'.$parent.'";');

// 返回该节点的右值+1
return $right+1;
}
?>


这是一个递归函数。你要从rebuild_tree('Food',1); 开始,这个函数就会获取所有的"Food"节点的子节点。


如果没有子节点,他就直接设置它的左值和右值。左值已经给出了,1,右值则是左值加1。如果有子节点,函数重复并且返回最后一个右值。这个右值用来作为"Food"的右值。


递归让这个函数有点复杂难于理解。然而,这个函数确实得到了同样的结果。他沿着树走,添加每一个他看见的节点。你运行了这个函数之后,你会发现左值和右值和预期的是一样的(一个快速检验的方法:根节点的右值应该是节点数量的两倍)。


添加一个节点


我们如何给这棵树添加一个节点?有两种方式:在表中保留"parent"列并且重新运行rebuild_tree() 函数--一个很简单但却不是很优雅的函数;或者你可以更新所有新节点右边的节点的左值和右值。


第一个想法比较简单。你使用邻接列表方法来更新,同时使用改进前序遍历树来查询。如果你想添加一个新的节点,你只需要把节点插入表格,并且设置好parent列。然后,你只需要重新运行rebuild_tree() 函数。这做起来很简单,但是对大的树效率不高。


第二种添加和删除节点的方法是更新新节点右边的所有节点。让我们看一下例子。我们要添加一种新的水果--"Strawberry",作为"Red" 的最后一个子节点。首先,我们要腾出一个空间。"Red"的右值要从6变成8,7-10的"Yellow"节点要变成9-12,如此类推。更新"Red" 节点意味着我们要把所有左值和右值大于5的节点加上2。


我们用一下查询:


UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;


现在我们可以添加一个新的节点"Strawberry"来填补这个新的空间。这个节点左值为6右值为7。


INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';


如果我们运行display_tree() 函数,我们将发现我们新的"Strawberry"节点已经成功地插入了树中:


Food
Fruit
Red
Cherry
Strawberry
Yellow
Banana
Meat
Beef
Pork


缺点


首先,改进前序遍历树算法看上去很难理解。它当然没有邻接列表方法简单。然而,一旦你习惯了左值和右值这两个属性,他就会变得清晰起来,你可以用这个技术来完成临街列表能完成的所有事情,同时改进前序遍历树算法更快。当然,更新树需要很多查询,要慢一点,但是取得节点却可以只用一个查询。


总结

你现在已经对两种在数据库存储树方式熟悉了吧。虽然在我这儿改进前序遍历树算法性能更好,但是也许在你特殊的情况下邻接列表方法可能表现更好一些。这个就留给你自己决定了


最后一点:就像我已经说得我部推荐你使用节点的标题来引用这个节点。你应该遵循数据库标准化的基本规则。我没有使用数字标识是因为用了之后例子就比较难读。


进一步阅读


数据库指导 Joe Celko写的更多关于SQL数据库中的树的问题: http://searchdatabase.techtarget.com/tip/1,289483,sid13_gci537290,00.html [6]


另外两种处理层次数据的方法: http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html [7]


Xindice, "本地XML数据库": http://xml.apache.org/xindice/ [8]


递归的一个解释: http://www.strath.ac.uk/IT/Docs/Ccourse/subsection3_9_5.html [9]


[1] /glossary.php?q=C#term_28
[2] /glossary.php?q=X#term_3
[3] /glossary.php?q=P#term_1
[4] /glossary.php?q=P#term_50
[5] /glossary.php?q=%23#term_72
[6] http://searchdatabase.techtarget.com/tip/1,289483,sid13_gci537290,00.html
[7] http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html
[8] http://xml.apache.org/xindice/
[9] http://www.strath.ac.uk/IT/Docs/Ccourse/subsection3_9_5.html

Zend framwork Components Roadmap

Components Roadmap


Here you will find an overview of the direction of framework development with respect to upcoming releases and affected framework components.


Zend Framework 1.0.0 Release Candidate (RC1)

We are currently targeting development in many areas for a 1.0.0 release candidate, and these are outlined below by components grouped by purpose. View the outstanding issues in Zend Framework

Authentication & Authorization

  • Zend_Acl
  • Zend_Authentication
  • Zend_Session

Core Infrastructure

  • Zend_Cache, Zend_Config, Zend_Console_Getopt, Zend_Filter, Zend_Log, Zend_Memory
  • Zend_Registry, Zend_Validate

Databases

  • Zend_Db
  • Zend_Db_Table
  • Zend_Db_Xml

Documentation

  • Improved correctness, readability, and more examples
  • Additional coverage by translation teams

Internationalization (i18n) & Localization (l10n)

  • Zend_Locale
  • Zend_Date, Zend_Calendar
  • Zend_Translate
  • Zend_Currency, Zend_Measure

Mail, Formats, & Search

  • Zend_Json, Zend_Pdf
  • Zend_Mail, Zend_Mime
  • Zend_Search_Lucene

Model-View-Controller (MVC)

  • Zend_Controller, Zend_Controller_Action, Zend_Controller_Dispatcher, Zend_Controller_Plugin, Zend_Controller_RewriteRouter, Zend_View
  • Zend_Http_Request, Zend_Http_Response

Web & Web Services

  • Consuming services: Zend_Feed, Zend_Rest_Client, Zend_Service, Zend_XmlRpc_Client, Zend_Gdata, Zend_Http_Client
  • Exposing services: Zend_Http_Server, Zend_Rest_Server, Zend_Server_Documentor, Zend_Server_Reflection, Zend_Soap_Server, Zend_XmlRpc_Server
  • Zend_Uri