海量数据排序总结

问题: 假设一个文件中有9 亿条不重复的9 位整数，现在要求对这个文件进行排序。

一般解题思路:

1 、将数据导入到内存中

2 、将数据进行排序（比如插入排序、快速排序）

3 、将排序好的数据存入文件

难题:

一个整数为4 个字节

即使使用数组也需要900,000,000 * 4byte = 3.4G 内存

对于32 位系统，访问2G 以上的内存非常困难，而且一般设备也没有这么多的物理内存

将数据完全导入到内存中的做法不现实

其他解决办法:

1 、导入数据库运算

2 、分段排序运算

3 、使用bit 位运算

解决方案一: 数据库排序

将文本文件导入到数据库，让数据库进行索引排序操作后提取数据到文件

优点：操作简单

缺点：运算速度慢，而且需要数据库设备。

解决方案二: 分段排序

操作方式：

规定一个内存大小，比如200M ，200M 可以记录(200*1024*1024/4) = 52428800 条记录，我们可以每次提取5000 万条记录到文件进行排序，要装满9 位整数需要20 次，所以一共要进行20 次排序，需要对文件进行20 次读操作

缺点：

编码复杂，速度也慢( 至少20 次搜索)

关键步骤：

先将整个9 位整数进行分段，亿条数据进行分成20 段，每段5000 万条

在文件中依次搜索0~5000 万，50000001~1 亿……

将排序的结果存入文件

解决方案三:bit 位操作

思考下面的问题:

一个最大的9 位整数为999999999

这9 亿条数据是不重复的

可不可以把这些数据组成一个队列或数组，让它有0~999999999(10 亿个) 元素

数组下标表示数值，节点中用0 表示这个数没有，1 表示有这个数

判断0 或1 只用一个bit 存储就够了

声明一个可以包含9 位整数的bit 数组(10 亿) ，一共需要10 亿/8=120M 内存

把内存中的数据全部初始化为0, 读取文件中的数据，并将数据放入内存。比如读到一个数据为3412459 09 这个数据，那就先在内存中找到341245909 这个bit ，并将bit 值置为1 遍历整个bit 数组，将b it 为1 的数组下标存入文件

关键代码

检查是某一个char 里面(first) 的第second 位中存储的数据是否为1

bool CompareBit (unsigned char first, int second)

{

const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

if (second > .8)

return false;

return (first & mark_buf[second]) == mark_buf[second];

}

将某一个char(Desc) 中的第source 位置为 1

bool WriteToBit (unsigned char *Desc, int source)

{

const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

if (source > .8)

return false;

Desc[0] |= mark_buf[source];

return true;

}

案例

在某个项目中，我们需要对2 亿条手机号码删除重复记录( 过滤号码黑名单同样有效)

工作难点就在于如何处理这2 亿条电话号码, 直接用哈希表存放手机号码不大现实, 即使经过优化, 用一个unsigned int 存放一条记录, 那也得需要2 亿*4=8 亿byte, 远超过32 位系统的寻址能力

解决方案:

将电话号码由12 位单个数字组成的字符串转换为一个unsigned int 型数据( 这个完全可能, 手机号码由前三位数字和后面八位数字组成, 后面八位需要占到1~1000 万的空间, 而前面用0~100 的数字存储已经足够) 为简单起见, 默认为0~4G 的数字都有可能分布号码, 为此我们分配4G/32=512M 的内存将这2 亿个号码整理成unsigned int 类型后按上述办法存放在这块内存中( 比如135******** 我们整理后为112345678, 我们找到内存中112345678bit 的下标, 并将此bit 值设为1) 遍历整个bit 数组, 记录下所有的号码, 这些号码即是不重复的手机号码

总结

建立一个足够大的bit 数组当作hash 表

以bit 数组的下标来表示一个整数

以bit 位中的0 或1 来表示这个整数是否在这个数组中存在

适用于无重复原始数据的搜索

原来每个整数需要4byte 空间变为1bit ，空间压缩率为32 倍

扩展后可实现其他类型（包括重复数据）的搜索

主题：3000w 数据的表，取某项字段前50 项数据，内存2G

偶然看到这个题，就想了一下怎么做，大体实现思路是这样子的，3000w 的数据划分为1000 段，也就是1-3w 为一段，30001-6w 项为第二段，依次类推，从每3w 的数据中提取出前50 条数据（这个根据sql 排序就能取出来，2 个g 的内存够了），最后1000 个50 就会产生5w 个数据，最后提取出来的5w 的数据放置到ArrayList 中去，最后5w 的数据统一排序，取出前50 条。5w*5w 的对比与交换是可以搞定的。具体实现，等最近的项目完了用多线程试试！

主题：【探讨】给你1G 内存，如何从3000 万个手机号码中检索出你要的号码，要求每秒检索>1000 次

主题：3 亿数据快速检索实现

上周有个需求，就是要做一个检索库：

１３亿个手机号码，并且每个号码２０个左右的属性例：地区，订阅等信息。

２在最短的时候内select 出来（５分钟，１０分钟）[ 最重要]

３允许更新。对这些号码进行发送信息后，状态改变。[ 可以让他慢慢更新]

和几个同事讨论了一下，具体要注意以下几点：

１如果发送下去状态改变，但是只发送一半，但状态改变了如何办？

２如果多个产品线一起下发，状态会不会混乱。

解决以上第二个问题，决定采用，队列等待的方式。第一个问题没想到好的解决办法，回滚也想过了，但感觉不是很现实！

解决方案：

经过实验500w 条的数据在用plsql 直接select ，只需要０. ２秒，所以总体采用分表的方式，每500w 条分一个表，然后同时查询！

----------------------------------------- 重新描述一下需求-------------------------------

很多人说需求不是很的清楚，这里重新整理了一下！

不过要注意的是数据库里已经有 3 亿个手机基数了！

一．号码入库。

不定期会有新的号码需要入库，入库需要记录号码的常规属性，如：手机号，省份，城市，入库时间，手机卡类型，是否支持彩信，号码来源情况等。

二．入库手机号源文件管理

入库手机号源文件要以文件形式保存在服务器上。

三．按需要提取号码（最关键部分）

要按照需求提取所需的号码。

例如：

提号要求：

1. 此号码非黑名单用户。

2. 此号码为的订购和退订用户。

3. 此号码2 个月内没有活动。

4. 省份要求：辽宁，云南，广东

5. 号段要求：137 和138 和 139 号段

6. 数量要求：每个省10w

7. 是否支持彩信：是（是，否，忽略三种情况）

……

最后，符合条件的号码，按照固定格式（每个手机号占一行），形成文本文件，将此文件测试号码，是否需要状态报告等信息形成最终可发送文件并提供下载功能，同时记录本次提取信息（发送时间，发送标识等）

注：文件格式如下：

139***85185#09#0

139***71283

139***33190

第1 列：手机号

第2 列：产品类型（#09 ）

第3 列：是否需要状态报告（#0 ）

四．统计功能

一．号码情况统计

1. 统计当前号码总量。

2. 按照2 个基本要求，统计现在库中可以使用的号码数量。

注：统计需要显示，全国总量，各省总量，各省省会总量，各省去除省会总量，各省7 天未下发总量（省会与其他城市分开显示），各省可以发送总量（省会与其他城市分开显示，所以单独列出来）。

二．发送产品统计

1. 按时间段、业务线等统计发送产品的情况，如：发送时间，最终发送文件等

五．黑名单及特殊号码管理

1. 添加黑名单

2. 去除黑名单

3. 过滤黑名单

4. 查询黑名单

以上除黑名单外都是迫切需要的，黑名单功能可以以后完善。

现在有一万（1-10000 ）的个数，从中拿掉一个数，还剩9999 个数，现在用一个数组来存储这9999 个数，问怎么才能找出拿掉的数？

用10000 个数的数组循环匹配9999 个数，匹配成功，从 9999 数组中去除，不成功就是该数。

大家还有什么好的思路没有？

问题: 假设一个文件中有9 亿条不重复的9 位整数，现在要求对这个文件进行排序。

一般解题思路: 1、将数据导入到内存中 2 、将数据进行排序（比如插入排序、快速排序） 3 、将排序好的数据存入文件

难题: 一个整数为4 个字节即使使用数组也需要900,000,000 * 4byte = 3.4G 内存对于32 位系统，访问2G 以上的内存非常困难，而且一般设备也没有这么多的物理内存将数据完全导入到内存中的做法不现实。

其他解决办法: 1、导入数据库运算 2 、分段排序运算 3 、使用bit 位运算

解决方案一: 数据库排序将文本文件导入到数据库，让数据库进行索引排序操作后提取数据到文件

优点：操作简单缺点：运算速度慢，而且需要数据库设备。

解决方案二: 分段排序操作方式：规定一个内存大小，比如200M ，200M 可以记录52428800 条记录，我们可以每次提取5000 万条记录到文件进行排序，要装满9 位整数需要20 次，所以一共要进行2 0 次排序，需要对文件进行20 次读操作

缺点：编码复杂，速度也慢( 至少20 次搜索)

关键步骤：先将整个9 位整数进行分段，亿条数据进行分成20 段，每段5000 万条，在文件中依次搜索0~5000 万，50000001~1 亿…… 将排序的结果存入文件

解决方案三:bit 位操作思考下面的问题: 一个最大的9 位整数为999999999 这9 亿条数据是不重复的，可不可以把这些数据组成一个队列或数组，让它有0~999999999(10 亿个) 元素数组下标表示数值，节点中用0 表示这个数没有，1 表示有这个数，判断0 或1 只用一个bit 存储就够了

声明一个可以包含9 位整数的bit 数组(10 亿) ，一共需要10 亿/8=120M 内存，把内存中的数据全部初始化为0 ，读取文件中的数据，并将数据放入内存。比如读到一个数据为341245909 这个数据，那就先在内存中找到341245909 这个bit ，并将bit 值置为1 ，遍历整个bit 数组，将bit 为1 的数组下标存入文件

关键代码检查是某一个char 里面(first) 的第second 位中存储的数据是否为1

bool CompareBit (unsigned char first, int second)

{

const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

if (second > 8) return false;

return (first & mark_buf[second]) == mark_buf[second];

}

将某一个char(Desc) 中的第source 位置为1

bool WriteToBit (unsigned char *Desc, int source)

{

const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

if (source > 8) return false;

Desc[0] |= mark_buf[source];

return true;

}

案例在某个项目中，我们需要对2 亿条手机号码删除重复记录( 过滤号码黑名单同样有效)

工作难点就在于如何处理这2 亿条电话号码, 直接用哈希表存放手机号码不大现实, 即使经过优化, 用一个unsigned int 存放一条记录, 那也得需要2 亿*4=8 亿byte, 远超过32 位系统的寻址能力

解决方案: 将电话号码由12 位单个数字组成的字符串转换为一个unsigned int 型数据( 这个完全可能,手机号码由前三位数字和后面八位数字组成，后面八位需要占到1~1000 万的空间, 而前面用0~100 的数字存储已经足够) ，为简单起见，默认为0~4G 的数字都有可能分布号码，为此我们分配4G/32=5 12M 的内存，将这2 亿个号码整理成unsigned int 类型后按上述办法存放在这块内存中( 比如1351 2345678 我们整理后为112345678, 我们找到内存中112345678bit 的下标, 并将此bit 值设为1)，遍历整个bit 数组, 记录下所有的号码, 这些号码即是不重复的手机号码

总结建立一个足够大的bit 数组当作hash 表，以bit 数组的下标来表示一个整数，以bit 位中的0 或1 来表示这个整数是否在这个数组中存在，适用于无重复原始数据的搜索，原来每个整数需要4byte 空间变为1bit ，空间压缩率为32 倍，扩展后可实现其他类型（包括重复数据）的搜索

注意由于操作系统和编程语言本身的限制，有可能内存足够，但无法分配一块连续大内存的情况，这样的话可以申请多块稍微小一点的内存，然后用链表或其他的方式连接起来使用

关于海量数据处理

常用的数据结构：

1.Bloom Filter

大致思想是这样，把一个数据通过N 个哈希函数映射到一个长度为M 的数组的一位上，将hash 函数对应的值的位数组置 1 ，查找时如果发现所有hash 函数对应位都是 1 说明该数据的存在。但不能保证完全正确性，但是此方法无比高效。

【实例】给你A,B 两个文件，各存放50 亿条URL ，每条URL 占用 64 字节，内存限制是 4G ，让你找出A,B 文件共同的URL 。如果是三个乃至n 个文件呢？

2. 哈希法

这个简单，无非是通过一些哈希函数把元素搞到一个指定的位置，简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。这个很一般啊感觉。无非就是分类查找么，完全不如1 猛。

3. 最大或最小堆

就是一个完全的最大或最小二叉树，用途，比如:1)100w 个数中找最大的前100 个数。用一个100个元素大小的最小堆即可。感觉还是不错的。

4.Bit-map

所谓的Bit-map 就是用一个bit 位来标记某个元素对应的Value ，而Key 即是该元素。由于采用了Bit 为单位来存储数据，因此在存储空间方面，可以大大节省。

【问题实例】

1) 已知某个文件内包含一些电话号码，每个号码为8 位数字，统计不同号码的个数。

8 位最多99 999 999 ，大概需要99M 个bit ，大概10 几m 字节的内存即可。（可以理解为从0-99 999 999 的数字，每个数字对应一个Bit 位，所以只需要99M 个Bit==1.2MBytes ，这样，就用了小小的1.2M 左右的内存表示了所有的8 位数的电话）

2)2.5 亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5 亿个整数。

将bit-map 扩展一下，用2bit 表示一个数即可，0 表示未出现，1 表示出现一次，2 表示出现2 次及以上，在遍历这些数的时候，如果对应位置的值是0 ，则将其置为1 ；如果是1 ，将其置为2 ；如果是2 ，则保持不变。或者我们不用2bit 来进行表示，我们用两个bit-map 即可模拟实现这个2bit -map ，都是一样的道理。

公司的一道考试题算法分析——大数据量整数排序

题目大意：移动公司需要对已经发放的所有139 段的号码进行统计排序，已经发放的139 号码段的文件都存放在一个文本文件中（原题是放在两个文件中），一个号码一行，现在需要将文件里的所有号码进行排序，并写入到一个新的文件中；号码可能会有很多，最多可能有一亿个不同的号码（所有的139 段号码），存入文本文件中大概要占 1.2G 的空间；jvm 最大的内存在300 以内，程序要考虑程序的可执行性及效率；只能使用Java 标准库，不得使用第三方工具。

这是个典型的大数据量的排序算法问题，首先要考虑空间问题，一下把 1.2G 的数据读入内存是不太可能的，就算把 1 一亿条数据，转都转换成int 类型存储也要占接近400M 的空间。当时做个题目我并没有想太多的执行效率问题，主要就考虑了空间，而且习惯性的想到合并排序，基本思想是原文件分割成若干个小文件并排序，再将排序好的小文件合并得到最后结果，算法大概如下：

1.顺序读取存放号码文件的中所有号码，并取139 之后的八位转换为int 类型；每读取号码数满一百万个，（这个数据可配置）将已经读取的号码排序并存入新建的临时文件。

2. 将所有生成的号码有序的临时文件合并存入结果文件。

这个算法虽然解决了空间问题，但是运行效率极低，由于IO 读写操作太多，加上步骤 1 中的排序的算

法（快速排序）本来效率就不高（对于电话排序这种特殊情况来说），导致 1 亿条数据排序运行 3 个小时才有结果。

如果和能够减少排序的时间呢？首当其冲的减少IO 操作，另外如果能够有更加好排序算法也行。前天无聊再看这个题目时突然想到大三时看《编程珠玑》时上面也有个问题的需求这个这个题目差不多，记得好像使用是位向量（实际上就是一个bit 数组），用电话作为index ，心中大喜，找到了解决此问题的最完美方案啦：用位向量存储电话号码，一个号码占一个bit ，一亿个电话号码也只需要大概12M 的空间；算法大概如下：

1. 初始化bits[capacity] ；

2. 顺序所有读入电话号码，并转换为int 类型，修改位向量值：bits[phoneNum]=1 ；

3. 遍历bits 数组，如果bits[index]=1 ，转换index 为电话号码输出。

Java 中没有 bit 类型，一个boolean 值占空间为1byte （感兴趣的可以自己写程序验证），我自己写个用int 模拟bit 数组的类，代码如下：

Java 代码

?public class BitArray {

?private int [] bits = null ;

?private int length;

?// 用于设置或者提取int 类型的数据的某一位(bit) 的值时使用

【数据结构面试】

1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：

例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL 指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。

struct link

{

int data;

link* next;

};

bool IsLoop(link* head)

{

link* p1=head, *p2 = head;

if (head ==NULL || head->next ==NULL)

{

return false;

}

do{

p1= p1->next;

p2 = p2->next->next;

} while(p2 && p2->next && p1!=p2);

if(p1 == p2)

return true;

else

return false;

}

2,链表反转

单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的：

1->2->3->4->5 通过反转后成为

5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：

struct linka {

int data;

linka* next;

};

void reverse(linka*& head)

{

if(head ==NULL)

return;

linka*pre, *cur, *ne;

pre=head;

cur=head->next;

while(cur)

{

ne = cur->next;

cur->next = pre;

pre = cur;

cur = ne;

}

head->next = NULL;

head = pre;

}

还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：

linka* reverse(linka* p,linka*&

head)

{

if(p == NULL || p->next ==

NULL)

{

head=p;

return p;

}

else

{

linka* tmp =

reverse(p->next,head);

tmp->next = p;

return p;

}

}

3,判断两个数组中是否存在相同的数字

给定两个排好序的数组，怎样高效得判断这两个数组中存在相同的数字？

这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binary search。用C++实现代码如下：

bool findcommon(int a[],int

size1,int b[],int size2)

{

int i;

for(i=0;i

{

int

start=0,end=size2-1,mid;

while(start<=end)

{

mid=(start+end)/2;

if(a[i]==b[mid])

return

true;

else if

(a[i]

end=mid-1;

else

start=mid+1;

}

}

return false;

}

后来发现有一个 O(n)算法。因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。

bool findcommon2(int a[],

int size1, int b[], int

size2)

{

int i=0,j=0;

while(i

j

{

if(a[i]==b[j])

return

true;

if(a[i]>b[j])

j++;

if(a[i]

i++;

}

return false;

}

4,最大子序列

问题：

给定一整数序列A1，A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大

例如：

整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。

对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls 一书。

在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用这一个递推，我们就可以得到下面这个算法：

int

max_sub(int

a[],int size)

{

int

i,j,v,max=a[0

];

for(i=0;i

e;i++)

{

v=0;

for(j=i;j

e;j++)

{

v=v+a[j];//Su

m(i, j+1) =

Sum(i, j) +

A[j+1]

if(v>max)

max=v;

}

}

return

max;

}

那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：

int

max_sub2

(int a[],

int size)

{

int

i,max=0,

temp_sum

=0;

for(i=0;

i

++)

{

temp_sum

+=a[i];

if(temp_

sum>max)

max=temp

_sum;

else

if(temp_

sum<0)

temp_sum

=0;

}

return

max;

}

在这一遍扫描数组当中，从左到右记录当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时temp_sum 将会小于max，当然max也就不更新。如果t emp_sum 降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将t emp_sum置为0。然后，t emp_sum将从后面开始将这个子段进行分析，若有比当前max大的子段，继续更新max。这样一趟扫描结果也就出来了。