面试之 top k问题

从大量数据里查找前多少大或者小的数据。

第一个例子：有4g内存，有1千万ipv4的地址。找其中出现次数最多的前100个。 设ipv4地址192.168.111.222。以字符串15个char,每个char两个字节。每个地址30字节存储。1千万就是3亿字节。 3亿字节 = 0.3g。所以内存够用。ipv4如果转为int存储。内存更小。

1.在内存够用的前提下：

首先进行统计。 再排序。

做出一个k,v的结构。每一个ip出现多少次。可以通过hashmap或者数组进行映射。 统计后排序找最大或最小。（这里的排序与堆排序有所不同） 比如找前100大的，我们假设先把hashmap或数组中的前100个当做最大的，只要记录这里边最小的那个。然后与新的数作比较。 大就留下把记录的那个丢掉，小的话就过。 借助顶堆降低复杂度。前一百大使用小顶堆，前一百小使用大顶堆。 比如找前100大的，可以创建一个100个节点的小顶堆，在维护小顶堆的时候与堆排序有所不同。堆排序是将所有的节点构造成一个堆，然后维护好之后呢他是每次将堆顶和最后一个节点互换位置。互换后将最后那个节点去掉。 这里的排序是维护一个100节点的堆。这个堆的大小不会改变。然后就是遍历咱们统计的那个hashmap或者是数组。先把前100个近似看作是出现最多的做成一个小顶堆。然后开始遍历第101个，每次与堆顶比较。如果比堆顶大。就与堆顶进行交换。交换完成后维护小顶堆。维护好就比较第102个数。这样依次比较下去就能得到前100个出现次数最多的堆。 复杂度nlogm,n代表这1千万，m代表前100。

2.内存不够：

给了100g的文本。文本出现如下两列，一个是ip地址，一个是url。找出url被不同的ip访问的次数的前100多的。 给了4g的机器，无限的硬盘。

1.2.3.4 baidu.com

1.2.3.4 taobao.com

1.2.3.3 taobao.com

1.2.2.2 baidu.com

1.2.2.2 baidu.com

这里就是baidu是2个，taobao也是2个。

1.有没有更多的机器。可以多机器处理，每个机器处理一部分。

2.借用现有的软件比如mysql。通过sql语句查出来。

3.借助硬盘排序。按照域名命名文件。把访问这个域名的ip放进来，或者使用hash，对域名进行对n求余，将相同的域名数据放入到同一个文本便于统计。 统计时读取文件，不需要把所有的文件都放在内存中，读一个文件把域名对应独立ip的个数统计一下。 统计完成之后又可以借助顶堆计算。