http://www.cnblogs.com/Geometry/archive/2009/04/11/1433679.html
楔子: 问题:假设一个文件中有9亿条不重复的9位整数,现在要求对这个文件进行排序。
一般解题思路: 1、将数据导入到内存中 2、将数据进行排序 (比如插入排序、快速排序) 3、将排序好的数据存入文件
难题: 一个整数为4个字节即使使用数组也需要900,000,000 * 4byte = 3.4G内存对于32位系统,访问2G以上的内存非常困难,而且一般设备也没有这么多的物理内存将数据完全导入到内存中的做法不现实。
其他解决办法: 1、导入数据库运算 2、分段排序运算 3、使用bit位运算
解决方案一:数据库排序 将文本文件导入到数据库,让数据库进行索引排序操作后提取数据到文件
优点:操作简单缺点:运算速度慢,而且需要数据库设备。
解决方案二:分段排序 操作方式:规定一个内存大小,比如200M,200M可以记录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 ,读取文件中的数据,并将数据放入内存。比如读到一个数据为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=512M的内存,将这2亿个号码整理成unsigned int类型后按上述办法存放在这块内存中(比如13512345678我们整理后为112345678,我们找到内存中112345678bit的下标,并将此bit值设为1) ,遍历整个bit数组,记录下所有的号码,这些号码即是不重复的手机号码
总结 建立一个足够大的bit数组当作hash表,以bit数组的下标来表示一个整数,以bit位中的0或1来表示这个整数是否在这个数组中存在,适用于无重复原始数据的搜索,原来每个整数需要4byte空间变为1bit,空间压缩率为32倍,扩展后可实现其他类型(包括重复数据)的搜索
注意 由于操作系统和编程语言本身的限制,有可能内存足够,但无法分配一块连续大内存的情况,这样的话可以申请多块稍微小一点的内存,然后用链表或其他的方式连接起来使用
分享到:
相关推荐
Verilog/C++实现排序算法:Verilog/C++实现排序算法:冒泡排序、选择排序、并行全比较排序、串行全比较排序。
选择排序(Selection Sort) 是另一种简单的排序算法,它通过多次遍历数组,在每一轮中选择最小的元素,并将其放置在已排序部分的末尾。选择排序的实现同样通过嵌套的循环来找到最小元素并进行交换。 这些示例代码...
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
算法I-IV(C++实现):基础数据结构排序和搜索(第3版) pdf
排序算法总汇:介绍了各种排序的算法,配有代码,大家赶紧来学习哦
排序算法演示:插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序
idea项目:一个主类选择调用6个排序类,记录了学习排序算法的过程,可以自己更改优化,每一种排序是一个类,有需要可以copy走,可重用性强
各种基本排序方法(直接插入、希尔、直接选择、冒泡、快速、堆、二路归并)的大致原理和过程、复杂性和稳定性、相应算法的程序段;
实验7: 内部排序算法比较.doc 实验7: 内部排序算法比较.doc 实验7: 内部排序算法比较.doc
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
matlab模糊算法:6 运算方法.zip
排序算法汇总P: 冒泡排序快速排序直接选择排序插入排序希尔排序 堆排序........
各种快速位运算算法
1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组不同的输入数据作比较;比较...
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在排序过程中需要...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
从零开始学算法:十种排序算法介绍 从零开始学算法:十种排序算法介绍
软件技术基础 数据结构 排序算法 查找算法