在一亿个数据中找出最大的100个
程序员文章站
2024-03-15 21:17:18
...
看到说从1亿个数中选取最大的100个,要求性能最好,本人也就试试了下,方法是维护一个有100个数字的数组,该数组按照从大到小排序,每来一个数,从下标0开始到100,如果比任何一个数字大,则放在此位置,同时后面的数字后移一位。或者这100个数字用链表表示,好处就是不需要逐个后移。我把前一种方法成为T1,后一种称为T2。这仅是本人的想法,如果有更好的方法,欢迎提出改正。
在测试的时候,我使用了单线程排序和多线程排序,分别计算时间。
下面是测试结果:
T1单线程和多线程:
[img]http://dl.iteye.com/upload/attachment/227719/b1967da8-89ef-3bec-ad83-2efa93f0162c.png[/img]
T2单线程和多线程:
[img]http://dl.iteye.com/upload/attachment/227721/3a67f250-a6cb-344e-be72-eeb0508e05d2.png[/img]
分析结果,发现2个线程比1个线程快近一倍,究其原因,,在任务管理器中查看一个线程是占用的CPU是50%,2个线程是99%,所以快进一倍,如果是10个线程还是占100%CPU,相比并未快多少,反而增加了线程的开销。可见,多线程适合分工做各自的事情,不适合一起做同一件事情!至于使用数组存储还是链式存储,由于只是100个数字,移动100个数字的开销非常小,所以2者结果差不多。
算法还能改进,改进点就是在插入排序这个算法上,如何使得将这个数最快的插入前100个数中?
后面是代码:很乱,供参考:
T1.java:
T2.java;维持top100数据
LinkNode.java:链表
Top100Thread.java:多线程
在测试的时候,我使用了单线程排序和多线程排序,分别计算时间。
下面是测试结果:
T1单线程和多线程:
[img]http://dl.iteye.com/upload/attachment/227719/b1967da8-89ef-3bec-ad83-2efa93f0162c.png[/img]
T2单线程和多线程:
[img]http://dl.iteye.com/upload/attachment/227721/3a67f250-a6cb-344e-be72-eeb0508e05d2.png[/img]
分析结果,发现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();
}
}
}
推荐阅读
-
从海量数值中找出最大的N个元素的算法实现
-
在一亿个数据中找出最大的100个
-
Python数据结构之堆并实现从海量数据中寻找最大的K个
-
堆(heap):从海量数据中寻找最大的k个值
-
从一个无序的数字序列中查找出前K个最大的数字[递归方式] 博客分类: algorithm TopKAlgorithmJava
-
python 如何快速找出两个电子表中数据的差异
-
python 如何快速找出两个电子表中数据的差异
-
在Excel中利用MEDIAN函数批量修订超过最大值和最小值的数据
-
洛谷OJP1008在1~9共9个数字中找出三个三位数,使它们的比例为1:2:3
-
ajax get请求得到了一个json格式的数据,在js中如何遍历出来