Skip to main content

Jquery Easyui中的坑

Jquery Easyui是一个不错的前端UI框架,它以非常低的学习和编程成本,尽可能的用非标准的HTML属性和特殊的css来标记页面,由框架统一解析为前端UI控件。
但是,框架的作者采用了类似半开源的方式,license可以使的软件免费使用,但是,它对javascript源码进行了混淆,不发布源码,文档虽然还算整理的不错,但是一旦遇到坑,那就十分捉急。但是,我对其用来做demo的速度赞不绝口,所以总结各种坑与大家共享如下:

坑1:DataGrid如何使用动态的查询参数?
场景如下,一个Datagrid上额外增加了几个表单参数,要动态的使用这些参数,就很麻烦。
如果你使用:

$('#orderGrid').datagrid('reload',
{
//参数对
});

这种情况下,每个表单的onchange都不想这么调用一遍,代码十分重复,而且一旦表单多,逻辑复杂,基本不可能实现。

另外一种情况是使用queryParams,但是这个参数设置后就不变了,是静态参数,
var orderGrid = $('#orderGrid').datagrid({
queryParams: {
startDate: $('#startDate').datebox('getValue'),
endDate:$('#endDate').datebox('getValue')
}
});

实现从queryParams入手,
一,获得到参数
var param=$('#orderGrid').datagrid('options').queryParams;
二,修改参数
param.startDate = ... ... ;
param.endDate = ... ...;

三,把参数设置回去(这一步很重要只有重设才会触发更改!)
$('#orderGrid').datagrid('options').queryParams=param;

坑二:datagrid的$(‘#orderGrid’).datagrid(‘getChecked’)和$(‘#orderGrid’).datagrid(‘getSelection’)等方法获取选中不一致的问题。

选中事件onCheck, onUncheck, onCheckAll, onUncheckAll配合使用时,建议使用回调参数
onUncheck:function(index,row)的index和row参数来决定选中行。直接使用$(‘#orderGrid’).datagrid(‘getSelection’)等方法得到的选择状态莫名其妙的错误和不一致。

高效的字符串匹配器

使用场景

String html="......<script type="text/javascript.........</script>"";

StringMatcher matcher = new StringMatcher("</script>");


for(int i=0;i<html.length;i++){

    matcher.push(html.charAt(i));

    if(matcher.isTarget()){

        //do something

    }

}
/**
 * StringMathcer是一个利用了循环链表原理的数组型字符串匹配器.
 * 
 * Matcher主要是在字符串处理中匹配字串,原理是把字符push到匹配器中 进行比较,匹配器不提供remove(int index)方法,只能放或者清空。
 * 用单纯的数组进行匹配时,很容易地,数组会满而导致大量的元素移动操作, 代价交代,用循环链表只需修改两次指针位置即可。
 * 为了更多的减少条件判断,在构造方法中就已经让数组处于满的状态。
 * 
 * @author maoanapex88@163.com
 * 
 */
public class StringMatcher {
	char[] cache;
	int start;
	String target;

	public StringMatcher(String s) {
		this.target = s;
		int length = s.length();
		cache = new char[length];
		start = 0;
		for (int i = 0; i < cache.length; i++)
			cache[i] = 128;
	}

	public void push(char c) {
		cache[start++] = c;
		start %= cache.length;
	}

	public boolean isTarget() {
		if (cache[(start + 1) % cache.length] == 128)
			return false;
		int index = 0;
		for (int i = start; i < cache.length; i++, index++)
			if (cache[i] != target.charAt(index))
				return false;
		for (int i = 0; i < start; i++, index++)
			if (cache[i] != target.charAt(index))
				return false;
		return true;
	}

	public boolean isTarget(boolean ignoreCase) {
		if (cache[(start + 1) % cache.length] == 128)
			return false;
		int index = 0;
		for (int i = start; i < cache.length; i++, index++) {
			if (ignoreCase && cache[i] != target.charAt(index)
					&& cache[i] - target.charAt(index) != 32
					&& cache[i] - target.charAt(index) != -32)
				return false;
		}
		for (int i = 0; i < start; i++, index++) {
			if (ignoreCase && cache[i] != target.charAt(index)
					&& cache[i] - target.charAt(index) != 32
					&& cache[i] - target.charAt(index) != -32)
				return false;
		}
		return true;
	}

	/**
	 * clear
	 */
	public void clear() {
		start = 0;
		for (int i = 0; i < cache.length; i++)
			cache[i] = 128;
	}

	/**
	 * @return
	 */
	public int length() {
		return target.length();
	}
}

为Java实现LinkedArray

前面的文章中,我们通过分析java的排序,顺便分析了ArrayList和LinkedList,这两个各有优缺点,那么我们能不能折合两者优点呢?我思考了一个问题-信息率,也就是为了存一个我希望存的对象而额外耗费的空间,

  • 对于ArrayList,每个数组的下标对于的地址单元存量一个对象指针,1:1的存,但是问题是在于增量导致的数组增长和整体数组的copy实在太损耗性能
  • 对于LinkedList,每一个链表节点,要额外增加一个前续来维持链表结构,1:2,事实JDK的LinkedList是prev和next都记录的,是双向链表,为1:3

既然有这个问题,我们可不可以增加信息率来提高些平均性能呢?如下

  • ArrayList: [a0,a1,a2,…,an]
  • LinkedList:  a0<->a1<->a2<->…..an
  • LinkedArray: [a0,a1,a2,….ai]<->[ai+1,….aj]<—>[aj+1,………an]

LinkedArray是用链表为基础,但是链表的节点是一个数组,这样节点的信息率上升为n:n+2,(n是数组的大小),这样可以这种一些两者的性能。

package net.sourceforge.util;

import java.util.AbstractList;
/**
 * 
 * @author maoanapex88@163.com
 * 
 * @param <E>
 */
public class LinkedArray<E> extends AbstractList<E> {
	public static final int DEFAULT_ARRAY_SIZE=10;
	public static final int DEFAULT_CATACITY=10;
	
	private int arraySize=DEFAULT_ARRAY_SIZE;
	private int size;
	
	private transient ListNode<E> head,tail;
	
	public LinkedArray(){
		this(DEFAULT_CATACITY,DEFAULT_ARRAY_SIZE);
	}
	public LinkedArray(int initialCapacity){
		this(initialCapacity,DEFAULT_ARRAY_SIZE);
	}
	public LinkedArray(int initialCapacity, int arrayLengthInNode){
		if(initialCapacity<=0) throw new IllegalArgumentException("initialCapacity < 0");
		if(arrayLengthInNode<=0) throw new IllegalArgumentException("arrayLengthInNode < 0");
		
		arraySize=arrayLengthInNode;
		
		int nodeCount=initialCapacity/arrayLengthInNode;
		if(initialCapacity%arrayLengthInNode!=0) nodeCount++;
		
		ListNode<E> pre=null;
		for(int i=0;i<nodeCount;i++){
			ListNode<E> node=new ListNode<E>(arraySize);
			if(i==0) head=node;
			else{
				pre.next=node;
				node.previous=pre;
			}
			
			if(i==nodeCount-1) tail=node;
			pre=node;
		}
		size=0;
	}
	
	@Override
	public E remove(int index) {
		rangeCheck(index);
		ListNode<E> node=findNodeByIndex(index);// must not be null
		E ret=node.objArray[index-node.globalStartIndex];

		int start = index - node.globalStartIndex + 1;
		for (int i = start; i < node.localSize; i++) {
			node.objArray[i - 1] = node.objArray[i];
		}
		node.objArray[arraySize - 1] = null;
		node.localSize--;
		
		if(node.localSize==0) {// remove the empty node
			ListNode<E> pre=node.previous;
			ListNode<E>  next=node.next;
			
			if(pre==null){// equals node is the head node
				node.previous=null;
				head=node;
				updateNode(head,0);
			}
			else{
				pre.next=next;
				if(next!=null) next.previous=pre;
				
				updateNode(pre.next,pre.globalStartIndex+pre.localSize);
			}
		}
		
		else updateNode(node.next,node.globalStartIndex+node.localSize);
		
		size--;
		return ret;
	}
	@Override
	public E set(int index, E element) {
		rangeCheck(index);
		ListNode<E> node=findNodeByIndex(index);// must not be null
		E ret=node.objArray[index-node.globalStartIndex];
		node.objArray[index-node.globalStartIndex]=element;
		return ret;
	}
	@Override
	public void add(int index, E element) {
		if (index > size || index < 0) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
		ListNode<E> node=findNodeByIndex(index);
		if(node==null){// equals to index==size
			if(tail.localSize==arraySize){//tail node's array is full, append a node
				ListNode<E> newNode=new ListNode<E>(arraySize);
				newNode.globalStartIndex=size;
				tail.next=newNode;
				tail=newNode;
			}
			tail.objArray[tail.localSize]=element;
			tail.localSize++;
			if(size==0) head.globalStartIndex=0;
		}
		else{//insert in the middle of node list
			if(node.localSize==arraySize) {//node's array is full
				ListNode<E> next=node.next;
				ListNode<E> newNode=new ListNode<E>(arraySize);
				node.next=newNode;
				newNode.previous=node;
				
				newNode.next=next;
				if(next!=null) next.previous=newNode;
				
				newNode.objArray[newNode.localSize]=element;
				newNode.localSize++;
				updateNode(newNode,node.globalStartIndex+node.localSize);
			}
			else {//node's array is not full
				node.objArray[node.localSize]=element;
				node.localSize++;
				updateNode(node.next,node.globalStartIndex+node.localSize);//node.next must not be null
			}
		}
		size++;
	}
	private void updateNode(ListNode<E> node, int myGlobalStartIndex) {
		if(node==null) return;
		node.globalStartIndex=myGlobalStartIndex;
		if(node.localSize!=0) updateNode(node.next,node.globalStartIndex+node.localSize);
	}
	
	public E get(int index) {
		rangeCheck(index);
		ListNode<E> cur=findNodeByIndex(index);
		if(cur==null) throw new IllegalStateException("This should be an inner error, findNodeByIndex can not return null when used by get method. index="+index);
		return cur.objArray[index-cur.globalStartIndex];
	}

	public int size() {
		return size;
	}
	private final ListNode<E> findNodeByIndex(final int index){
		ListNode<E> cur=head;
		while(cur!=null) {
			if(cur.globalStartIndex+cur.localSize>index) return cur;
			cur=cur.next;
		}
		return null;
	}
	private final void rangeCheck(int index) {
		if (index<0||index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: "+ size);
	}
	
	public String toString() {
		StringBuilder builder=new StringBuilder();
		ListNode<E> node=head;
		builder.append("{").append(size).append(",");
		while(node!=null) {
			builder.append(node.toString()).append("->");
			node=node.next;
		}
		builder.append("}");
		return builder.toString();
	}
	
	private static class ListNode<E> {
		static final int NULL=-1;
		transient E[] objArray;
		ListNode<E> previous,next;
		int globalStartIndex=NULL, localSize=0;
		@SuppressWarnings("unchecked")
		public ListNode(int arrayLength) {
			super();
			objArray=(E[])new Object[arrayLength];
		}
		@Override
		public String toString() {
			StringBuilder sb=new StringBuilder();
			sb.append("(")
			.append(globalStartIndex).append(",")
			.append(localSize).append(",[");
			for(int i=0;i<localSize;i++) sb.append(objArray[i]).append(",");
			sb.append("])");
			return sb.toString();
		}
	}
}

谈一谈内存排序在JDK中的实现

说起内存排序,我立刻想到了大学和数据结构+算法设计老师的聊天,她推荐我去看《大道至简》,告诉我说,在很多复杂的情况下,先做内排序得到一个有序序列可以排除很多后续难题。我至今受用。

现在的计算机语言越来越高级,门槛越来越低,很多的基础细节再无人问津。万变不离其宗,作为科班出身的程序员,应该时刻温习基础知识。这里和大家一起从源码出发,看看Java中的排序是如何实现的。

还是先温习下内排序:

sort

那么,java中到底是怎么排序的呢?它是使用的哪一种呢?首先,Java中用于给集合排序的API是,你只需要写个排序器或者实现排序接口,然后一句优雅的代码即可搞定排序,

  • Collections.sort用于给List<T> 类型的对象集合排序
  • Arrays.sort用于给T[]对象数组来排序

我们先来看看Collections.sort是怎么工作的,少废话,看源码。

sort-1

Oh!天哪。Java很粗暴的直接用来list.toArray来把对象集合转化为对象数组,直接调用了Arrays.sort方法来sort,sort完成后再赋值回对象集合list中。那么,进一步探究,toArray干了什么?进一步看源代码,java中的list大家常用的是ArrayList和LinkedList,数组实现和链表实现。

  • ArrayList:他非常暴力的直接新建了一个和list一样长度的数组,把ArrayList的data[]都copy了进去

sort-2

  • LinkedList:他也非常暴力的直接新建了一个和list一样长度的数组,然后采用了迭代器(Iteraotr)遍历一遍,把对象都copy了过去。

sort-3

所以,从这里可以得出一个结论,编程过程中,如果能预知目标对象长度,请尽量使用对象数组来来管理多个对象,这里顺便补充些知识点,学过C的人都知道,想操作系统申请内存只能是一段连续的内存单元,编写过C语言的人对malloc和relloc函数很熟悉,一个拥有开辟一片内存,一个是追加内存。LinkedList我们都知道采用链表实现,无所谓浪费空间。ArrayList封装的就是一个数组private transient Object[] elementData; 那么ArrayList是怎么让你可以自由的add(T  t)的呢?我们也来看源代码,它在add方法中每次都要事先调用一句ensureCapacityInternal(size + 1);  // Increments modCount!! 即确保容量的过程,追溯代码如下:

这里是JDK1.7中的源码,JDK1.5之前,ensureCapcity算法有点不一样,但是也是类似,大家自行比较!

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); 这句话等价于 新的数组大小等于当前的大小乘以1.5,也就是增加50%

 

//如果新的大小比要求的最小容量小,则以最小容量为准,换言之,新容量=老容量+1
if (newCapacity – minCapacity < 0)
newCapacity = minCapacity;

 

//处理超大容量,如果对象巨大,达到了最大值(int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;)新数组大小就是 Integer.MAX_VALUE这么大,还不够,代码是OutOfMemoryError!!
if (newCapacity – MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:

 

//最后是让我及其讨厌的内存复制,
elementData = Arrays.copyOf(elementData, newCapacity);
}

 

代码可以看得出,程序员在随意的add的时候,JDK随时在检查给你的对象集合扩容,这个扩展的速度十分可观,可以每次增加50%,如果你使用的构造函数是new ArrayList<YourDomain>,那么初始大小是10,此增长速度就是10*1.5的n次方。所以,这里建议大家:

如果你能预知和估算将要存的对象的数据,请使用new ArrayList<YourDomain>(size); 这会大大减少不断的扩充数组,复制对象….

如果你有频繁的中间插入对象,删除对象等等,请使用LinkedList

我们回到主题,来看排序算法问题,现在我们已经知道不管是Collection还是Array最终都是在Array上进行的排序。

sort-4

我们看一下,jdk7中,进sort首先是一个if – else,说明一下,legacy的英文意思是遗留,这里的意思是,如果你想使用jdk5遗留的老排序算法的话,则使用老的MergeSort,否则使用新的TimSort,注意了,JDK5后排序算法有重大改进!如果你想在jdk5后的jdk中想继续沿用老的排序算法,则可以通过启动参数

-Djava.util.Arrays.useLegacyMergeSort=true

来强制使用遗留的MergeSort。

ok,接下来,我们的按JDK5以前(含5)的归并排序算法和JDK5后的算法分开讨论了。那么JDK5的归并排序算法,请自行看JDK的源码,

void java.util.Arrays.mergeSort(Object[] src, Object[] dest, int low, int high, int off)

对于这个排序,这里无需多言,他是一个实实在在,纯的归并排序算法,只是在size<7,因为数组是在太小了,不需要浪费空间交换时间里,草草一个插入排序解决。

归并算法还记得么,温习一下,“归并排序是将两个或者多个有序序列合并为一个新的有序表”,系统采用的双路归并算法-将一维数组中前后相邻的两个有序序列归并为一个有序序列。

JDK6后的排序算法叫TimSort,一脸懵逼?什么是TimSort,没听过啊,看百科,别百度。 https://en.wikipedia.org/wiki/Timsort

从源码可以看得出,TimSort是一种杂和的排序算法,Java是怎么杂和的呢,上源码如下。

如果你仔细读以下源代码,你会发现其实他很简单,就是把数组分组排序,每组大小如果小于了MIN_MERGE-1=31个,这31个关键字采用binarySort,这个binarySort不做进一步解释,他是简单插入排序的简单改进型。

排序算法如何改进?请记住,尽你所能,

  1. 减少关键字比较次数
  2. 减少记录移动次数

binarySort就是在插入排序的比较关键字过程重不使用for循环,采用折半搜索快速跳跃的方式来比较关键字。就这么简单。

static void sort(Object[] a, int lo, int hi) {

//检查范围,防止数组越界问题
rangeCheck(a.length, lo, hi);
int nRemaining = hi – lo;//还剩下没有排的数组范围

 

//如果仅是1个没有排,显数组已经排好了,一个数他自身是有序的
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted

 

//如果这一段待排序的数组长度<32了,小规模的可以采用简单排序了,上binarySort

// If array is small, do a “mini-TimSort” with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}

 

/**
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/

//这里是核心算法,他采用了栈模拟递归的方法来做分块排序
ComparableTimSort ts = new ComparableTimSort(a);
int minRun = minRunLength(nRemaining);//计算最小的排序长度
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi);//计算下一趟运行的长度

// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;//还有一个强制的最小run的长度force
binarySort(a, lo, lo + force, lo + runLen);//足够小了,开始用小规模快读排序法-基于折半查找的插入排序法
runLen = force;
}

// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);//把排序的块信息压栈
ts.mergeCollapse();

//合并,这个很有意思,把栈元素进行合并,啥意思?很简单 某次排序 得到子序列如下:[2,3,5] [7,9,10],

//第一块的最大值比后一块的最小值小,这俩合并也是有序的。具体的看JDK注释,这是简单粗暴的解释!

// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);

// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();//还强制合并一下下
assert ts.stackSize == 1;//还下个断言,方便是方便,影响性能啊
}

 

 

那么,JDK为什么要摒弃MergerSort,转而改用TimSort呢?也很简单,事关时间和空间转换的法则,我们进入了大数据时代,CPU性能提高很多,MergerSort需要和原来一模一样大小的数据来最归并,这个新的空间复杂度和对象拷贝的过程相当损耗性能。

我们假设一下,一个程序员用了new ArrayList<>();没有指定初始大小,它存了200万个对象,ArrayList的elementData长度是850万,从200万+1到后面都是NULL。

那么MergeSort还没开始,它就要耗费:200万x4bytes = 7812.5K, 合计7.63M。 存对象的数组我理解为一个指针变量,按Int算,不算其他额外对象开销,然后还要花大量时间去Copy200万的对象到新数组,然后排序还没有开始。

TimSort适当的牺牲了时间性能,(我没有仔细测试,实际上不一定有牺牲),但是挽救了大量的内存消耗,性能大大提升。