在一亿个数据中找出最大的100个

看到说从1亿个数中选取最大的100个，要求性能最好，本人也就试试了下，方法是维护一个有100个数字的数组，该数组按照从大到小排序，每来一个数，从下标0开始到100，如果比任何一个数字大，则放在此位置，同时后面的数字后移一位。或者这100个数字用链表表示，好处就是不需要逐个后移。我把前一种方法成为T1，后一种称为T2。这仅是本人的想法，如果有更好的方法，欢迎提出改正。

在测试的时候，我使用了单线程排序和多线程排序，分别计算时间。

下面是测试结果：

T1单线程和多线程：





T2单线程和多线程：





分析结果，发现2个线程比1个线程快近一倍，究其原因，，在任务管理器中查看一个线程是占用的CPU是50%，2个线程是99%，所以快进一倍，如果是10个线程还是占100%CPU，相比并未快多少，反而增加了线程的开销。可见，多线程适合分工做各自的事情，不适合一起做同一件事情！至于使用数组存储还是链式存储，由于只是100个数字，移动100个数字的开销非常小，所以2者结果差不多。

算法还能改进，改进点就是在插入排序这个算法上，如何使得将这个数最快的插入前100个数中？


后面是代码：很乱，供参考：

T1.java:

package ddd;

import java.util.Date;
import java.util.Random;

public class T1 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long st = 0;long et=0;
		int[] test =new int[100000000];//1亿个数字
		Random r = new Random();
		T2 t = new T2();
		t.print("开始随机生成数组："+new Date());
		for(int i=0;i<test.length;i++){
			test[i] = r.nextInt(test.length * 2);
		}
		t.print("\n随机生成数完毕组："+new Date()+",开始找最大的100个数");
		st = System.currentTimeMillis();
		for(int i=0;i<test.length;i++){
			t.insert(test[i]);
		}
		et = System.currentTimeMillis();
		t.print("T1总用时："+(et-st)+"ms\n");
		t.printResult();
		
//		t.print("下面第二种方法开始计算\n");
//		//第二种方法
//		T2 t2 = new T2();
//		st = System.currentTimeMillis();
//		for(int i=0;i<test.length;i++){
//			t2.insert(test[i]);
//		}
//		et = System.currentTimeMillis();
//		t2.print("总用时："+(et-st)+"ms\n");
//		t2.printResult();
//		
		t.print("下面第三种方法开始计算\n");
		//第三种方法
		T2 t3 = new T2(true);
		st = System.currentTimeMillis();
		for(int i=0;i<test.length;i++){
			t3.insert2(test[i]);
		}
		et = System.currentTimeMillis();
		t3.print("T2第三种总用时："+(et-st)+"ms\n");
		t3.printLinkResult();
		
//		t.print("下面多线程方法开始计算\n");
//		st = System.currentTimeMillis();
//		Top100Thread[] threads = new Top100Thread[2];
//		//下面准备用10个线程分别计算
//		for(int i=0;i<2;i++){
//			threads[i] = new Top100Thread(false, test,i*50000000,i*50000000+50000000);
//			threads[i].start();
//		}
//		for(int i=0;i<2;i++){
//			try {
//				threads[i].join();//尝试等待10个线程完毕
//			} catch (InterruptedException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//		}
//		//下面将10个线程的10×100数字集合起来选出top100
//		
//		T2 t4 = new T2();
//		int[] temp = null;
//		for(int i=0;i<2;i++){
//			temp = threads[i].getTop100();
//			for(int j=0;j<temp.length;j++){
//				t4.insert(temp[j]);
//			}
//		}
//		et = System.currentTimeMillis();
//		t4.print("T1多线程总用时："+(et-st)+"ms\n");
//		t4.printResult();
		
		
//		t.print("下面多线程方法开始计算\n");
//		st = System.currentTimeMillis();
//		Top100Thread[] threads = new Top100Thread[2];
//		//下面准备用10个线程分别计算
//		for(int i=0;i<2;i++){
//			threads[i] = new Top100Thread(true,test,i*50000000,i*50000000+50000000);
//			threads[i].start();
//		}
//		for(int i=0;i<2;i++){
//			try {
//				threads[i].join();//尝试等待10个线程完毕
//			} catch (InterruptedException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//		}
//		//下面将10个线程的10×100数字集合起来选出top100
//		
//		T2 t4 = new T2(true);
//		int[] temp = null;
//		for(int i=0;i<2;i++){
//			temp = threads[i].getTop100();
//			for(int j=0;j<temp.length;j++){
//				t4.insert2(temp[j]);
//			}
//		}
//		et = System.currentTimeMillis();
//		t4.print("T2多线程总用时："+(et-st)+"ms\n");
//		t4.printLinkResult();
	}

}

T2.java；维持top100数据

package ddd;

public class T2 {
	private int[] data = new int[100];//最大的100个数字
	private LinkNode  sdata = null;
	public T2(){
	}
	
	public T2(boolean linked){
		sdata = new LinkNode(Integer.MIN_VALUE);
	}
	public static void print(Object obj){
		System.out.print(obj);
	}
	public void insert(int a){
		//维持数组从大到小排序
		for(int i=0;i<data.length;i++){
			if(a>data[i]){//a放到data[i].同时i开始到100，后移
				for(int j=data.length -1 ;j>i;j--){
					data[j] = data[j-1];
				}
				data[i] = a;
				break;
			}
		}
		//printResult();
	}
	public void insert1(int a){
		//因为数组已经是从大到小排序，因此从尾部到头部开始，大的插入，小的话则继续
		if(a < data[data.length - 1]) return;//比最小的还小则退出
		for(int i =0;i<data.length; i++){
			if(a > data[i]){
				for(int j=data.length -1 ;j>i;j--){
					data[j] = data[j-1];
				}
				data[i] = a;
				break;
			}
		}
	}
	
	public void insert2(int a){//linkNode插入
		LinkNode t = sdata;
		LinkNode pre = null;
		int idx = 0;
		while(t!= null){
			idx++;
			if(idx >= 100){
				t.setNext(null);
				break;
			}
			if(a > t.getData()){
				LinkNode temp = new LinkNode(a);
				temp.setNext(t);
				if(sdata == t)sdata = temp;
				if(pre != null)pre.setNext(temp);
				//printLinkResult();
				break;
			}
			pre = t;
			t = t.getNext();
			
			//printLinkResult();
			
		}
		
		
	}
	public void printResult(){
		for(int i=0;i<data.length;i++)print(data[i]+" ");
		print("\n");
	}
	public void printLinkResult(){
		LinkNode t = sdata;
		while(t!= null){
			print(t.getData()+" ");
			t = t.getNext();
		}
		print("\n");
	}
	public int[] getData() {
		return data;
	}
	public int[] getLinkData() {
		LinkNode t = sdata;
		int i = 0;
		while(t!= null){
			data[i++] = t.getData();
			t = t.getNext();
		}
		return data;
	}
	
}

LinkNode.java:链表

package ddd;

public class LinkNode {
	private int data;
	private LinkNode next;
	public LinkNode(int data) {
		this.data = data;
		this.next = null;
	}
	public LinkNode getNext() {
		return next;
	}
	public void setNext(LinkNode next) {
		this.next = next;
	}
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	
}

Top100Thread.java：多线程

package ddd;

public class Top100Thread extends Thread {
	private int[] top100;
	private int sidx = 0;
	private int eidx = 0;
	private int[] data = null;
	private boolean linked = false;
	public Top100Thread(boolean linked,int[] d, int sidx, int eidx){
		this.linked = linked;
		data = d;
		this.sidx = sidx;
		this.eidx = eidx;
	}
	
	public int[] getTop100() {
		return top100;
	}

	@Override
	public void run() {
		// TODO Auto-generated method stub
		super.run();
		//从sidx到eidx中选取最大的100个数
		if(this.linked){
			T2 t = new T2(true);
			long st = System.currentTimeMillis();
			for(int i= sidx;i<eidx;i++){
				t.insert2(data[i]);
			}
			long et = System.currentTimeMillis();
			t.print(this.getName()+"总用时："+(et-st)+"ms\n");
			t.printLinkResult();
			this.top100 = t.getLinkData();
		}else{
			T2 t = new T2();
			long st = System.currentTimeMillis();
			for(int i= sidx;i<eidx;i++){
				t.insert(data[i]);
			}
			long et = System.currentTimeMillis();
			t.print(this.getName()+"总用时："+(et-st)+"ms\n");
			t.printResult();
			this.top100 = t.getData();
		}
		

		
	}

}

评论

2 楼 fuliang 2010-04-01  

维持100个大小的最大堆

1 楼 Heis 2010-04-01  

如果用二叉树来代替数组存储，可以减少对比次数。