|
精华帖 (1) :: 良好帖 (0) :: 新手帖 (11) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-10-03
上学的时候没学过分冶还是咋地
分分不就出来了。。。 |
| 返回顶楼 | |
|
发表时间：2009-10-03
kunee 写道 上学的时候没学过分冶还是咋地
分分不就出来了。。。 恩 忘记了 赐教？ |
| 返回顶楼 | |
|
发表时间：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大的数，那么你不是取不到了么? 看清我的算法，明显不是简单地取每组最大那个数。 |
| 返回顶楼 | |
|
发表时间：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大的数，那么你不是取不到了么? 看清我的算法，明显不是简单地取每组最大那个数。 看到了哈，这个要复杂些 |
| 返回顶楼 | |
|
发表时间：2009-10-03
最小化堆，能够找到一个数在一个序列中的位置。这个算法如果我没记错的话是快速排序的基础，学过数据结构的应该知道。
所以这个题很简单，只要每次在内存允许的范围内取数据放入内存，去做最小化堆的筛选。然后根据每次筛选的位置结果，把多余的数据去掉。然后重复多次即可。 |
| 返回顶楼 | |
|
发表时间：2009-10-04
最后修改：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?? |
| 返回顶楼 | |
|
发表时间：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）？ |
| 返回顶楼 | |
|
发表时间：2009-10-05
其实最快的方法就是遍历整组数据，取最大值，然后删掉它，重复50次，每次时间代价为O(3000w)，50次就是1.5billion，这个复杂度不错了，至少比那些O(n log n)的堆好
|
| 返回顶楼 | |
|
发表时间：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 暂时走开暂存 |
| 返回顶楼 | |
|
发表时间：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 暂时走开暂存 内存不足的办法？ 不是分批取么？ |
| 返回顶楼 | |
