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

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

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

评论

52 楼 berlou 2010-03-18  

强强爱妍妍 写道

berlou 写道

抛出异常的爱 写道

berlou 写道

Else 写道

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

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

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

人品问题见仁见智。
问题本身来讲， 需要思考。1个深度是10的问题， 你起码有3的思考， 楼主连2都到不了， 甚至简单1的思考就来指导大家一下， 这是误人子弟。
我指出的是他最基本的算法问题， 当作挖苦也好，当作啥都好，能谦虚接受才能进步。不用你来帮着维护。

菜B,是你没理解楼主的思路. 楼主的多线程固然是牵强附会,他的算法没问题.

我一直奇怪这个帖子怎么有这么多2B冲出来装牛逼人， 我不牛逼， 我比较笨， 我知道用最简单的test case去证明一个算法是不是正确。
既然这么多sb说楼主除了线程外，算法和思路挺好，看来有必要和你们这些人研究研究到底谁是菜比。
test case:(直接忽略线程了）
A数组：1， 2， 3， 4， 5
B数组：2， 3， 4， 5， 6
X和Y为大小是3的数组。 z为交集结果集数组
以楼主算法， 第一次， A读出1, 2, 3到x, B读出2, 3, 4到y
这样x = {1, 2, 3}; y = {2, 3, 4}
显然，第一轮z里填充2，3 即z = {2, 3}

OK， 接着楼主说“比较完后清空y”。
x = {1, 2, 3}; y = {};
"启动B接着读取写入Y"， 接着啥意思？汉语读过小学应该知道从B数组的第四个元素5开始读吧？
好，x = {1, 2, 3}; y = {5, 6}
这样取交集， 结果是空。那么z仍然是[2, 3}
"比较完后，清空Y" “文件二操作完成后，再清空X再启动A”
就是说现在 x = {}; y = {} （注，即使理解成y = {5, 6}也没关系）
“再清空X再启动A，再重复上面的步骤，直到文件一全部操作完。 ”
则 x = {4, 5} 这时， 如果y是空， 则全部丢弃， 最终结果是z = {2, 3}， 如果y没清空， 仍然是{5, 6}则最终结果是{2, 3, 5}

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

51 楼 MySpace 2010-03-18  

iaimstar 写道

看到这里我囧了

我承认我一看下来基本哪个帖子也没看懂

+1
   和我一块蛋疼吧。。

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

berlou 写道

抛出异常的爱 写道

berlou 写道

Else 写道

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

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

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

人品问题见仁见智。
问题本身来讲， 需要思考。1个深度是10的问题， 你起码有3的思考， 楼主连2都到不了， 甚至简单1的思考就来指导大家一下， 这是误人子弟。
我指出的是他最基本的算法问题， 当作挖苦也好，当作啥都好，能谦虚接受才能进步。不用你来帮着维护。

菜B,是你没理解楼主的思路. 楼主的多线程固然是牵强附会,他的算法没问题.

49 楼 iaimstar 2010-03-18  

看到这里我囧了

我承认我一看下来基本哪个帖子也没看懂

48 楼 yyyyy5101 2010-03-18  

第一个没看出哪用到多线程了，还不如一个线程去跑。

47 楼 lai008 2010-03-18  

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次，不太优，第二题也是用位图法求交集，至于你在写什么没太看懂

46 楼 zha_zi 2010-03-18  

两个解题思想都挺好的，但是不用依赖线程

45 楼 berlou 2010-03-18  

抛出异常的爱 写道

berlou 写道

Else 写道

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

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

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

人品问题见仁见智。
问题本身来讲， 需要思考。1个深度是10的问题， 你起码有3的思考， 楼主连2都到不了， 甚至简单1的思考就来指导大家一下， 这是误人子弟。
我指出的是他最基本的算法问题， 当作挖苦也好，当作啥都好，能谦虚接受才能进步。不用你来帮着维护。

44 楼 抛出异常的爱 2010-03-18  

berlou 写道

Else 写道

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

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

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

43 楼 ahuango 2010-03-18  

两个线程是顺序执行的，和单线程看不出有多大的区别。 楼主貌似没有说在重点上

42 楼 linsea 2010-03-18  

大家不要嘲笑LZ了,其他的很多同学也不见得高明到哪儿去,还有写程序测试的呢.
这里是要找到理论上的算法方案,显然没有讨论到问题的点上去,不过有几位的思想很好

41 楼 berlou 2010-03-18  

Else 写道

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

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

40 楼 Else 2010-03-18  

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

39 楼 zha_zi 2010-03-18  

比大小用多线程确实有点牵强了，lz的思想不过是用一个有限大缓存数组多次去读取解决大型文件。

38 楼 zhangdp_neu 2010-03-18  

基本上考的是
数据结构和算法，而已有一定的技巧性。
推荐看一本《编程珠玑》
通过你的描述.
如果你的机器上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);

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

37 楼 刃之舞 2010-03-17  

已经把一个完整的CPU给你用了，你还多线程个什么劲啊，又不是让你跟很多程序同时运行，什么思路啊，还感觉自己很牛逼了

36 楼 lai008 2010-03-17  

跟多线程没有什么关系吧

第一题：数据再大也不怕，分组读入，只用读入数据保存当前最大值和最小值，然后继续读入数据，跟最大最小值比较，符合就替换，复杂度应该是O(n)

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

35 楼 deyami 2010-03-17  

flysunsystem 写道

veryls 写道

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

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

引用抛哥个一句话，牛b的人往往是牛逼哄哄。

34 楼 ryxxlong 2010-03-17  

veryls 写道

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

++,真是服了YOU! 我只想说LZ实在太有才,不是我等敢与之比肩的.

33 楼 wangruosong 2010-03-17  

看懵掉了  楼上正解。。。