在一堆随机数中，找出最大的N个数 - 开源中国社区
当前访客身份：游客 [
当前位置：
发布于 日 17时,
TOPN，Java实现
代码片段(1)
1.&[代码][Java]代码&&&&
package com.
import java.util.R
使用小顶堆求解
AMD 4400+,Win7 64 ,4G RAM,JDK1.6_update24
求1亿随机数TopN，耗时1.4S
public class TopN {
private int[] arr=
private int setCount=0;
public TopN(){
this(100);
public TopN(int top){
this.top =
private void init(){
arr = new int[top];
random = new Random();
for(int i=0;i&i++){
arr[i] = Integer.MIN_VALUE;
public boolean compare(int index,int value){
if(arr[index]&value){
public void setValue(int index,int value){
this.arr[index] =
public void setInMax(int value){
this.arr[setCount++] =
if(setCount == top){
this.heap();
public boolean isMaxSetCount(){
return setCount&=
public int getNextInt(){
int i = this.random.nextInt();
public void heap(){
int length =arr.
int t= (length-1)&&1;
for(int i=t;i&=0;i--){
minHeapify(arr,i,length);
private void minHeapify(int[] array,int i,int size){
int l = ((i&&1)+1);
int r = l+1;
if(l&size && pare(l, arr[min])){
if(r&size && pare(r, arr[min])){
if(min != i){
swap(array,min,i);
if(min&size-1){
minHeapify(array, min, size);
private void swap(int[] array,int i,int j){
array[i]^=array[j];
array[j]^=array[i];
array[i]^=array[j];
public void print(){
for(int i : arr){
System.out.print(i+",");
if(j&=10){
System.out.println();
System.out.println();
public static void main(String[] args){
long start =System.nanoTime();
TopN t100 = new TopN(100);
for(long i=0;i&;i++){
int tmp = t100.getNextInt();
if(!t100.isMaxSetCount()){
t100.setInMax(tmp);
}else pare(0, tmp)){
t100.setValue(0, tmp);
t100.heap();
long end = System.nanoTime();
t100.print();
System.out.println("Used time:"+(end-start)/1000000+" ms");
开源中国-程序员在线工具：
minHeapify方法和heap方法起什么作用。。能不能把算法细节描述一下。
2楼：excepiton 发表于
引用来自“zhanghua.1199”的评论minHeapify方法和heap方法起什么作用。。能不能把算法细节描述一下。堆排序的其中一步，把这个数组按照堆的性质排列，保证堆顶数是最小数，这个是小顶堆
3楼：zhanghua.1199 发表于
&intt= (length-1)&&1;
&intl = ((i&&1)+1);
我对这两步起什么作用，实在不解，望解答，谢谢。
4楼：excepiton 发表于
引用来自“zhanghua.1199”的评论&intt= (length-1)&&1;
&intl = ((i&&1)+1);
我对这两步起什么作用，实在不解，望解答，谢谢。用移位来代替乘除。 int t = (length-1)&&1，这里是取数组中，中间的数的index。 int l = ((i&&1)+1)相当于i*2+1 小顶堆的性质是 ki&=k(2i）且ki&=k(2i+1)(1≤i≤ n
5楼：朱柳瑞 发表于
array[i]^ 这个^是啥意思？？
6楼：excepiton 发表于
引用来自“朱柳瑞”的评论array[i]^ 这个^是啥意思？？异或，用异或来代替新开变量交换，心里上是速度高点
7楼：朱柳瑞 发表于
引用来自“throwable”的评论引用来自“朱柳瑞”的评论array[i]^ 这个^是啥意思？？异或，用异或来代替新开变量交换，心里上是速度高点就是 异或 的速度会快一点是吧
开源从代码分享开始
excepiton的其它代码 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
实用数据结构 教学配套课件
作者 佟伟光 第七章 排序 在线阅读 下载
下载积分：400
内容提示：实用数据结构 教学配套课件
作者 佟伟光 第七章 排序 在线阅读 下载
文档格式：PDF|
浏览次数：1|
上传日期： 04:45:35|
文档星级：
全文阅读已结束，如果下载本文需要使用
 400 积分
下载此文档
该用户还上传了这些文档
实用数据结构 教学配套课件
作者 佟伟光 第七章 排序
官方公共微信主题信息（必填）
主题描述（最多限制在50个字符）
申请人信息（必填）
申请信息已提交审核，请注意查收邮件，我们会尽快给您反馈。
如有疑问，请联系
CSDN &《程序员》编辑/记者，投稿&纠错等事宜请致邮
傻丫头和高科技产物小心翼翼的初恋
如今的编程是一场程序员和上帝的竞赛，程序员要开发出更大更好、傻瓜都会用到软件。而上帝在努力创造出更大更傻的傻瓜。目前为止，上帝是赢的。个人网站：。个人QQ群：、
个人大数据技术博客：
所谓海量数据处理，是指基于海量数据的存储、处理或操作。因为数据量太大，导致要么无法在较短时间内迅速解决，要么无法一次性装入内存。事实上，对于时间问题，可以采用巧妙的算法搭配合适的数据结构（如布隆过滤器、散列、位图、堆、数据库、倒排索引、Trie 树）来解决；对于空间问题，可以采取分而治之的方法（如利用散列映射），把规模大的数据转化为规模小的，最终各个击破。处理海量数据问题有很多种方法，本章介绍10种典型方法：散列分治、多层划分、MapReduce、外排序、位图、布隆过滤器、Trie树、数据库、倒排索引和simhash算法。本章将摒弃绝大部分的细节，重点谈方法和模式论，且注重用通俗、直白的语言阐述相关问题。最后，有一点必须强调的是，本章内容是基于面试题的分析基础进行讲述的，具体实践过程中要视具体情况具体分析，且各个场景下需要考虑的细节也远比本章所描述的任何一种解决方案复杂得多。基础知识：STL容器先具体了解一下STL容器，它是许多解决方案的基础。一般来说，STL容器分两种：序列式容器和关联式容器。序列式容器包括vector、list、deque、stack、queue、heap等，而关联式容器中，每笔数据或每个元素都有一个键（key）和一个值（value），即所谓的键值对。当元素被插入到关联式容器中时，容器的内部结构（可能是红黑树，也可能是散列表）便会依照其值大小，以某种特定规则将这个元素放置于适当的位置。在C++ 11标准之前，旧标准规定标准的关联式容器分为set（集合）和map（映射）两大类，以及这两大类的衍生体multiset（多键集合）和multimap（多键映射），这些容器均基于red-black tree（红黑树）实现。此外，还有另一类非标准的关联式容器，即hashtable（散列表），以及以hashtable为底层实现机制的hash_set（散列集合）、hash_map（散列映射）、hash_multiset（散列多重集合）和hash_multimap（散列多重映射）。也就是说，set、map、multiset和multimap都内含一个红黑树，而hash_set、hash_map、hash_multiset、和hash_multimap都内含一个hashtable{![ C++ 11标准之后，准备引入非标准的关联式容器hashtable，但为了避免与已经存在的hash_map等第三方容器的名字产生冲突，命名了基于散列函数实现的unordered_set、unordered_map和unordered_multiset、unordered_multimap，分别相当于hash_set、hash_map和hash_multiset、hash_multimap。但是，采用哪种名字不是本书的重点，所以下文在用到无序的关联式容器时，依然会继续沿用旧标准中的hash_set、hash_map、hash_multiset和hash_multimap。]}，具体关系如图6-1所示。图6-1set、map、multiset 和multimapset同map一样，所有元素都会根据元素的键自动排序，因为set和map两者的所有操作都只是转而调用红黑树的操作行为。不过，值得注意的是，两者都不允许任意两个元素有相同的键。不同的是，set的元素不像map那样可以同时拥有值和键，set元素的值就是键，键就是值，而map的所有元素都是pair，同时拥有值和键，pair的第一个元素被视为键，第二个元素被视为值。至于multiset和multimap，它们的特性及用法与set和map几乎相同，唯一的差别就是它们允许键重复，即所有的插入操作基于红黑树的insert_equal()而非insert_unique()。hash_set、hash_map、hash_multiset和hash_multimaphash_set和hash_map的一切操作都是基于hashtable的。不同的是，hash_set同set一样，同时拥有值和键，且值就是键，键就是值，而hash_map同map一样，每一个元素同时拥有一个值和一个键，所以其使用方式和map基本相同。另外，因为hash_set和hash_map都是基于hashtable的，而hashtable没有自动排序功能，所以hash_set和hash_map都不具备自动排序功能。至于hash_multiset和hash_multimap，它们的特性与multiset和multimap几乎完全相同，唯一的差别就是hash_multiset和hash_multimap的底层实现机制是hashtable（区别于multiset和multimap的底层实现机制红黑树），所以它们的元素都不会被自动排序，不过都允许键重复。综上所述，什么样的结构决定其什么样的性质，因为set、map、multiset和multimap的实现都是基于红黑树的，所以有自动排序功能，而hash_set、hash_map、hash_multiset和hash_multimap的实现都是基于hashtable的，所以不含有自动排序功能，加个前缀multi无非就是允许键重复而已，如图6-1所示。散列分治方法介绍对于海量数据而言，由于无法将其一次性装进内存进行处理，不得不将其通过散列映射的方法分割成相应的小块数据，然后再针对各个小块数据通过hash_map进行统计或其他操作。那么什么是散列映射呢？简单来说，为了方便计算机在有限的内存中处理大量数据，通过映射的方式让数据均匀分布在对应的内存位置上（例如，大数据通过取余的方式映射成小数据存放在内存中，或把大文件映射成多个小文件），而这种映射的方式通常通过散列函数进行映射，好的散列函数能让数据均匀分布而减少冲突。问题实例寻找Top IP从海量日志数据中提取出某日访问百度（）次数最多的那个IP。 分析： 百度作为国内第一大搜索引擎，每天访问它的IP数量巨大，如果想一次性把所有IP数据装进内存处理，内存容量通常不够，故针对数据量太大、内存受限的情况，可以把大文件转化成（取模映射）小文件，从而大而化小，逐个处理。简言之，先映射，而后统计，最后排序。 解法： 具体分为下述三个步骤。（1）分而治之/散列映射。先将该日访问百度的所有IP从访问日志中提取出来，然后逐个写入一个大文件中，接着采取散列映射的方法（如hash(IP) % 1000），把整个大文件的数据映射到1000个小文件中{![hash取模是一种等价映射，不会存在同一个IP分散到不同的小文件中的情况。换言之，如果两个IP相等，那么经过hash(IP)之后的散列值是相同的，将此散列值取模（如模1000）必定仍然相等，所以同一个IP在散列取模后，只可能落在同一个小文件中，不可能被分散。]}。（2）hash_map统计。大文件转化成了小文件，便可以采用hash_map(ip, value)分别对1000个小文件的IP进行频率统计，找出每个小文件中出现频率最高的IP，总共1000个IP。（3）堆/快速排序。统计出1000个频率最高的IP后，依据它们各自频率的大小进行排序（可采取堆排序），找出最终那个出现频率最高的IP，即为所求。寻找热门查询搜索引擎会通过日志文件把用户每次检索所使用的所有查询串都记录下来，每个查询串的长度为1～255字节。假设目前有1000万条查询记录（但是，因为这些查询串的重复度比较高，所以虽然总数是 1000 万，但如果除去重复后，查询串query不超过300万个），请统计其中最热门的10个查询串，要求使用的内存不能超过1 GB。 分析： 一个查询串的重复度越高说明查询它的用户越多，也就是越热门。如果是1亿个IP求Top 10，可先00将IP分到1000个小文件中去，并保证一个IP只出现在一个文件中，再对每个小文件中的IP进行hash_map统计并按数量排序，最后用归并或者最小堆依次处理每个小文件中的Top 10以得到最后的结果。但是对于本题，是否也需要先把大文件弄成小文件呢？根据题目描述，虽然有1000万个查询，但是因为重复度比较高，去除重复后，事实上只有300万个查询，每个查询为255字节，所以可以考虑把它们全部放进内存中去（假设300万个字符串没有重复，都是最大长度，那么最多占用内存3000000 × 255 = 765MB=0.765GB，所以可以将所有字符串都存放在内存中进行处理）。考虑到本题中的数据规模比较小，能一次性装入内存，因而放弃分而治之/散列映射的步骤，直接用hash_map统计，然后排序。事实上，针对此类典型的Top k问题，采取的对策一般都是“分而治之/散列映射（如有必要）+ hash_map+堆”。 解法： （1）hash_map统计。对这批海量数据进行预处理，用hash_map完成频率统计。具体做法是：维护一个键为query、value为该query出现次数的hash_map，即hash_map(query, value)，每次读取一个query，如果该query不在hash_map中，那么将该query放入hash_map中，并将它的value值设为1；如果该query在hash_map中，那么将该query的计数value加1即可。最终我们用hash_map在O(n)的时间复杂度内完成了所有query的频率统计。（2）堆排序。借助堆这种数据结构，找出Top k，时间复杂度为O(n’logk)。也就是说，借助堆可以在对数级的时间内查找或调整移动。因此，维护一个k（该题目中是10）大小的最小堆，然后遍历300万个query，分别和根元素进行比较，最终的时间复杂度是O(n) + O(n’logk)，其中n为1000万，n’为300万。关于上述过程中的第2步（堆排序），进一步讲，可以维护k个元素的最小堆，即用容量为k的最小堆存储最先遍历到的k个数，并假设它们就是最大的k个数，建堆费时O(k)，有k1 & k2 &…& kmin（设kmin为最小堆中最小元素）。继续遍历整个数列剩下的n-k个元素，每次遍历一个元素x，将其与堆顶元素进行比较，若x & kmin则更新堆（x入堆，每次调整堆费时O(log k)），否则不更新堆。这样下来，总费时O(k + (n-k)log k ) = O(nlogk)。此方法得益于在堆中查找等各项操作的时间复杂度均为O(log k)。当然，也可以采用Trie树，结点里存该查询串出现的次数，没有出现则为0，最后用10个元素的最小堆来对出现频率进行排序。寻找出现频率最高的100个词有一个1 GB大小的文件，里面每一行是一个词，每个词的大小不超过16字节，内存大小限制是1 MB。请返回出现频率最高的100个词。 解法： （1）分而治之/散列映射。按先后顺序读取文件，对于每个词x，执行hash(x)%5000，然后将该值存到5000个小文件（记为x0, x1,…, x4999）中。此时，每个小文件的大小大概是200 KB。当然，如果其中有的小文件超过了1 MB，则可以按照类似的方法继续往下分，直到分解得到的所有小文件都不超过1MB。（2）hash_map统计。对每个小文件采用hash_map/Trie树等数据结构，统计每个小文件中出现的词及其相应的出现次数。（3）堆排序或者归并排序。取出出现次数最多的100个词（可以用含100个结点的最小堆）后，再把100个词及相应的出现次数存入文件中，这样又得到5000个文件。最后对这5000个文件进行归并（可以用归并排序）。寻找Top 10有海量数据分布在100台电脑中，请想个办法高效统计出这批数据出现次数最多的Top 10。 解法一： 如果同一个数据元素只出现在某一台机器中，那么可以采取以下步骤统计出现次数为Top 10的数据元素。（1）堆排序。在每台电脑上求出Top 10，可以采用包含10个元素的堆完成。（求Top 10小用最大堆，求Top 10大用最小堆。比如，求Top 10大，首先取前10个元素调整成最小堆，假设这10个元素就是Top 10大，然后扫描后面的数据，并与堆顶元素进行比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆，否则不调整。最后堆中的元素就是Top 10大。）（2）组合归并。求出每台电脑上的Top 10后，把这100台电脑上的Top 10组合起来，共1000个数据，再根据这1000个数据求出Top 10就可以了。 解法二： 但是，如果同一个元素重复出现在不同的电脑中呢？举个例子，给定两台机器，第一台机器的数据及各自出现的次数为a（53）、b（52）、c（49）、d（49）、e（0）、f（0）（括号里的数字代表某个数据出现的次数），第二台机器的数据及各自出现的次数为a（0）、b（0）、c（49）、d（49）、e（51）、f（50），求所有数据中出现次数最多的Top 2。很明显，如果先求出第一台机器的Top 2——a（53）和b（52），然后再求出第二台机器的Top 2——e（51）和f（50），最后归并a（53）、b（52）、e（51）和f（50），得出最终的Top 2——a（53）和b（52）并非实际的Top 2，因为实际的Top 2是c（49 + 49）和d（49 + 49）。有两种方法可以解决这个问题。
遍历一遍所有数据，重新散列取模，使同一个元素只出现在单独的一台电脑中，然后采取上面所说的方法，统计每台电脑中各个元素的出现次数，找出Top 10，继而组合100台电脑上的Top 10，找出最终的Top 10。
蛮力求解，直接统计每台电脑中各个元素的出现次数，然后把同一个元素在不同机器中的出现次数相加，最终从所有数据中找出Top 10。
查询串的重新排列有10个文件，每个文件的大小是1 GB，每个文件的每一行存放的都是用户的查询串query，每个文件的query都可能重复。请按照query的频度排序。 解法一： 分为以下三个步骤。（1）散列映射。顺序读取10个文件，按照hash(query)的结果将query写入另外10个文件（记为a0, a1,…, a9）中。这样，新生成的每个文件的大小约为1 GB（假设散列函数是随机的）。（2）hash_map统计。找一台内存在2 GB左右的机器，依次用hash_map(query, query_count)来统计每个query出现的次数。注意，hash_map(query, query_count)是用来统计每个 query 的出现次数的，而不是存储它们的值，query 出现一次则query_count+1。（3）堆排序、快速排序或者归并排序。利用快速排序、堆排序或者归并排序按照出现次数进行排序，将排好序的query和对应的query_cout输出到文件中。这样就得到了10个排好序的文件（记为b0, b1,…, b9）。最后，对这10个文件进行归并排序（内排序与外排序相结合）。 解法二： 一般情况下，query的总量是有限的，只是重复的次数比较多而已，对于所有的query，可能一次性就可以加入内存。这样就可以采用Trie树、hash_map等直接统计每个query出现的次数，然后按出现次数做快速排序、堆排序或者归并排序就可以了。 解法三： 与解法一类似，但在做完散列，分成多个文件后，可以交给多个文件，采用分布式架构来处理（如MapReduce），最后再进行合并。寻找共同的URL给定a和b两个文件，各存放50亿个URL，每个URL占64字节，内存限制是4 GB。请找出a和b文件中共同的URL。 解法： 可以估计出每个文件的大小为×64=320 GB，远远大于内存限制的4 GB，所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。（1）分而治之/散列映射。遍历文件a，对每个URL求取hash(URL)00，然后根据所取得的值将URL分别存储到1000个小文件中（记为 a0, a1,…, a999）。这样每个小文件大约为300 MB。遍历文件b，采取和a相同的方式将URL分别存储到1000小文件中（记为b0, b1,…, b999）。这样处理后，所有可能相同的URL都在对应的小文件中（a0对应b0, a1对应b1,…, a999对应b999），不对应的小文件不可能有相同的URL。然后只要求出1000对小文件中相同的URL即可。（2）hash_set统计。求每对小文件中相同的URL时，可以把其中一个小文件的URL存储到hash_set中，然后遍历另一个小文件的每个URL，看其是否在刚才构建的hash_set中，如果在，就是共同的URL，保存到文件里就可以了。举一反三寻找最大的100个数从100万个数中找出最大的100个数。
{提示：!}选取前100个元素并排序，记为序列L。然后依次扫描剩余的元素x，与排好序的100个元素中最小的元素比较，如果比这个最小的元素大，就把这个最小的元素删除，利用插入排序的思想将x插入到序列L中。依次循环，直到扫描完所有的元素。复杂度为O(10***8***×100)。也可以利用快速排序的思想，每次分割之后只考虑比主元大的一部分，直到比主元大的一部分比100多的时候，采用传统排序算法排序，取前100个。复杂度为O(10***8***× 100)。此外，还可以用一个含100个元素的最小堆来完成，复杂度为O(10***8***× log100)。
统计10个出现次数最多的词一个文本文件有上亿行甚至10亿行，每行中存放一个词，要求统计出其中出现次数最多的前10个词。 解法一： 如果文件比较大，无法一次性读入内存，可以采用散列取模的方法，将大文件分解为多个小文件，对单个小文件利用hash_map统计出每个小文件中10个出现次数最多的词，然后再进行归并处理，找出最终的10个出现次数最多的词。 解法二： 通过散列取模将大文件分解为多个小文件后，除了可以用hash_map统计出每个小文件中10个出现次数的词，也可以用Trie树统计每个词出现的次数，最终同样找出出现次数最多的前10个词（可用堆来实现）。寻找出现次数最多的数怎样在海量数据中找出重复次数最多的一个？
{提示：!}先做散列，然后求模，映射为小文件，求出每个小文件中重复次数最多的一个数，并记录重复次数，最后找出上一步求出的数据中重复次数最多的一个，即是所求。
统计出现次数最多的前n个数据有上千万或上亿个数据（有重复），统计其中出现次数最多的前n个数据。
{提示：!}上千万或上亿个数据在现在的机器的内存中应该能存下，所以考虑采用hash_map、搜索二叉树、红黑树等来进行次数统计，然后取出前n个出现次数最多的数据，这一步可以用堆完成。
1000万个字符串的去重有1000万个字符串，其中有些字符串是重复的，请把重复的字符串全部去掉，保留没有重复的字符串。
{提示：!}本题用Trie树比较合适，hash_map也行。当然，也可以先散列成小文件分开处理再综合。
多层划分方法介绍多层划分法本质上还是遵循分而治之的思想。因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后在一个可以接受的范围内进行查找。问题实例寻找不重复的数在2.5亿个整数中找出不重复的整数的个数。注意，内存空间不足以容纳这2.5亿个整数。 分析： 类似于鸽巢原理，因为整数个数为2***32***，所以，可以将这2***32***个数划分为2***8***个区域（比如，用一个文件代表一个区域），然后将数据分到不同的区域，最后不同的区域再利用位图进行统计就可以直接解决了。也就是说，只要有足够的内存空间，就可以很方便地解决。寻找中位数找出5亿个int型数的中位数。 分析： 首先将这5亿个int型数划分为2***16***个区域，然后读取数据统计落到各个区域里的数的个数，根据统计结果就可以判断中位数落到哪个区域，并知道这个区域中的第几大数刚好是中位数。然后，第二次扫描只统计落在这个区域中的那些数就可以了。实际上，如果不是int型而是int64型，经过3次这样的划分即可降低到能够接受的程度。也就是说，可以先将5亿个int64型数划分为2***24***个区域，确定每个数是其所在区域的第几大数，然后再将该区域分成2***20***个子区域，确定是子区域的第几大数，最后当子区域里的数的个数只有2***20***个时，就可以利用直接寻址表进行统计。MapReduce方法介绍MapReduce是一种计算模型，简单地说就是将大批量的工作或数据分解执行（称之为Map），然后再将结果合并成最终结果（称之为Reduce）。这样做的好处是，可以在任务被分解后通过大量机器进行分布式并行计算，减少整个操作的时间。可以说，MapReduce的原理就是一个归并排序，它的适用范围为数据量大而数据种类少以致可以放入内存的场景。MapReduce模式的主要思想是将要执行的问题（如程序）自动拆分成Map和Reduce的方式，其流程如图6-2所示。图6-2在数据被分割后，通过Map函数将数据映射到不同的区块，分配给计算机集群处理，以达到分布式计算的效果，再通过Reduce函数的程序将结果汇总，从而输出需要的结果。MapReduce 借鉴了函数式程序设计语言的设计思想，其软件实现是指定一个Map函数，把键值对映射成新的键值对，形成一系列中间结果构成的键值对，然后把它们传给 Reduce 函数，把具有相同中间形式的键值对合并在一起。Map 函数和Reduce函数具有一定的关联性。问题实例寻找n2个数的中数一共有n台机器，每台机器上有n个数，每台机器最多存O(n)个数并对它们进行操作。如何找到n2个数的中数（median）？外排序方法介绍顾名思义，所谓外排序就是在内存外面的排序。当要处理的数据量很大而不能一次性装入内存时，只能将数据放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据，将其排序后输出到一个临时文件，依次进行，将待排序数据组织为多个有序的临时文件，而后在归并阶段将这些临时文件组合为一个大的有序文件，即为排序结果。举个例子。假定现在有一个含有20个数据{5, 11, 0, 18, 4, 14, 9, 7, 6, 8, 12, 17, 16, 13, 19, 10, 2, 1, 3, 15}的文件A，但使用的是一次只能装4个数据的内存，所以可以每趟对4个数据进行排序，即5路归并，具体方法如下述步骤所示。首先把“大”文件A分割为a1、a2、a3、a4、a5这5个小文件，每个小文件包含4个数据：
a1文件的内容为{5, 11, 0, 18}；
a2文件的内容为{4, 14, 9, 7}；
a3文件的内容为{6, 8, 12, 17}；
a4文件的内容为{16, 13, 19, 10}；
a5文件的内容为{2, 1, 3, 15}。
然后依次对5个小文件进行排序：
a1文件完成排序后的内容为{0, 5, 11, 18}；
a2文件完成排序后的内容为{4, 7, 9, 14}；
a3文件完成排序后的内容为{6, 8, 12, 17}；
a4文件完成排序后的内容为{10, 13, 16, 19}；
a5文件完成排序后的内容为{1, 2, 3, 15}。
最终进行多路归并，完成整个排序。最后，整个大文件A文件完成排序后变为{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}。问题实例给10***7***个数据的磁盘文件排序给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复的正整数），且其中每个数都小于等于n（n = 10***7***）。请输出一个按从小到大升序排列的包含所有输入整数的列表。假设最多有大约1 MB的内存空间可用，但磁盘空间足够。要求运行时间在5分钟以内，10秒为最佳结果。解法一：位图方案你可能会想到把磁盘文件进行归并排序，但题目假设只有1 MB的内存空间可用，所以归并排序这种方法不行。熟悉位图的人可能会想到用位图来表示这个文件集合{![本节后面的6.6节即讲位图，不熟悉的读者可以先阅读一下6.6节。]}。比如，用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，如集合{1, 2, 3, 5, 8, 13}，在字符串中将集合中各个数对应的位置置为1，没有对应的数的位置置为0，用字符串表示为。针对本题的10***7***个数据的磁盘文件排序问题，可以这么考虑：由于每个7位十进制整数表示一个小于1000万的整数，所以可以使用一个具有1000万个位的字符串来表示这个文件，当且仅当整数i在文件中存在时，字符串中的第i位置为1。采取这个位图的方案是因为考虑到本问题的特殊性：
输入数据限制在相对较小的范围内；
数据没有重复；
其中的每条记录都是单一的整数，没有任何其他与之关联的数据。
所以，此问题用位图的方案可以分为以下三步进行解决。（1）将所有的位都初始化为0。（2）通过读入文件中的每个整数来建立集合，将每个整数对应的位都置为1。（3）检验每一位，如果该位为1，就输出对应的整数。经过以上三步后，就产生了一个有序的输出文件。令n为位图向量中的位数（本例中为10 000 000），伪代码表示如下：// 磁盘文件排序位图方案的伪代码
// 第一步：将所有的位都初始化为0
for i ={0,....n}　　
　　 bit[i]=0;
// 第二步：通过读入文件中的每个整数来建立集合，将每个整数对应的位都置为1
for each i in the input file　　
　　 bit[i]=1;
// 第三步：检验每一位，如果该位为1，就输出对应的整数
for i={0...n}　　
　　 if bit[i]==1　　　　
　　　　 write i on the output file
上述的位图方案共需要扫描输入数据两次，具体执行步骤如下。（1）第一次只处理1～5 000 000的数据，这些数都是小于5 000 000的。对这些数进行位图排序，只需要约5 000 000/8=625 000字节，即0.625 MB，排序后输出。（2）第二次扫描输入文件时，只处理5 000 001～10 000 000的数据，也只需要0.625 MB（可以使用第一次处理申请的内存）。因此，这种位图的方法总共只需要0.625 MB。但是，很快我们就意识到，用位图方案的话，需要约1.2 MB（若每条记录是8位的正整数，则空间消耗约等于10***7***/()≈ 192 MB）的空间，而现在只有1 MB的可用存储空间，所以严格来说，用位图方法还是不行{![顺便说一句，位图的适用范围是对不重复的数据进行排序。若数据有重复，位图方案就不适用了。]}。那么究竟该如何处理呢？解法二：多路归并诚然，在面对本题时，通过计算分析出可以用上述解法一这样的位图法解决。但实际上，很多时候我们都面临着这样一个问题：文件太大，无法一次性放入内存中计算处理。这时候应该怎么办呢？分而治之，大而化小，也就是把整个大文件分为若干大小的几块，然后分别对每一块进行排序，最后完成整个过程的排序。k趟算法可以在O(kn)的时间开销内和O(n/k)的空间开销内完成对最多n个小于n的无重复正整数的排序。比如，可分为2块（k=2时，一趟反正占用的内存只有1.25/2 MB），即1～5 000 000和5 000 001～10 000 000。先遍历一趟，排序处理1～5 000 000的整数（用5 000 000/8=625 000字节的存储空间来排序1～5 000 000的整数），然后再第二趟，对5 000 001～1 000 000的整数进行排序处理。解法总结本节中位图和多路归并两种方案的时间复杂度及空间复杂度的比较如表6-1所示。表6-1
时间复杂度
空间复杂度
多路归并的时间复杂度为O(k × n/k × log n/k) = O(nlogn){![k × n/k × log(n/k) = n × log(n/k) = n × logn / logk，所以，O(k × n/k × log(n/k)) = O(n × logn / logk)，考虑到k是个定制，所以可以忽略掉它。]}。但严格来说，还要加上读写磁盘的时间，而此算法的绝大部分时间也正是浪费在读写磁盘的步骤上。位图方法介绍什么是位图所谓位图，就是用一个位（bit）来标记某个元素对应的值，而键就是该元素。由于采用了位为单位来存储数据，因此可以大大节省存储空间。位图通过使用位数组来表示某些元素是否存在，可进行数据的快速查找、判重、删除。来看一个具体的例子。假设我们要对0～7中的5个元素（4, 7, 2, 5, 3）进行排序（假设这些元素没有重复），此时就可以采用位图的方法来达到排序的目的。因为要表示8个数，所以只需要8位，由于8位等于1字节，所以开辟1字节的空间，并将这个空间的所有位都置为0，如图6-3所示。图6-3然后遍历这5个元素。因为待排序序列的第一个元素是4，所以把4对应的位重置为1（可以这样操作：p + (i/8) | (001 && (i % 8)) 。当然，这里的操作涉及big-endian和little-endian{![ little-endian就是低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。big-endian就是高位字节排放在内存的低地址端，低位字节排放在内存的高地址端。]}的情况，这里默认为big-endian），又由于是从0开始计数的，所以把第5位重置为1，如图6-4所示。图6-4然后再处理待排序序列的第二个元素7，将第8个位重置为1。接着再处理待排序序列的第三个元素2，一直到处理完所有的元素。将相应的位置为1后，这时候内存的位的状态如图6-5所示。现在遍历一遍这个位区域，将某位是1的位的编号（2, 3, 4, 5, 7）输出，这样就达到了排序的目的。图6-5问题实例电话号码的统计已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。8位数字最多组成99 999 999个号码，大概需要99兆位，大概十几兆字节的内存即可。2.5亿个整数的去重在2.5亿个整数中找出不重复的整数。注意，内存不足以容纳这2.5亿个整数。 分析： 采用2位图（每个数分配2位，00表示不存在，01表示出现一次，10表示出现多次，11无意义），共需内存2***32*** × 2=1 GB内存，可以接受。然后扫描这2.5亿个整数，查看位图中相对应的位，如果是00就变为01，如果是01就变为10，如果是10就保持不变。扫描完之后，查看位图，把对应位是01的整数输出即可。也可以先划分成小文件，然后在小文件中找出不重复的整数，并排序，最后归并，归并的同时去除重复的数。整数的快速查询给定40亿个不重复的没排过序的unsigned int型整数，然后再给定一个数，如何快速判断这个数是否在这40亿个整数当中？ 分析： 可以用位图的方法，申请512 MB的内存，一个位代表一个unsigned int型的值。读入40亿个数，设置相应的位，读入要查询的数，查看相应位是否为1，如果为1表示存在，如果为0表示不存在。布隆过滤器方法介绍我们经常会遇到这样的问题：判断一个元素是否在一个集合中。常见的做法是用散列表实现集合，然后遇到一个新的元素时，在散列表中查找：如果能找到则意味着存在于集合中，反之不存在。但是散列表有一个弊端，它耗费的空间太大。本节来看一种新的方法，即布隆过滤器（Bloom filter）。布隆过滤器是一种空间效率很高的随机数据结构，它可以看成是对位图的扩展。其结构是长度为n（如何计算最优n，后面会给出）的位数组，初始化为全0。当一个元素被加入集合中时，通过k个散列函数将这个元素映射成一个位数组中的k个点，并将这k个点全部置为1。在检索一个元素是否在一个集合中时，我们只要看看这个元素被映射成位阵列的k个点是不是都是1，就能大致判断出集合中有没有那个元素：如果这k个点中有任何一个点为0，则被检索元素在集合中一定不存在；如果这k个点都是1，则被检索元素很可能在集合中。但是，布隆过滤器也有它的缺点或不足，即它有一定的误判率——在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误判为属于这个集合。因此，它不适合那些“零误判”的应用场合。而在能容忍低误判率的应用场合下，布隆过滤器通过极少的误判换取了存储空间的极大节省。集合表示和元素查询下面我们来具体看看布隆过滤器是如何用位数组表示集合的。如图6-6所示，初始状态时，布隆过滤器是一个包含m位的位数组，每一位都置为0。图6-6对于S={x1, x2,…, x___n___}这样一个n个元素的集合，布隆过滤器使用k个互相独立的散列函数分别将集合S={x1, x2,…, x___n___}中的每个元素映射到{1,…, m}的范围中。对于任意一个元素x，第i个散列函数映射的位置h___i___(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在图6-7中，k=3且有两个散列函数选中同一个位置（从左边数第五位，即第二个1处）。图6-7于此，在判断y是否属于图6-6所示的集合S={x1, x2, …, x___n___}时，对y应用k次散列函数，如果所有h___i___(y)的位置都是1（1≤i≤k），那么就认为y是集合S={x1, x2, …, x___n___}中的元素，否则就认为y不是集合中的元素。例如，图6-8中的y1可以确定不是集合S={x1, x2, …, x___n___}中的元素，因为y1有两处指向了0位，而y2可能属于这个集合，也可能刚好是一个误判。图6-8误判率估计前面已经提到，布隆过滤器在判断一个元素是否属于它表示的集合时会有一定的误判率（false positive rate），下面就来估计一下这个误判率的大小。为了简化模型，假设kn & m且各个散列函数是完全随机的。每插入一个新元素第一个散列函数就会把过滤器中的某个位置为1，因此任意一个位被置成1的概率为1/m，反之，它没被置为1（依然是0）的概率为1-1/m。如果这个元素的k个散列函数都没有把某个位置为1，即在做完k次散列后，某个位还是0（意味着k次散列都没有选中它）的概率就是(1-1/m)k。如果插入第二个元素，某个位依然没有被置为1的概率为(1-1/m)2k，所以如果插入n个元素都还没有把某个位置为1的概率为(1-1/m)kn。也就是说，当集合S = {x1, x2, …, x___n___}中的所有元素都被k个散列函数映射到m位的位数组中时，这个位数组中某一位还是0的概率是为了简化运算，可以令，则有如果令为位数组中0的比例，则的数学期望。在已知的情况下，误判率为为位数组中1的比例，表示k次散列都刚好选中1的区域，即误判率。上式中的第二步近似在前面已经提到了，现在来看第一步近似。p’只是的数学期望，在实际中的值有可能偏离它的数学期望值。M. Mitzenmacher已经证明，位数组中0的比例非常集中地分布在它的数学期望值的附近。因此，第一步近似得以成立。分别将p和p’代入上式中，得与p’和f ‘ 相比，使用p 和f 通常在分析中更为方便。最优的散列函数个数既然布隆过滤器要靠多个散列函数将集合映射到位数组中，那么应该选择几个散列函数才能使元素查询时的误判率降到最低呢？这里有两个互斥的理由：如果散列函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但是，如果散列函数的个数少，那么位数组中的0就多。为了得到最优的散列函数个数，我们需要根据上一节中的误判率公式进行计算。先用p 和f 进行计算。注意到f = exp(k ln(1-e***kn/m))，我们令g = k ln(1-ekn/m)，只要让g取到最小，f 自然也取到最小。由于p = e-kn/m*，可以将g写成根据对称性法则可以很容易看出：当p = 1/2，也就是k = (m/n)ln2≈0.693m/n时，g取得最小值。在这种情况下，最小误判率f等于(1/2)k≈(0.6185)m/n。另外，注意到p是位数组中某一位仍是0的概率，所以p = 1/2对应着位数组中0和1各一半。换句话说，要想保持误判率低，最好让位数组有一半还空着。需要强调的一点是，p = 1/2时误判率最小这个结果并不依赖于近似值p和f。同样，对于f’ = exp(k ln(1-(1-1/m)kn))，g’ = k ln(1-(1-1/m)kn)，p’ = (1-1/m)kn，可以将g‘写成同样，根据对称性法则可以得到当p’ = 1/2时，g’取得最小值。位数组的大小下面来看看在不超过一定误判率的情况下，布隆过滤器至少需要多少位才能表示全集中任意n个元素的集合。假设全集中共有u个元素，允许的最大误判率为?，下面来求位数组的位数m。假设X为全集中任取n个元素的集合，F(X)是表示X的位数组。那么，对于集合X中任意一个元素x，在s = F(X)中查询x都能得到肯定的结果，即s能够接受x。显然，由于布隆过滤器引入了误判，s能够接受的不仅仅是X中的元素，它还能够接受?(u-n)个误判。因此，对于一个确定的位数组来说，它能够接受总共n +? (u-n)个元素。在n +? (u-n)个元素中，s真正表示的只有其中n个，所以一个确定的位数组可以表示个集合。m位的位数组共有2***m*个不同的组合，进而可以推出，m位的位数组可以表示个集合。全集中n个元素的集合总共有个，因此要让m位的位数组能够表示所有n个元素的集合，必须有即上式中的近似前提是n和?u相比很小，这也是实际情况中常常发生的。根据上式，我们得出结论：在误判率不大于?的情况下，m至少要等于n log2(1/?)才能表示任意n个元素的集合。上一节中我们曾算出当k = m/n ln2时误判率f最小，这时f = (1/2)k= (1/2)mln2 / n。现在令f ≤?，可以推出这个结果比前面算得的下界n log___2___(1/)大了log___2___≈1.44倍。这说明，在散列函数的个数取到最优时，要让误判率不超过?，m至少需要取到最小值的1.44倍。布隆过滤器可以用来实现数据字典，进行数据的判重或者集合求交集。问题实例寻找通过URL给定A和B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4 GB，请找出A和B两个文件中共同的URL。 分析： 如果允许有一定的误判率，可以使用布隆过滤器，4 GB内存大概可以表示340亿位。将其中一个文件中的URL使用布隆过滤器映射到这340亿位，然后挨个读取另外一个文件中的URL，检查这两个URL是否相同，如果是，那么该URL应该是共同的URL。如果是3个乃至n个文件呢？读者可以继续独立思考。垃圾邮件过滤用过电子邮箱的朋友都知道，经常会收到各种垃圾邮件，可能是广告，可能是病毒，所以邮件提供商每天都需要过滤数以几十亿计的垃圾邮件，请想一个办法过滤这些垃圾邮件。 分析： 比较直观的想法是把常见的垃圾邮件地址存到一个巨大的集合中，然后遇到某个新邮件就将它的地址和集合中的全部垃圾邮件地址一一进行比较，如果有元素与之匹配，则判定新邮件为垃圾邮件。虽然本节开始部分提到集合可以用散列表实现，但它太占空间。例如，存储1亿个电子邮件地址就需要1.6 GB内存，存储几十亿个电子邮件地址就需要上百GB的内存，虽然现在有的机器内存达到了上百GB，但终究是少数。事实上，如果允许一定的误判率的话，可以使用布隆过滤器。解决了存储的问题后，可以利用贝叶斯分类鉴别一份邮件是否为垃圾邮件，减少误判率。Trie树方法介绍什么是Trie树Trie树，即字典树，又称单词查找树或键树，是一种树形结构，常用于统计和排序大量字符串等场景中（但不仅限于字符串），且经常被搜索引擎用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。Trie树的核心思想是以空间换时间，利用字符串的公共前缀来降低查询时间的开销，以达到提高效率的目的。它有以下三个基本性质。（1）根结点不包含字符，除根结点外每一个结点都只包含一个字符。（2）从根结点到某一结点的路径上经过的字符连接起来，即为该结点对应的字符串。（3）每个结点的所有子结点包含的字符都不相同。Trie树的构建先来看一个问题：假如现在给定10万个长度不超过10个字母的单词，对于每一个单词，要判断它出没出现过，如果出现了，求第一次出现在第几个位置。这个问题该怎么解决呢？如果采取最笨拙的方法，对每一个单词都去查找它前面的单词中是否有它，那么这个算法的复杂度就是O(n2)。显然对于10万的范围难以接受。换个思路想：假设要查询的单词是abcd，那么在它前面的单词中，以b，c，d，f之类开头的显然就不必考虑了，而只要找以a开头的单词中是否存在abcd就可以了。同样，在以a开头的单词中，只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。因此，如果现在有b、abc、abd、bcd、abcd、efg和hii这6个单词，可以构建一棵图6-9所示的Trie树。如图6-9所示，从根结点遍历到每一个结点的路径就是一个单词，如果某个结点被标记为红色（如图中加黑点的节点），就表示这个单词存在，否则不存在。那么，对于一个单词，只要顺着它从根结点走到对应的结点，再看这个结点是否被标记为红色就可以知道它是否出现过了。把这个结点标记为红色，就相当于插入了这个单词。这样一来，查询和插入可以一起完成，所用时间仅仅为单词长度（在这个例子中，便是10）。这就是一棵Trie树。图6-9我们可以看到，Trie树每一层的结点数是26***i*级别的。所以，为了节省空间，还可以用动态链表，或者用数组来模拟动态，而空间的花费不会超过单词数乘以单词长度。查询Trie 树是简单且实用的数据结构，通常用于实现字典查询。我们做即时响应用户输入的Ajax搜索框时，就是以Trie树为基础数据结构的。本质上，Trie树是一棵存储多个字符串的树。相邻结点间的边代表一个字符，这样树的每条分支代表一个子串，而树的叶结点则代表完整的字符串。和普通树不同的地方是，相同的字符串前缀共享同一条分支。下面再举一个例子。给出一组单词inn、int、ate、age、adv、ant，可以得到图6-10所示的Trie树。可以看出以下几条。
每条边对应一个字母。
每个结点对应一项前缀。叶结点对应最长前缀，即单词本身。
单词inn与单词int有共同的前缀”in”，所以它们共享左边的一条分支（根结点→i→in）。同理，ate、age、adv和ant共享前缀”a”，所以它们共享从根结点到结点a的边。
图6-10查询操纵非常简单。例如，要查找int，顺着路径i→ in→int就找到了。搭建Trie的基本算法也很简单，无非是逐一把每个单词的每个字母插入Trie树。插入前先看前缀是否存在：如果存在，就共享，否则创建对应的结点和边。例如，要插入单词add，就有下面几步。（1）考察前缀”a”，发现边a已经存在。于是顺着边a走到结点a。（2）考察剩下的字符串”dd”的前缀”d”，发现从结点a出发，已经有边d存在。于是顺着边d走到结点ad。（3）考察最后一个字符”d”，这次从结点ad出发没有边d了，于是创建结点ad的子结点add，并把边ad→add标记为d。问题实例10个频繁出现的词在一个文本文件中大约有1万行，每行1个词，要求统计出其中出现次数最频繁的10个词。 分析： 用Trie树统计每个词出现的次数，时间复杂度是O(nl)（l表示单词的平均长度），最终找出出现最频繁的前10个词（可用堆来实现，时间复杂度是O(nlog10)。寻找热门查询搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度为1～255字节。假设目前有1000万条记录（因为查询串的重复度比较高，虽然总数是1000万，但是如果去除重复，不超过300万个）。请统计最热门的10个查询串，要求使用的内存不能超过1 GB。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。） 分析： 可以利用Trie树，观察关键字在该查询串出现的次数，若没有出现则为0。最后用10个元素的最小堆来对出现频率进行排序。数据库方法介绍当遇到大数据量的增、删、改、查时，一般把数据装进数据库中，利用数据库的设计和实现方法对海量数据的增、删、改、查进行处理。而数据库索引的建立则对查询速度起着至关重要的作用。散列索引实际上就是通过一定的散列算法，对需要索引的键进行散列运算，然后将得到的散列值存入散列表中。检索时，根据散列表中的散列值逆散列运算，反馈原键。散列索引在MySQL中使用并不多，目前在Memory和NDB Cluster存储引擎中使用。第3章中介绍了B树、B+树等索引。事实上，InnoDB存储引擎的B树索引使用的存储结构就是B+树。B+树在B树的基础上做了很小的改造，在每一个叶结点上除了存放索引键的相关信息外，还存储了指向与该叶结点相邻的后一个叶结点的指针，此举是为了加快检索多个相邻叶结点的效率。换言之，B+树的叶结点中除了跟B树一样包含了键的信息之外，还包含了指向相邻叶结点的指针，因此，叶结点之间就有了联系并有序了。B*树则更进一步，增加了兄弟结点之间的指针。由此可见，无处不透露着数据结构与算法思想，数据库也不例外，尤其是涉及数据库性能优化时更是如此。问题实例索引的选择我们知道，散列索引的效率比B树高很多，但是为什么常见的数据库中一般都不用散列索引而使用B树索引呢？你能说出几个原因？倒排索引方法介绍倒排索引（inverted index）是一种索引方法，用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射，常用于搜索引擎和关键字查询等问题中。以英文为例，下面是要被索引的文本：T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"
我们就能得到下面的倒排索引："a":　　　{2}
"banana": {2}
"is":　　 {0, 1, 2}
"it":　　 {0, 1, 2}
"what":　 {0, 1}
检索的条件”what”、”is”和”it”将对应集合的交集。正向索引开发出来用于存储每个文档的单词的列表。正向索引的查询能够满足每个文档有序、频繁的全文查询和每个单词在校验文档中验证这样的查询。在正向索引中，文档占据了中心位置，每个文档指向了一个它所包含的索引项的序列，也就是说，文档指向了它包含的那些单词。而反向索引则是单词指向了包含它的文档，在倒排索引中，很容易看到这个反向的关系。【阅读全文点击】本文摘自July的《编程之法》
内容简介：
CSDN访问量千万的博客“结构之法 算法之道”博主July著作本书涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路、多种解法，不断优化、逐层递进。本书第1章至第6章分别阐述字符串、数组、树、查找、动态规划、海量数据处理等相关的编程面试题和算法，第7章介绍机器学习的两个算法—K近邻和SVM。此外，每一章都有“举一反三”和“习题”，以便读者及时运用所学的方法解决相似的问题，且在附录中收录了语言、链表、概率等其他题型。书中的每一道题都是面试的高频题目，反复出现在最近5年各大公司的笔试和面试中，对面试备考有着极强的参考价值。全书逻辑清晰、通俗易懂，适合热爱编程、算法、机器学习，以及准备IT笔试和面试，即将求职、找工作的读者阅读。读到这里有赠书在本文中评论者，将赠出《编程之法》1本。共选5名幸运者。11月30日公布获奖人员名单，请记得到时回来关注获奖结果。
评论内容提示：
学习算法心得
点击后做题回复在本文下方
谈谈你的编程体会