今日点击： 10
This page validates as XHTML 1.0, and will look much better in a browser that supports web standards, but it is accessible to any browser or Internet device. It was created using techniques detailed at glish.com/css/.
星期五 2007年09月14日 在Java SE 5.0中，引入了一些新的Collection API，PriorityQueue就是其中的一个。今天由于机缘巧合，花了一个小时看了一下这个类的内部实现，代码很有点意思，所以写下来跟大家分享一下。从中也可以看到，Java源代码的OpenSource对于我们程序员编程带来了多大的帮助。
最初的起因是我阅读文档不仔细，使用PriorityQueue出现了问题。我刚开始只是把它当作一个一般的FIFO实现来使用，结果发现poll()的结果跟我想象的不一样，后来才发现，PriorityQueue会对入队的元素进行排序，所以在队列顶端的总是最小的元素。
有趣的是，我在仔细阅读文档以前，曾经用调试器察看了我的PriorityQueue，所以即便我后来阅读文档知道了它的正确行为，却发现内部实现似乎跟我想象的不同。把问题简化成下面的代码：
| public static void main(String[] args) { PriorityQueue<String> pq = new PriorityQueue<String>(); pq.add("dog"); pq.add("apple"); pq.add("fox"); pq.add("easy"); pq.add("boy"); while (!pq.isEmpty()) { for (String s : pq) { System.out.print(s + " "); } System.out.println(); System.out.println("pq.poll(): " + pq.poll()); } } |
输出的结果如下：
apple boy fox easy dog
pq.poll(): apple
boy dog fox easy
pq.poll(): boy
dog easy fox
pq.poll(): dog
easy fox
pq.poll(): easy
fox
pq.poll(): fox
可以看到，虽然PriorityQueue保持了队列顶部元素总是最小，但内部的其它元素的顺序却随着元素的减少始终处于变化之中。由于没有总结出有效的规律，我决定察看源代码来一探究竟。从Netbeans中非常方便的连接到PriorityQueue的add函数实现，最终跟踪到函数private void siftUpComparable(int k, E x)，定义如下：
| private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key; } |
相对于add的操作，该函数的入口参数k是指新加入元素的下标，而x就是新加入的元素。乍一看，这个函数的实现比较令人费解，尤其是parent的定义。通过进一步分析了解到，PriorityQueue内部成员数组queue其实是实现了一个二叉树的数据结构，这棵二叉树的根节点是queue[0]，左子节点是queue[1]，右子节点是queue[2]，而queue[3]又是queue[1]的左子节点，依此类推，给定元素queue[i]，该节点的父节点是queue[(i-1)/2]。因此parent变量就是对应于下标为k的节点的父节点。
弄清楚了这个用数组表示的二叉树，就可以理解上面的代码中while循环进行的工作是，当欲加入的元素小于其父节点时，就将两个节点的位置交换。这个算法保证了如果只执行add操作，那么queue这个二叉树是有序的：该二叉树中的任意一个节点都小于以该节点为根节点的子数中的任意其它节点。这也就保证了queue[0]，即队顶元素总是所有元素中最小的。
需要注意的是，这种算法无法保证不同子树上的两个节点之间的大小关系。举例来说，queue[3]一定会小于queue[7]，但是未必会小于queue[9]，因为queue[9]不在以queue[3]为根节点的子树上。
弄清楚了add的操作，那么当队列中的元素有变化的时候，对应的数组queue又该如何变化呢？察看函数poll()，最终追中到函数private E removeAt(int i)，代码如下：
| private E removeAt(int i) { assert i >= 0 && i < size; modCount++; int s = --size; if (s == i) // removed last element queue[i] = null; else { E moved = (E) queue[s]; queue[s] = null; siftDown(i, moved); if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null; } |
这个函数的实现方法是，将队尾元素取出，插入到位置i，替代被删除的元素，然后做相应的调整，保证二叉树的有序，即任意节点都是以它为根节点的子树中的最小节点。进一步的代码就留给有兴趣的读者自行分析，要说明的是，对于queue这样的二叉树结构有一个特性，即如果数组的长度为length，那么所有下标大于length/2的节点都是叶子节点，其它的节点都有子节点。
总结：可以看到这种算法的实现，充分利用了树结构在搜索操作时的优势，效率又高于维护一个全部有序的队列。
星期二 2007年07月10日 好久好久没有在这里写Blog了。今天重新开始吧，另外就是以后我的Blog大多数都会采用中文来记录。
开篇先来回忆一下今年的JavaONE感受吧。
今年是我第二年的JavaONE，不再有去年头一次参加的激动心情，最大的不同是今年拿到了Speaker Pass，除掉要做两个Lab的Proctor以外，四天从早上九点到晚上10点，几乎所有的时间都在听各种讲座。
相对于去年是Java EE 5.0和Java SE 6发布的大年，今年没有重量级的产品Release。今年的新鲜技术从我的理解上看大概有如下几点：Java FX Mobile/Script，Java TV session, Realtime Java的一些进展。
Java FX Mobile和Java FX Script完全是两个不相干的东西。Java FX Mobile是一个SmartPhone整个软件Stack的参考实现，具体包含了一个裁减过的Linux内核，一个不晚于Java SE 1.3的JVM和其它一些标准的应用程序。今年Sun做了一个不很起眼的并购：SavaJE。去年JavaONE上，SavaJE Phone风光无限，300多美元的纯Java Smart Phone在会场上即供不应求。而SavaJE就是一个智能手机上的Java SE实现(我最初以为是CDC实现，后证实不确)。去年声称的是操作系统也是拿Java写的，引起了我的兴趣，不过当时展台的工作人员没有一个人可以回答我如何用Java实现设备驱动的问题。不知什么原因，去年一年并没有带来想象中SavaJE手机的大红大紫，最终被Sun收购，作为Java FX Mobile解决方案的最主要部分。
Java FX Script是另外一种脚本语言，主要用来做界面相关的各种程序，目前为止，Java FX Script程序还只能够通过Java Web Start的方式部署，将来也许可以像Applet和Flash那样直接在网页上内嵌。Java FX Script底层是用Java代码(主要是Swing和Java2D)实现的。不似Swing采用的是Event/Listener机制，和较为严格的MVC，Java FX Script用更等级层次化的方式直观的组织界面，因而编程更为方便灵活。同时Java FX Script也将一些Java 2D的操作暴露出来，用户可以直接在控件中进行渲染。具体细节我会另外撰文详述。在Demo中，Chris Oliver将一些网站上很炫的Flash程序用Java FX改写成Swing的程序，很有点意思，也很有些深意。
Java TV是今年的一个新的Track，据说大概在10年前，就曾经有过这个Track，但是后来由于听众实在太少，就没有后续了，中断了很多年。今年重新开始，我只去听了它的Key Notes，有个细节很有意思，演讲者问底下观众有多少人是从事电视行业软件开发的，举手的只有五六个人，大多数听众都是跟我一样来看看热闹，试试水深的机会主义者。整体上讲，由于数字电视经过了多年的发展，到今天已经是大势所趋了，各家标准也基本上已经确定了，而中间件无一例外的(包括中国正在制定的数字电视标准)建立在Java技术基础之上。Sony带来了一个非常Cool的基于BlueRay的Demo，数字电视和BlueRay技术可以给用户带来更丰富的视听感受，通过Java带来的可移植性和丰富的编程接口，可以编制出更好的用户界面。似乎该是Java TV打翻身仗的时代了。
我没有去参加Realtime Java的任何Session，不过今年跟去年相比，有更多的内容，也有更多实际产品面世了。
除去上面讲的这些，整体而言，AJAX仍然是很大的热点，Ruby也风头正劲，而且由于Java SE 6中加入了脚本语言的集成，在Java程序员中，对于脚本语言的兴趣也大大提升。另外，我还参加了一些Swing和Java Trouble Shooting的讲座，尤其值得一提的是Extreme GUI Makeover, 挺有意思的，很生动，不过技术上讲，基本的方法也都跟去年大同小异，无外乎Timing Framework，Java 2D渲染，控件的定制。能不能写出有趣味的应用程序，关键还是在于富有创意的点子。另外，Java Trouble Shooting的BOF非常棒，新的Java SE 6中提供的诊断工具功能十分强大，很有帮助，以后我会另外撰文详述。今年最后一天的Key Notes还是James Gosling的Toy Show，有很多很有意思，很炫的Demo，机器人，飞机，令人眼花缭乱。大多是Java在嵌入式领域的应用。另外，今年一个有意思的看点是，居然有微软的展台，虽然场地不大。
总结一下技术发展趋势，最近似乎又轮回到Client端了，AJAX，脚本语言，Swing，JavaME这些都是客户端的技术。在Server端的技术基本趋于稳定以后，越来越多的重点被转向了如何提供更生动，更丰富的用户体验上，所谓Rich Client。