当年腾讯笔试最后附加题

diwayou

1G可用内存，3G整型数据在硬盘上，设计算法找到中位数，大家给点思路吧

diwayou

都不感兴趣？ 腾讯每年都有一道类似的题，大家给点思路！3Q

lidudu

一个做法：

取mid为初始中间值，比如整数的(max + min) /2
顺序读取数据（不占内存），得到大于m的整数个数nAbove和小于的个数nBelow
如果nAbove较大则递归处理（mid,max)的范围，nBelow较大则递归处理(min, mid)的范围
相等则mid即为中位数

另一个做法：
用堆排序整个排序了，然后取中位数

diwayou

你这个方法不对，第一你不知道整数的分布情况，mid没法取
第二你每次递归都需要从硬盘读取数据，性能很差
最重要的是你求不出正确结果

diwayou

lidudu: Re:当年腾讯笔试最后附加题

一个做法：

取mid为初始中间值，比如整数的(max + min) /2
顺序读取数据（不占内存），得到大于m的整数...

刚注意，你竟然用堆排序，你看题了吗？ 数据是3G,内存只有1G

OpenGPU

支持一下 ：〉


-------------------------------------------------------------------------------------------

欢迎访问开源图形处理器体系结构论坛(OpenGPU论坛) http://www.opengpu.org/bbs/

OpenGPU Graphics Open Source community（图形开源社区），聚焦领域(focus domain)包括：
  * GPU Architecture（图形处理器体系结构）
  * Graphics Algorithm（图形算法）
  * GPGPU Programming （面向通用的图形处理器编程）
  * Open Source Rendering Engine（开源渲染器）
  * Open Source GPU Simulator/RTL Implement（开源GPU模拟器

lidudu

diwayou: Re:当年腾讯笔试最后附加题

你这个方法不对，第一你不知道整数的分布情况，mid没法取
第二你每次递归都需要从硬盘读取数据，性能很差
最重要的是你求不出正确结果

早知道你这种思维就不回你了。谁说要知道整数分布情况了，我都说了是(max + min)/2，对有符号整数0就行了

第二种方法，你连堆排序是外部排序算法的一种都不知道，也就不用考虑这些问题了

diwayou

lidudu: Re: Re:当年腾讯笔试最后附加题



早知道你这种思维就不回你了。谁说要知道整数分布情况了，我都说了是(max + min)/2，对有符号整数0就行...

我的错，但是你第一种方法需要读取数据多少遍呢？ 从硬盘读取数据可是昂贵的。
第二种：堆排序是每次删除堆顶的数据，而每次重新建堆都需要所有的数据吧？你能每次都重新读取数据？

lidudu

diwayou: Re: Re: Re:当年腾讯笔试最后附加题


我的错，但是你第一种方法需要读取数据多少遍呢？ 从硬盘读取数据可是昂贵的。
第二种：堆排序是每次删除堆顶的数据，而每次重新建堆都需要所有的数据吧？你能每次都重新读取数据？

第一种方法读取 log n 遍

第二种请看堆排序的外部排序版本

diwayou

lidudu: Re: Re: Re: Re:当年腾讯笔试最后附加题



第一种方法读取 log n 遍

第二种请看堆排序的外部排序版本

第一种怎么处理重复的数据呢？问了这么多，真的很感谢你！希望不要烦。 [em10]