首页 > 代码库 > 编程珠玑-外部排序问题
编程珠玑-外部排序问题
问题描述:
n个不同的数,范围在0~10的7次方之间(为了追求模拟效果,也就是排序的内容超出了内存容量,用的10的8次方),然后需要我们用有限的内存和时间内尽快排序,注意,不能有相同的数字.否则出错
1.问题准备,首先要准备0-10的7次方之间的数据打乱后放到磁盘中,那么我们有两种实现方式
实现方式1:
思想:用一个大小为n的数组,放入0-n,每次从里面随机取出来一个数,要保证每个数都被取到而且只被取一次,那么用一个boolean数组,表征数组位置i的数取出来了没.然后用一个elsenums表示当前取出了多少个数据,然后还需要取多少个.
代码:
Writer w = new FileWriter(f); int n = (int)Math.pow(10, 7); int[] nums = new int[n]; boolean[] check = new boolean[n]; for(int i=0;i<n;i++){ nums[i] = i; check[i] = false; } Random r = new Random(); int elsenums = n; while (elsenums>0) { int index = r.nextInt(n); if (check[index] == false) { w.write(nums[index]+"\n"); elsenums--; check[index] = true; } } w.close();
可以看到中间有个check来表示随机出来的下标所在的数被取过,如果被取过了就什么都不做,重新开始下一轮循环,在这里我们可以看到这算法需要注意命中率问题,也就是假如生成了多次相同的随机数.
实现方式2:
思想:利用java的集合,由于集合的size是变动的,我们每次从中间随机取出来一个数,并且remove掉,然后再随机取一个,这样不用去担心取到和之前相同的数的问题.
w = new FileWriter(f); List<Integer> numlist = new ArrayList<Integer>(); Random r1 = new Random(); for(int i=0; i<n;i++){ numlist.add(i); } int currentsize = numlist.size(); while (currentsize>0) { int index1 = r1.nextInt(currentsize); w.write(numlist.get(index1).toString()+"\n"); numlist.remove(index1); currentsize--; } w.close();
乍看上去,第二中方式实现更加优雅,但是如果我们看运行时间的话,可以看到,第一种的运行时间是远远短于第二种时间的.第一种方法虽然存在命中的问题,但是随机数由于采用了线性同余法,所以其实在随机数种子一定的情况下,每个数的概率是大致相等的,也就是说,重复的概率是比较小的.
但是第二种的性能损耗就相当大了,首先是arraylist的原理,它的底层是采用数组实现的,也就是每次的remove操作都需要去移动数组,那么每移除一个数据就需要移动一下数组,那么可想而知会有多慢.
采用第一种方案,得到文件了以后然后开始做题目.
编程珠玑-外部排序问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。