闲来无事,顺便写一个快排的代码。结果却引发了java.OutOfMemoryError:Java heap space。
首先谈谈快速排序,这是一种在统计上很快的排序,他的核心思想是,在一个数组中随便取一个数作为基准(通常取最后一个),然后把整个数组划分,把比基准小或等于的数放在基准之前,把大于基准的数放在基准之后。然后再分别对基准之前的数组和基准之后的数组进行快速排序。
java 代码:
void quicksort(int[] nums,int begin,int end) { if(end <= begin)return; int p = begin-1; for(int i = begin;i <= end;i++) if(nums[i] <= nums[end]) { p++; int temp = nums[i]; nums[i] = nums[p]; nums[p] = temp; } quicksort(nums,begin,p-1); quicksort(nums,p+1,end); }
这里唯一难理解的就是这个p,这里的思想是,p及其左侧都是小于等于基准的数,而p的右侧都是大于基准的数。因此,遍历这个数组的时候,若数大于基准,则访问下一个,否则把p+1,然后交换p和这个位置上的数,这样就能成功划分。
因为它是快速排序,所以我想小数据量并不能体现它的快速。因此,我使用了一个很大的数组,并且使用随机数填充它。
Random random = new Random(); int[] nums = new int[ (1024*1024*1024) ]; for(int i = 0;i < nums.length;i++) nums[i] = random.nextInt(500000);
这个数组的大小是4个GB,因为一个int是4B,而1024*1024是1M,而1024M是1G。
正当我要运行程序并且统计其运行时间时,悲剧发生了!!!
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
这是一个堆内存溢出错误。
于是我立马想到一个解决方法,那就是 扩大堆内存 !
数组大小只有4GB,我现在给JVM进程5000MB大小的堆内存,也就是大约4.8GB的内存,程序一定是没问题的了。于是我添加了参数-Xms5000m。 这个参数的意义是,最小堆内存为5000MB。
然鹅,结果是
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
why???
要说明这个必须先知道 java内存结构 。
理解了java内存结构之后,才能明白。堆内存又分为,新生代(Young)和老年代(Old),而数组这种大对象一般是直接分配在老年代中。虽然我设置了5000MB的堆内存,但是这5000MB的内存并不都是给老年代的,老年代和新生代内存的默认比例是2,也就是说5000MB里只有2/3是老年代的,也就是3333MB≈3.25GB,这个大小仍然小于数组的4GB,因此现在我设置老-新比例为9,也就是老年代拥有5000MB*0.9=4500MB≈4.39GB,此时已经大于数组所需要的内存大小!
添加完参数-Xms5000m -XX:NewRatio=9后,我再次运行程序,运行成功!!!经过漫长的等待,输出了排序的时间为1443.11s,也就是大约 24分钟 !!!
最后,java 核心代码:
public static void main(String[] args) { Random random = new Random(); int[] nums = new int[ (1024*1024*1024) ]; for(int i = 0;i < nums.length;i++) nums[i] = random.nextInt(500000); long being = System.currentTimeMillis(); quicksort(nums,0,nums.length-1); long end = System.currentTimeMillis(); System.out.println(((double) (end-being))/1000+"s"); } static void quicksort(int[] nums,int begin,int end) { if(end <= begin)return; int p = begin-1; for(int i = begin;i <= end;i++) if(nums[i] <= nums[end]) { p++; int temp = nums[i]; nums[i] = nums[p]; nums[p] = temp; } quicksort(nums,begin,p-1); quicksort(nums,p+1,end); }