JVM运行期内存结构(Run-Time Data Areas)

这里翻译自:http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-2.html 第2.5节运行期数据区域划分.

JVM规范定义了程序在运行期间不同数据区域的划分。其中部分数据是在JVM启动时创建,同时在JVM结束时消失。另一些则与线程相关,在线程被创建时被创建,线程结束时这部分数据被删除。
总共的区域划分为 PC寄存器线程执行栈数据堆方法区常量池本地执行栈,共6个区域。

A PC寄存器

在同一时刻,在JVM内部有多个线程在同时执行。在某一时刻,线程就会取出一条指令进行执行,那么PC寄存器就表示当前线程正在执行哪一条指令,即正在执行指令的一个引用指针,以方便进行定位和执行下一条指令。即寄存器会同时记录每个线程的执行点。如果当前线程正在执行native方法时,寄存器的值是未定义的。

B 线程执行栈

线程执行栈即表示每一个线程在执行不同的方法所创建的按方法区分的帧。就比如在调用ex.printStackTrace时,每一个调用方法就表示一个方法帧。在每个方法帧上,存储着在当前执行点上存储的一些临时变量以及下个方法返回的数据值。在具体执行时,当调用一个新方法时,就会创建一个新的执行帧,同时push到当前的执行栈中;当方法返回时,就会把当前的执行帧从执行栈中pop掉。

在具体实现时,每个执行栈的内存并没有要求一定是连续的。
在某些情况下,特别是在递归调用中,经常会报StackOverflowError的错误,就是因为创建的执行帧太多,而每个执行帧会占用一定的内存。当总执行栈超过设定值时,就会发生这个异常。比如,在Oracle JVM上,可以通过-Xss来指定每个执行栈的最大内存。

继续阅读“JVM运行期内存结构(Run-Time Data Areas)”

java中删除avl树节点方法

    在很多的数据结构书上,关于avl树,都有记录如何进行插入节点以及如何进行树的翻转操作。但对于,如何删除节点,却都是作为练习或者没有提供相应的代码以供参考。笔者,根据插入节点的实现,并部分参考网上其它c++代码,提出一个简单的删除节点的实现,并记录如下。

    删除一个节点的主要步骤如下所示:

  1. 如果是null节点,则直接返回null
  2. 如果删除的值<当前节点,则转入left节点进行递归删除
  3. 如果删除的值>当前节点,则转入right节点进行递归删除
  4. 如果删除的值为当前节点,如果当前节点只有一个子树,则直接返回该子树
  5. 如果删除的值为当前节点,且当前节点有两个子树,则将当前值更改为右子树中最小的节点值,并递归在右子树中删除该节点值
  6. 重新修正该处理节点的height值
  7. 对处理节点进行重新翻转处理,以修正在删除过程中可能出现的树不平衡情况

    经过以上的逻辑,那么实现代码就不那么困难了。简单实现如下所示:

继续阅读“java中删除avl树节点方法”

通过递归建立avl树以及如何删除节点(C++版)转

    本文转自 http://www.asiteof.me/2010/06/avl/
    用到的树的节点如下所示:

struct node{
     int data;
     int bf;
     node *lchild;
     node *rchild;
};

    其中data表示该节点存储数据,bf表示当前节点的高度,lchild指向当前节点的左儿子,rchild指向当前节点的右儿子。

    对于二叉树的建立与节点的插入在本次实验中采用递归的方法,首先找到插入节点,然后递归的判断,如果节点左儿子与右儿子的高度差大于等于2,则对该节点进行平衡调整。
    对于二叉树的删除操作,先递归的搜索要删除的节点A,用该节点的右儿子的最左儿子B代替该节点,以A的右儿子和B当前的数值作为线索继续遍历,只到找到B,删除B。然后递归的对B的祖先节点进行平衡调整,具体调整操作和二叉树的插入操作的平衡调整相同。

    对二叉树的平衡调整过程,主要包含四种旋转操作:LL,LR,RR,RL。
     LR由当前节点左儿子的一次RR旋转和当前节点的一次LL旋转构成。同理, RR由当前节点右儿子的一次LL旋转和当前节点的一次RR旋转构成。

继续阅读“通过递归建立avl树以及如何删除节点(C++版)转”

深入理解java快速排序的正确性

    说起快速排序,很多人都能够写出一个正确的快速排序,但就快速排序的正确性,就无从探究了。为什么说写出来的快速排序就是正确的。在快速排序中间的关键几步,以什么样的数据组织来保障快速排序的正确性。本文以《数据结构与算法 Java语言描述》中所描述的快速排序来进行理解,以查看其中的正确性。

    首先查看排序的整体伪代码:

public static void quicksort(int[] a, int left, int right) {
                //第1步
		if(left + CUTOFF > right) {
			insertsort(a, left, right);
			return;
		}
                //第2步
		int pivot = med(a, left, right);
                //第3步
		int i = left, j = right - 1;
		while(true) {
			while(a[++i] < pivot)
				;
			while(a[--j] > pivot)
				;
                        //第4步
			if(i < j)
				swap(a, i, j);
			else
				break;
		}
                //第5步
		swap(a, i, right - 1);
                //第6步
		quicksort(a, left, i - 1);
		quicksort(a, i + 1, right);
	}

    其中,中间所涉及的med算法如下所示:

private static int med(int[] a, int left, int right) {
		int center = (left + right) / 2;
		if(a[center] < a[left])
			swap(a, left, center);
		if(a[right] < a[left])
			swap(a, left, right);
		if(a[right] < a[center])
			swap(a, center, right);
		swap(a, center, right - 1);
		return a[right - 1];
	}

    以上即整个快速排序算法以及相对应的获取pivot的算法。
    那么我们首先从源码上分析整个排序算法的正确性,以及在特殊的控制点上是如何取得正确的(在后续的说明中 小于的意思为小于或等于 大于的意思为大于或等于,即不对=pivot的数进行特殊处理)。

继续阅读“深入理解java快速排序的正确性”

冒泡,选择,插入排序的简单理解和实现

    最近关注了一下c++,又想到很久没有碰的数据结构又快忘完了。又开始从简单的排序开始温习了。作为排序的最经典也是最简单的方法,冒泡,选择,插入这三种排序方法是最让人能够理解的。当然,三种方法的效率也是差不多的,都是O(n2)时间。以下就3种实现,根据自己的理解,简单的描述一番。以下实现均以由小到大的顺序进行实现。

    冒泡排序:

/**
	 * 演示冒泡排序算法
	 * 实质在于通过每次循环的冒泡将最小的放到第一位,因此从整个未排序的数组中,从后将最小的位往前推
	 */
	private static void maopaoSort(int[] ints) {
		for(int i = 0;i < ints.length;i++) {
			for(int j = ints.length - 1;j > i;j--) {//从后面往前开始冒
				if(ints[j] < ints[j - 1])
					swap(ints, j, j - 1);//将小的往前冒,即做一次转换操作
			}
		}
	}

    由上可知,冒泡就是一个将整个数组当中最小的数字,从最后面慢慢地往前冒的过程。假设最小的数在第N位,那么在冒泡的过程中,就是首先通过N冒泡,将N冒到N-1位上,再冒到N-2上(由N-1与N-2比较),最后一直冒到数组的第0位。这样一次子循环下来,最小的数就冒好了。接下来,就开始冒第二小的数了,那么这个数自然就放到i+1即第1位上了。

    选择排序:

/**
	 * 演示选择排序算法
	 * 选择排序的实质在于每次循环从后面的数中选择一个最小的数,放到数组的最前面
	 * 因此每次的比较在于将当前最小的数与当前数相比较,比较之后将小的放到正确的位置上
	 */
	private static void xuanzeSort(int[] ints) {
		for(int i = 0;i < ints.length;i++) {
			int m = i;//假设当前最小的数的下标即为i
			for(int j = i + 1;j < ints.length;j++) {
				if(ints[m] > ints[j]) {//与最小的数比,即与下标为m的数比
					m = j;//重置最小的数的下标
				}
			}
			swap(ints, i, m);//交换两个数,将最小的数放到当前位置上
		}
	}

    由代码可以看出,选择排序和冒泡排序差不多,区别在于在选择排序当中,不再需要两两对比和交换,而是将最小的数与循环中的数进行比较,而且只需要记录最小的数的下标即可。最后将最小的数的下标和当前正在处理的数下标交换即可。如当前正确排到第3位了,前2位自然是已经排好序的了。假设第5位数是最小的,那么最后,就是交换第3位和第5位,然后又从第4位数进行处理了。

    插入排序:

/**
	 * 演示插入排序
	 * <p/>
	 * 实质在于将当前位置上的数插入到前面已经排好序的数组当中,即在进行排序时,当前位置之前的数组实际上是已
	 * 经排好序了的
	 */
	private static void charuSort(int[] ints) {
		for(int i = 1;i < ints.length;i++) {
			int j = i;//记录当前操作的数的下标,即从当前下票开始
			int temp = ints[j];//记录当前要操作的数
			while(j > 0 && temp < ints[j - 1]) {//只有当操作的数小于前面的数时才往前移位置
				ints[j] = ints[j - 1];//将前面的一个数往后移,即将前一个数的值放到后一个下标当中
				j--;
			}
			//找到最终的一个下标,当前数比下标前一个数小,下标后面的数在比较过程中均往后移了一位
			ints[j] = temp;
		}
	}

    插入排序是和前面两个排序最不相同的排序方法了。前面两种方法即是将已经处理且不会再进行二次处理的的数放到一边,再处理剩余的数。而插入是假设前面的数是排好序的,并不关心没有排序的数是否就一定要比排好序的数小。它所做的即是将当前正在处理的数放到前面处理好排好序的数的中间。即原来处理好的数的长度为5,当增加当前处理数之后,长度就变为6了。且数根据一定的规则放到6位长度的数中的其中一个位置上。
    插入核心的地方就是处理将数往前面的数组里面插入的过程,在这里,当然可以使用swap,将当前处理的数和前面比较的数进行调换位置,但考虑到效率上的原因。这里直接将前面比较的数往后放,等到找到一个可以放当前处理数的一标时,再将此数放到正确的位置上即可。

    总结:

    在实现中,前面三个算法在实现的过程当中,肯定有很多的陷阱。如何更好地实现一个排序,并考虑到效率和理解程序上。一个简单的程序也可以写得很长。但简单的算法肯定要考虑到很多种情况,并且要在大多数的场景下都可以很好地工作。重在理解,理解好了,程序就好写了。