详细分解classFile常量池(HelloWorld)

当一个java文件被javac编译之后,就可以成为一个通用的class文件格式。我们之前说JVM里面的运行期常量池,主要也就是说的从classFile中读取的常量信息。作为JVM来说,它并没有对类,接口,实例等有一个内部的数据结构,所有的指令的引用信息均来自于常量池中。
Java Virtual Machine instructions do not rely on the run-time layout of classes, interfaces, class instances, or arrays. Instead, instructions refer to symbolic information in the constant_pool table.
本文自:http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-4.html 4.4节

这里,我们有一个很简单的HelloWorld例子,如下所示:

public class T {
    public static void main(String args[]) {
        String s = "abcdefghijk";
        System.out.println(s);
    }
}

采用指令:javac -g:none T.java进行编译。编译之后产生的class如下所示:

Offset     0  1  2  3  4  5  6  7   8  9  A  B  C  D  E  F

00000000   CA FE BA BE 00 00 00 33  00 1A 0A 00 06 00 0C 08     3        
00000010   00 0D 09 00 0E 00 0F 0A  00 10 00 11 07 00 12 07                   
00000020   00 13 01 00 06 3C 69 6E  69 74 3E 01 00 03 28 29        <init>   ()
00000030   56 01 00 04 43 6F 64 65  01 00 04 6D 61 69 6E 01   V   Code   main 
00000040   00 16 28 5B 4C 6A 61 76  61 2F 6C 61 6E 67 2F 53     ([Ljava/lang/S
00000050   74 72 69 6E 67 3B 29 56  0C 00 07 00 08 01 00 0B   tring;)V        
00000060   61 62 63 64 65 66 67 68  69 6A 6B 07 00 14 0C 00   abcdefghijk     
00000070   15 00 16 07 00 17 0C 00  18 00 19 01 00 01 54 01                 T 
00000080   00 10 6A 61 76 61 2F 6C  61 6E 67 2F 4F 62 6A 65     java/lang/Obje
00000090   63 74 01 00 10 6A 61 76  61 2F 6C 61 6E 67 2F 53   ct   java/lang/S
000000A0   79 73 74 65 6D 01 00 03  6F 75 74 01 00 15 4C 6A   ystem   out   Lj
000000B0   61 76 61 2F 69 6F 2F 50  72 69 6E 74 53 74 72 65   ava/io/PrintStre
000000C0   61 6D 3B 01 00 13 6A 61  76 61 2F 69 6F 2F 50 72   am;   java/io/Pr
000000D0   69 6E 74 53 74 72 65 61  6D 01 00 07 70 72 69 6E   intStream   prin
000000E0   74 6C 6E 01 00 15 28 4C  6A 61 76 61 2F 6C 61 6E   tln   (Ljava/lan
000000F0   67 2F 53 74 72 69 6E 67  3B 29 56 00 21 00 05 00   g/String;)V !   
00000100   06 00 00 00 00 00 02 00  01 00 07 00 08 00 01 00                   
00000110   09 00 00 00 11 00 01 00  01 00 00 00 05 2A B7 00                *?
00000120   01 B1 00 00 00 00 00 09  00 0A 00 0B 00 01 00 09    ?             
00000130   00 00 00 17 00 02 00 02  00 00 00 0B 12 02 4C B2                 L?
00000140   00 03 2B B6 00 04 B1 00  00 00 00 00 00                   +? ?     

本文是描述如何从这个classFile中详细的找出相应的常量池信息,从文件本身描述的信息中手动地找出相应的内部结构,以方便进一步掌握class的结构形式,以方便了解JVM规范及组织。

继续阅读“详细分解classFile常量池(HelloWorld)”

nio通讯中cpu 100%的问题及处理(转)

本文转自:http://marlonyao.iteye.com/blog/1005690 原文作者:marlonyao

在经典的nio通讯例子中,通常是这样写的:

if (key.isAcceptable()) {  
                        ServerSocketChannel server = (ServerSocketChannel) key.channel();  
                        SocketChannel client = server.accept();  
                        System.out.println("Accepted connection from " + client);  
                        client.configureBlocking(false);  
//开始注册读写事件
                        SelectionKey clientKey = client.register(selector, SelectionKey.OP_WRITE|SelectionKey.OP_READ);  
}
//开始写
if (key.isWritable()) {  
                        // System.out.println("is writable...");  
                        SocketChannel client = (SocketChannel) key.channel();  
                        ByteBuffer buffer = (ByteBuffer) key.attachment();  
                        buffer.flip();  
                        client.write(buffer);  
                        buffer.compact();  
                    }  

在测试例子中,该例子也能够正常的输出,不过就是有一个现象:

但是如果你这时top用看一下发现服务器进程CPU占用到95%以上,如果取消掉32行的注释,服务器会不断地输出"is writable…",这是为什么呢?让我们来分析当第一个客户端连接上时发生什么情况。

  1. 在连接之前,服务器第11行:selector.select()处阻塞。当阻塞时,内核会将这个进程调度至休眠状态,此时基本不耗CPU。
  2.     当客户端发起一个连接时,服务器检测到客户端连接,selector.select()返回。selector.selectedKeys()返回已就绪的SelectionKey的集合,在这种情况下,它只包含一个key,也就是53行注册的acceptable key。服务器开始运行17-25行的代码,server.accept()返回代码客户端连接的socket,第22行在socket上注册OP_READ和OP_WRITE,表示当socket可读或者可写时就会通知selector。
  3.     接着服务器又回到第11行,尽管这时客户端还没有任何输入,但这时selector.select()不会阻塞,因为22行在socket注册了写操作,而socket只要send buffer不满就可以写,刚开始send buffer为空,socket总是可以写,于是server.select()立即返回,包含在22行注册的key。由于这个key可写,所以服务器会运行31-38行的代码,但是这时buffer为空,client.write(buffer)没有向socket写任何东西,立即返回0。
  4.     接着服务器又回到第11行,由于客户端连接socket可以写,这时selector.select()会立即返回,然后运行31-38行的代码,像步骤3一样,由于buffer为空,服务器没有干任何事又返回到第11行,这样不断循环,服务器却实际没有干事情,却耗大量的CPU。

从上面的分析可以看出问题在于我们在没有数据可写时就在socket上注册了OP_WRITE,导致服务器浪费大量CPU资源,解决办法是只有数据可以写时才注册OP_WRITE操作。上面的版本还不只浪费CPU那么简单,它还可能导致潜在的死锁。虽然死锁在我的机器上没有发生,对于这个简单的例子似乎也不大可能发生在别的机器上,但是在对于复杂的情况,比如我写的端口转发工具中就发生了,这还依赖于jdk的实现。

继续阅读“nio通讯中cpu 100%的问题及处理(转)”

gcd(最大公约数算法)数学证明(转)

本文转自:http://www.cnblogs.com/ider/archive/2010/11/16/gcd_euclid.html,原文作者:Ider。内容有整理。

常识:如果 a≥b 并且 b≤a,那么 a=b.

前提:
1)只在正数(原谅为非负整数)范围内讨论两个数 m 和 n 的最大公约数,即 m, n ∈ N.
2)不考虑0的情况。(原文为处理0的特殊情况)

引理:
假设 k|a(表示a能够被整除), k|b,则对任意的 x,y  ∈ Z, k|(xa+yb)均成立.
证明:
  k|a => a=pk, k|b => b==qk (其中 p,q ∈ Z)
  于是有 xa+yb=xpk+yqk=(xp+yq)k
  因为 k|(xp+yq)k, 所以 k|(xa+yb)
这上面的结论表示,对于都能被k整除的a和b,对a和b进行整数倍的乘法,并相加起来的结果仍然能够被k整除,可以理解为整除的结合率。

gcd的Euclid算法证明:
命题:对任意 m, n ∈ N,证明gcd(m,n) = gcd(n, m mod n)
证明:
证明第一节
  令 k=gcd(m,n),则 k|m 并且 k|n;
  令 j=gcd(n, m mod n), 则j|n 并且 j|(m mod n);
  对于m, 可以用n 表示为 m=pn+(m mod n);//即m可以表示为xn+y(m mod n)的方式,x为p,y为1
  由引理可知 j|m(其中 x=p,y=1), 又 j|n,于是 j 是 m 和 n 的公约数(但不一定是最大的);
  因为 k 是 m 和 n 的最大公约数,所以必有 k≥j;
证明第二节
  通过另一种表示形式:(m mod n)=m-pn,同理可得://即m mod n可以表示为xm+yn的方式,x为1,y为-p
  k|(m mod n),又k|n,于是 k 是 (m mod n) 和 n 的公约数(也不一定是最大的);
  同样由 j 是 n 和 (m mod n) 的最大公约数可以得到 j≥k;
//证明第三节,使用常识
  由常识,得出结论 k=j,
  即gcd(m,n) = gcd(n, m mod n) ,得证。

使用group by和count in语句实现find contains many的另一种做法

接上一篇文章一个实现类似find contains many(many in many)的sql 语句,原文使用了group by,另外使用了子句的count case when来做条件的过滤。经过笔者的再三实践,发现了另一种做法,即直接在子查询中使用count语句和in的组合来实现这种操作。

原要求:查询即有名字叫张三,也有名字叫李四的班的名字。
翻译为:查询班信息,其中要求学生名字中存在张三,李四的名字的人数至少大于等于2。(不考虑名字重复)

根据这个实现,以下即为完整的sql语句,能够完美地实现这个操作:

select * from class t where (select count(1) from student where classid = t.id and name in (张三,李四)) >= 2

这种做法,即是直接在谓语上使用count语句,并对count子句做过滤操作。
本实现暂未考虑效率问题,不知道和上一篇文章,哪个效率更好一些。

一个实现类似find contains many(many in many)的sql 语句

有如下一种需求(使用班级class和学生student表来描述)

找到学生中即有名字叫张三也有名字叫李四的班级,其中参数<名字>表示任意多个名字,即不限仅有两个参数。

在这种需求中,如果仅只有张三和李四两个条件,则sql可以写成如下:

select a.* from class a where 
exists(select 1 from student where classId=a.id and name=张三) 
and exists(select 1 from student where classid=a.id and name=李四)

在以上的条件中,有两个条件,因此有两个exists子句。而如果有更多呢,比如三个或四个以上,那么 这个exists就会更多。在使用以java实现的sql语句中,就需要使用程序(如for循环)来组装sql了。

有一种更好的解决办法如下,即类似一种 (张三,李四)均在指定班级的学生列表中这种理解方式。使用伪码来描述就是

select a.* rom class a inner join a.studentList where a.studentList.names contains(张三,李思)
或
select a.* rom class a inner join a.studentList where (张三,李思)in a.studentList.names

就是这种集合之间包含的例子,即保证一个集合在另一个集合中。然而现在的sql还没有能够直接表示这种的,更多的使用是使用in来表示一个参数值在一个集合中,而不是一个子集合包含一系列指定的参数。

那么反过来呢,我们利用in来处理这种问题,当学生有一个名字满足参数中值的时候就+1,那么符合条件的班级中的对学生计数的值一定就等于参数列表的长度了(这里必须假设参数值是不相同的)。简单的逻辑如下所示:

对每一个班级进行分组
对每一个班级中的学生进行处理
当学生中的名字满足条件,计数值+1
即最终计数值=条件长度的班级信息,此即我们要查找的班级

使用sql来实现,那么整个实现的sql如下所示:

select * from class where id in (
    select a.id from class a inner join student b on b.classId = a.id
    group by a.id 
    having count(case b.name in (张三,李四) then 1 end)=2
)

以上sql在oracle 10g下测试通过,这里利用了count只对有值的数据计数,而对null不计数的特点。
此文参考了以下文章
http://www.itpub.net/thread-1169213-3-1.html(如何判断多个集合相等,包含)

选择数问题,最坏情况下时间为O(n)的算法实现参考

在前一篇讲选择数问题时,使用了一种类似于快速排序的算法来解决选择数问题,见:http://www.iflym.com/index.php/code/201108240001.html。
而根据算法导论上的一种最坏时间为O(n)的一种解法,其详细的步骤如下所示:

  1.     将数组s按5个为一组,划分成不同的小组,小组数
  2.     对每个小组,进行插入排序,并选择其中的中位数
  3.     将每个小组的中位数,组成一个新的数组,并递归的选择出最终的中位数m
  4.     以m作为参照数,将数组s划分成两个部分,使得m所处的位置数比左侧的数目大1
  5.     如果左侧的数目数恰好为寻找的第k位数,则m即为我们要找的数,否则继续在左侧或者右侧进行查找

有了几个的思路,具体算法就很简单了。参考代码如下所示:

private static int find2(int[] ints, int k, int start, int end) {
//如果k为1,则寻找最小数,如果k为end-start+1则寻找最大数
		//总长度小于5,直接插入排序并查找
......
		//寻找到中位数
		int z = findMiddle(ints, start, end);
		//按中位数分割数组,其中ints[divide]=z
		int divide = divide(ints, z, start, end);
		//判断在哪个部分
		int frontNum = divide - start;
		//恰好为中位数
		if(frontNum == k - 1)
			return ints[divide];
		//高部分
		if(frontNum < k)
			return find2(ints, (k - frontNum), divide + 1, end);
		//低部分
		return find2(ints, k, start, divide - 1);
	}

继续阅读“选择数问题,最坏情况下时间为O(n)的算法实现参考”