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

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

评论

33 楼 rrsy23 2009-10-07  

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

肯定看你怎么考虑的；

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

呵呵！

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

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

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

读取I/O效率怎么样？

很多问题要考虑；

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

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

每种可能 什么思路？

32 楼 mikeandmore 2009-10-07  

liuxuan620 写道

最小堆的时间复杂度是O(nlogk),其中k=50,n=3000w
你说的遍历的时间复杂度是O(nk)
就单线程来说的话，用最小堆肯定是最优的

xiaokan 写道

其实最快的方法就是遍历整组数据，取最大值，然后删掉它，重复50次，每次时间代价为O(3000w)，50次就是1.5billion，这个复杂度不错了，至少比那些O(n log n)的堆好

re
其实50对于30M来说，应该算是常数了，于是能算成 O(n)了。。。。
当然那个O(nk)的也就。。。。。。。。。

不过那个 O(nk)的肯定慢死了。。。光seek就能seek到死。。。

PS原来这里有人一帖多发啊。。。

31 楼 mikeandmore 2009-10-07  

J-catTeam 写道

GooHome 写道

xiaokan 写道

其实最快的方法就是遍历整组数据，取最大值，然后删掉它，重复50次，每次时间代价为O(3000w)，50次就是1.5billion，这个复杂度不错了，至少比那些O(n log n)的堆好

我说了一个3000W和内存的分支点 大家都没有注意到吧。

一个算法的好与坏，不是算法的本身，而是算法的应用范围。oracle有什么成本优化什么的。

这道题目到底考什么，我想出题的公司比我们更了解。本身并不难的题目，被大家推成热点话题。
可能是大家没有真正接触过大数据量，3000W对于一般的大企业而言是一个很小的数据量，我接触过
的一个小型商品连锁零售商，全日本前3甲吧。一天的数据量都超过这个数目，就更别说大型连锁超市了。
分析最畅销的商品是什么?这就是题目实际应用的一种吧。

考的就是你的分析能力和基本计算机优化常识。

CPU >Cache>Mem>HDD 这是目前CPU优化的基本原则。

按照常识来讲，数据库存在硬盘上取数需要内存。
内存装不下，就要想办法 这是key 1

暂时走开暂存

内存不足的办法？
不是分批取么？

分页。。。。
这里可以偷懒直接mmap。。。。如果vm够的话

30 楼 liuxuan620 2009-10-06  

最小堆的时间复杂度是O(nlogk),其中k=50,n=3000w
你说的遍历的时间复杂度是O(nk)
就单线程来说的话，用最小堆肯定是最优的

xiaokan 写道

其实最快的方法就是遍历整组数据，取最大值，然后删掉它，重复50次，每次时间代价为O(3000w)，50次就是1.5billion，这个复杂度不错了，至少比那些O(n log n)的堆好

29 楼 J-catTeam 2009-10-05  

GooHome 写道

xiaokan 写道

其实最快的方法就是遍历整组数据，取最大值，然后删掉它，重复50次，每次时间代价为O(3000w)，50次就是1.5billion，这个复杂度不错了，至少比那些O(n log n)的堆好

我说了一个3000W和内存的分支点 大家都没有注意到吧。

一个算法的好与坏，不是算法的本身，而是算法的应用范围。oracle有什么成本优化什么的。

这道题目到底考什么，我想出题的公司比我们更了解。本身并不难的题目，被大家推成热点话题。
可能是大家没有真正接触过大数据量，3000W对于一般的大企业而言是一个很小的数据量，我接触过
的一个小型商品连锁零售商，全日本前3甲吧。一天的数据量都超过这个数目，就更别说大型连锁超市了。
分析最畅销的商品是什么?这就是题目实际应用的一种吧。

考的就是你的分析能力和基本计算机优化常识。

CPU >Cache>Mem>HDD 这是目前CPU优化的基本原则。

按照常识来讲，数据库存在硬盘上取数需要内存。
内存装不下，就要想办法 这是key 1

暂时走开暂存

内存不足的办法？
不是分批取么？

28 楼 GooHome 2009-10-05  

xiaokan 写道

其实最快的方法就是遍历整组数据，取最大值，然后删掉它，重复50次，每次时间代价为O(3000w)，50次就是1.5billion，这个复杂度不错了，至少比那些O(n log n)的堆好

我说了一个3000W和内存的分支点 大家都没有注意到吧。

一个算法的好与坏，不是算法的本身，而是算法的应用范围。oracle有什么成本优化什么的。

这道题目到底考什么，我想出题的公司比我们更了解。本身并不难的题目，被大家推成热点话题。
可能是大家没有真正接触过大数据量，3000W对于一般的大企业而言是一个很小的数据量，我接触过
的一个小型商品连锁零售商，全日本前3甲吧。一天的数据量都超过这个数目，就更别说大型连锁超市了。
分析最畅销的商品是什么?这就是题目实际应用的一种吧。

考的就是你的分析能力和基本计算机优化常识。

CPU >Cache>Mem>HDD 这是目前CPU优化的基本原则。

按照常识来讲，数据库存在硬盘上取数需要内存。
内存装不下，就要想办法 这是key 1

暂时走开暂存

27 楼 xiaokan 2009-10-05  

其实最快的方法就是遍历整组数据，取最大值，然后删掉它，重复50次，每次时间代价为O(3000w)，50次就是1.5billion，这个复杂度不错了，至少比那些O(n log n)的堆好

26 楼 rong889 2009-10-04  

C_J 写道

-堆排序是快速排序的基础么???我记得好像是不同的排序

-快速排序可以加分治,把数据拆分成很多块,然后分别排序...

-楼上几位仁兄的意思是不是以下这个意思??
如取个堆大小为N个节点的堆,先做一个最小堆排序,大致如:
           4
      5         6
  7      8    9    10

然后换掉底下的一层的某数 ,如换掉这里的7为3,然后再排个序..达到如下效果

第一趟:
             4
     3            6
5         8    9      10

第二趟:
            3
      4            6
5         8    9       10

当然内存里取50个节点浪费了内存.可以拆分30000个数据,用多线程分别排序,最后取最小的50个数据.

-那么,以把30000拆分成块,一点一点做,取最后取最小50个呢?这样很多排序都可以呀? 用快速排序,取小于2G的数据到内存,这批做完,释放heap上内存,然后再做下批,最后取最小50个,这完全用代码能现场写出来..


-如果是那意思的话,这题目30000的数据真忽悠人的...


-这职位月薪10K??

同意你的看法，如果只是排序的话，多大数据量都没问题。


另外之前碰到过这样一个题目，大家讨论一下：
一个8G的访问日志文件，每行一个URL，如何统计出访问量最高的10个URL（Top 10）？

25 楼 C_J 2009-10-04  

-堆排序是快速排序的基础么???我记得好像是不同的排序

-快速排序可以加分治,把数据拆分成很多块,然后分别排序...

-楼上几位仁兄的意思是不是以下这个意思??
如取个堆大小为N个节点的堆,先做一个最小堆排序,大致如:
           4
      5         6
  7      8    9    10

然后换掉底下的一层的某数 ,如换掉这里的7为3,然后再排个序..达到如下效果

第一趟:
             4
     3            6
5         8    9      10

第二趟:
            3
      4            6
5         8    9       10

当然内存里取50个节点浪费了内存.可以拆分30000个数据,用多线程分别排序,最后取最小的50个数据.

-那么,以把30000拆分成块,一点一点做,取最后取最小50个呢?这样很多排序都可以呀? 用快速排序,取小于2G的数据到内存,这批做完,释放heap上内存,然后再做下批,最后取最小50个,这完全用代码能现场写出来..


-如果是那意思的话,这题目30000的数据真忽悠人的...


-这职位月薪10K??

24 楼 downpour 2009-10-03  

最小化堆，能够找到一个数在一个序列中的位置。这个算法如果我没记错的话是快速排序的基础，学过数据结构的应该知道。

所以这个题很简单，只要每次在内存允许的范围内取数据放入内存，去做最小化堆的筛选。然后根据每次筛选的位置结果，把多余的数据去掉。然后重复多次即可。

23 楼 J-catTeam 2009-10-03  

lnaigg 写道

J-catTeam 写道

lnaigg 写道

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

朋友这个是有问题的，1000条里面你每个只找一条 如果莫一个1000条的第二大的数是整个3000w数据第2大的数，那么你不是取不到了么?

看清我的算法，明显不是简单地取每组最大那个数。

看到了哈，这个要复杂些

22 楼 lnaigg 2009-10-03  

J-catTeam 写道

lnaigg 写道

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

朋友这个是有问题的，1000条里面你每个只找一条 如果莫一个1000条的第二大的数是整个3000w数据第2大的数，那么你不是取不到了么?

看清我的算法，明显不是简单地取每组最大那个数。

21 楼 J-catTeam 2009-10-03  

kunee 写道

上学的时候没学过分冶还是咋地

分分不就出来了。。。

恩 忘记了 赐教？

20 楼 kunee 2009-10-03  

上学的时候没学过分冶还是咋地

分分不就出来了。。。

19 楼 J-catTeam 2009-10-02  

GooHome 写道

最小堆 大家知道吗？ 分冶法呀！

按照pk顺序去取50（这样数据库不会排序，排序就是一个死）然后合并 砍掉50 继续去下面的50 复杂度 我就不说了。

这是简单的而且普遍的处理办法。


补充一点：
这里的3000W件 其实一个幌子，而且还是一个分支点。

如果 3000W条记录*行记录字节数>2G的临界 不能一次取得内存队列里 （注意伪列和排序问题）

分析问题要一步一步来，然后就是多线程问题 加什么该死的二分法呀什么的。

这道题目不值10K月薪。

朋友能解释的再详细一点么？
在上面有一个朋友提到了 他说这道题是考验算法的 如果真是考验数据量的话，数据库分层，切分表什么的就能做的 ，是DBA考虑的东西，
所以这道题 ··我已经有点晕了

你最后说的不值10k还是不止10k啊？

18 楼 GooHome 2009-10-02  

最小堆 大家知道吗？ 分冶法呀！

按照pk顺序去取50（这样数据库不会排序，排序就是一个死）然后合并 砍掉50 继续去下面的50 复杂度 我就不说了。

这是简单的而且普遍的处理办法。


补充一点：
这里的3000W件 其实一个幌子，而且还是一个分支点。

如果 3000W条记录*行记录字节数>2G的临界 不能一次取得内存队列里 （注意伪列和排序问题）

分析问题要一步一步来，然后就是多线程问题 加什么该死的二分法呀什么的。

这道题目不值10K月薪。

17 楼 sky726 2009-10-02  

J-catTeam 写道

sky726 写道

恕我愚昧，不是很清楚题目意思
“取某项字段前50项数据”

比如这字段全部都是数字(1~3000w升序)
那题目做出来的结果，是不是1~50？
如果是这样，那分段来做结果怎么会对呢？

朋友你看哈 分成1000段 我取出来的是每段的前50条数据 这个样子就是为了避免 前面那位朋友出现的情况
···3000w的数据在数据库里面直接排序是不可能的~

原来如此，我想说的就是前面那位朋友的情况

16 楼 J-catTeam 2009-10-02  

sky726 写道

恕我愚昧，不是很清楚题目意思
“取某项字段前50项数据”

比如这字段全部都是数字(1~3000w升序)
那题目做出来的结果，是不是1~50？
如果是这样，那分段来做结果怎么会对呢？

朋友你看哈 分成1000段 我取出来的是每段的前50条数据 这个样子就是为了避免 前面那位朋友出现的情况
···3000w的数据在数据库里面直接排序是不可能的~

15 楼 J-catTeam 2009-10-02  

lnaigg 写道

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

朋友这个是有问题的，1000条里面你每个只找一条 如果莫一个1000条的第二大的数是整个3000w数据第2大的数，那么你不是取不到了么?

14 楼 boobmoom 2009-10-02  

题目确实写的不太清楚
对于我们这些小菜，不理解其中的一些默认条件
高手常常会把问题往难了想
我们就常常会把问题往简单了想