blog和wiki数据恢复记

昨天度过了噩梦般的一天。从早上8点多起床到晚上12点半睡觉,都在忙活,连吃饭都搞得很不规律。

早上和下午的主要工作就是重装前面blog提到的肉鸡服务器。备份好数据,格盘,重装,一切顺利。没想到在网卡驱动上栽了一道。本来的管理员说搞个驱动精灵就OK了,傻眼的是驱动精灵还通过网络来下载驱动。想看机器的型号,服务器死死的绑定在机架上没法挪腾。从机器的CPU、显卡、内存和硬盘的配置来搜索,可连服务器是thinkcentre还是lenovo都弄不明白。最后进了BIOS,把序列号抄出来才查到。

狗日的网卡驱动居然要88M之巨,把XP,Vista,32/64位这四个组合全打包一块了,公司网络又慢,只有10多K要下2个小时,只好回宿舍下。

原本的apis服务很快就弄好了,但blog和wiki却不见了。遍寻D盘和E盘两个MySQL的数据文件夹不得。一股不详的预感向我袭来。查了查新装的MySQL,程序安装在E盘,数据居然放在了C盘!blog还好,就2篇短文,wiki那可是我辛辛苦苦写了2个星期的用户手册啊。正好开会的时间到了,先跳上鼓扬回浦口开会去吧。

浦口会后,先上EasyRecovery。C盘本来是15G,系统和程序占了三分之一,如果RP好的话兴许能够恢复回来一些。但现实是残酷的,恢复后的frm文件一个也用不上。binlog显然也指望不上的(今天才知道MySQL有个叫binlog的东西,显然也没开启)。

就在山穷水尽之时,在Google上苦苦搜索的我突然瞄上了Google的网页快照。一搜,好家伙,几篇blog的内容都在,wiki虽然不是很全,好歹也缓存了7篇。一不做二不休赶紧保存下来,生怕第二天Google一更新把缓存都删了。但剩下的10多篇wiki页面仍然没有着落,其中包括了内容最长的Probe和项目计划。

回鼓楼,下车和LP通话中瞬间想起了浏览器的缓存。大部分页面都是用Chrome写的,并且Chrome的缓存我从来都没有清理过。并且Chrome对这些数据应该有很好的组织,不然对浏览记录的搜索也不可能做的这么好。打开缓存记录,发现Chrome只保留7天左右的完全缓存(包括图片),另外文字记录都保存成了sqlite的数据库文件。用一条Select语句一查,所有的文字记录都在,顿时热泪盈眶。

第二天很人肉的把这些数据恢复了上去。虽然不是很完美,但至少恢复了95%的资料。

后续:把服务器MySQL的数据文件夹指向了E盘,并且打开了log-bin。

p.s.:从网页缓存的搜索结果看(用site:xxx.cn),Google内容最多最全(10+页面),有道其次(2个页面),百度压根没收录。唉。

肉鸡

导师的项目借用了某公司的一台服务器对外服务,Windows2003 Server。需要用Windows是无可奈何的事情,虽然程序是用Java写的,试运行的时候也跑在Linux上,但一个比较重要的功能–导入数据需要处理access文件,而读取mdb文件在linux上没有什么成熟的方案,故只能迁就Windows。

拿到帐户登进去的时候被两个情况雷焦了。第一,查看系统属性的时候,发现装的竟然是雨林木风版的Windows。我们个人用户这么盗版也无所谓了,在公网上跑商业应用也用这个,看来真不怕微软的律师信。第二打开浏览器,居然跳出一个类似黄网的页面,哎,居然还中木马。这么没装杀毒软件防火墙的在公网上裸奔,还是需要一点勇气的。既然人家一直这么用都好好的,我也管不了了。

后来两次发现有骇客入侵,手动把骇客的帐号禁用了也就暂时相安无事。把这个情况报告给服务器管理者,似乎没啥反应。前天碰到一个比较狠的骇客,直接把两个管理员的帐号给干掉了。恢复后简单用360查了个木马,揪出来9个程序。

不知道下次服务器的沦陷会是多久以后,怕人家下次直接把数据库给干掉了,只能干瞪眼。

Java的几个术语(覆写, 重载, 隐藏, 遮蔽, 遮掩)

这几天看Java Puzzler,被里面的题目折腾得死去活来,特别是标题里的几个概念。于是决定发篇小文澄清下几个概念。
覆写(Override)
即子类的实例方法覆写了父类的实例方法,即函数的多态。
陷阱1:覆写仅仅对于实例方法有效,对于属性和静态方法不适用。后两者的情况属于隐藏(hide)的范畴。覆写的函数调用时动态绑定的,根据实际类型进行调用;而隐藏的调用则是静态绑定,编译期间就确定了。
陷阱2:覆写要求父类函数的参数和子类函数的参数类型相同。举两个例子:

        public class Base{
                public void foo(Object a){}
                public void bar(int a){}
        }
        public class Derived extends Base{
                @Override
                public void foo(String a){}
                @Override
                public void bar(Integer a){}
        }

上面的代码能通过编译吗?结论是都不行。Java要求类型严格的一致,所以上面的例子实际上表现的是函数的重载。
正如例子中写的那样,对于Java5以上的版本,确定子类函数是否覆写了父类函数,只需要给子类函数添加一个@Override注释,如果子类函数并未覆写任何父类函数,则无法通过编译。
陷阱3:覆写要求父类函数的访问限制对子类可见(public/protected/package)。上例子:

        public class Base{
                private void foo(){System.out.println("base foo");}
                public void bar(){foo();}
        }
        public class Derived extends Base{
                public void foo(){System.out.println("derived foo");}
                public void static main(String[] args){new Derived().bar();}
        }

上面的例子将会输出base foo。子类并没有覆写父类的函数。
在Java虚拟机中,多态的调用通过invokevirtual和invokeinterface两条指令进行调用,前者用于类引用,后者用于接口引用。上面两个方法均是动态绑定。而invokestatic和invokespecial指令使用静态绑定。前者用于静态方法的调用,后者用于实例方法的调用,分为三种情况:第一种用于构造函数(<init>),显然构造函数不需要动态绑定;第二种情况用于调用私有的实例方法,也是上面这个例子里的情况,原因在于,既然这个方法不可能被子类方法覆写,所以直接使用静态绑定(不能推广到final关键字上);第三种情况用于super关键字,在子类方法中强行指定调用父类方法时使用super指代父类,但此类的调用JVM使用动态绑定,具体不再赘述,参见《深入Java虚拟机》第19章的内容。
重载(Overload)
重载这个技术,仅仅是针对语言而言,而在JVM中其实并没有重载的概念。函数的调用匹配本身是通过函数名+函数参数确定的,在匹配函数名后,再匹配函数参数。在选择相同名字的方法时,编译器会选择一个最精确的重载版本。举个例子

public class Main {
        public int a = 1;
        public static void main(String[] args){
                new Main().test(3);
                new Main().test(new Integer(3));
                new Main().test(new ArrayList());
        }
        public void test(int a){System.out.println("int");}
        public void test(Object a){System.out.println("object");}
        public void test(List a){System.out.println("intlist");}
}

上面的方法会打印int int intlist。第一个调用匹配了同为int,Integer类型的函数;第二个调用在寻找Integer类型的参数未果的情况下,把Integer自动拆箱,匹配到了int类型;第三个调用则匹配了最精确的类型List,而不是不精确的Object。如果我们增加一个Integer类型作为参数的函数:

public class Main {
        public int a = 1;
        public static void main(String[] args){
                new Main().test(3);
                new Main().test(new Integer(3));
                new Main().test(new ArrayList<int>());
        }
        public void test(int a){System.out.println("int");}
                public void test(Integer a){System.out.println("integer");}
        public void test(Object a){System.out.println("object");}
        public void test(List<int> a){System.out.println("intlist");}
}

则会精确匹配类型,打印int integer intlist。
再看一个例子,思想来自于Java Puzzlers #46

public class Main {
        public int a = 1;
        public static void main(String[] args){
                new Main().test(null);
        }
        public void test(int[] a){System.out.println("intarray");}
        public void test(Object a){System.out.println("object");}
}

这次的输出会是什么?答案是intarray。如果我们调用的是new Main().test(new int[0]),那么结果总是很好理解;而如果传递一个null,则就有违直觉了。关键在于,编译器总是需要寻找更加精确的类型,而匹配的测试并没有使用实参(参数的实际类型)进行匹配。对于编译器来说,null都可以是Object类型变量和int[]类型变量的合法值,而int[]变量可以是Object类型,但Object类型变量不一定是int[]类型,相较之下int[]更为精确,所以编译器选择了int[]。如果一定要让编译器选择Object,那我们只需要通过new Main().test((Object)null)的形式即可。编译器在重载的时候只认形式参数,不认实际参数。
如何匹配重载函数的代码,Spring里有一个查找constructor的例子,在org.springframework.beans.factory.support.ConstructorResolver的autowireConstructor()函数,以前曾经在Spring配置的时候发生过问题Trace到这里。这个匹配算法使用了贪心的思想(代码里这么注释的),对于每个候选的构造函数都通过一个评估函数(getTypeDifferenceWeight())评估与调用参数类型(constructor-arg里配置的)的相似度,最后取最相似的候选函数。有兴趣的朋友可以自己看看。
隐藏(Hide)
隐藏的概念应用于父类和子类之间。子类的域、静态方法和类型声明可以隐藏父类具有相同名称或函数签名的域、静态方法和类型声明。同final方法不能被覆写类似,final的方法也不能被隐藏。考虑下面的代码:

class Point {
        int x = 2;
}
class Test extends Point {
        double x = 4.7;
        void printBoth() {
                System.out.println(x + " " + super.x);
        }
        public static void main(String[] args) {
                Test sample = new Test();
                sample.printBoth();
                System.out.println(sample.x + " " + ((Point)sample).x);
        }
}

上面的代码将打印4.7 2 \n 4.7 2。子类中的x变量隐藏了父类中的x变量,尽管两个变量类型不同。要访问父类中的变量必须使用super关键字或者进行类型强制转换。下面的代码展示了实例变量隐藏静态变量:

class Base{
        public static String str = "Base";
}
public class Main extends Base{
    public String str = "Main";
    public  static void main(String[] args){
        System.out.println(Main.str);
    }
}

上面的代码不能正确编译,原因是子类中的实例域把父类中的静态域给隐藏了。如果去掉子类中str的声明就可以正确编译。
静态方法和类型声明的隐藏的情况,和域隐藏的情况大同小异,不再给出具体的例子。
遮蔽(shadow)
遮蔽(shadow)指的是在一个范围内(比如{}之间),同名的变量,同名的类型声明,同名的域之间的名称遮蔽。我们最常见到的遮蔽就是IDE为我们自动生成的setter:

public class Pojo{
        private int x;
        public void setX(int x){
                this.x = x;
        }
}

即使是变量类型不相同也可以遮蔽。在上个例子中把setX(int x)的参数类型改为short,也能通过编译。函数的遮蔽常见于匿名类里的函数遮蔽原先类的函数等情况。
上面的几种遮掩比较常见,下面情况就比较特殊了(来源于Java Puzzlers#71)。其中Arrays.toString()方法提供了多个重载版本,可以方便的把基本类型数组转换为字符串。

import static java.util.Arrays.toString;
public class ImportDuty{
        public static void main(String[] args){
                printArgs(1, 2, 3, 4, 5);
        }
        static void printArgs(Object... args){
                System.out.println(toString(args));
        }
}

结果是不能编译,并且返回的信息告诉我们,Object.toString()方法不适用。这是为什么呢?原因在于,Object.toString()方法把Arrays.toString()方法给遮蔽了。下面的代码虽然可以编译,但运行时会提示找不到main方法入口:

class String{
}
public final class Main{
        public static void main(String[] args){
        }
}

原因在于我们自定义的String类型把java.lang.String类型遮蔽了。而如果强行加入import java.lang.String;语句,则不能通过编译。
遮掩(obscure)
遮掩很容易与遮蔽(shadow)混淆。其最重要的区别在于,遮蔽是相同元素之间的遮蔽,变量遮蔽变量,类型声明遮蔽类型声明,函数遮蔽函数。而遮掩却是变量遮掩类型和包声明,类型声明遮掩包声明。
遮掩的例子不多,看下面的例子,来自Java Puzzlers#68:

class ShadesOfGray{
        public static void main(String[] args){
                System.out.println(X.Y.Z);
        }
}
class X{
        static class Y{
                static String Z = "Black";
        }
        static C Y = new C();
}
class C{
        String Z = "White";
}

上面的例子不仅能通过编译,还将打印White。原因就在于当一个变量和一个类型具有相同名称,且具有相同作用域时,变量名优先级大。而类型的声明又具有比包声明更高的优先级。下面一个例子也不能通过编译:

public class Obscure{
        static String System;//变量遮掩了java.lang.System类型
        public static void main(String[] args){
                System.out.println("hello, obscure world!");
        }
}

小结
只有覆写是运行时的技术,另外其他的技术都是编译期的技术。
除了重载、覆写和作为setter的遮蔽,其他特性都强烈不推荐使用,这只会给你和你的继任者带来无穷无尽的麻烦,事实上,重载我认为也少用为妙,特别是结合了使用不确定参数个数的”…”函数的重载,会使你回头看代码时晕头转向。
p.s. 准备技术笔试/面试的语言类题目,C/C++的话,程序员面试宝典里有一些题目,另外就是C++的那些effective系列的书,具体还请C++达人列举(被点名的同学请自觉回帖)。Java的话,首推Joshua Bloch的Effecitve Java;第二就是Java Puzzlers,而后者其实更适合要参加技术笔试面试的同学。剩下的书,应该还有Practical Java,不过我没看过。

百度在线笔试(实习)

今天同学参加百度在线笔试,有幸分享了一下题目。每道题我都做了一些思考,一并记录下来。其中可能有一些重大的纰漏,也欢迎高手指正。

一、编程题(30分)
输入:N(整数)
输入:数据文件A.txt,不超过6条记录,字符串长度不超过15个字节
文件格式如下:
字符串\t数字\n

说明:
每行为1条记录;字符串中不含有\t。
数字描述的是该字符串的出现概率,小于等于100的整数。
多条记录的出现概率之和为100,如果A.txt不满足该条件,程序则退出;
如果文件格式错误,程序也退出。

要求:
编写一个程序,输入为N(正整数),读入文件A.txt,按照字符串出现概率随机地输出字符串,输出N条记录

例如:
输入文件A.txt
abc\t20
a\t30
de\t50
输入为:10

即 abc有20%的概率输出,a有30%的概率输出,de有50%的概率输出,输出10条记录
以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
de
abc
de
a
de
a
de

二、算法题(35分)
题目描述:
设有n个正整数,将它们联接成一排,组成一个最小的多位整数。

程序输入:n个数
程序输出:联接成的多位数

例如:
n=2时,2个整数32,321连接成的最小整数为:32132,
n=4时,4个整数55,31,312, 33 联接成的最小整数为:312313355

[题目要求]
1. 给出伪代码即可,请给出对应的文字说明,并使用上面给出的例子试验你的算法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。(非常重要)

三、系统设计题(35分)
在一个有1000万用户的系统中,设计一个推送(feed)系统。以下是一些预定义概念
1、用户:在这个系统中,每个用户用一个递增的unsigned int来表示user id(简写为uid);则uid的范围是从1到1000万的正整数。
2、好友:用户之间可以形成好友关系,好友是双向的;比如说uid为3和uid为4的两个用户可以互为好友。每个用户好友的上限是500个;用户之间的好友关系可以被解除
3、活动:每个用户只能发文章;文章可以被作者删除,其他人不能删除非自己发表的文章;每篇文章通过一个blogid表示。
4、feed:我们希望,每个用户可以看到他所有好友的活动列表,在这个简化的系统中就是所有好友的文章更新列表。
5、访问量要求:所有feed访问量每天在1亿量级;所有的blogid增加量每天在百万量级。

题目:请在以上限制条件下,设计一个高效的feed访问系统。

要求:
1、能够尽快的返回每个用户的好友feed列表,每个用户可以最多保留1000条feed;feed的展现按照时间倒排序,最新的在最前面
2、用户删除某篇文章后,被推出去的feed需要及时消失。即每个用户看到的好友feed都是未被删除的
3、尽可能高效。

我的解答:

一、这个题目感觉意思有歧义。什么是”按照字符串出现概率随机地输出字符串,输出N条记录”?可以有几种理解。第一,每次掷骰子,掷出了哪个就输出哪个,不管前面输出了什么。第二,要考虑前面出现的字符串。按照题目里的例子,如果前面输出了两次abc,那接下来的无论随机出了什么数,都不能输出abc,最后的结果在数量上符合开始给的概率条件,只是顺序有所不同。这让我想起了排列组合里的袋中取黑球红球问题。把字符串abc,a,de当作2个红球,3个黑球和5个白球,放入袋中。每次拿一个球出来,并记录拿出球的颜色。第一种情况就是拿出球后,把球放回袋中进行下一次抽取;而第二种自然就是不放回的抽取。

顺着百度的笔试不可能那么弱智的想法,同时给出的例子也符合第二种情况的形势,就照着第二种思路往下做。这个题目在从鼓楼到浦口的鼓扬线上最近刚看过,就是编程珠玑II(More Programming Pearls) ,第13章的内容(绝妙的取样)。对于这个题,就是给出abc*2, a*3, de*5,输出随机排列。比较笨的算法就是每次得到一个随机数,如果这个随机数代表的球已经耗尽,那就取下一个随机数。这样的缺点是效率低,越往后效率越低,基本是在拼RP。还是拿例子说事儿,如果随机数为1-2,则输出abc,3-5输出a,6-10输出de。如果到了第9次,还剩下一个abc没输出,则要一直随机到出现1,2为止才结束。

第二种办法是Floyd提出来的(似乎就是那个Floyd-Warshall)。算法如下:

S = []
for j= 1 to N do
        T = RandInt(1, j);
        if T is not in S then
                prefix T to S
        else
                insert J in S after T

不过这个题目还有一个问题:对于每个字符串,生成的期望个数并不一定为整数。例子中的N改成5的话,那就是期望输出1.5个a和2.5个de,随机序列自然没法搞。这个时候回到第一个方法仍然可以做,不过题目也因此解释不通了。同学的解释是,如果是期望输出1.4个a和2.6个de,这一个a和de的争议值,在2/5的情况下输出a,剩下的情况输出b。不过我们其实是没有理由把这个不确定的情况限制在一个整数单位区间里的,即对于1.4个a和2.6个de,必须输出1a+3de或者2a+2de才算合法输出,而把4de,3a+1de的情况定位非法。我觉得这块说不同,所以不需要考虑非整数的不确定情况(如果直接四舍五入到整数,还是算整数的确定情况的)。

二、这题我没怎么考虑。同学的思想在于,把n个正整数按优先级排个序,然后按照排序的结果从小到大排列组成最小的整数。注意这个排序并不是普通的算术排序,而是基于一定的规则。比较的时候把两个数字当成字符串进行字典排序,如果一个数字正好是另外一个数字的前缀的时候,去掉较长字符串的前缀,继续进行比较,直到分出胜负。当然也有旗鼓相当的时候,比如31和313131,这两者的优先级即相同。

时间复杂度,每次比较的平均时间复杂度为O(1),假设输入为随机整数;排序使用快排,复杂度为O(nlgn),所以最终时间复杂度为O(nlgn)。空间复杂度就是O(n)。

算法证明的话我倒是一时半会儿没搞出来。

三、考虑了很久还是决定用数据库做,设计表。完全没有海量数据的表结构设计的经验,因此都是靠感觉来。没用什么技巧,除了数据库的水平分库。

数据库结构设计为4张表,结构如下(引用只是表示关联关系,并非加上外键约束):
User
int uid#主键
char(12) username
Friend
int uid#用户uid,引用User.uid,加索引
int fuid#朋友uid,引用User.uid,加索引
Blog
int blogid#主键
int uid#发表用户uid,引用User.uid,加索引
varchar(60) title
text content
datetime publish_time
Feed#存储每个用户的好友feed列表
int uid#引用User.uid,加索引
int blogid#引用Blog.blogid,加索引
varchar(60) title#可有可无,根据生成Feed是否需要Feed标题决定

在存储方面,Friend表和Feed表数量较大,因此采用水平分库存储的形式。即Friend表分散在几个数据库内,按照第一个uid的最后几位进行划分。如有10个数据库,即可根据个位数映射到0-9号数据库上。同理可得Feed表的存储方式,按照uid进行水平分库。

如果用户a和用户b是好朋友,则在Friend表中添加(a,b)和(b,a)两条记录,分别添加到a,b所属的库里。解除关系的话删除这两条记录。

用户发表文章的时候,首先在Blog表添加一条记录;第二,查询Friend表得出当前用户的所有好友,然后给Feed表添加记录,格式为(好友id, blogid, title),一共添加好友个数条记录。第三查询所有好友的Feed数记录,如果Feed超过了1000条,则删除该好友最早的一条Feed。第二第三步可以根据好友uid,把存储在相同库的好友Feed在同一次操作里批量添加/查询/删除。

用户要得到自己的Feed列表,只需要先计算自己的uid属于哪个数据库,然后从该数据库里取出所有的Feed记录,即可以快速得到Feed列表,只需要一个数据库查询,不需要做表间的连接操作。

用户删除文章的时候,把Feed表里blogid等于目标文章id的记录都删除。

排序算法简单小结

最近开始准备算法。本来看的是Algorithms(算法概论),后来瞄了瞄算法导论,决定还是从基本的数据结构看起。Eric Raymond曾经说过:Show me your code and conceal your data structure, and I shall continue to be mystified. Show me your data structure, and I won’t need your code; it’ll be obvious.
虽然看的是数据结构的书(殷人昆的那本C++),但第一眼还是算法–排序。主要是昨天的IBM笔试,把排序的一些基本知识都给忘光了。下面进入正题。
排序首先分为内排序和外排序。其中内排序是基础,外排序则是在内存不足的情况下,对内排序进行了一些相应的改进。
简单的内排序主要有以下几种:
插入排序

简单插入排序。假定前i个元素有序,从后面不断取出元素插入前面有序数组中。复杂度为O(n2),最好情况为O(n)(数组原本有序)。稳定排序。
折半插入排序。简单插入排序的改进。在插入过程中,使用折半搜索找到插入的位置,其他方法相同。虽然比较的次数下降到了O(nlogn),但是移动次数仍然为O(n2)。稳定排序。
链表插入排序。改进简单插入排序,减少了移动次数。但比较次数仍然为O(n2)。稳定排序。
希尔排序(Shell Sort)。每隔几个元素为一组,进行简单插入排序;不断缩小间隔直至对整个数组进行简单插入排序。由于前面阶段每次排序元素数目少,所以开销不大;后面阶段中,每次参与排序的元素或多或少都有点排序的基础了,所以效率也挺高。没有确定的时间复杂度分析结果。Knuth做了大量的实验,结论大概为O(n^1.25-1.6n^1.25)不稳定排序(听说有稳定排序的实现,但先权当不稳定)。

交换排序

冒泡排序。不断交换,每一次Pass都把最小的换到最前面或者把最大的换到最后面。O(n2)。稳定。这是我接触的第一个算法,不过当时死活没明白,因为只有小学3、4年级。老爸倒是明白了,当时无限崇拜。
快速排序。Divide & Conquer思想。面试里很喜欢考的排序算法。把小于数组里某个数(这个数的挑选有学问)的数放到这个数的左边,大于的数放到这个数的右边。然后递归排序其左右两边的子数组。O(nlogn)。不稳定。

选择排序

直接选择排序。每次从后面的数组里挑最小的一个放到最左边。O(n^2)。不稳定排序。
竞标赛排序(胜者树)。改进了选择算法,使用两两比较的算法选择最小数。O(nlogn)。稳定排序。
堆排序。所有的parent < child。O(n)的建堆时间,很适合求一个数组内top n个数。O(nlogn)排序时间。不稳定排序

归并排序(Merge Sort)

2路归并排序。迭代或递归的从小到大不断合并。O(nlogn)。稳定排序。

基数排序

扩展了桶排序(Bin Sort)的思想,把桶分级了。可能需要消耗较多的空间。应用受到局限。O(d(n+radix)),d为级别数,radix为桶数(假定每一级的桶数相等)。稳定排序。

外排序主要在归并排序上做文章。如k路平衡归并,扩大初始归并段,还有借鉴了霍夫曼树的最佳归并树优化,均是为了减少IO次数。值得一提的是,k路平衡归并里使用了败者树。和胜者树不同的是,败者树每次选择了败者进入上级节点,而把胜者信息单独记录。从而简化了每次重构(UpdateTree)的过程,比如不需要判定对手是在左边还是右边,直接和parent做比较(因为上次的败者被选择进了parent)。
另外排序算法还有其他的衡量指标,比如空间复杂度。部分算法是就地排序,使用O(1)的空间,比如插入排序(链表除外),直接选择排序,堆排序,交换排序。
只是简单的整理。更详细的资料可参阅维基百科词条:排序算法Sorting Algorithm

使用 Equinox 开发 OSGi 应用程序(上)

本文大量参考了IBM Developerworks上的文章使用 Equinox 开发 OSGi 应用程序,之所以重新发表,是因为原文使用的是Eclipse 3.3,现在主流的版本为3.4,其中有些不同的地方。另外有一部分语焉不详,很容易使人卡在半途(主要在下一篇里)。因此我针对3.4做了一些整理,也重新截了图,作为对OSGi入门开发的一个小结。
OSGi中文的大部分资料都和BlueDavy有很大的关系。如果想对OSGi有一个入门性或者较为深入的理解,请参阅BlueDavy编写的OSGi实战和OSGi进阶的OpenDoc。本文假定读者对OSGi有一些了解,所以对OSGi的介绍就不再赘述。
对于Eclipse(3.2+)来说,其上运行的所有插件都是OSGi的Bundle。其核心Equinox就是OSGiR4的参考实现。所以,在Eclipse里,我们通过开发插件的形式,开发符合OSGi规范的Bundle。我们从HelloWorld开始。

  1. 建立一个 plug-in 工程,File > New > Project,选择 Plug-in development > Plug-in Project
    新建插件项目
    新建插件项目
  2. 在建立工程的第一个向导,填入工程的名称:osgi.test.helloworld,使用缺省的工程路径。由于我们的项目是一个通用的 OSGi bundle,所以选择 equinox。比3.3多出来的Working Set的概念我还没搞清楚,就默认吧。
    新插件项目设置
    新插件项目设置

  3. 这个步骤主要是填写插件/Bundle一些信息。可以不做修改直接“Next”。其中最后的是关于Activator的设置,相当于一个Java程序的main()入口,控制着整个Bundle的生命周期。与3.3相比,多出了Execution Environment选项。如果只在本机HelloWorld的话,就用默认的环境。
    新插件项目信息
    新插件项目信息
  4. 去掉所有的模板设置,结束新建newpluginprojectnotemplate
  5. 完成,切换到插件开发的视角。新建了osgi.test.helloworld.Activator类,用于控制Bundle的生命周期,初始化等等(不过初始化工作不必都放在这里,OSGi提供了完整了Listener的支持)。最重要的配置文件是MANIFEST.MF,Eclipse提供了完整的编辑器支持,有几个标签页。比如在Dependencies里设置导入的包和依赖的Bundle/Plugin,Runtime则配置了导出的包及其他信息。newpluginprojectfinish
  6. 编辑 Activator.java,找到start()方法,输入 hello world 语句,代码如下:
    package osgi.test.helloworld;
    import org.osgi.framework.BundleActivator;
    import org.osgi.framework.BundleContext;
    public class Activator implements BundleActivator {
    	/*
    	 * (non-Javadoc)
    	 * @see org.osgi.framework.BundleActivator#start(org.osgi.framework.BundleContext)
    	 */
    	public void start(BundleContext context) throws Exception {
    		System.out.println("hello world");
    	}
    	/*
    	 * (non-Javadoc)
    	 * @see org.osgi.framework.BundleActivator#stop(org.osgi.framework.BundleContext)
    	 */
    	public void stop(BundleContext context) throws Exception {
    	}
    }

    每个Activator都实现了BundleActivator这个接口。OSGi就通过这个调用接口的 start()和stop()实现Bundle的启动和停止。
    注意:bundle 的 Activator 必须含有无参数构造函数,这样框架才能使用 Class.newInstance() 方式反射构造 bundle 的 Activator 实例。

  7. 运行实例。和普通Java程序直接运行不同的是,运行Bundle需要一些配置。选择Run->Run Configurations…,在 OSGi framework 中右键点击选择 new 一个新的 OSGi 运行环境
    Bundle运行配置初始对话框
    Bundle运行配置初始对话框
  8. 在右边的运行环境对话框中,输入运行环境的名字、start level 和依赖的插件。Start Level越高,启动顺序越靠后。图中默认的Start Level(SL)为4,我们把helloworld的Start Level设置为5,即较后加载的Bundle。由于目前不需要其它的第三方插件,因此只需要勾上系统的 org.eclipse.osgi 插件,如果不选择此插件,hello world 将无法运行。只有当点击了 validate bundles 按钮 ,并且提示无问题之后,才表明运行环境基本 OK 了。runconfigrequirebundel1
  9. 点击“Run”,运行,应该能够在Console看到HelloWorld输出
    运行控制台
    运行控制台

OSGi控制台使用命令行控制Bundle的状态查看、加载、卸载和更新。OSGi的好处在于能够在不重启应用的情况下,实现对模块的热插拔。如通过SS命令查看所有Bundle的简单状态(SS=Simple Status)。图中模块的状态为ACTIVE。
runss
下图展示了OSGi Bundle的状态图:
我可以直接修改HelloWorld里Activator的代码,编译后。使用Refresh命令更新helloworld的Bundle,得到更新后的运行输出:runchangedrefresh
下面列出了主要的控制台命令。也可以在控制台中输入? 获得帮助

类别 命令 含义
控制框架 launch 启动框架
shutdown 停止框架
close 关闭、退出框架
exit 立即退出,相当于 System.exit
init 卸载所有 bundle(前提是已经 shutdown)
setprop 设置属性,在运行时进行
控制 bundle Install 安装
uninstall 卸载
Start 启动
Stop 停止
Refresh 刷新
Update 更新
展示状态 Status 展示安装的 bundle 和注册的服务
Ss 展示所有 bundle 的简单状态
Services 展示注册服务的详细信息
Packages 展示导入、导出包的状态
Bundles 展示所有已经安装的 bundles 的状态
Headers 展示 bundles 的头信息,即 MANIFEST.MF 中的内容
Log 展示 LOG 入口信息
其它 Exec 在另外一个进程中执行一个命令(阻塞状态)
Fork 和 EXEC 不同的是不会引起阻塞
Gc 促使垃圾回收
Getprop 得到属性,或者某个属性
控制启动级别 Sl 得到某个 bundle 或者整个框架的 start level 信息
Setfwsl 设置框架的 start level
Setbsl 设置 bundle 的 start level
setibsl 设置初始化 bundle 的 start level

压缩软件

大概99年的时候,家里有了电脑。那时候机器贵硬盘空间小,虽然8000块钱的机器,硬盘只有5.1G。宽带还没普及,经常要用到1.44M的软盘。压缩软件自然居家必备。Windows 98的时代,Windows还原生不支持zip,需要Winzip来搞定。可是Winzip只是共享软件,非免费软件,过了试用期都会提示你付费,只好到处找破解版。后来Winrar不知为何取代了Winzip,占领了用户的桌面。(后文有解答)
这几天导师让我做个课程主页,里面要带上Slide。可是Office转换而成的HTML效果总是不尽如人意,而且一般总是IE only。还好有个网站叫Cometdocs,支持PDF->HTML。我先用PDF Creator打印成PDF,再上传到网站转换HTML。
转好了发现体积太大了。原本2M的Slide转成HTML居然涨到了10M。这也不能怪别人,HTML和PDF很不一样,背景图一张一张分开放,Slide一多就不行。正愁怎么发给老板,想到了7z的压缩比比zip好,于是就压缩成7z的格式试试。
一试吓一跳。25M的网站,压缩成zip剩下23M多,换成7z只剩下4.5M!!!原来7z支持文件间的对比压缩,而这些幻灯片的背景图大同小异,自然得到很理想的压缩比。不过文件间压缩的缺点在于,一旦只想解压缩一部分文件的时候,只能解压缩所有的文件之后再把目标文件给抽出来。
在搜索7z文件间压缩的时候,不经意看到善用佳软的两篇推荐7zip的文章,在这里这里。其中提到的传奇文章《压缩大战真相》,揭露了当初RAR PK掉ZIP的一些故事。
最后再给7-zip做做广告。全免费(个人可能无所谓用破解,但公司可承担不起这个法律风险),支持格式丰富,压缩比高,使用简单。用惯了winrar也不用怕,7zip也支持rar的解压缩,别人发给你的rar照样能打开,基本没有软件切换的成本。
想起来俺家小白也在我的唆使下用起了7-zip,挺好使的,是吧?

IE6设置Image.src的bug

这个问题我现在也没彻底搞懂。网站有一块需要建立一个Image对象,设置好src属性,onerror和onload属性,然后把Image添加为div的子元素,交给浏览器去请求图片并渲染(请看p.s.)。用其他浏览器都很正常,但用IE6浏览器访问,虽然能得到图片,但服务器的日志里会报错,第一个Exception是Connection reset by peer,第二个是多次调用response.getOutputStream()或getJspWriter()。
上了调试器,发现一次图片的调用,服务器会在入口函数的断点停留两次,说明浏览器发出了两次请求。用Fiddler看各次请求的内容,居然再也无法重现错误了。换用HttpWatch,终于重现了错误。每次图片的调用都会有两个请求,第一个请求发出后马上被掐掉(Aborted),然后接着发出第二个请求。这解释了为什么会抛Connection reset by peer的异常。第二个异常的原因,估计是当浏览器的reset请求到达服务器时,服务器的代码已经完成了生成图片的工作,并把图片塞进了response,这个时候抛来一个异常,被forward到error.jsp,于是乎二次调用了getJspWriter,报错。
网上搜了搜这个问题,有少许提到这个bug。我的解决方法很简单,就是在image append到div之后,再设置src属性。经测试解决了IE6的Aborted问题,其他浏览器,如IE7,FF3和Chrome都没什么影响。
p.s. 后来看到玉伯的博客,发现Image对象在设置了src对象以后就马上请求图片,并不等到被添加到DOM上再请求,因为Image本来就是用来做图像预加载的。所以原本的代码就有一些错误,应该先设置onerror和onload属性后,再设置src才有意义。
p.s.2 这里是一篇描述了IE中Aborted的文章,推翻了不少本文的无妄猜测。
p.s.3 经我第三次的测试,发现IE6中如果先设置image.src在appendChild,会出现Aborted问题,相反顺序则没有问题。

简单比较Apache+Tomcat的mod_jk和mod_proxy方法

这几天服务上线。由于80端口还需要blog和wiki两个服务,所以把80给了Apache管理,然后再通过apache连接后面8080的Tomcat。
Apache+Tomcat主要有三种办法实现: mod_jk, mod_proxy和ajp_proxy。mod_jk是比较专门针对Tomcat的方法,通过AJP协议连接Tomcat,mod_proxy不止可以连接Tomcat,只要是HTTP应用都可以进行反向代理。ajp_proxy不是很清楚,具体参见这里
我前后碰到过三种不同的配置环境。第一次是搭建试验服务的时候,服务搭建在一台内网机器上,通过外网机器的8080端口映射内网的80端口进行访问。由于可对外暴露的端口只有被映射的一个80端口,自然把Apache推了上去。使用mod_proxy进行反向代理配置。后来上面要求搭建两个运行实例,于是开了两份Tomcat,配了两份的proxy。一个在18080,一个在28080。

ProxyPass /app http://localhost:18080/app
ProxyPassReverse /app http://localhost:18080/app
ProxyPass /app2 http://localhost:28080/app2
ProxyPassReverse /app2 http://localhost:28080/app2
第二次的环境并不是Apache+Tomcat,而是IIS+Tomcat。对IIS的不熟悉让我一段时间之内挠破了头。IIS上我没有找到比较实用的mod_proxy组件,特别是使用ISAPI的mod_proxy。而另外一个重大变化在需求上,这次要求服务支持SaaS,而我们服务的SaaS通过访问的域名来区别不同的租户。比如通过abc.example.com和def.example.com访问的用户,虽然使用的是同一个应用,但是却在不同的租户空间内进行操作。
可行的办法是使用ISAPI Rewrite。ISAPI Rewrite事实上是提供Proxy功能的,但那是收费版本。免费的Lite版本只有URL Rewrite的功能。我只好彻底放弃了Proxy的打算,对用户做重定向。比如访问http://abc.example.com的用户将被重定向到http://abc.exmaple.com:8080/app。对于wiki和blog这些访问,在配置文件中当作例外处理。以下是配置文件:
RewriteCond %{HTTP:Host} example\.com$
RewriteCond %{HTTP:Host} !www\.example\.com$
RewriteCond %{HTTP:Host} !wiki\.example\.com$
RewriteCond %{HTTP:Host} !blog\.example\.com$
RewriteRule app/(.*) http://%{HTTP:Host}\:8080/app/$1 [NC,R=301]
RewriteCond %{HTTP:Host} example\.com$
RewriteCond %{HTTP:Host} !www\.example\.com$
RewriteCond %{HTTP:Host} !wiki\.example\.com$
RewriteCond %{HTTP:Host} !blog\.example\.com$
RewriteRule (.*) http://%{HTTP:Host}\:8080/app [NC,R=301]
RewriteCond %{HTTP:Host} www\.example\.com$
RewriteRule ^/$ http://%{HTTP:Host}/app/index.htm [NC,R=301]
RewriteCond %{HTTP:Host} wiki\.example\.com$
RewriteRule ^/(.*)$ http://www.example.com/wiki/$1
RewriteCond %{HTTP:Host} blog\.example\.com$
RewriteRule ^/(.*)$ http://www.example.com/blog/$1
第三次,经过争取,服务器的80端口让位于Apache。当我打算切回第一次的mod_proxy配置时,却发现一个致命的问题:Request里Host的内容已经被mod_proxy修改成了配置文件里的localhost,没有反映用户真实请求里的abc.example.com或者def.example.com。况且系统还要求支持实时添加租户,即在不重启系统的情况下增加新的*.example.com的访问。
mod_proxy虽然能对后台任何的HTTP服务做反向代理,却把泛域名访问给挡在了门边。另外我也终于明白了为什么试验服务器上的Tomcat访问日志里,来源都是127.0.0.1——因为来源都是Apache这个代理。
mod_jk的配置里,虽然仍然需要输入Tomcat的Host,但是似乎AJP协议的保留了前台访问的域名(后台程序通过request.getServerName()获得)。而客户端的IP地址也被成功的记录下来。有兴趣的同学们可以参见AJP 1.3的协议参考。mod_jk的配置就不贴出来了,具体可以看开头介绍proxy_ajp的那个链接

使用JMeter进行压力测试

JMeter是一款优秀的开源压力测试工具。网上有不少介绍的文章,比如DeveloperWorks上有一篇。不过脚本的制作比较麻烦,自己手动输入参数比较不实际。cnblog上有一测试达人在这里介绍了一个免费工具Badboy,可以录制在IE上的操作并导出JMeter脚本。Badboy本身是一个Web自动化测试工具。不足的是,一些Badboy录制的动作JMeter并不支持,比如多窗口操作。在导出jmx文件的时候Badboy会提示不能导出的内容。Badboy也有一些不够智能的地方,比如写死了服务器地址,而不是创建一个默认的HTTP访问器。
一开始使用JMeter进行压力测试完全是冲着JMeter的Cookie Manager功能去的。如果使用简单的工具,比如apache自带的ab工具,则要想方设法绕过应用程序的登录机制。使用Cookie Manager虽然不需要配置,但要注意的是,要把发来初始cookie的地址给包括进来。我测试的系统在/login.do这里发放cookie,但我直接访问/acegi_login登录,结果就丢掉了cookie,导致后续步骤失败。