面试遇到大数据量的问题到底在考什么？

    面试遇到问大数据量的问题到底在考什么？这里讨论在程序中并非数据库中，也并不考虑借助数据库或者其他辅助工具。

    他是考验你算法？会不会遍历？集合的使用？还是考验计算机内存大小的？我感觉都不是，是在考你思路。前面有人发表了“两个1000W个元素的数组，如何有效的找出他们的交集”，等会我说下思路，对的话大家顶下，谢谢。

    先说我以前我也遇到过一道类似的题，4G大小的文件，里面全部是整数，求出最大，最小值。别告诉我拿8G内存的计算机用数组存储，然后遍历，比较。。。如果人家说8G的文件呢？16G的文件呢？当时我第一反应是把4G文件分开，但是后来马上想到的是多线程，最后说出了思路，描述如下：
    A,B两个线程
    定义两个变量int max,min;
    一个int数组，大小任意（决定大小的因素，计算机，语言等因素，这里不详细说了），例如大小10000的数组X
    A读取文件写入X，写满A暂停，B启动在数组X种找到最大最小分别赋值给变量max，min
    遍历完后清空X，暂停B，然后启动A同样是读取文件，写入数组，之后暂停A，遍历和max，min比较，遍历完最大和最小值分别赋值给变量max和min
    重复操作，直到全部读取比较完，结束。
     这只是个思路，其中多线程的操作和IO等操作不做详细说明了。

    下面来说下前面有人说到的“两个1000W个元素的数组，如何有效的找出他们的交集”，如果内存够大，当然好了，直接操作最好。如果元素的最小值是，1E呢？内存怎么办？如果是几个亿的元素呢？
    看题来说，两个数组元素不太可能存在内存中，就假设存在文件一和文件二中吧。

    给个简单思路，两个数组的数据存在文件一，文件二
    定义A,B,C三个线程
    X,Y两个数组，每个大小就拿10000个来说吧（决定大小的因素，计算机，语言等因素，这里不详细说了）
    A读文件一写入X数组写满A停止，B读取第二个文件写入Y数组写满B停止，这时候C启动，在X,Y两个数组找出交集，大小10000的两个数组怎么找交集这个大家自由发挥总之取到后写入另外个文件中，就当是文件三吧。
    比较完后，清空Y，然后C停止，启动B接着读取写入Y，然后再启动C去重复上面的步骤，直到文件二完全操作完。
    文件二操作完成后，再清空X再启动A，再重复上面的步骤，直到文件一全部操作完。
    这个时候文件三就是结果了，记得别忘了去除重复元素。如果文件小，很好去除，如果文件依旧很大，那么还是按多线程的思路去解决。
   
    取最大最小值的算法和取交集的算法本人不发表了，本人虽然是个程序员但是非数学，计算机专业，算法不敢和各位大虾去比，当然多线程和IO等其他操作中的问题，各自去解决吧，以上的思路觉得对的大家顶下，觉得不对的尽管提出，有更好思路的还望赐教。
    MSN:[e-mail]

评论

32 楼 berlou 2010-03-17  

一帮人长篇大论， 连楼主最基础的算法是对是错都没看明白。
这么明显的错误没人知道？数据切分来取交集？？？
A和A1没有交集， A和B1可以有交集么？A就这么被你丢掉了。。。
真搞笑， 顺序执行的程序还在用线程。。。。。

31 楼 keanu-re 2010-03-17  

开始那个读文件算法乱写的  现改为如下 ：
优势是是先判断高位 高位如果比现在的小 就无须继续判断低位
缓存依然是 40M  机器好的自己改

总共耗时5分钟

public static void printMax() throws IOException{
		String path="d:/bf";
		File file=new File(path);
		FileInputStream fis=new FileInputStream(file);
		byte[] max=new byte[4];
		byte[] b=new byte[40000000];
		for(int i=0;i<100;i++){
			fis.read(b);
			for(int j=0;j<10000000;j+=4){
				if((b[j]>max[0])&&(b[j+1]>max[1])&&(b[j+2]>max[2])&&(b[j+3]>max[3])){
					max[0]=b[j];
					max[1]=b[j+1];
					max[2]=b[j+2];
					max[3]=b[j+3];
				}
			}
			System.out.println(i+"%");
		}
		fis.close();
		int intMax=0;
		for(int i=0;i<4;i++){
			intMax+=max[i]<<(3-i);
		}
		System.out.println(intMax);
	}

30 楼 Else 2010-03-17  

楼上为什么不直接用data流写int和读int,你这样做法有什么优势?

29 楼 lydawen 2010-03-17  

wlwolf 写道

使用流不就完了吗

  FileReader fr=new FileReader(new File("4g.file"));
		BufferedReader br=new BufferedReader(fr);
		String s;
		int max=0,min=0,tmp;
		boolean isfirst=true;		
		while((s=br.readLine())!=null){
			s=s.trim();
			if(!"".equals(s)){
				tmp=Integer.parseInt(s);
				if(isfirst){
					max=tmp;
					min=tmp;
					isfirst=false;
				}
				max=(max>tmp)?max:tmp;
				min=(min<tmp)?min:tmp;
			}
		}
		System.out.println("max:"+max+"\r\nmin:"+min);

如果文件只有一行怎么办呀

28 楼 keanu-re 2010-03-17  

蛋疼无聊。。先写4G int文件 一共10亿个
缓存为40M  机器好的 请自行修改byte数组长度
生成测试文件一共2分钟

package momo.jni;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Random;

public class GenFile {

	public static void genBinaryFile() throws IOException{
		String path="d:/bf";
		Random r=new Random();
		File file=new File(path);
		FileOutputStream fos=new FileOutputStream(file);
		byte[] b=new byte[40000000];
		int index=0;
		for(int i=0;i<1000000000;i++){
			int temp=r.nextInt(Integer.MAX_VALUE);
			b[index++]=(byte)(temp>>24&0xFF);
			b[index++]=(byte)(temp>>16&0xFF);
			b[index++]=(byte)(temp>>8&0xFF);
			b[index++]=(byte)(temp&0xFF);
			if(index==40000000){
				fos.write(b);
				index=0;
			}	
		}
		fos.flush();
		fos.close();
	}
	
	public static void printMax() throws IOException{
		String path="d:/bf";
		File file=new File(path);
		FileInputStream fis=new FileInputStream(file);
		int max=0;
		byte[] b=new byte[4];
		for(int i=0;i<1000000000;i++){
			fis.read(b);
			int temp=0;
			for(int j=0;j<4;j++){
				temp+=b[j]<<8*(3-j);
			}
			if(temp>max)
				max=temp;
		}
		fis.close();
		System.out.println(max);
	}
	
	public static void main(String[] args) throws IOException {
		//genBinaryFile();
		//System.out.println("----------------------------------");
		printMax();
	}

}

27 楼 wlwolf 2010-03-17  

使用流不就完了吗

  FileReader fr=new FileReader(new File("4g.file"));
		BufferedReader br=new BufferedReader(fr);
		String s;
		int max=0,min=0,tmp;
		boolean isfirst=true;		
		while((s=br.readLine())!=null){
			s=s.trim();
			if(!"".equals(s)){
				tmp=Integer.parseInt(s);
				if(isfirst){
					max=tmp;
					min=tmp;
					isfirst=false;
				}
				max=(max>tmp)?max:tmp;
				min=(min<tmp)?min:tmp;
			}
		}
		System.out.println("max:"+max+"\r\nmin:"+min);

26 楼 keanu-re 2010-03-17  

flysunsystem 写道

bingyuan 写道

老实说，我看不到使用多线程的理由：
1>求最大最小数，两个线程不是并行的，没有必要，循环就可以搞定。
2>求两个集合的交集，LZ给出的方案效率太低，不如hash

4G的数据存在文本中，你怎么循环？不会你拿出8G的计算机去做吧。

就冲这句话。。不得不围观。。。。。。。。。。。。。。。。。。。。。。
你是文科转计算机的么。。。。。。。。。。。

25 楼 yymt 2010-03-17  

平时多了解计算机的基础知识,虚心接受别人的指教

24 楼 redwatch 2010-03-17  

用不到多线程

用向量排序
一个整数有32位
如:00000000 00000000 00000000 00000000
一个整数就可以代表32个数
如上面就可以代表1-32

如果有某个数，对应位就为1
如有31,32
就是:00000000 00000000 00000000 00000011

把所有的数遍历一次
取最开始和最后为1的数  就可以知道最大和最小了

23 楼 xzqttt 2010-03-17  

两点

1，你是用了多个线程，但不是多线程，你这是单线程，呵呵
2，如果用java来做，你那个数组能new多大，取决于你虚拟机启动参数，还到不了物理内存这一层

22 楼 hello_player 2010-03-17  

要求如何有效的求交集，都顶到首页上了，请问下这种思路的效率体现在什么地方？

21 楼 flysunsystem 2010-03-17  

veryls 写道

flysunsystem 写道

superheizai 写道

楼主，如您所说，如果要先有A执行，再有B执行的话，就是要依赖线程A，B的顺序关系了。但是，java多线程好像是不推荐这么做的。再者说，您做的顺序就是：读数据——》找最大最小值——》再读数据——》再找最大最小值。。。。，这个循环应该可以做的吧。

循环当然可以做，你的计算机内存有多大？

我水平不高，但我知道你还嫩，多去看看书吧

自知水平不高写了个简单的思路，并没写详细算法，说我很嫩，不了也不大，看书是要天天看的。貌似你很牛逼，给个解决方法，就4G的数据文件，你找最大值。

20 楼 veryls 2010-03-17  

flysunsystem 写道

superheizai 写道

楼主，如您所说，如果要先有A执行，再有B执行的话，就是要依赖线程A，B的顺序关系了。但是，java多线程好像是不推荐这么做的。再者说，您做的顺序就是：读数据——》找最大最小值——》再读数据——》再找最大最小值。。。。，这个循环应该可以做的吧。

循环当然可以做，你的计算机内存有多大？

我水平不高，但我知道你还嫩，多去看看书吧

19 楼 flysunsystem 2010-03-17  

superheizai 写道

楼主，如您所说，如果要先有A执行，再有B执行的话，就是要依赖线程A，B的顺序关系了。但是，java多线程好像是不推荐这么做的。再者说，您做的顺序就是：读数据——》找最大最小值——》再读数据——》再找最大最小值。。。。，这个循环应该可以做的吧。

循环当然可以做，你的计算机内存有多大？

18 楼 强强爱妍妍 2010-03-17  

抛出异常的爱 写道

flysunsystem 写道

veryls 写道

楼主，这种题会想到多线程真牛逼，先去看看计算机原理，看看cpu，内存是怎么工作的，再来谈多线程

4G的数据放在文本文件中如果是8G或者16G的数据呢？你想怎么搞定？看你写这两句话，貌似很牛逼，牛逼给个思路解决。

围观一下牛X

抛哥你先别笑哪,万一人家16G的数据也是分多个文件存的呢.

17 楼 lkj107 2010-03-17  

这个事统计局最拿手

效率最高，结果最和谐

16 楼 yaobiao753 2010-03-17  

抛出异常的爱 写道

flysunsystem 写道

veryls 写道

楼主，这种题会想到多线程真牛逼，先去看看计算机原理，看看cpu，内存是怎么工作的，再来谈多线程

4G的数据放在文本文件中如果是8G或者16G的数据呢？你想怎么搞定？看你写这两句话，貌似很牛逼，牛逼给个思路解决。

围观一下牛X

+1

15 楼 抛出异常的爱 2010-03-17  

flysunsystem 写道

veryls 写道

楼主，这种题会想到多线程真牛逼，先去看看计算机原理，看看cpu，内存是怎么工作的，再来谈多线程

4G的数据放在文本文件中如果是8G或者16G的数据呢？你想怎么搞定？看你写这两句话，貌似很牛逼，牛逼给个思路解决。

围观一下牛X

14 楼 jiabiao011 2010-03-17  

你这也能叫多线程？

13 楼 superheizai 2010-03-17  

楼主，如您所说，如果要先有A执行，再有B执行的话，就是要依赖线程A，B的顺序关系了。但是，java多线程好像是不推荐这么做的。再者说，您做的顺序就是：读数据——》找最大最小值——》再读数据——》再找最大最小值。。。。，这个循环应该可以做的吧。