3000w数据的表，取某项字段前50项数据 ，内存2g

偶然看到这个题，就想了一下怎么做，大体实现思路是这样子的，3000w的数据划分为1000段，也就是1-3w为一段，30001-6w项为第二段，依次类推，从每3w的数据中提取出前50条数据（这个根据sql排序就能取出来，2个g的内存够了），最后1000个50就会产生5w个数据，最后提取出来的5w的数据放置到ArrayList中去，最后5w的数据统一排序，取出前50条。5w*5w的对比与交换是可以搞定的。具体实现，等最近的项目完了 用多线程试试！~

评论

53 楼 J-catTeam 2009-10-15  

云中苍月 写道

dazuiba 写道

这个题目可以抽象为这样：
一个数据文件，有3000W行，每行有一个id号，文件内容无任何排序。
现在让你把id前 TOP 位取出来, TOP = 50.

要求：你的程序最多能吃2G的内存，其他不限，要求考虑io/cup最优。

解决思路：

1 建一个top_array, 长度为50.
2 再建一个buffer, 长度为2^20 (1G)
3 循环开始
4   读取文件到buffer，直到buffer满为止
5   将Buffer的前50位读到top_array
7   将top_array排序，按照id升序
6   循环开始
7      接着读取buffer的下一位
       如果比最后一个还大，next;
        否则，插入到top_array相应位置，并删除最后一个。
    循环到Buffer全部读完为止

9  循环到文件读完为止

和我的思路基本一致。楼主思考时请摆脱“数据库”“SQL”之类的干扰条件。

谢谢~~

52 楼 云中苍月 2009-10-15  

dazuiba 写道

这个题目可以抽象为这样：
一个数据文件，有3000W行，每行有一个id号，文件内容无任何排序。
现在让你把id前 TOP 位取出来, TOP = 50.

要求：你的程序最多能吃2G的内存，其他不限，要求考虑io/cup最优。

解决思路：

1 建一个top_array, 长度为50.
2 再建一个buffer, 长度为2^20 (1G)
3 循环开始
4   读取文件到buffer，直到buffer满为止
5   将Buffer的前50位读到top_array
7   将top_array排序，按照id升序
6   循环开始
7      接着读取buffer的下一位
       如果比最后一个还大，next;
        否则，插入到top_array相应位置，并删除最后一个。
    循环到Buffer全部读完为止

9  循环到文件读完为止

和我的思路基本一致。楼主思考时请摆脱“数据库”“SQL”之类的干扰条件。

51 楼 dazuiba 2009-10-15  

这个题目可以抽象为这样：
一个数据文件，有3000W行，每行有一个id号，文件内容无任何排序。
现在让你把id前 TOP 位取出来, TOP = 50.

要求：你的程序最多能吃2G的内存，其他不限，要求考虑io/cup最优。

解决思路：

1 建一个top_array, 长度为50.
2 再建一个buffer, 长度为2^20 (1G)
3 循环开始
4   读取文件到buffer，直到buffer满为止
5   将Buffer的前50位读到top_array
7   将top_array排序，按照id升序
6   循环开始
7      接着读取buffer的下一位
       如果比最后一个还大，next;
        否则，插入到top_array相应位置，并删除最后一个。
    循环到Buffer全部读完为止

9  循环到文件读完为止

50 楼 leon_a 2009-10-12  

J-catTeam 写道

云中苍月 写道

云中苍月 写道

如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。

自己犯傻，被2G内存的条件忽悠了。
其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。
这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。

朋友 你这样好像是不可行的
1：你50条数据的堆是吧，请问你50条数据你放什么数据？随意放置么？如果随意放置你怎么确定这50条数据在3000w数据中存在.当然你会说先select出来是吧，你觉得花多少时间?
2：你说50条数据每一条对比3000w的数据那么最后对比的次数就是3000w*50就是15亿次是吧？ 你觉得会花多少时间
我测试过，3000w的数据我要得到其中的一条数据要花我30秒的时间（至少），那么算算一共会花多少时间啊？
当然，你的思路和别人不一样哈

最小堆，复杂度3000W*lg50
http://leon-a.iteye.com/blog/483918

49 楼 J-catTeam 2009-10-12  

云中苍月 写道

J-catTeam 写道

云中苍月 写道

云中苍月 写道

如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。

自己犯傻，被2G内存的条件忽悠了。
其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。
这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。

朋友 你这样好像是不可行的
1：你50条数据的堆是吧，请问你50条数据你放什么数据？随意放置么？如果随意放置你怎么确定这50条数据在3000w数据中存在.当然你会说先select出来是吧，你觉得花多少时间?
2：你说50条数据每一条对比3000w的数据那么最后对比的次数就是3000w*50就是15亿次是吧？ 你觉得会花多少时间
我测试过，3000w的数据我要得到其中的一条数据要花我30秒的时间（至少），那么算算一共会花多少时间啊？
当然，你的思路和别人不一样哈

1.这样做是肯定可以的，想想看大学课程里的外部排序是怎么做的。这道题目只是一个简化了的外部排序过程。
2.第二个问题我不想回答你，因为你没有明白我描述算法的意思，我的语文不太好所以建议你去读一下《计算机编程艺术》关于外部排序的章节。
考虑算法题的时候把什么数据库，什么select语句都扔掉，正常情况下考官不会要这样的答案。

你不回答我可以，但是我可以继续问吧，我还是那个意思 堆里面的50条数据你从哪里来？
如果你要select出来我可以告诉你至少时间要花40秒左右（假设数据在一张表中），
好吧 你现在有了数据了你又说要比较，再交换。朋友你试着写过么？要花多少时间。这道题考虑的肯定是以性能为主。我可以很负责任的告诉你我试过，mysql里面放3000w的数据一条select语句搞出来几条数据大概就是一分钟，如果按照你的这中思路，你觉得会花多长时间，每一个人提出来的想法都是可以实现的。我一条select *id from table order by ** limit0，50都能搞出来~
所以关键是性能。
当然 只是论题 不论人·呵呵

48 楼 taobuguo 2009-10-12  

云中苍月 写道

J-catTeam 写道

云中苍月 写道

云中苍月 写道

如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。

自己犯傻，被2G内存的条件忽悠了。
其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。
这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。

朋友 你这样好像是不可行的
1：你50条数据的堆是吧，请问你50条数据你放什么数据？随意放置么？如果随意放置你怎么确定这50条数据在3000w数据中存在.当然你会说先select出来是吧，你觉得花多少时间?
2：你说50条数据每一条对比3000w的数据那么最后对比的次数就是3000w*50就是15亿次是吧？ 你觉得会花多少时间
我测试过，3000w的数据我要得到其中的一条数据要花我30秒的时间（至少），那么算算一共会花多少时间啊？
当然，你的思路和别人不一样哈

1.这样做是肯定可以的，想想看大学课程里的外部排序是怎么做的。这道题目只是一个简化了的外部排序过程。
2.第二个问题我不想回答你，因为你没有明白我描述算法的意思，我的语文不太好所以建议你去读一下《计算机编程艺术》关于外部排序的章节。
考虑算法题的时候把什么数据库，什么select语句都扔掉，正常情况下考官不会要这样的答案。

目前 貌似我只看懂了的做法， 前面大家说的都没明白！

我的理解是 3000W条 无序数据，取某个条件的 前50条 一定至少 历便一次! 事先准备 一个 放50个“顺续”盒子，
然后依次读 3000w中的数据，每次仅仅读 内存允许的数据量，在拿这条数据 和 50个盒子里的数据对比，确定该数据能不能放进盒子， 直到数据循环完填满盒子。    这是一个单线程的做法。


如果是多线程的话， 就每个线程 读取指定“开始位置”和“结束位置”的数据，放入属于自己的盒子。
所有线程都完成后， 在对比 每个线程中 选出的50个盒子中的数据集合，放入最终的50个盒子.这样是不是会快些

47 楼 云中苍月 2009-10-11  

J-catTeam 写道

云中苍月 写道

云中苍月 写道

如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。

自己犯傻，被2G内存的条件忽悠了。
其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。
这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。

朋友 你这样好像是不可行的
1：你50条数据的堆是吧，请问你50条数据你放什么数据？随意放置么？如果随意放置你怎么确定这50条数据在3000w数据中存在.当然你会说先select出来是吧，你觉得花多少时间?
2：你说50条数据每一条对比3000w的数据那么最后对比的次数就是3000w*50就是15亿次是吧？ 你觉得会花多少时间
我测试过，3000w的数据我要得到其中的一条数据要花我30秒的时间（至少），那么算算一共会花多少时间啊？
当然，你的思路和别人不一样哈

1.这样做是肯定可以的，想想看大学课程里的外部排序是怎么做的。这道题目只是一个简化了的外部排序过程。
2.第二个问题我不想回答你，因为你没有明白我描述算法的意思，我的语文不太好所以建议你去读一下《计算机编程艺术》关于外部排序的章节。
考虑算法题的时候把什么数据库，什么select语句都扔掉，正常情况下考官不会要这样的答案。

46 楼 J-catTeam 2009-10-10  

云中苍月 写道

云中苍月 写道

如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。

自己犯傻，被2G内存的条件忽悠了。
其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。
这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。

朋友 你这样好像是不可行的
1：你50条数据的堆是吧，请问你50条数据你放什么数据？随意放置么？如果随意放置你怎么确定这50条数据在3000w数据中存在.当然你会说先select出来是吧，你觉得花多少时间?
2：你说50条数据每一条对比3000w的数据那么最后对比的次数就是3000w*50就是15亿次是吧？ 你觉得会花多少时间
我测试过，3000w的数据我要得到其中的一条数据要花我30秒的时间（至少），那么算算一共会花多少时间啊？
当然，你的思路和别人不一样哈

45 楼 云中苍月 2009-10-10  

云中苍月 写道

如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。

自己犯傻，被2G内存的条件忽悠了。
其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。
这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。

44 楼 云中苍月 2009-10-10  

如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。

43 楼 elmar 2009-10-10  

rrsy23 写道

这个题目 其实 没有什么标准 答案；

肯定看你怎么考虑的；

要是 我每条记录有个图像都是几M怎么办？

呵呵！

我们只能忽略每条记录列的大小；简单理解没条记录暂用很少空间；

3000w的数据再那里，在硬盘，已经在内存，在内存怎么存放？

如果在硬盘，你读进来这么存放？

读取I/O效率怎么样？

很多问题要考虑；

其实是解决问题 思考问题能力；

要是我遇见这样题目，我肯定列出N种可能；

每种可能 什么思路？

如果数据是存放在文件里的，就很好办了啊，保存一个50个数的最小堆，一路遍历就好了。

42 楼 elmar 2009-10-10  

lnaigg 写道

我想的：
a. 3000w数据，分成3000组，每组1000条。分组不用占内存，前提是数据是顺序数据。

如果是顺序数组，，，直接取最后50条不就得了……

41 楼 J-catTeam 2009-10-09  

niveko 写道

J-catTeam 写道

niveko 写道

我觉得可以这样，
如果3000万数据在一个文件里面的话，可以用RandomAccessFile来读文件，每次读的时候数据小于2G内存就可以。然后用一个TreeMap(红黑树的实现)往里面一直放最多50条记录，当然每条记录需要实现Comparator接口，这样才能比较每条记录。放完了记录再接着往下读就可以，这样读一遍就可以选出前50条记录。也可以再针对这50条记录排序就行。

朋友··你看··jvm在windows上能控制的内存是在1.6g左右的，这里面肯定还有其他的开销，最后真正能放置数据的内存量是小于1.6g的，如果真的是把全部数据都往内存里面读（读到内存可以接受的最大值）···系统会很慢的，几乎被占完了~
当然你的思路是很好的哈~~~

你在linux下就可以超过2G，当然你读数据肯定不能按这个大小来读，你还得预估其他计算的开销，比如TreeMap的大小，还有数据的解码需要的内存等，我只是说说大体的思路，

嘿嘿~~~是哈

40 楼 niveko 2009-10-09  

J-catTeam 写道

niveko 写道

我觉得可以这样，
如果3000万数据在一个文件里面的话，可以用RandomAccessFile来读文件，每次读的时候数据小于2G内存就可以。然后用一个TreeMap(红黑树的实现)往里面一直放最多50条记录，当然每条记录需要实现Comparator接口，这样才能比较每条记录。放完了记录再接着往下读就可以，这样读一遍就可以选出前50条记录。也可以再针对这50条记录排序就行。

朋友··你看··jvm在windows上能控制的内存是在1.6g左右的，这里面肯定还有其他的开销，最后真正能放置数据的内存量是小于1.6g的，如果真的是把全部数据都往内存里面读（读到内存可以接受的最大值）···系统会很慢的，几乎被占完了~
当然你的思路是很好的哈~~~

你在linux下就可以超过2G，当然你读数据肯定不能按这个大小来读，你还得预估其他计算的开销，比如TreeMap的大小，还有数据的解码需要的内存等，我只是说说大体的思路，

39 楼 J-catTeam 2009-10-09  

niveko 写道

我觉得可以这样，
如果3000万数据在一个文件里面的话，可以用RandomAccessFile来读文件，每次读的时候数据小于2G内存就可以。然后用一个TreeMap(红黑树的实现)往里面一直放最多50条记录，当然每条记录需要实现Comparator接口，这样才能比较每条记录。放完了记录再接着往下读就可以，这样读一遍就可以选出前50条记录。也可以再针对这50条记录排序就行。

朋友··你看··jvm在windows上能控制的内存是在1.6g左右的，这里面肯定还有其他的开销，最后真正能放置数据的内存量是小于1.6g的，如果真的是把全部数据都往内存里面读（读到内存可以接受的最大值）···系统会很慢的，几乎被占完了~
当然你的思路是很好的哈~~~

38 楼 niveko 2009-10-09  

我觉得可以这样，
如果3000万数据在一个文件里面的话，可以用RandomAccessFile来读文件，每次读的时候数据小于2G内存就可以。然后用一个TreeMap(红黑树的实现)往里面一直放最多50条记录，当然每条记录需要实现Comparator接口，这样才能比较每条记录。放完了记录再接着往下读就可以，这样读一遍就可以选出前50条记录。也可以再针对这50条记录排序就行。

37 楼 J-catTeam 2009-10-08  

这道题··实际少是没有标准的答案吧？
不论是最小堆，分治法或者其他怎么··我们是不是过多的考虑到了算法或其他的东西
··对于阿里巴巴而言
3000w的数据很少，但是是一定会切库，分表，读写分离，==一系列的操作。是为了保证性能。
··所以我们考虑这道题的基础到底是不是放在这3000w的数据放在切分的表中
还是考虑这3000w的数据是放在一张表中·····
如果3000w的数据像第一种，已经被分化好了。那么是不是可以这样子想。··直接按照每表取50条这种策略来想
如果是第二种的东西那又怎么办。select的语句···20w的数据几乎就是比较慢的，当然是对于我们这种自己用的笔记本什么的。jvm在windows上能控制的内存最大为大约为1.6g。

这1.6g也不可能全部拿去放置select出来的数据。如果是这样子又怎么样。
所以对于先那个朋友说3000w的数据每次找出最大的然后删除。
我只能说··不可能的。
我试过 20w的数据找出最大值已经很慢了。3000w的数据，我更不敢想······
而且，要是这张表是需要使用的表，随意的删除，别人怎么读？
所以不论怎么想，我们试试，就会发现···问题远远不止这些，当然，学习到得会更多。

36 楼 nathanlee 2009-10-08  

J-catTeam 写道

偶然看到这个题，就想了一下怎么做，大体实现思路是这样子的，3000w的数据划分为1000段，也就是1-3w为一段，30001-6w项为第二段，依次类推，从每3w的数据中提取出前50条数据（这个根据sql排序就能取出来，2个g的内存够了），最后1000个50就会产生5w个数据，最后提取出来的5w的数据放置到ArrayList中去，最后5w的数据统一排序，取出前50条。5w*5w的对比与交换是可以搞定的。具体实现，等最近的项目完了 用多线程试试！~

lz的分而治之(Divide and Conquer)可以再略优化一下:

第一组取前50条记录后存在内存中,记录为result[50];
第二组取前50条记录后存在内存中,记录为new[50];

此时就可在内存中比较result[50]+new[50]的100条记录,并获取前50条记录在result[50]中,

也即, 对于第n组的前new[50]条都可和已存在的result[50]比较, 如此对于每组前[50]分而治之，无需再最后对于5w条统一排序.

35 楼 putonyuer 2009-10-07  

lnaigg 写道

我想的：
a. 3000w数据，分成3000组，每组1000条。分组不用占内存，前提是数据是顺序数据。
b. 每组数据找出最大值，并记录该组ID。找最大值的算法只需要1K内存，存各族最大值及组ID是3K内存。
c. 对各组的最大值进行排序，找出前50组ID。3K数据排序，内存需求也不高。
d. 排序前50组数据，总共就剩下5万条了，直接排序即可。
e. 5万条数据也可以再按之前方法细分一次。

a. 3000w数据，分成3000组   每组是1w条啊

34 楼 rrsy23 2009-10-07  

分3000组 每组1000条  还是分1000组每组3000条效率高哦？

这个可以思考哦；

for(int  i<10;i<3000;i++){

  for(int j=0;j<1000;j++){
     a();
  }
}

for(int  i<10;i<1000;i++){

  for(int j=0;j<3000;j++){
     a();
  }
}

这2个二从for循环 那个快哦；呵呵思考哈

大学导师是最早弄56k内存做图像的，教育了N多这样的小问题；
但是当数据了大道一定时候还是节约很多

比如每个访问节约10k内存，如果像google这样的系统 解决多少？


我只能想想而已哦，我们这样的公司 不会遇见；