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

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

    他是考验你算法？会不会遍历？集合的使用？还是考验计算机内存大小的？我感觉都不是，是在考你思路。前面有人发表了“两个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]

评论

72 楼 crackcell 2010-03-18  

bloom filter 也是一种思路

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

跟残疾人斗没意思,老夫下班去也

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

也难怪,你是盲人,用菊花观察世界是你这种sb才能想到的事情

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

berlou 写道

再跟你这sb强调一下， 别拿菊花观察世界。

不要以为你的眼睛是菊花世界就是菊花

68 楼 berlou 2010-03-18  

再跟你这sb强调一下， 别拿菊花观察世界。

67 楼 berlou 2010-03-18  

强强爱妍妍 写道

berlou 写道

接着读B文件是楼主自己说的， 接着读A文件是你说的。
到此为止， 我不想再和你这种sb讨论， 拉低我智商。

原来你不仅语文不及格,还是盲人.
拿好你的放大镜照照,楼主哪里写了"接着读"三个字!
不要拿你弱智的脑子里的思路代替睿智者的思路

讨论问题结束了， 改对骂是吧？接着读这3字， 如果你瞎， 你可以Ctrl + F一下， 目前主流浏览器都支持。
如果你还是找不到， 可以用你这个算法， 把网页文件读出来， 匹配一下这3个字不是吗？
你眼睛长菊花上了？

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

berlou 写道

接着读B文件是楼主自己说的， 接着读A文件是你说的。
到此为止， 我不想再和你这种sb讨论， 拉低我智商。

原来你不仅语文不及格,还是盲人.
拿好你的放大镜照照,楼主哪里写了"接着读"三个字!
不要拿你弱智的脑子里的思路代替睿智者的思路

65 楼 berlou 2010-03-18  

接着读B文件是楼主自己说的， 接着读A文件是你说的。
到此为止， 我不想再和你这种sb讨论， 拉低我智商。

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

berlou 写道

你这种人， 不给你一条一条摆出来就是嘴硬。
我们理理楼主的话。
1. 创建x, y两个数组
2. 读A文件写入x， 直到x满为止
3. 读B文件写入y， 直到y满为止
4. 找A和B的的交集，写入文件C
5. 清空y
6. 接着读B文件写入y（这里还有B结束的问题）， 直到y满为止
7. 重复4，5的步骤知道执行6的时候B文件读完为止。
8. B文件读完后，清空x.
9. ？？？
到这，你个傻逼争论的地方来了， “重复上面的步骤”。
你告诉我从哪个步骤开始重复能达到算法预期效果？
从1还是从2还是从7？
如果不考虑时间和空间复杂度，这个算法想正确也只能是把7,8,9合并到2，3，4的步骤中。用语文描述就得是接着读文件A（如未读过则从头读）， 接着读文件B(如未读过则从头读）.....

真是属鸭子的。。。。

菜B菜B菜B 骂的就是你
你知道"接着读B文件",想不到接着读A文件?  死鸭子还给你

63 楼 berlou 2010-03-18  

强强爱妍妍 写道

berlou 写道

感情你在玩文字游戏是不？你的上面上到哪？包括楼主说的所有的话么？这样重复的话， 是无限循环。
不要试图告诉我， 这个”上面“的断点是” A读文件一写入X数组写满A停止，B读取第二个文件写入Y数组写满B停止，这时候C启动，在X,Y两个数组找出交集，大小10000的两个数组怎么找交集这个大家自由发挥总之取到后写入另外个文件中，就当是文件三吧。“这句话中第一个逗号后面的部分， 你这个上也太会“上”了。即使以你这种“上”法， 也应该是“接着读A文件（如果没读过从头读）”， 才能使算法成立。
你要教人语文和语法， 就别弄出一个模棱两可的标准， 你要是上代表上面全部流程， 就把逗号前的带进去， 别以你的意思去断句。
拜托你还是省省， 别2b呵呵的在这现眼。

2你妹,你就傻b一个,跑来给小学语文老师丢脸

你这种人， 不给你一条一条摆出来就是嘴硬。
我们理理楼主的话。
1. 创建x, y两个数组
2. 读A文件写入x， 直到x满为止
3. 读B文件写入y， 直到y满为止
4. 找A和B的的交集，写入文件C
5. 清空y
6. 接着读B文件写入y（这里还有B结束的问题）， 直到y满为止
7. 重复4，5的步骤知道执行6的时候B文件读完为止。
8. B文件读完后，清空x.
9. ？？？
到这，你个傻逼争论的地方来了， “重复上面的步骤”。
你告诉我从哪个步骤开始重复能达到算法预期效果？
从1还是从2还是从7？
如果不考虑时间和空间复杂度，这个算法想正确也只能是把7,8,9合并到2，3，4的步骤中。用语文描述就得是接着读文件A（如未读过则从头读）， 接着读文件B(如未读过则从头读）.....

真是属鸭子的。。。。

62 楼 berlou 2010-03-18  

fanfq 写道

抛出异常的爱 写道

berlou 写道

Else 写道

就算是人家lz错了,也不用这么挖苦人吧,这么搞,谁敢发贴讨论问题啊

它利用线程拙劣的方式就不说了， 连最基础最直观的错误算法都能贴出来让大家参观， 大家还客气什么？

说出来总比不懂装懂强多
这回不懂下回不就懂了?
PS:问题是问题
人品是人品
技术上的事不至于...

很多人心态有问题，就算LZ的不对，你加以指正并且说明你的想法好了。
实在有点看不下去了。以后还有人敢提问么？
谁不需要一个“脱菜”的过程啊。

非得你捧捧我，我鼓励鼓励你这样才是好的学术和技术氛围么？如果这样的话， 那真是和谐社会了。
互相挑刺笑骂比互相捧臭脚强多了。哪个牛逼产品不是在骂声中和指责声中长大的？
期望想婴儿宝宝一样受呵护， 能长大么？

61 楼 zhangdp_neu 2010-03-18  

lai008 写道

zhangdp_neu 写道

基本上考的是
数据结构和算法，而已有一定的技巧性。
推荐看一本《编程珠玑》
通过你的描述.
如果你的机器上int 为32位的话。

int max ,int min
先按无符号的数据来算吧，最大的值为4294967295 不到 43亿。


也就是可以说，去除重复后，文件中的整数不会超过43亿个。

43亿个整数 int 大小 4294967295 * 4B（每个int四个字节） 约等于
17179869180 B（字节）约等于16777215KB 约等于16383MB 约等于 16G


放入内存排序不要想了。

问题是找出最大的和最小的值。
那么，可以确定的是，最大值一定在 0-4294967295 之间。

如果定义一个数组int[4294967295]可以做的话，一个好的办法。
是用类似桶排序的原理。将对应的值扔到对应下标的数组里，如果有1233这个整数，就把下标1233的值设置为1.
那么最后一个不为空的位置 就是最大值，第一个不为空的就是最小值。
时间复杂度为 O(N)，空间O(N)，但是Ｎ太大，内存扛不住。
每个数组元素 取值只有1和0. 用Int型有些浪费了。用一个二进制位就可以表示了。

如果把int[4294967295]　型数组，每个元素大小缩小３２倍。int 大小是32位，那么这个数组
可以表示为  bit[4294967295] 大小约等于4294967295/8 = 536870911B约等于534287KB约等于512M了.

那么别说是4G了，8G，100G也不会过这个范围。



算法描述如下
1bit = byte/8;

bit[4294967295] = init{0};

for(遍历文件)//可以批量读入提高性能。
{
取一个整数 X
        setBit(x);//将第x位值设置为1
}

//找出最大值
for(int i = 4294967295;i>=0;i--)
{
    if(bit[i]==1)return i;//i为最大值

}

//找出最小值
for(int int = 0; i <= 4294967295;i++)
{
    if(bit[i]==1)return i;//i为最小值

}

如果你觉得单线程处理不够快，那么就引入多线程。
把文件分割成N块（前提是你知道如何分割）如果分割不了，可以用两个线程首位读文件，两个指针相遇结束。
每个线程都执行 setBit(x)操作，并且不需要同步，但是多线程不一定可以提高性能啊。

如果是无符号数据的话，略微变形也可以解决。

第二个问题，也可以用类似方法解决，不过数组元素大小设置2bit就可以了。空间也不会超过1G的。

另外，如果不把数据读取内存中。

int max = 文件第一个int数据
int min = 文件第一个int数据
for(遍历文件)//可以批量读入提高性能。
{
   取一个元素X
   if(max<X)max = x;
   if(min>X)min = x;
}

print(max);
print(min); 这是 是你说的 第一个题的解法。


这样也可以解第一个问题。

第一题根本没有必要用位图法，因为只需要找到一个最大值和一个最小值（而不是前n个最大和最小），直接弄2个变量分别存最大值和最小，然后分批读入数据并比较就完了，只需遍历一次就够了，你这样做得话还有遍历2次，不太优，第二题也是用位图法求交集，至于你在写什么没太看懂

第二个，我描述的不清楚，不过前面已经有人描述过了，方法是相同的

lai008 写道

第二题：我的想法是先对2个集合排序，然后遍历一次求集合，排序复杂度是O(nlogn),遍历一次复杂度是O(n),总共大约是O(nlogN+n)，不过还有更快的方法，都是整数的话，用位图法，一个位代表一个整数，2个集合就设置2个位图，读入数据，置相应的位图为1，全部读入后对2个位图做与操作，再读入每个位所代表的数据，复杂度是O(n)

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

berlou 写道

感情你在玩文字游戏是不？你的上面上到哪？包括楼主说的所有的话么？这样重复的话， 是无限循环。
不要试图告诉我， 这个”上面“的断点是” A读文件一写入X数组写满A停止，B读取第二个文件写入Y数组写满B停止，这时候C启动，在X,Y两个数组找出交集，大小10000的两个数组怎么找交集这个大家自由发挥总之取到后写入另外个文件中，就当是文件三吧。“这句话中第一个逗号后面的部分， 你这个上也太会“上”了。即使以你这种“上”法， 也应该是“接着读A文件（如果没读过从头读）”， 才能使算法成立。
你要教人语文和语法， 就别弄出一个模棱两可的标准， 你要是上代表上面全部流程， 就把逗号前的带进去， 别以你的意思去断句。
拜托你还是省省， 别2b呵呵的在这现眼。

2你妹,你就傻b一个,跑来给小学语文老师丢脸

59 楼 zzj_2046 2010-03-18  

哎~关注..........

58 楼 fanfq 2010-03-18  

抛出异常的爱 写道

berlou 写道

Else 写道

就算是人家lz错了,也不用这么挖苦人吧,这么搞,谁敢发贴讨论问题啊

它利用线程拙劣的方式就不说了， 连最基础最直观的错误算法都能贴出来让大家参观， 大家还客气什么？

说出来总比不懂装懂强多
这回不懂下回不就懂了?
PS:问题是问题
人品是人品
技术上的事不至于...

很多人心态有问题，就算LZ的不对，你加以指正并且说明你的想法好了。
实在有点看不下去了。以后还有人敢提问么？
谁不需要一个“脱菜”的过程啊。

57 楼 berlou 2010-03-18  

强强爱妍妍 写道

berlou 写道

...
“再清空X再启动A，再重复上面的步骤，直到文件一全部操作完。 ”
则 x = {4, 5} 这时， 如果y是空， 则全部丢弃， 最终结果是z = {2, 3}， 如果y没清空， 仍然是{5, 6}则最终结果是{2, 3, 5}

你这个什么傻逼愿意爱谁爱谁去， 别在这丢人现眼， je你这种人不缺。

同学,语文不及格. "再重复上面的步骤"你懂不, 就是让你再从头读取数组B的内容到Y

懂否?

感情你在玩文字游戏是不？你的上面上到哪？包括楼主说的所有的话么？这样重复的话， 是无限循环。
不要试图告诉我， 这个”上面“的断点是” A读文件一写入X数组写满A停止，B读取第二个文件写入Y数组写满B停止，这时候C启动，在X,Y两个数组找出交集，大小10000的两个数组怎么找交集这个大家自由发挥总之取到后写入另外个文件中，就当是文件三吧。“这句话中第一个逗号后面的部分， 你这个上也太会“上”了。即使以你这种“上”法， 也应该是“接着读A文件（如果没读过从头读）”， 才能使算法成立。
你要教人语文和语法， 就别弄出一个模棱两可的标准， 你要是上代表上面全部流程， 就把逗号前的带进去， 别以你的意思去断句。
拜托你还是省省， 别2b呵呵的在这现眼。

56 楼 xiaojing3517 2010-03-18  

围观,这算不算是群殴?

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

berlou 写道

...
“再清空X再启动A，再重复上面的步骤，直到文件一全部操作完。 ”
则 x = {4, 5} 这时， 如果y是空， 则全部丢弃， 最终结果是z = {2, 3}， 如果y没清空， 仍然是{5, 6}则最终结果是{2, 3, 5}

你这个什么傻逼愿意爱谁爱谁去， 别在这丢人现眼， je你这种人不缺。

同学,语文不及格. "再重复上面的步骤"你懂不, 就是让你再从头读取数组B的内容到Y

懂否?

54 楼 laoshifu 2010-03-18  

看了所有的回帖。
对于第一题，很多人说不用多线程，没有体现出多线程的特点，这点我认同，但是楼主使用两个线程的原因，可能不少回帖说循环分片读入的朋友不太明了。我认为，楼主最初的目的就是用一个线程来读数据，同时也是为了保存读入文件的状态，也就是处理了那些数据。这就是楼主所说的线程A的作用，而线程B处理最大最小这个不用说了。对于第一个问题的解决，我也认同楼主的算法很普通，基本上有逻辑思维的人都可以想到，而我比较认同zhangdp_neu 写的解决方法，而lai008这位朋友评论zhangdp_neu的话，不太认同，先不说分批读入的文件状态的保存问题，就是占用的内存也远远比zhangdp_neu的算法差的多的多。
对于第二题，有朋友指出算法错误了，没什么说的。
最后，大家在评论的时候，骂人可以，但请说出骂的理由以及支持理由的证据，我看了很多人在骂，但是不知道骂什么。骂完之后，说出你的思路，让后来的看贴人定论是非。

回来之后，在路上忽然想到了这个问题，觉得第一题的确不用这么麻烦，因为只是求最大最小值，又不是排序。如果是排序，zhangdp_neu的说的算法就不错，如果只是求最大及最小值，lai008这位朋友说的还是在理的。
而第二条题目的算法，我们可以改动一下zhangdp_neu的说的算法，我们设两个一样大小的数组，然后看相应的位置是否都是1，如果是，那么就应该是交集的元素了。

53 楼 berlou 2010-03-18  

连最基础的算法都没整明白，再谈大数据量， 空中楼阁么？
很多人看了大数据量和1000w就好象高潮了一样， 都开始“性能”啊， “瓶颈”啊。于是开始解决楼主说到的算法的潜在的性能问题， 首先搞明白一件事， 这算法对不对？
不对的算法还谈什么优化？你们是不是都是那种每天就写点业务代码，连unit test都懒的写的人？出了问题再改， 改了再犯， 千锤百炼？
让我对这个问题写一个前无古人后无来者的高性能算法我差远了，但是让我不会犯这么低级的算法错误。
像什么“爱妍妍”你这种人不管是马甲还是啥，最好别丢人现眼， 要么你就给我论证一下楼主的是算法是怎么正确的， 给我提高一下可怜智商。