|
精华帖 (1) :: 良好帖 (0) :: 新手帖 (11) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-10-06
最小堆的时间复杂度是O(nlogk),其中k=50,n=3000w
你说的遍历的时间复杂度是O(nk) 就单线程来说的话，用最小堆肯定是最优的 xiaokan 写道 其实最快的方法就是遍历整组数据，取最大值，然后删掉它，重复50次，每次时间代价为O(3000w)，50次就是1.5billion，这个复杂度不错了，至少比那些O(n log n)的堆好
|
| 返回顶楼 | |
|
发表时间：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够的话 |
| 返回顶楼 | |
|
发表时间：2009-10-07
最后修改：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原来这里有人一帖多发啊。。。 |
| 返回顶楼 | |
|
发表时间：2009-10-07
最后修改：2009-10-07
这个题目 其实 没有什么标准 答案；
肯定看你怎么考虑的； 要是 我每条记录有个图像都是几M怎么办？ 呵呵！ 我们只能忽略每条记录列的大小；简单理解没条记录暂用很少空间； 3000w的数据再那里，在硬盘，已经在内存，在内存怎么存放？ 如果在硬盘，你读进来这么存放？ 读取I/O效率怎么样？ 很多问题要考虑； 其实是解决问题 思考问题能力； 要是我遇见这样题目，我肯定列出N种可能； 每种可能 什么思路？ |
| 返回顶楼 | |
|
发表时间：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这样的系统 解决多少？ 我只能想想而已哦，我们这样的公司 不会遇见； |
| 返回顶楼 | |
|
发表时间：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条啊 |
| 返回顶楼 | |
|
发表时间：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条统一排序. |
| 返回顶楼 | |
|
发表时间：2009-10-08
这道题··实际少是没有标准的答案吧？
不论是最小堆，分治法或者其他怎么··我们是不是过多的考虑到了算法或其他的东西 ··对于阿里巴巴而言 3000w的数据很少，但是是一定会切库，分表，读写分离，==一系列的操作。是为了保证性能。 ··所以我们考虑这道题的基础到底是不是放在这3000w的数据放在切分的表中 还是考虑这3000w的数据是放在一张表中····· 如果3000w的数据像第一种，已经被分化好了。那么是不是可以这样子想。··直接按照每表取50条这种策略来想 如果是第二种的东西那又怎么办。select的语句···20w的数据几乎就是比较慢的，当然是对于我们这种自己用的笔记本什么的。jvm在windows上能控制的内存最大为大约为1.6g。 这1.6g也不可能全部拿去放置select出来的数据。如果是这样子又怎么样。 所以对于先那个朋友说3000w的数据每次找出最大的然后删除。 我只能说··不可能的。 我试过 20w的数据找出最大值已经很慢了。3000w的数据，我更不敢想······ 而且，要是这张表是需要使用的表，随意的删除，别人怎么读？ 所以不论怎么想，我们试试，就会发现···问题远远不止这些，当然，学习到得会更多。 |
| 返回顶楼 | |
|
发表时间：2009-10-09
我觉得可以这样，
如果3000万数据在一个文件里面的话，可以用RandomAccessFile来读文件，每次读的时候数据小于2G内存就可以。然后用一个TreeMap(红黑树的实现)往里面一直放最多50条记录，当然每条记录需要实现Comparator接口，这样才能比较每条记录。放完了记录再接着往下读就可以，这样读一遍就可以选出前50条记录。也可以再针对这50条记录排序就行。 |
| 返回顶楼 | |
|
发表时间：2009-10-09
niveko 写道 我觉得可以这样，
如果3000万数据在一个文件里面的话，可以用RandomAccessFile来读文件，每次读的时候数据小于2G内存就可以。然后用一个TreeMap(红黑树的实现)往里面一直放最多50条记录，当然每条记录需要实现Comparator接口，这样才能比较每条记录。放完了记录再接着往下读就可以，这样读一遍就可以选出前50条记录。也可以再针对这50条记录排序就行。 朋友··你看··jvm在windows上能控制的内存是在1.6g左右的，这里面肯定还有其他的开销，最后真正能放置数据的内存量是小于1.6g的，如果真的是把全部数据都往内存里面读（读到内存可以接受的最大值）···系统会很慢的，几乎被占完了~ 当然你的思路是很好的哈~~~ |
| 返回顶楼 | |
