alibaba fastjson(json序列化器)序列化部分源码解析-1-总体分析

    fastjson官方地址: http://code.alibabatech.com/wiki/display/FastJSON/Home
    从javaeye上看到了阿里一位人士写的fastjson,特别是其中如何将java对象序列化成json字符串这段。笔者比较关注,因为在笔者的项目中就用了一个json序列化器(造的轮子)。就下载下来看了一看,先不说和笔者所用的轮子有何区别,单就用了一个简单的测试器,来测试一下两者的处理速度。测试代码就不贴了,简单地说下测试结果。在jvm充分优化的情况下(for循环执行了很多次之后),笔者所使用的java序列化器处理速度不是很均匀,在结尾有短暂的变化(可能与虚拟机回收有关系);而fastjson在后面的处理过程当中,一般很均匀(后来发现与使用的buf分配方式有关)。最主要的区别莫在于,fastjson的速度那是不能对比了。
    经过分析源码之后,发现fastjson在处理json优化上面还是下了很大的工夫的。笔者准备从以下几个方面对fastjson作一个简单的解析,也让使用fastjson的同学对fastjson有一个简单的认识。
        1    总体分析    分析json序列化的总体思路和解析过程
        2    性能分析A  针对字符生产部分(即outWriter)对不同类型数据的处理和与性能相关处理部分
        3    性别分析B  针对序列化过程部分(即objectSerializer)对不同类型的序列化过程处理和与性能相关处理部分
        4    对象解析分析    对javaBean解析部分和针对字段输出部分的处理和解析
    源码分析基于1.0.5版本。

    总体分析,首先上图,即fastjson的总体处理思想,其实也是所有json序列化器需要考虑的问题。
    在这里,需要考虑的主要有两个部分,一是临时保存在序列化过程中用于储存数据的容器,二是处理对象序列化的序列化器。
    在fastjson中,保存数据的容器使用了wirter,字符输出流,而且是自实现的一个字符输出流。相对原来的writer,追加了很多需要输出的信息的实现,比如输出一个字符串,输出一个字符,输出一个long类型数据等。而处理对象序列化的序列化器,而使用了责任链模式和工厂模式,将不同类型的java对象分散到不同的序列化器当中。而每个序列化器只处理与自身类型相对应的数据信息,这样就避免了在处理时,各种情况交织在一块,逻辑混乱的问题。
    下面就源码本身作一个分析,其中结合两个部分进行分析。

继续阅读“alibaba fastjson(json序列化器)序列化部分源码解析-1-总体分析”

理解希尔排序,缩减增量排序

    话说使用冒泡排序,选择排序和插入排序,都是平均使用了On2的时间,因为它们都是只能一次移动一个位置。如果对于这种情况,即最小的数在最后一位,那么就需要根据具体地算法将数据从最后慢慢地往前移了。对于冒泡排序,时间不会减少;对于选择排序时间也不会减少,因为每次都将第二大的数又再一次放到最后一位了;对于插入排序,会稍微地提高一次效率,因为只能最后一次才需要移动数组。

    那有没有可以一次性移动多个位置的算法呢,那就是希尔排序,它是对于插入排序的地种改进。即使得要进行排序的数,在进行位置移动的时候,可以一次性地移动 多个位置,再不用一位一位地移动了。因为需要一次性移动多个位置,那就需要有一个移动的位置数,即gap。同时,它有一个要求,是必须要满足的,就是对于 数组中的每个数i,在进行移动之后,必须满足Array[i]<=Array[i+gap]。即前面的数必须要比后面的数小(按从小到大排序的 话)。因为每次移动是超过一个位置的移动,因为在移动之后,不能保证前一个数必须比后一个数小,因为还需要进行第二次移动,同时最后必须要有一个 gap=1情况,即最后有一个类似插入排序的动作。只不过到最后进行插入排序时,因为前面的移动已使得数组已相对排序,所以最后一次插入排序速度很快。

    因为有gap的存在,希尔排序实际上就是一个先将数组按照gap大小进行分组,然后对每一个分组进行插入排序的过程。对分组进行插入排序,以保证每个分组都是已经排好序的。这样一直到gap=1时,实际上就是一个将一个大组进行插入排序了。
    这几个主要有两个需要注意的,一就是分组的概念,即gap的概念,使用gap将数组按照一定的间隔进行排序;二就是插入排序的概念,在每个分组中是使用插入排序进行排序的。主要弄清楚这两个部分,那么在理解希尔排序的程序算法时,就能很好地理解了。

    使用gap一般是按照从大到小的顺序,同时也有一个如何使用gap的问题。不同的gap会使得最终的排序效率会不一样,因为这影响实际的分组,以及在多次分组之后,是否存在重复排序的问题。具体的选择这里就直接省略了,直接使用wikipedia中的一个gap数组进行处理。

private static void shellSort(int[] ints) {
		int[] gaps = {1, 5, 13, 43, 113};
		//首先确定gap大小
		int i = 0;
		while(gaps[i] < ints.length)
			i++;
		//进行分组再排序了
		while(i >= 0) {
			//使用当前对应的gap进行分组排序
			int gap = gaps[i];
			//以下就是一个插入排序的过程,以gap为排序间隔进行插入排序
			for(int j = gap;j < ints.length;j++) {
				//初始即从当前排序数开始进行
				int k = j;
				int temp = ints[k];
				//使用temp和k-gap之间进行比较,这里k-gap>=0因此k >= gap
				while(k >= gap && temp < ints[k - gap]) {
					ints[k] = ints[k - gap];
					k -= gap;
				}
				ints[k] = temp;
			}
			//gap往下减1,即使用下一个比较小的gap
			i--;
		}
	}

    希尔排序的效率很高,一般情况下为On3/2,但好的gap数组可以达到On5/4,以致On7/6,这样的效率足够和快速排序相比了。并且,这个理解起来简单。只需要记住以下几点即可:
    插入排序在数组已经接近排好序的情况下,效率很高,可以达到On
    使用希尔选择gap可以将数组从快速的方式组织成接近排好序的情况,使用增量式移位比单个移位更快
    希尔排序的内部始终是插入排序,并且最后一次肯定是一个最原始的插入排序

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

    最近关注了一下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,将当前处理的数和前面比较的数进行调换位置,但考虑到效率上的原因。这里直接将前面比较的数往后放,等到找到一个可以放当前处理数的一标时,再将此数放到正确的位置上即可。

    总结:

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