package lhz.algorithm.chapter.six;
/**
* "优先级队列",《算法导论》6.5章节
* 原文摘要:
* A priority queue is a data structure for maintaining a set S of elements, each with an
* associated value called a key. A max-priority queue supports the following operations.
* ・INSERT(S, x) inserts the element x into the set S. This operation could be written as S←S{x}.
* ・MAXIMUM(S) returns the element of S with the largest key.
* ・EXTRACT-MAX(S) removes and returns the element of S with the largest key.
* ・INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k,
* which is assumed to be at least as large as x's current key value.
* 堆的一种实际应用,可用于任务调度队列等。包含四个操作方法。
* @author lihzh(OneCoder)
* @blog http://www.coderli.com
*/
public class PriorityQueue {
private static final int DEFAULT_CAPACITY_VALUE = 16;
//初始化一个长度为16的队列(可作为构造参数),此处选择16参考HashMap的初始化值
private int[] queue;
//堆大小
private int heapSize = 0;
public static void main(String[] args) {
PriorityQueue q = new PriorityQueue();
q.insert(2);
q.insert(6);
q.insert(3);
q.insert(8);
q.insert(7);
q.insert(9);
q.insert(1);
q.insert(10);
q.insert(9);
System.out.println(q.extractMax());
System.out.println(q.extractMax());
q.insert(9);
q.insert(1);
q.insert(10);
System.out.println(q.extractMax());
System.out.println(q.extractMax());
System.out.println(q.extractMax());
System.out.println(q.extractMax());
System.out.println(q.extractMax());
System.out.println(q.extractMax());
System.out.println(q.extractMax());
}
public PriorityQueue(int capacity) {
this.queue = new int[capacity];
}
public PriorityQueue() {
this(DEFAULT_CAPACITY_VALUE);
}
/**
* 返回当前最大值
* @return
*/
public int maximum() {
return queue[0];
}
/**
* 往优先级队列出,插入一个元素
* 利用INCREASE-Key方法,从堆的最后增加元素
* 伪代码:
* MAX-HEAP-INSERT(A, key)
* 1 heap-size[A] ← heap-size[A] + 1
* 2 A[heap-size[A]] ← -∞
* 3 HEAP-INCREASE-KEY(A, heap-size[A], key)
* 时间复杂度:O(lg n)
* @param value 待插入元素
*/
public void insert(int value) {
//注意堆容量和数组索引的错位 1
queue[heapSize] = value;
heapSize++;
increaceKey(heapSize, value);
}
/**
* 增加给定索引位元素的值,并重新构成MaxHeap。
* 新值必须大于等于原有值
* 伪代码:
* HEAP-INCREASE-KEY(A, i, key)
* 1 if key < A[i]
* 2 then error "new key is smaller than current key"
* 3 A[i] ← key
* 4 while i > 1 and A[PARENT(i)] < A[i]
* 5 do exchange A[i] ⟷ A[PARENT(i)]
* 6 i ← PARENT(i)
* 时间复杂度:O(lg n)
* @param index 索引位
* @param newValue 新值
*/
public void increaceKey (int heapIndex, int newValue) {
if (newValue < queue[heapIndex-1]) {
System.err.println("错误:新值小于原有值!");
return;
}
queue[heapIndex-1] = newValue;
int parentIndex = heapIndex / 2;
while (parentIndex > 0 && queue[parentIndex-1] < newValue ) {
int temp = queue[parentIndex-1];
queue[parentIndex-1] = newValue;
queue[heapIndex-1] = temp;
heapIndex = parentIndex;
parentIndex = parentIndex / 2;
}
}
/**
* 返回堆顶元素(最大值),并且将堆顶元素移除
* 伪代码:
* HEAP-EXTRACT-MAX(A)
* 1 if heap-size[A] < 1
* 2 then error "heap underflow"
* 3 max ← A[1]
* 4 A[1] ← A[heap-size[A]]
* 5 heap-size[A] ← heap-size[A] - 1
* 6 MAX-HEAPIFY(A, 1)
* 7 return max
* 时间复杂度:O(lg n),
* @return
*/
public int extractMax() {
if (heapSize < 1) {
System.err.println("堆中已经没有元素!");
return -1;
}
int max = queue[0];
queue[0] = queue[heapSize-1];
heapSize--;
maxHeapify(queue, 1);
return max;
}
/**
* 之前介绍的保持最大堆的算法
* @param array
* @param index
*/
private void maxHeapify(int[] array, int index) {
int l = index * 2;
int r = l + 1;
int largest;
//如果左叶子节点索引小于堆大小,比较当前值和左叶子节点的值,取值大的索引值
if (l <= heapSize && array[l-1] > array[index-1]) {
largest = l;
} else {
largest = index;
}
//如果右叶子节点索引小于堆大小,比较右叶子节点和之前比较得出的较大值,取大的索引值
if (r <= heapSize && array[r-1] > array[largest-1]) {
largest = r;
}
//交换位置,并继续递归调用该方法调整位置。
if (largest != index) {
int temp = array[index-1];
array[index-1] = array[largest-1];
array[largest-1] = temp;
maxHeapify(array, largest);
}
}
public int[] getQueue() {
return queue;
}
}
云计算开源产品推荐 - CloudStack项目简介
CloudStack是思杰(Citrix)旗下的一款开源的虚拟化环境管理软件。核心代码用Java开发。CloudStack的目标是成为一个可以部署并管理大量的虚拟机网络资源,具有高可用和扩展性的云计算管理平台。目前已经支持许多主流的虚拟化平台,如:VMware、Oracle VM、KVM、XenServer、Xen。CloudStack不仅提供了UI支持,也提供了命令行的操作方式,和可用于开发的Restful API。 CloudStack目前已经基于ASL2.0协议,有利于二次开发。目前最近版本为3.0 可以通过CloudBridge支持Amazon EC2接口。
- 官网地址:http://cloudstack.apache.org/
- CloudStack Git项目主页:https://git-wip-us.apache.org/repos/asf?p=cloudstack.git
开发人员应留意的开源软件许可证简介
作为一个Java开发人员,开发中总会依赖很多的项目(jar包),一般来说这些项目大部分都是开源的,但是开源不等于随意使用甚至商用。开源软件都有着自己的许可证,不同的许可证自然约束也是不同的。稍不留神,可能会自讨苦吃。
先引用百度百科的开源软件的定义:
开源软件定义Version 1.9
开源不仅仅表示开放程序源代码。从发行角度定义的开源软件必须符合如下条件:
1. 自由再发行
许可证不能限制任何团体销售或赠送软件,软件可以是几个不同来源的程序集成后的软件发行版中的其中一个原件。许可证不能要求对这样的销售收取许可证费或其他费用。
2. 程序源代码
程序必须包含源代码。必须允许发行版在包含编译形式的同时也包含程序源代码。当产品以某种形式发行时没有包含源代码,必须非常醒目的告知用户,如何通过Internet免费的下载源代码。源代码必须是以当程序员修改程序时优先选用的形式提供。故意地扰乱源代码是不允许的。以预处理程序或翻译器这样的中间 形式作为源代码也是不允许的。
3. 派生程序
许可证必须允许更改或派生程序。必须允许这些程序按与初始软件相同的许可证发行。
4. 作者源代码的完整性
只有当许可证允许在程序开发阶段,为了调整程序的目的将“修补文件”的发行版与源代码一起发行时,许可证才能限制源代码以更改后的形式发行。许可证必须明确地允许按更改后的源代码所建立的程序发行。许可证可以要求派生的程序使用与初始软件不同的名称或版本号。
5. 无个人或团体歧视
许可证不能都有针对任何个人或团体制在专门奋斗领域内的任何人使用该程序。例如不能限制程序应用于商业领域,或者应用于遗传研究。
6. 对程序在任何领域内的利用不得有差别待遇
该条款的主要目的是禁止许可证中含有使开放源代码软件无法在商业上使用的规定。我们需要商业用户参与我们的工作,而不让他们感到被排除在外。
7. 许可证发行
伴随程序所具有权力必须适用于所有的程序分销商,而不需要这些团体之间再附加许可证签字盖章。
8. 许可证不能特制某个产品
如果程序是某个特殊的软件发行版中的一部分,伴随该程序所具有的权力不能只以来于这一发行版。如果程序是从那一发行版中摘录出来的,使用或发行时用的都是那个程序的许可证,分销程序的所有团体都应拥有与初始软件版所允许的所有权力。
9. 许可证不能排斥其他软件
许可证不能限制随该许可证软件一起发行的其他软件。例如,许可证不能要求所有与之一起发行的其他软件都是开源软件。
10. 许可证实例
GNU GPL、BSD、X Consortiun和Artistic许可证都是我们认为符合开源软件定义的许可证。MPL也是一样。
上面的定义可能比较书面和晦涩。一般在产生法律纠纷的时候会有作用,我们主要关注的是我们所使用项目的所遵循的许可证协议。说白了就是我们的产品是否需要开源,能不能商用。概括如下: 按照使用条件的不同,开源软件许可证可以分为三类(严苛程度递减)
- 使用该开源软件的代码再散布(redistribute)时,源码也必须以相同许可证公开。代表许可类型:GPL, AGPL。
- 使用该开源软件的代码并且对开源代码有所修改后再散布时,源码必须以相同许可证公开。代表许可类型:LGPL, CPL,CDDL, CPL,MPL等。
- 使用该开源软件的代码(包括修改)再散布(redistribute)时,没有特殊限制,只需要明记许可。代表许可类型:ASL, BSD,MIT等。
一般Java开源人员常用的Spring,Apache-commons系列的项目等,都是属于ASL协议的。所以我们可以随意使用,但是玩意你用到了什么项目是GPL协议的,那你就得小心考虑了:)笔者是吃过苦的:)。
更多关于许可证的信息可访问网站:http://www.opensource.org/licenses
堆排序 - Java实现
package lhz.algorithm.chapter.six;
/**
* "排序",《算法导论》6.4章节
* 利用之前实现的构建MaxHeap和MaxHeapify算法完成排序。
* 伪代码:
* HEAPSORT(A)
* 1 BUILD-MAX-HEAP(A)
* 2 for i <- length[A] downto 2
* 3 do exchange A[1] <-> A[i]
* 4 heap-size[A] <- heap-size[A] - 1
* 5 MAX-HEAPIFY(A, 1)
* @author lihzh(OneCoder)
* @OneCoder-Blog http://www.coderli.com
*/
public class HeapSort {
private static int[] input = new int[] {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};
public static void main(String[] args) {
//堆排序
heapSort();
//打印数组
printArray();
}
/**
* 堆排序,《算法导论》原文摘要:
* The heapsort algorithm starts by using BUILD-MAX-HEAP to build a max-heap on the input
* array A[1 - n], where n = length[A]. Since the maximum element of the array is stored at the
* root A[1], it can be put into its correct final position by exchanging it with A[n].
* If we now "discard" node n from the heap (by decrementing heap-size[A]), we observe that
* A[1 , (n -1)] can easily be made into a max-heap. The children of the root remain max-heaps,
* but the new root element may violate the max-heap property. All that is needed to restore
* the maxheap property, however, is one call to MAX-HEAPIFY(A, 1), which leaves a max-heap
* in A[1, (n - 1)]. The heapsort algorithm then repeats this process for the max-heap of size
* n - 1 down to a heap of size 2.
* 复杂度:
* 由之前分析可知,buildMaxHeap复杂度为O(n lg n),运行一次。
* maxHeapify的复杂度为O(lg n),运行n-1次。
* 综上,复杂度为O(n lg n)。
*/
private static void heapSort() {
int length = input.length;
//构造max-heap
buildMaxHeap(input, length);//交换位置
for (int i = length - 1; i > 0; i--) {
int temp = input[i];
input[i] = input[0];
input[0] = temp;
maxHeapify(input, 1, i);
}
}
private static void buildMaxHeap(int[] array, int heapSize) {
for (int i = heapSize / 2; i > 0; i--) {
maxHeapify(array, i, heapSize);
}
}
private static void maxHeapify(int[] array, int index, int heapSize) {
int l = index * 2;
int r = l + 1;
int largest;
//如果左叶子节点索引小于堆大小,比较当前值和左叶子节点的值,取值大的索引值
if (l <= heapSize && array[l-1] > array[index-1]) {
largest = l;
} else {
largest = index;
}
//如果右叶子节点索引小于堆大小,比较右叶子节点和之前比较得出的较大值,取大的索引值
if (r <= heapSize && array[r-1] > array[largest-1]) {
largest = r;
}
//交换位置,并继续递归调用该方法调整位置。
if (largest != index) {
int temp = array[index-1];
array[index-1] = array[largest-1];
array[largest-1] = temp;
maxHeapify(array, largest, heapSize);
}
}
private static void printArray() {
for (int i : input) {
System.out.print(i + " ");
}
}
}
选择排序 - Java实现
/**
* "选择排序",《算法导论》习题2.2-2
* Consider sorting n numbers stored in array A by first
* finding the smallest element of A and exchanging it with the element in A[1].
* Then find the second smallest element of A, and exchange it with A[2].
* Continue in this manner for the first n - 1 elements of A. Write pseudocode
* for this algorithm, which is known as selection sort . What loop invariant
* does this algorithm maintain? Why does it need to run for only the first n -
* 1 elements, rather than for all n elements? Give the best-case and worst-
* case running times of selection sort in θ- notation.
* 伪代码:
* for i <- 1 to length[A]-1
* key <- A[i]
* index <- i
* for j <- 2 to length[A]
* key = key < A[j] ? key : A[j];
index = key < A[j] ? index : j;
* A[index] = A[i];
A[i] = key;
* @author lihzh(OneCoder)
* @OneCoder-Blog http://www.coderli.com
*/
public class SelectionSort {
private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 };
public static void main(String[] args) {
for (int i=0; i<input.length-1; i++) {//复杂度:n
int key = input[i];
int index = i;
//比较当前值和下一个值的关系,记录下较小值的值和索引数,用于交换。
for (int j=i+1; j<input.length; j++) {//复杂度:1+2+...+(n-1)=θ(n^2)
key = key < input[j] ? key : input[j];
index = key < input[j] ? index : j;
}
input[index] = input[i];
input[i] = key;
}
/*
* 复杂度分析:
* 最坏情况下,复杂度为:n*n=n^2(若略微精确的计算即为:n-1+1+2+...+n-1=(2+n)*(n-1)/2,
* 所以复杂度仍为n^2。
* 最优情况下,由于不论原数组是否排序好,均需要全部遍历以确定当前的最小值,所以复杂度不变仍未n^2。
*
*/
//打印数组
printArray();
}
private static void printArray() {
for (int i : input) {
System.out.print(i + " ");
}
}
}
插入排序 - Java实现
/**
* "插入排序 ",对少量元素进行排序的有效算法。
* 《算法导论》原文摘要:
* Insertion sort works the way many people sort a hand
* of playing cards. We start with an empty left hand and the cards face down on
* the table. We then remove one card at a time from the table and insert it
* into the correct position in the left hand. To find the correct position for
* a card, we compare it with each of the cards already in the hand, from right
* to left, as illustrated in Figure 2.1. At all times, the cards held in the
* left hand are sorted, and these cards were originally the top cards of the
* pile on the table.
* 伪代码如下:
* for j<- 2 to length[A]
* do key <- A[j]
* >Insert A[j] into the sorted sequence A[1..j-1] (>符号代表后面的部分是注释)
* i <- j-1
* while i>0 and A[i]>key
* do A[i+1] <- A[i]
* i <- i-1
* A[i+1] <- key
* 算法复杂度:n^2
* @author lihzh(OneCoder)
* @OneCoder-Blog http://www.coderli.com
*/
public class InsertionSort {
private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 };
public static void main(String[] args) {
//从数组第二个元素开始排序,因为第一个元素本身肯定是已经排好序的
for (int j = 1; j < input.length; j++) {// 复杂度 n
int key = input[j];
int i = j - 1;
//依次跟之前的元素进行比较,如果发现比前面的原素小,则交换位置,最终完成排序。
while (i >= 0 && input[i] > key) {//复杂度:1+2+...+(n-1)=Θ(n^2)
input[i + 1] = input[i];
input[i] = key;
i--;
}
}
/*
* 所以最终复杂度为n*n=n^2。最优情况下(即都已经排列好的情况下),第二个n=1, 所以在最优情况下,复杂度为n。
*/
// 打印数组
printArray();
}
private static void printArray() {
for (int i : input) {
System.out.print(i + " ");
}
}
}
利用堆合并数组- Java实现
/**
* 《算法导论》习题6.5-8: Give an θ(nlgk)-time algorithm to merge k sorted lists into
* one sorted list, where n is the total number of elements in all the input
* lists. (Hint: Use a min-heap for k-way merging.)
* @author lihzh(OneCoder)
* @OneCoder-Blog http://www.coderli.com
*/
public class Exercice658 {
// 给定3(k=3)个已排好序的数组,这里考虑简单情况,
// 即所有数组包含的元素个数一致。
// 注:因为已实现MaxHeapify算法,所以此处用最大到小排好序的数组举例
private static int[] arrayOne = new int[] { 7, 4, 3, 1 };
private static int[] arrayTwo = new int[] { 10, 9, 5, 2 };
private static int[] arrayThree = new int[] { 12, 11, 8, 6 };
// 已排好序中的数组中,元素的个数
private static int length = arrayOne.length;
// 已排好序的数组的个数
private static int k = 3;
// 所有数组中元素的总个数
private static int n = length * k;
// 合并后输出数组
private static int[] output = new int[n];
public static void main(String[] args) {
mergeSortedArrays();
// 打印数组
printArray();
}
/**
* 合并已排序的数组,利用<code>;PriorityQueue</code>;中 的insert和extractMax算法实现
* 复杂度分析:
* 根据当前实现,复杂度应该为:θ(nk),并不满足题意。
* 但是所用思路,与习题参考中的思路一致,参考原文如下:
* Given k sorted lists with a total of n elements show how to merge them in O(n lg k) time. Insert
* all k elements a position 1 from each list into a heap. Use EXTRACT-MAX to obtain the rst element
* of the merged list. Insert element at position 2 from the list where the largest element originally
* came from into the heap. Continuing in this fashion yields the desired algorithm. Clearly the
* running time is θ(n lg k).
* 差异之处在于,当从堆中取出一个元素之后,需要知道这个元素原来所属数组,这里也需要去判断,这里耗时K。另外,在插入的时候,
* 也需要判断
*/
private static void mergeSortedArrays() {
// 利用前面实现的优先级队列中的方法,构造一个容量为k=3的堆
PriorityQueue priQueue = new PriorityQueue(k);
int count = 0;
//用于保存各数组当前插入元素索引位的数组
int[] indexArray = new int[k];
int arrayChoice = 0;
//初始情况,向堆中插入各数组首位元素
//复杂度:θ(klgk)
priQueue.insert(arrayOne[0]);
priQueue.insert(arrayTwo[0]);
priQueue.insert(arrayThree[0]);
for (int i = 0; i < n; i++) {// 该循环复杂度:θ(n)
// 取出当前最大值,复杂度θ(lgk)
int value = priQueue.extractMax();
count++;
// 赋值
output[n-count] = value;
// 判断当前取出的最大元素所在数组,硬编码:(疑惑:复杂度θ(k),因为最差会进行k次比较,此处如何优化)
if (value == arrayOne[indexArray[0]]) {
arrayChoice = 0;
} else if (value == arrayTwo[indexArray[1]]) {
arrayChoice = 1;
} else {
arrayChoice = 2;
}
// 相应的索引位+1
indexArray[arrayChoice]++;
// 向堆中插入元素,如果备选数组中还有元素,则继续从该数组选取(疑惑:采用switch语句,复杂度是否降到θ(lgk)以下)
// 根据:http://hi.baidu.com/software_one/blog/item/254990dfd96aee205982ddcb.html 中介绍,似乎可以。
// 望高手指导!
switch (arrayChoice) {
case 0 :
if (indexArray[0] < length) {
priQueue.insert(arrayOne[indexArray[0]]);
}
break;
case 1 :
if (indexArray[1] < length) {
priQueue.insert(arrayTwo[indexArray[1]]);
}
break;
case 2 :
if (indexArray[2] < length) {
priQueue.insert(arrayThree[indexArray[2]]);
}
break;
}
}
}
private static void printArray() {
for (int i : output) {
System.out.print(i + " ");
}
}
}
快速排序 - Java实现
/**
* 快速排序,《算法导论》第七章
* @author lihzh(OneCoder)
* @OneCoder-Blog http://www.coderli.com
*/
public class QuickSort {
//待排数组
private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 };
public static void main(String[] args) {
//快速排序
quickSort(input, 0, input.length - 1);
//打印数组
printArray();
}
/**
* 快速排序,伪代码:
* QUICKSORT(A, p, r)
* 1 if p < r
* 2 then q → PARTITION(A, p, r)
* 3 QUICKSORT(A, p, q - 1)
* 4 QUICKSORT(A, q + 1, r)
*
* PARTITION(A, p, r)
* 1 x → A[r]
* 2 i → p - 1
* 3 for j → p to r - 1
* 4 do if A[j] <= x
* 5 then i → i + 1
* 6 exchange A[i] ⟷ A[j]
* 7 exchange A[i + 1] ⟷ A[r]
* 8 return i + 1
* 复杂度,最坏情况下:θ(n^2)
* 一般平衡情况:θ(nlgn)
* @param array 待排数组
* @param from 起始位置
* @param to 终止位置
*/
private static void quickSort(int[] array, int from, int to) {
if (from < to) {
int temp = array[to];
int i = from - 1;
for (int j = from; j < to; j++) {
if (array[j] <= temp) {
i++;
int tempValue = array[j];
array[j] = array[i];
array[i] = tempValue;
}
}
array[to] = array[i+1];
array[i+1] = temp;
quickSort(array, from, i);
quickSort(array, i + 1, to);
}
}
private static void printArray() {
for (int i : input) {
System.out.print(i + " ");
}
}
}
slf4j+logback配置方式和logback.groovy配置文件
最近看到slf4j+logback的日志方案,并且介绍说,与log4j出自同一作者且做了不少优化,所以决定从commons-logging+log4j切换过来。
- logback官网:(该作者即为log4j的作者)http://logback.qos.ch/
切换方式非常简单,在原有基础上加入如下jar包即可。
- slf4j-api-1.6.2.jar
- jcl-over-slf4j-1.6.2.jar \\用于桥接commons-logging 到 slf4j
如果直接使用slf4j+logback的方案则无需此jar logback目前最新版是1.0.3
Maven依赖如下:
<dependency>
<groupId>org.slf4j</groupId>
<artifactId>slf4j-api</artifactId>
<version>1.6.2</version>
</dependency>
<dependency>
<groupId>org.slf4j</groupId>
<artifactId>jcl-over-slf4j</artifactId>
<version>1.6.2</version>
</dependency>
<dependency>
<groupId>ch.qos.logback</groupId>
<artifactId>logback-core</artifactId>
<version>0.9.29</version>
</dependency>
<dependency>
<groupId>ch.qos.logback</groupId>
<artifactId>logback-classic</artifactId>
<version>0.9.29</version>
</dependency>
logback会依次读取以下类型配置文件:
- logback.groovy
- logback-test.xml
- logback.xml 如果均不存在会采用默认配置
logback.xml样例如下:
<?xml version="1.0" encoding="UTF-8"?>
<configuration>
<appender name="stdout" class="ch.qos.logback.core.ConsoleAppender">
<encoder class="ch.qos.logback.classic.encoder.PatternLayoutEncoder">
<pattern>%d{yyyy/MM/dd-HH:mm:ss.SSS} %level [%thread] %class:%line>>%msg%n</pattern>
</encoder >
</appender>
<root level="INFO">
<appender-ref ref="stdout" />
</root>
</configuration>
其中pattern属性的意义跟log4j基本相同,具体可参考
logback.groovy的样例代码如下:
import static ch.qos.logback.classic.Level.DEBUG
import ch.qos.logback.classic.encoder.PatternLayoutEncoder
import ch.qos.logback.core.ConsoleAppender
appender("CONSOLE", ConsoleAppender) {
encoder(PatternLayoutEncoder) {
pattern = "%d{yyyy/MM/dd-HH:mm:ss} %-5level [%thread] %class{5}:%line>>%msg%n"
}
}
root(DEBUG, ["CONSOLE"])
官方提供了logback.xml->logback.groovy的转换工具
对于logback.groovy的使用,需要注意: logback.groovy需要放在源码包的根目录下,否则会找不到。 在eclipse中,如果安装了groovy的插件,需要将放置logback.groovy的源码包位置设置为groovysrcipt的所在位置,即在编译的时候不将goorvy编译成class文件,而是直接将groovy脚本复制到output path下。否则仍无法生效。
Java 利用ASM读取变量值(Field value)问题研究
最近在学习Spring源码的过程中,遇到了spring-asm工程的重新打包的问题,于是突然就想研究一下asm这个开源字节码操作工具。秉承我的一贯风格,想到啥就立马学啥。 对于开源产品,我的一贯风格就是通过其官方提供的源码版本管理地址(svn/git等),直接下载最新代码,构建Java工程,直接通过工程依赖的方式研究学习。(你说这样跟依赖jar包并且绑定源码比有啥好处? 一般情况下差不多,最多就是,我可以随时更新代码,可以本地随意修改代码等等呵呵。个人喜好。)
废话不多说,进入正题。我当时想研究的主要问题,就是想尝试通过ASM读取到class文件中声明的变量及其值(其实ASM的主要功能应该是动态生成字节码)。其他东西,我认为是可以触类旁通的。所以,我简单阅读了一下其官方文档,发现其tree API还是非常简单易懂,好上手的。所以,立即动手,我先新建了一个待读取的类。叫ForReadClass,内容如下:
/**
* @author lihzh
* @date 2012-4-21 下午10:18:46
*/
public class ForReadClass {
final int init = 110;
private final Integer intField = 120;
public final String stringField = "Public Final Strng Value";
public static String commStr = "Common String value";
String str = "Just a string value";
final double d = 1.1;
final Double D = 1.2;
public ForReadClass() {
}
public void methodA() {
System.out.println(intField);
}
}
然后编写读取类如下:
/**
* @param args
* @author lihzh
* @date 2012-4-21 下午10:17:22
*/
public static void main(String[] args) {
try {
ClassReader reader = new ClassReader("cn.home.practice.bean.ForReadClass");
ClassNode cn = new ClassNode();
reader.accept(cn, 0);
System.out.println(cn.name);
List<FieldNode> fieldList = cn.fields;
for (FieldNode fieldNode : fieldList) {
System.out.println("Field name: " + fieldNode.name);
System.out.println("Field desc: " + fieldNode.desc);
System.out.println("Filed value: " + fieldNode.value);
System.out.println("Filed access: " + fieldNode.access);
}
} catch (IOException e) {
e.printStackTrace();
}
}
代码很简单,并且语义也很清晰。Tree API,顾名思义是根据Class的结构,一层层读取其中的信息。但是,当我打印出值的时候,结果却让我大跌眼镜。所有vlaue都是null。
注:第一次读取的时候ForReadClass中,只有三个变量,并且既不是final也不是基本数据类型
查看接口说明,发现其是从常量池中读取的值,并且要求filed类型必须是Integer/Double/….的。于是我又构造了几个final的和基本数据类型,如上所示。这次终于有值了。有值的都是 final 并且是基本数据类型的(String类型的必须是String s = “str”方式声明的,如果是new String(“str”)的也读取不到)
看似问题解决了一个,但是接下来的问题就是,那些非final和非基本数据类型的变量的值该如何获取呢?这个问题着实困扰了许久,google了一大顿(ps:还是翻墙的google)也没找到答案,网上用ASM的多是用其生成字节码。不死心我的决定自己研究。在网上的一篇博客中,我注意到一个样例,给出的是用MethodVisitor来改变一个变量的值。于是,我立即把目光从FieldNode转移到MethodNode之上。通过观察变异后class字节码,几番周折,有了如下代码:
/**
* @param args
* @author lihzh
* @date 2012-4-21 下午10:17:22
*/
public static void main(String[] args) {
try {
ClassReader reader = new ClassReader(
"cn.home.practice.bean.ForReadClass");
ClassNode cn = new ClassNode();
reader.accept(cn, 0);
List<MethodNode> methodList = cn.methods;
for (MethodNode md : methodList) {
System.out.println(md.name);
System.out.println(md.access);
System.out.println(md.desc);
System.out.println(md.signature);
List<LocalVariableNode> lvNodeList = md.localVariables;
for (LocalVariableNode lvn : lvNodeList) {
System.out.println("Local name: " + lvn.name);
System.out.println("Local name: " + lvn.start.getLabel());
System.out.println("Local name: " + lvn.desc);
System.out.println("Local name: " + lvn.signature);
}
Iterator<AbstractInsnNode> instraIter = md.instructions.iterator();
while (instraIter.hasNext()) {
AbstractInsnNode abi = instraIter.next();
if (abi instanceof LdcInsnNode) {
LdcInsnNode ldcI = (LdcInsnNode) abi;
System.out.println("LDC node value: " + ldcI.cst);
}
}
}
MethodVisitor mv = cn.visitMethod(Opcodes.AALOAD, "<init>", Type
.getType(String.class).toString(), null, null);
mv.visitFieldInsn(Opcodes.GETFIELD, Type.getInternalName(String.class), "str", Type
.getType(String.class).toString());
System.out.println(cn.name);
List<FieldNode> fieldList = cn.fields;
for (FieldNode fieldNode : fieldList) {
System.out.println("Field name: " + fieldNode.name);
System.out.println("Field desc: " + fieldNode.desc);
System.out.println("Filed value: " + fieldNode.value);
System.out.println("Filed access: " + fieldNode.access);
if (fieldNode.visibleAnnotations != null) {
for (AnnotationNode anNode : fieldNode.visibleAnnotations) {
System.out.println(anNode.desc);
}
}
}
} catch (IOException e) {
e.printStackTrace();
} catch (SecurityException e) {
e.printStackTrace();
} catch (IllegalArgumentException e) {
e.printStackTrace();
}
}
从AbstractInsnNode中,我终于取到了其他变量的值。
总结:之所以大费周章,主要还是因为我对Class字节码的不熟悉,网上之所以少有我遇到的问题,我想一方面是由于,我的使用场景与大多数人不同,另一方面可能是由于使用ASM的人大多对字节码还算了解,不会犯我这样的错误。:)
呵呵,总而言之,虽然耗费一定的时间,总归还有收获,心满意足。