十一月, 2006 | iJohn.org

Archive for 十一月, 2006

7th
十一月 2006

Adobe的AJAX框架–Spry
爱因万江斯坦@2006年11月07日 00:33 Post in Web开发 No Comments »

最近看完了Adobe的AJAX框架Spry的所有文档和Demo,觉得这东西挺有意思的,在这里介绍给大家。
Spry框架的开发人员是来自于DreamWeaver开发组,他们把Spry框架做为DreamWeaver的一个完美补充为设计者和开发者提供对AJAX技术的支持。Spry框架是一个轻量级的AJAX框架,它的代码和标签十分的简洁和优雅,以保证让用户能便捷的使用,并不会为过繁杂的标签所惑。

Spry框架的官方网址:
http://labs.adobe.com/technologies/spry
在这里你能找到最新的文档和下载最新的Spry版本,目前版本是预览版1.3_08-11。
大家可以先在下面的看到Spry的示例和Demo:
http://labs.adobe.com/technologies/spry/samples/
http://labs.adobe.com/technologies/spry/demos/

 

Spry框架其实就是一个客户端的JavaScript类库,包含了一组JavaScript文件,CSS,图片文件,通过官方的框架结构图,我们能看出Spry框架的核心是四部分:XML数据器(XML Data Sets),动态区域(Dynamic Regions),装饰器库(Widgets)和变化效果库(Transition Effects)。

我们可以看出,Spry框架接收的数据格式只是XML数据格式。

一,XML数据器(XML Data Sets)
XML数据器是一个提供了从XML文档中载入和管理数据的JavaScript对象。它是Spry框架中处理XML格式数据的一个JavaScript功能实现。通过它,我们可以从XML中直接得到转换成表格数据格式的行和列的值,其实就是数组。它封装了获取XMLhttpRequest的方法,和发送并接收数据等一系列获取数据的方法。
要创建一个XML数据器,你必须在你的HTML文件中加入两行引入JavaScript文件的代码:

<script type=”text/javascript” src=”../../includes/xpath.js”></script>
<script type=”text/javascript” src=”../../includes/SpryData.js”></script>

上面引入的是Spry框架的核心js文件之一。”xpath.js”是Google基于XPath 1.0标准的JavaScript功能实现。你如果想获得更多的关于它的信息,可以访问Google的开源项目 google-ajaxslt project page .
”SpryData.js”则包含了定义XML数据器和动态区域的代码。
构造XML数据器就好像新建一个类一样,用”new”关键字即可:
<script type=”text/javascript”>
var dsPhotos = new Spry.Data.XMLDataSet(”/photos.php?galleryid=2000″, “/gallery/photos/photo”);
</script>
Spry框架为XML数据器提供了一些有特色的功能:如数据排序,数据过滤,按指定时间间隔自动更新,并引入了观察者通知模式以支持事件的触发。
关于XML数据器更多资料,大家可以参考http://labs.adobe.com/technologies/spry/articles/data_set_overview/,这一部分笔者已经翻译完成了,但英文原文其实写的通俗易懂,如果对一些名词翻译的不准确反倒会误导了大家,所以还是不贴出来了,大家可以参考官方英文文档。

二,动态区域(Dynamic Regions)
一旦你建立了XML数据器,你就可以在动态区域中去显示这个数据器的数据了。
创建动态区域块很简单,只要在html标签的相应位置加上”spry:region”属性就可以了,Spry框架就会知道这一块是被标识成动态区域了。
在动态区域,你可以有条件的选择要输出的数据,也可用循环输出。
动态区域另一个特点就是,它分为master和detail两个区域类型。
如下面的Demo截图:

master区域的数据改变会使detail区域的数据相应发生改变

两者都注册成XML数据器的观察者

当master区域的数据变化时,触发detail区域的响应事件,从面达到更新相应数据。
大家可参考http://labs.adobe.com/technologies/spry/samples/DataSetMasterDetailSample.html所示的功能。
这只是动态区域简单的示例,复杂的情况可能会有多个XML数据器与多个动态区域相互关联触发。

三,装饰器库(Widgets)
一个装饰器是由一组HTML,CSS,JavaScript封装成的高级UI。最常见的装饰器有可折叠的菜单,树型菜单和选项table面板等。这些对象都比较难于创建,需要一些更高级的编程经验。Spry的开发组在创建装饰器这一概念就是希望开发者们能相互协作,共享各自的设计,把这些高级界面元素用在自己的页面上。
Spry框架下的装饰器是易于编辑的。这种模型非常适合于设计者和编辑人员:要改变外观,只要改变CSS就可以了,要增加一个可折叠菜单只要copy和paste一个代码块就够了。
如,你能看懂的这段代码是创建了一个可折叠菜单吗?
<div id=”Acc1″ >
<div>
<div>Panel Header  1</div>
<div>Panel  1 Content </div>
</div>
<div>
<div>Panel Header  2</div>
<div>Panel  2 Content</div>
</div>
<div>
<div>Panel Header  3</div>
<div>Panel  3 Content</div>
</div>
</div>
<script>
var acc1 = new  Hanzo.Widget.Accordion(”Acc1″);
</script>
这段代码是非常简洁清晰的,没有什么繁杂的标签,这样设计是为了易于阅读。
关于这个例子,可以参考http://labs.adobe.com/technologies/spry/samples/accordion/AccordionSample.html

四,变化效果库(Transition Effects)
Spry框架的变化效果库都存于SpryEffects.js文件中,是基于JavaScript的一些动态变化效果,如,淡出,改变形状等。
Spry框架在设计时,曾考虑直接用第三方的效果库,如Script.aculo.us,但后来开发小组觉得要保证框架代码和标签的一致性,还是选择了自已开发,但是也基本上是以Script.aculo.us为原型进行设计,因为Script.aculo.us 本身就是一个非常优秀的变化效果库框架。
由于Spry框架现在只是预览版,所以目前只支持七种变换:
Appear/Fade Makes an element appear or fade away
Highlight Flashes a color as the background of an element
BlindUp/BlindDown Simulates a window blind, up or down, where the contents of the affected elements stay in place
SlideUp/SlideDown  Simulates a window blind, where the contents of the affected element scroll accordingly
Grow/Shrink Increases/reduces the size of the element
Shake Moves the element slightly to the left, then to the right, repeatedly
Squish Reduces the element to its top-left corner and disappears

可能到这大家对Spry框架已经有了大致的了解,其实这个东西已经足够我们的大多数应用的开发了,笔者也十分期待着正式版能早日放出,并打算在自己现在的项目中试一试了。

6th
十一月 2006

排序研究一
爱因万江斯坦@2006年11月06日 00:54 Post in 性能 No Comments »

排序是数据结构中重要的一个部分,也是在实际开发中最易遇到的问题之一,当然了,你也可以不考虑这些排序的算法,直接把要排序的数据insert到数据库中,用数据库的order by 再select一下,也能产生排序结果,不过,开发一个好的系统,性能同样很重要。

在一堆数据中,是比较的执行耗时多,还是复制交换的执行耗时比较多,大量数据比较时,是否会有内存限制等等,在综合这些因素后,我们选择适当的排序算法,常常会让系统性能提升数倍,当然了,如果你的系统中没有任何需要数据排序的,那就不考虑了。

所有的排序算法,都是在大数据量时才会显示出其运行差别,所以,在下面的讨论中,大家了解各特性,按需选用。(如果你觉得往数据库里插入数据,再带着order by 去select执行耗时最小,那就使用我提的这个方法吧)

注:以下的排序,均以int或long型来比较,其实,比较的元素可以是除这以外的任何对象,要对象实现比较功能,可参考jdk的compareable接口,这个后面再讨论。

所有的问题,都会有一个简单的解决方法,但它往往并不是最佳的方法。

一,冒泡排序

public void bubbleSort(int[] array) {
  int temp;
  for(int i=0;i<array.length-1;i++){
   for(int j=i+1;j<array.length;j++){
    if (array[i]>array[j]){
     temp=array[i];
     array[i]=array[j];
     array[j]=temp;
    }
   }
  }

这个是最简单,最易理解的排序算法。从队列的最左边开始,比较0号位置和1号位置的元素,如果左边的元素(0号)大,就让两个元素交换;如果右边的元素大,就什么也不做。然后右移一个位置比较1号位置和2号位置;沿着这个队列照这样比较下去,一直比较到队列的最右端,虽然没有把所有元素排好充,但是最大的那个元素已经在最右边了,也就像是在水底下冒泡一样,冒上来了。然后再从左边的1号开始,再循环前面的操作。。。。

可以看出,冒泡排序运行需要O(N^2)时间级别,其速度是很慢的,比较次数:N*(N-1)/2,交换次数最坏的情况也是:N*(N-1)/2。

2,选择排序

选择排序与冒泡排序有点相似,但是,选择排序对冒泡排序做了些许优化:减少元素交换的次数。
从下面的代码中,我们可以看出,通过每一次循环,标识出当前最小的元素,再做交换。

选择排序和冒泡排序执行了相同的比较次数:N*(N-1)/2,对于100个数据项就是要4950次比较,但选择排序只进行了不到100次交换。当N值很大时,比较的次数是主要的。所以,当N比较小,特别是如果交换的性能消耗比比较的性能消耗大得多时,用选择排序是相当快的。

public void selectionSort(int[] array)
      {
      int out, in, min,nElems=array.length;

      for(out=0; out<nElems-1; out++)   // 外层循环
         {
         min = out;                     // 最小值
         for(in=out+1; in<nElems; in++) // 内层循环
            if(a[in] < a[min] )         // 如果有比最小值还小的
                min = in;               // 得到新最小值
         swap(out, min);                // 交换
         }  // end for(out)
      }  // end selectionSort()

 private void swap(int one, int two)
      {
      long temp = a[one];
      a[one] = a[two];
      a[two] = temp;
      }

三,插入排序

插入排序的特点是局部有序,通过循环,在(局部)有序组中的适当位置插入元素进行排序。然而要做到这一点,就需要把部分已排序的队员右移以让出空间。当把最后一个要比较的元素移位之后,这个移动的过程就结束了。

public void insertionSort(int a[]){
      int in, out,nElems=a.length;

      for(out=1; out<nElems; out++) {    // 外层循环
          long temp = a[out];            // 先把要插入有序队列中的元素取出
         in = out;                      // 要从这个元素的左边开始依次比较了
         while(in>0 && a[in-1] >= temp){ // 比较条件,
            a[in] = a[in-1];            // 比temp大的元素,就要右移了
            --in;                       // 再比较左边的
            }
         a[in] = temp;                  // 找到合适的位置了
         }  // end for
      }  // end insertionSort()

在外层的for循环中,out变量从1开始,向右移动。它标记了未排序部分的最左端的数据。而在内层的while循环中,in变量从out变量开始,向左移动,直到temp变量小于in所指的数组数据项,或者它已经不能再往左移动了。while循环的每一趟都向右移动了一个已排序的数据项。

这个算法需要多少次比较和复制呢?在第一趟排序中,它最多比较一次,在第二趟中最多比较两次,依此类推了,最后一趟最多,N-1次.所以:

1+2+3+……+N-1=N*(N-1)/2

然而,在每一趟排序发现插入点之前,平均只有全体数据项的一半真的进行了比较,所以实际上大约是N*(N-1)/4 次 (这个值不是精确值,只是一个概率的估算值,学过数理统计的朋友就不要太过计较了)

复制的次数大致等于比较的次数,由于一次复制与一次交换的时间耗费不同,所以相对于随机数据,这个算法比冒泡排序快一倍,比选择排序略快。

如果数据基本有序,插入排序几乎只需要O(N)的时间;然后对于逆序排列的数据,每次比较和移动都会执行,所以这时插入排序并不比冒泡快。

大家在选择算法时,要注意了,在事先估算待排序数据的状况下,再选择相应的算法。

四,有序链表排序

这里存储数据的方式就不是前面讨论的用数组来存储了,而是用链表这一个数据结构。

有序链表排序是一种高效的排序机制。所设有一个无序数组,如果从这个数组中取出数据,然后一个一个地插入有序链表,它们自动地按序排列,把它们从链表中删除重新放入数组,那么数组就会排好序了。

建立链表类Link.java:

class Link
   {
   public long dData;                  

   public Link next;
   public Link(long dd)
      { dData = dd; }
   }

建立有序链表SortedList.java

class SortedList
   {
   private Link first;
   public SortedList()
      { first = null; }
   public SortedList(Link[] linkArr)  

      {                               

      first = null;
      for(int j=0; j<linkArr.length; j++)
         insert( linkArr[j] );             

      }
   public void insert(Link k)     

      {
      Link previous = null;
      Link current = first;

      while(current != null && k.dData > current.dData)
         {                             

         previous = current;
         current = current.next;
         }
      if(previous==null)
         first = k;                    

      else
         previous.next = k;            

      k.next = current;
      }  // end insert()
   public Link remove()           

      {
      Link temp = first;             

      first = first.next;             

      return temp;                     

      }
   }

测试类ListInsertionSortApp.java:

class ListInsertionSortApp
   {
   public static void main(String[] args)
      {
      int size = 10;
                                 // 建立一个随机数组
      Link[] linkArray = new Link[size];

      for(int j=0; j<size; j++)  

         {
         int n = (int)(java.lang.Math.random()*99);
         Link newLink = new Link(n);  // 建立链表

         linkArray[j] = newLink;      

         }

      System.out.print("Unsorted array: ");
      for(int j=0; j<size; j++)
         System.out.print( linkArray[j].dData + " " );
      System.out.println("");

      SortedList theSortedList = new SortedList(linkArray);

      for(int j=0; j<size; j++)
         linkArray[j] = theSortedList.remove();

      System.out.print("Sorted Array:   ");
      for(int j=0; j<size; j++)
         System.out.print(linkArray[j].dData + " ");
      System.out.println("");
      } 

   }

这种排序方式总体上比在数组中用常用的插入排序效率更高一些,因为这种方式进行的复制次数少一些,但它仍然是一个时间级为O(N^2)的过程,因为在有序链表中每插入一个新的链结点,平均要与一半已存在数据进行比较。如果插入N个新数据,就进行了N*N/4次比较。每一个链结点只进行两次复制:一次从数组到链表,一次从链表到数组。在数组中进行插入排序需要N*N次移动,相比之下,2*N次移动更好。

注:以上提供的算法出自《Data Structures & Algorithms in Java》by Robert Lafore Sams © 1998

2nd
十一月 2006

《黑客帝国》的故事(转自央视第10放映室)
爱因万江斯坦@2006年11月02日 09:44 Post in 一千零一夜 No Comments »

什么是Matrix(矩阵)? 
Matrix的本意是子宫、母体、孕育生命的地方,同时,在数学名词中,矩阵用来表示统计数据等方面的各种有关联的数据。这个定义很好地解释了Matrix代码制造世界的数学逻辑基础。在电影中,Matrix不仅是一个虚拟程序,也是一个实际存在的地方。在这里,人类的身体被放在一个盛满营养液的器皿中,身上插满了各种插头以接受电脑系统的感官刺激信号。人类就依靠这些信号,生活在一个完全虚拟的电脑幻景中。机器用这样的方式占领了人类的思维空间,用人类的身体作为电池以维持自己的运行。

在电影中,Matrix是一套复杂的模拟系统程序,它是由具有人工智能的机器建立的,模拟了人类以前的世界,用以控制人类。在Matrix中出现的人物,都可以看做是具有人类意识特征的程序。这些程序根据所附着的载体不同有三类:一类是附着在生物载体上的,就是在矩阵中生活的普通人;一类是附着在电脑芯片上的,就是具有人工智能的机器;这些载体通过硬件与Matrix连接。而另一类则是自由程序,它没有载体,诸如再特工、先知、建筑师、梅罗文加、火车人等。

Matrix是一个巨大的网络,连接着无数人的意识,系统分配给他们不同的角色,就象电脑游戏中的角色扮演游戏一样,只是他们没有选择角色的权利和意识。人类通过这种联网的虚拟生活来维持自身的生存需要,但Matrix中的智能程序,也就是先知的角色,发现在系统中有1%的人由于自主意识过强,不能兼容系统分配的角色,如果对他们不进行控制就会导致系统的不稳定,进而导致系统崩溃。因此编写Matrix的智能程序,也就是建筑师就制造了“救世主”,让他有部分自主意识,并成为觉醒人类的领袖,带领他们建造了锡安。

什么是Zion(锡安)?

“Zion(锡安)”一词在《圣经》中,是所罗门王建造圣殿所坐落的山,位于圣城耶路撒冷。而在犹太教中,“锡安”代表着上帝的荣耀,是神的救赎来临的标志。当大地被毁灭后,人类将在锡安接受最后的审判。

在电影中,“锡安”是指那些从Matrix中被解放的人类所栖居的家园,位于地球深处,依靠地热作为能源,成为人类对抗Matrix和机器之城的最后基地。电影用这个名字来命名人类的最后家园,象征着这里是正义得到彰显的地方,是对抗机器的圣地。

锡安的议会结构很象古罗马的元老院,是兼有立法和管理权的国家机构,制定一切法律和制度,通过执行官进行管理。

锡安是由占据Matrix 人口总数的1%的觉醒者构成的,其中主要是以有色人种为主,尤其是议会里的议员和战舰的船长等高层人员,都是黑人。而电影中之所以这样设置锡安的人口,主要是为了体现多民族的融合与宽容,因为这是一个讲述人类对抗共同敌人的故事,人类自己首先要团结,要实现大同的理想。而从另一个角度讲,在西方主流科幻电影中,破败的未来以及非白人的世界,一直是最重要的两个视觉元素。沃卓斯基兄弟作为科幻片导演,自然会在电影中加入这两个西方电影观众耳熟能详的视觉元素。

Matrix中的救世主

Matrix是一个建立在数学基础上的严整系统,一切都是有规律的,包括特工们和尼奥的超能力在内,都是包含在这个系统中的。而尼奥这个“救世主”的产生,则和数学中的哥德尔命题有关。奥地利数学家哥德尔在1931年发表了题为《论<数学原理>及有关系统的形式不可判定命题》的论文,其中提出这样一个观点,在任何数学系统中,只要其能包含整数的算术,这个系统的相容性就不可能通过几个基础学派所采用的逻辑原理建立。简单地说,就是在任何系统中,总有些真理是游离于逻辑之外的,这些真理就叫做歌德尔命题。

在Matrix中,尼奥就是在Matrix这个严整系统中不能被数学推得的歌德尔命题,不符合系统的规律。(建筑师对尼奥的谈话中涉及部分)当尼奥重生后,他就担负起系统所有的扰动,所有的规则在他面前都变得透明,因此他能够看到系统中别人所看不到的东西。先知叫尼奥回到源头去终止灾难,在数学逻辑中就是将歌德尔命题变成整个系统的一部分,当作系统的一个变量,从而消除整个系统的不确定性。如果尼奥当初选择了毁灭锡安的门,他所携带的代码将反馈给系统,将系统的稳定性提高到一个新阶段。而这个选择的前提则是系统中没有斯密斯这个狂人。但从数学的角度上来说,这样的稳定也是暂时的,不是对系统的彻底修正,新的系统还是会产生自己的歌德尔命题,从而继续这个轮回。这就是为什么在尼奥之前会有六任救世主的原因。

按照建筑师最初编写救世主时的任务,救世主的使命就是在锡安运行一段时间后,将锡安的代码带回到Matrix的源程序进行重装,同时机器摧毁锡安,完成Matrix系统的升级。之后救世主将按照初始设置,带领16女7男返回真实世界,再开始重建锡安,等待下一代的救世主。而尼奥与前任们不同的是,建筑师在他的意识中编写了关于爱的编码,这本来是系统处于不断升级的需要,也是考察人类反应的新实验。但这个关于爱的编码,不但导致了尼奥在第二集中做出违背程序设置的选择,而且在第三集中将“爱情”升华为“博爱”,从而最后终结了战争,终止了矩阵和锡安之间的循环。

特工史密斯 
电影中的特工史密斯实际上就是矩阵这个程序世界中的杀毒程序,他们在矩阵中是没有身体的,由于他们是杀毒程序,所以他们被矩阵赋予了超越常人的能力。在矩阵中他们具有改写人类角色程序的能力,所以可以不断借用他人身体。

尼奥最后可以战胜特工,实际上是因为他复活后具有了识别矩阵代码的能力,并可以轻松改写这些代码,所以特工就不能再利用超能力战胜他了。

特工史密斯被尼奥消灭后,因为在他被尼奥消灭前明明是他先杀死了尼奥,所以这就导致了一个逻辑错误。因为这种程序上的逻辑运算错误,导致了特工史密斯不但拒绝被系统删除,而且由杀毒程序变成了病毒,最后危害到了整个矩阵世界。

因为这个逻辑错误是由尼奥导致的,所以特工史密斯就变成了和尼奥相对的负极。最后尼奥选择了让史密斯感染自己,在复制过程中矩阵掌握了史密斯的代码,最后才得以将他们两个同时删除,使矩阵回到了平衡。

尼奥(Neo)/托马斯·安德森(Thomas Anderson)

在希伯来语中,托马斯的意思是双生。这象征着尼奥平时的双重身份:一个是程序员托马斯·安德森,一个是黑客尼奥。而安德森在希伯来语中的含义是“人之子”,这正是耶稣的身份。

组成Neo(尼奥)的这三个字母掉转顺序后就可以组成“one”,表示他就是那个拯救人类的救世主“The One”。而“基督”一词在希伯来语中的本意就是“被指定的那个人”——The One。

墨菲斯(Morpheus)

在希腊神话中,墨菲斯是梦神,拥有改变梦境的能力。在电影中,墨菲斯是把人们从梦境般的虚幻世界中唤醒的指路人。

墨菲斯指挥的飞船是“尼布甲尼撒”号,这是用巴比伦的智慧之神的名字命名的。而在《圣经》中,尼布甲尼撒是巴比伦的国王,曾找人解梦。而在电影中,墨菲斯等人乘坐“尼布甲尼撒”号飞船去找先知诠释什么是真实。

崔尼蒂(Trinity)

Trinity的意思是“三位一体”,在基督教中,“三位一体”指得是圣父、圣子、圣灵。而在现代心理学的奠基之作《梦的解析》一书中,“三位一体”指代了女性意识,她能够进入神秘的领地和完美的境界。

先知(Oracle)

Oracle的希腊语本意是解惑、传递解释神的预言,可以是人、地方,也可以是物品。这些预言通常是模糊的,是现实的一种扭曲,所以能解释的人一定要很有智慧,但即使是他们也不一定能保证预言正确。先知的目的是用自己看到的模糊景象指导信徒,但不能帮他们做决定,决定本身完全取决于人们主观的意愿。

史密斯(Smith)

英文中的Smith意思就是铁匠,而他的车牌号是IS 5416,这都暗含着宗教含义。在《圣经·以塞亚书》第54章16节里说到:吹嘘炭火,打造合用的器械的铁匠是我所造;残害人、行毁灭的也是我所造。这正暗指特工史密斯在矩阵系统中的作用——消灭一切危害矩阵运行的异常程序。

梅罗纹加(Merovingian)

梅罗纹加是法国封建社会中六个王朝的第一个,欧洲中世纪的黑暗历史正是从梅罗纹加王朝开始的,经历六朝,正符合电影中矩阵曾经有六代版本的故事。在电影中,梅罗纹加是一个曾经很有力量的人,而且他喜欢说法语,居住在法国式的城堡中。

法国的梅罗纹加王朝也是欧洲浪漫神话的发源时期,而这些神话的核心人物则是“堕落天使”,他们因为背叛上帝被赶出天堂,撒旦正是这些堕落天使的首领。这也正符合电影中梅罗纹加在矩阵中的身份——他是所有背叛矩阵的程序人的首领,利用自己的能力来对抗矩阵。

塞拉夫(Seraph)

塞拉夫是先知的守卫者,这个名字在欧洲中世纪神话中是天使9个等级里级别最高的六翼天使。当尼奥在矩阵中第一次见到他的时候,他的代码呈现了与众不同的金色。塞拉夫在矩阵中的作用相当于保护先知不受侵害的防火墙,非常有力量,曾经打败过史密斯。

卡玛拉(Kamala)

卡玛拉在梵语中的意思是“莲华”,代表的是清净。在佛教中有句真言就叫做“卡玛拉”。在影片中,卡玛拉是一个由程序自行产生出的新程序,是矩阵世界中第一个由人工智能培养出来的智能程序。在影片结尾暗示了她具有改变矩阵世界代码的能力。