海量数据处理专题(九)——外排序

【引言】

在数据结构的课程上,我们学习了不少的排序算法,冒泡,堆,快排,归并等。但是这些排序方法有着共同的特点,那就是所有的操作都是在内存中完成的,算法过程中不需要IO,这就使得这样的算法总体上速度比较快,但是也随之出现了一个问题:当需要排序的数据量异常的大的时候,以上的算法就显得力不从心了。这时候,你需要一种另外的排序算法,它的名字叫“外排序”。

通常的,设备的内存读取速度要比外存读取速度快得多(RAM的访问速度大约是磁盘的25万倍),但是内存的容量却要比外存小很多,当所有的数据不能在内存中完全放下的时候,就需要使用到外排序。这是外排序的一个显著特征。 继续阅读

m进制转换为n进制-任意进制转换算法

这种题也是一道经典的面试题,主要考察进制转换细想,Coding质量等。

当我们把十进制转成二进制的时候,我们通过辗转相除,取余,逆置余数序列的过程得到新的进制的数。因此我们可以借助这种思想把M进制转成N进制的数。 继续阅读

一个Sqrt函数引发的血案

好吧,我承认我标题党了,不过既然你来了,就认真看下去吧,保证你有收获。

我们平时经常会有一些数据运算的操作,需要调用sqrt,exp,abs等函数,那么时候你有没有想过:这个些函数系统是如何实现的?就拿最常用的sqrt函数来说吧,系统怎么来实现这个经常调用的函数呢?

虽然有可能你平时没有想过这个问题,不过正所谓是“临阵磨枪,不快也光”,你“眉头一皱,计上心来”,这个不是太简单了嘛,用二分的方法,在一个区间中,每次拿中间数的平方来试验,如果大了,就再试左区间的中间数;如果小了,就再拿右区间的中间数来试。比如求sqrt(16)的结果,你先试(0+16)/2=8,8*8=64,64比16大,然后就向左移,试(0+8)/2=4,4*4=16刚好,你得到了正确的结果sqrt(16)=4。然后你三下五除二就把程序写出来了: 继续阅读

Top K算法详细解析—百度面试

问题描述:

这是在网上找到的一道百度的面试题:

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。


问题解析:

【分析】:要统计最热门查询,首先就是要统计每个Query出现的次数,然后根据统计结果,找出Top 10。所以我们可以基于这个思路分两步来设计该算法。下面分别给出这两步的算法: 继续阅读