今日点击： 15
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年09月10日 It's been a while that my Solaris laptop(Sony VAIO S48CP/B) couldn't work well with the projectors. So it was a shame that I had to do most of my presentations and demos on Windows.
A few days ago, I reinstalled the laptop with some recent Solaris Express build. I found the NVIDIA driver now comes with a very neat configuration tool, which has been successfully ported from other platform like Linux and FreeBSD. You could launch it from "Start Menu"->"All Applications"->"System Tools"->"NVIDIA X Server Settings"
This tool provides ways to set various of video/display features.For projectors only, you could just select "X Server Display Configuration". If there is a projector or other display connected to your system, just click the "Detect Displays" button, it will detect all the connected displays to your systems.
Select the new detected display, click "Configure..." button, select "TwinView", Click OK.
Set the "Position" combobox as "Clones", then click "Apply" button.
Now, you should have copied your screen to the projector or other displays.
Pretty nice, isn't it? With the open sourcing of Solaris, the drivers support on Solaris is getting much better, it looks promising to use Solaris as the development platform.