`
skzr.org
  • 浏览: 365525 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

10G的文件里都是乱序的整数,要求找出中位数。

阅读更多

问题帖子:10G的文件里都是乱序的整数,要求找出中位数

此问题可以引申为:

  1. 数据不一定为整数,而是任何个比较的数据
  2. 查找第N个数

思考了2个小时 我的思路

输入所有数据,返回第dataSize/2个值

-->分段读取数据-->分成N等分已经排好序的(保存每一段的最大,最小,中值,作为切分值点)

-->依次取N等分 使用切分值点切分追加到文件split(i)中 i表示第i个切分点

-->得到中间值所在的区间split(i) 好了现在回到了初始状态了,需要获取的是数据集split(i)的第(dataSize/2 - sum(i-1))个值;sum(i)=sum(i-1) + split(i).size

详细见图


  • 大小: 26.9 KB
分享到:
评论
8 楼 skzr.org 2010-04-07  
10G样本,按2G为一组
第1组:[1, 10G] 2G个
第2组:[2, 10G - 1]2G个
第3组:[3, 10G - 2]2G个
第4组:[4, 10G - 3]2G个
第5组:[5, 10G - 4]2G个
我的treeset只是需要一个合理的分割值而已,用于对10G数据进行合理的分割用
至于排序,这里使用treeset肯定是不合理的!因为可能存在相同的数

看样子需要实现一下来进行测试才好阿^ ^
7 楼 kimmking 2010-04-07  
<div class="quote_title">study2009 写道</div>
<div class="quote_div">呵呵,和前面腾讯面试题一样啊. <br><br>一个可以保证最坏运行时间为O(n)的算法,叫做 "Median of Medians algorithm" <br><br>1.将这n个元素分为5个一组,找出每组里的中间数,形成新的n/5亿个中间值组成的集合 <br>   2.对这n/5个值再分为5个一组,找出每组中间的数...重复这些步骤,只至找的到最后的中间值m <br>   3.以m为中值,将n个数分为L,R两组,L集合里的数都小于m,R集合里的数都大于m <br>     如果m=n/2,则返回m <br>     否则 如果L集合里的数多余一半,则从L集合中找出第n/2小的数 <br>          如果R集合里的数多余一半,R集合的元素个数为k, 则从R集合中找出第k-n/2小的数. <br>   4.如此重复迭代调用,直至找到中值. <br><br>网上可以找到该算法实现的源代码,多为内存排序,但也比较容易改为外排序. <br><br>对这个问题详细探讨间Blum, Floyd, Pratt, Rivest, and Tarjan 在1973年发表 <br>的论文"Time bounds for selection",这篇文章很难看懂. <br>也可以直接搜索"Median of Medians algorithm" <br><br><br>
</div>
<p> </p>
<p> 没什么大问题。</p>
<p>lz的方法有问题,不用排序,也不需要treeset。</p>
<p>另外一个方法是,先分成内存可操作的合适大小的块,比如1G内存,每次load 大概700-800M的数据量,</p>
<p>然后按这个标准切割所有数据分块。</p>
<p>每块内,使用类似快排的方式,找到中位数,o(块的length)</p>
<p>然后各个块的中位数最大的那个,可以去掉一半的数据,最小的那个,也可以去掉一半数据。</p>
<p>去掉后,再找中位数,再比较。</p>
<p>迭代。</p>
<p>即可。</p>
<p>平均应该是o(N)的。</p>
<p> </p>
<p> </p>
<p> </p>
6 楼 study2009 2010-04-06  
有什么问题?有些错别字,但总体上没有问题吧
5 楼 kimmking 2010-04-06  
楼上的步骤明显有问题。
4 楼 study2009 2010-04-06  
呵呵,和前面腾讯面试题一样啊.

一个可以保证最坏运行时间为O(n)的算法,叫做 "Median of Medians algorithm"

1.将这n个元素分为5个一组,找出每组里的中间数,形成新的n/5亿个中间值组成的集合
   2.对这n/5个值再分为5个一组,找出每组中间的数...重复这些步骤,只至找的到最后的中间值m
   3.以m为中值,将n个数分为L,R两组,L集合里的数都小于m,R集合里的数都大于m
     如果m=n/2,则返回m
     否则 如果L集合里的数多余一半,则从L集合中找出第n/2小的数
          如果R集合里的数多余一半,R集合的元素个数为k, 则从R集合中找出第k-n/2小的数.
   4.如此重复迭代调用,直至找到中值.

网上可以找到该算法实现的源代码,多为内存排序,但也比较容易改为外排序.

对这个问题详细探讨间Blum, Floyd, Pratt, Rivest, and Tarjan 在1973年发表
的论文"Time bounds for selection",这篇文章很难看懂.
也可以直接搜索"Median of Medians algorithm"


3 楼 worldterminator 2010-04-06  
一道算法题,比较简单,就是应用快排的思想。关于快排,不多说。
某个数的位置相当于文件指针吧,整个文件当成数组就可以。
2 楼 skzr.org 2010-04-06  
10G的文件里都是乱序的整数
都是乱序的整数!就是这一点,根本无法保证
中序值一定出现在这两个整数中(当缓存数组装满时,对数组进行排序,并取出中间的两个整数,保存)

比如缓存可以取2G,那么可以分5组,对应的值所在区间分别为
第1组:[1, 10G]
第2组:[2, 10G - 1]
第3组:[3, 10G - 2]
第4组:[4, 10G - 3]
第5组:[5, 10G - 4]
那就麻烦了

我的思路就是一步一步去第N个值肯定不在的区间!那么第n个值一定在剩余的区间中!从而问题回到递归开始,只是这个位置N会谁递归发生改变
1 楼 夜是天堂 2010-04-06  
数学不好,不知道这道题目可不可以这样解:

  • 根据可用内存大小,设置一个缓存数组,数组长度为偶数
  • 顺序读取文件,将整数逐个放入缓存数组
  • 当缓存数组装满时,对数组进行排序,并取出中间的两个整数,保存
  • 清空缓存数组,重复执行2-3
  • 如果最后一批无法装满缓存数组,需要特殊处理:
  • 重新构造一个数组,使其长度等于剩下整数的个数
  • 对新的数组进行排序
  • 如果数组长度为偶数,取中间两个整数,否则取最中间的那个整数,保存
  • 对上述保存的所有中间数字进行排序,这些数字的中位数是不是就等于所有整数序列的中位数?


如果上述逻辑可行,那程序就非常简单啊,读取一次文件就可以了。

相关推荐

Global site tag (gtag.js) - Google Analytics