用位图排序无重复数据集实例代码(C++版)

《Programming Pearls》(编程珠玑下载)第一章讲述了如何用位图排序无重复的数据集,整个思想很简洁,今天实践了下。

一、主要思想

位图排序的思想就是在内存中申请一块连续的空间作为位图,初始时将位图的每一位都置为0,然后依次读取待排序文件的整数,将整数所在的位设置为1,最后扫描位图,如果某一位为1,则说明这个数存在,输出到已排序文件。比如待排序的数据S={3,0,4,1,7,2,5},max(S)=7,我们可以设置一个八位的位图B,将位图的每一位初始为0,即B=[0,0,0,0,0,0,0,0],对S中的每一个整数d,设置B[d]=1,即B=[1,1,1,1,1,1,0,1],最后扫描位图,对位图的每一位i,如果B[i]==1,则输出i到已排序文件,排序后的S={0,1,2,3,4,5,7}。
整个过程只需要遍历一遍待排序文件和位图,时间复杂度O(n),需要的辅助空间为(max(S)/8)B。虽然这个排序算法只能在无重复的整数集上运行,但对于有些需求,确实做到高效实现,比如说给手机号码排序,手机号码11位,第一位始终为1,理论上可以有10^10个号码,但一些号码未发放,即有些号码在系统中不存在,假设系统中有50%的合法号码,每个号码用long int表示,这么多号码所需要的空间为50%*(10^10)*4B=20GB,不能放在内存中进行快速排序。一个可选的方案是分多趟进行归并排序,但需要较长的时间。我们申请一个10^10位的位图,需要的内存是10^10/8B=1.25GB,完全可以在当代的PC机上运行,在扫描位图时,假设某一位i为1,输出文件时,在前面添加一个1,例如i=3885201314,输出为13885201314。

二、算法实现

 用c语言实现的话,需要自己封装位图操作,这里需要用到三个操作:设置位图的所有位为0(setAllZero);设定指定的位为1(setOne);查看指定的位是否为1(find);代码如下:

复制代码 代码如下:

#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

#define MAX_NUM 16777216//最大的数,也就是需要的位
#define BYTE_NUM (1+MAX_NUM/8)//字节数
#define MASK 0x07

void setAllZero(unsigned char *p,long size);
void setOne(unsigned char *p,long loc);
int find(unsigned char *p,long loc);
bool getSorted(unsigned char *bitmap,char *fileName);
bool setBitmap(unsigned char *bitmap,char *fileName);
int bitmapSort();
int main(){
    return bitmapSort();
}
int bitmapSort(){
    unsigned char *bitmap;    //位图指针
    bitmap = (unsigned char *)malloc(BYTE_NUM*sizeof(unsigned char));
    if(bitmap == NULL){
        printf("Malloc failed\n");
        return -1;
    }   
    setAllZero(bitmap,BYTE_NUM);//将位图所有位设置为0
    setBitmap(bitmap,"phoneNumber.txt");//扫描待排文件,将位图对应位设置为1
    getSorted(bitmap,"bitmapSort.txt");    //扫描位图,将位图为1的位号输出到文件
    free(bitmap);//释放位图
    return 0;
}
/***********设置待排序数据的位图**************/
bool setBitmap(unsigned char *bitmap,char *fileName){
    FILE *readFp;
    printf("Setting bitmap...\n");
    readFp = fopen(fileName,"r");
    if(readFp == NULL)
        return false;   
    long phoneNum=0;
    while(fscanf(readFp,"%ld\n",&phoneNum) != EOF){
        setOne(bitmap,phoneNum);//将    phoneNum位设置为1   
    }
    fclose(readFp);
    return true;
}
/*****顺序遍历位图输出记录,从而实现排序****************/
bool getSorted(unsigned char *bitmap,char *fileName){
    printf("Search bitmap...\n");
    FILE *writeFp;
    writeFp = fopen(fileName,"w");
    if(writeFp == NULL)
        return false;
    long phoneNum=0;
    for(phoneNum = 0; phoneNum < MAX_NUM; phoneNum += 1){
        if(find(bitmap,phoneNum)){
            fprintf(writeFp,"%ld\n",phoneNum);
        }
    }
    fclose(writeFp);
    return true;
}
/******先将位图清零********/
void setAllZero(unsigned char *bitmap,long size){
    for(long i=0;i<size;i++)
        *(bitmap+i) &= 0;
}
/*************************************************
将指定的位置为1
(loc>>3)相当于整除2^3=8,即定位到字节数,MASK=0x07,loc&MASK相当于loc%8
***************************************************/
void setOne(unsigned char *bitmap,long loc){
    *(bitmap+(loc>>3)) |= (1<<(loc&MASK));//
}

/******查找指定的位是否为1********/
int find(unsigned char *bitmap,long loc){
    return ((*(bitmap+(loc>>3))) & (1<<(loc&MASK))) == (1<<(loc&MASK));   
}

C++的STL中有一个数据结构bitset,操作位图很方便。

复制代码 代码如下:

#include <bitset>
#define MAX_NUM 4000000//最多的数,即需要的位数
using namespace std;

int main(){
    FILE *readFp,*writeFp;
    readFp = fopen("phoneNumber1.txt","r");       
    writeFp = fopen("bitsetSorted.txt","w");   
    bitset<MAX_NUM> bitmap;
    for(long i=0;i<MAX_NUM;i++){//先将位图初试化为0
        bitmap.set(i,0);
    }
    printf("Begin set bitmap...\n");
    long number = 0;
    while(fscanf(readFp,"%ld\n",&number) != EOF){
        bitmap.set(number,1);//将number所在位设置为1       
    }
    printf("Begin search bitmap...\n");
    for(long i=0;i<MAX_NUM;i++){
        if(bitmap[i] == 1)//将位1的位输出到已排序文件
            fprintf(writeFp,"%ld\n",number);
    }
    fclose(writeFp);
    fclose(readFp);
}

排序算法很快就写好了,就开始生成测试数据,想生成0—2^31的乱序数据集还真不容易,首先要保证不重复,第二要丢掉40%的数(无效手机号码),第三要尽可能的乱序,捣了很久,最终还是找到了实现办法,生成了12GB的数据集,关于生成这个数据集的办法,欢迎一起讨论,我将会在下一篇中总结一下我的方法。
完整的代码可以参考github。

时间: 2013-11-17

C++画正弦线实例代码

本文实例讲述了C++画正弦线的实现代码,分享给大家供大家参考. 主要功能代码如下: 复制代码 代码如下: case WM_PAINT:          hdc = BeginPaint(hWnd, &ps);          // TODO: 在此添加任意绘图代码...          //画正玄线          #define  PI 3.1415926          #define SEGMENT 500          int cxClient,cyClient;     

C++实现位图排序实例

在<编程珠玑>一书里提到了一种算法导论里没有提到过的位图排序方法,这种排序方法是通过牺牲空间效率来追求时间效率(线性时间)以达到时间-空间折中与双赢的目的.本文以实例形式简单讲一下位图排序思想. 一.问题描述 1.输入:一个至多包含1千万个非负整数的文件 2.特征:①每个数都是小于10000000的非负整数:②没有重复的数字:③数据之间不存在关联关系. 3.约束:①最多1MB的内存空间可用:②磁盘空间充足:③运行时间最多几分钟,最好是线性时间.           4.输出:按升序排列的整数序

C++实现多线程查找文件实例

主要是多线程的互斥 文件 的查找 多线程互斥的框架 复制代码 代码如下: //线程函数  UINT FinderEntry(LPVOID lpParam)  {      //CRapidFinder通过参数传递进来       CRapidFinder* pFinder = (CRapidFinder*)lpParam;      CDirectoryNode* pNode = NULL;      BOOL bActive = TRUE; //bActive为TRUE,表示当前线程激活   

C++模板类的用法实例

本文实例讲述了C++中模板类的用法,分享给大家供大家参考.具体方法如下: //#include "StdAfx.h #ifndef __AFXTLS_H__ #define __AFXTLS_H__ #include <Windows.h> class CSimpleList { public: CSimpleList(int nNextOffset=0); void Construct(int nNextOffset); //接口 BOOL IsEmpty() const; voi

C++实现图形界面时钟表盘代码

本文实例讲述了C++实现图形界面时钟表盘代码,分享给大家供大家参考. 具体实现代码如下: 复制代码 代码如下: //POINT的数组可以这么用      POINT pt[]={          0, 450,          225,390,          390,225,          450,0,          390,-225,          225,-390,          0,-450,          -225,-390,          -390,-2

C++基于Directx MMX实现的图像灰度转换代码

本文实例讲述了基于Directx MMX 编写的实现图像灰度处理的方法,要编译此程序需DirectX SDK5.0,代码中所需要的ddutil.h与ddutil.cpp文件,请自行下载加入工程.在WindowNT4.0+SP3环境中编译通过,代码已经过整理,包含有注释.如下所示: #include <windows.h> #include <windowsx.h> #include <stdio.h> #include <ddraw.h> #include

VC++基于Dx实现的截图程序示例代码

本文所述的程序示例为VC++图象特效的截图示例,需要DirectX 3.0以上版,代码中的GetScreen函数是本截图程序的关键.运行这个程序可用Esc键结束.代码中需要ddutil.h与ddutil.cpp文件,请自行下载添加.关于InitDDraw()函数,功能是初始化DirectDraw环境,创建换页链(主页面,一个后台缓冲区),以及创建一个定时器. 具体的功能代码如下: #include <windows.h> #include <windowsx.h> #include

CISBitmap派生的VC++位图透明类实例

本文所述为一个由CISBitmap派生的VC++位图透明类,可以方便实现BMP图像的透明处理,主要包含两个文件,使用时主需要将其引入到你的C++工程中即可,具体的类代码如下: CISBitmap.cpp文件代码如下: #include <stdafx.h> #include "CISBitmap.h" #ifdef _DEBUG #undef THIS_FILE static char THIS_FILE[]=__FILE__; #define new DEBUG_NEW

C++使用ADO实现存取图片的方法

一般在网上查到的资料中向Server2000存储图片代码比较多,从数据库中读取图片并显示也不少,但是把图片从数据库中二进制数据转换为原图片保存在本地,就很少有C++代码了.本文就此问题一步一步地讲一讲解决的方法: 一.使用数据库前的准备 我们使用ADO,是用_ConnectionPtr,_RecordsetPtr来操纵数据库的.还有一个_CommandPtr,本程序没有使用它. 为了使用ADO,需要导入ADO动态链接库.在工程的stdafx.h文件中,添加如下代码: //导入ADO #impor

C++实现二维图形的傅里叶变换

本文实例讲述了C++实现二维图形的傅里叶变换的方法.有一定的借鉴价值.分享给大家供大家参考. 具体代码如下: // Fourier.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdio.h" #include "math.h" #include <cv.h> #include <highg

使用python绘制二维图形示例

我就废话不多说了,直接上代码吧! import matplotlib.pyplot as plt #也可以使用 import pylab as pl import matplotlib.font_manager as fm myfont = fm.FontProperties(fname=r'C:\Windows\Fonts\simkai.ttf') #或许字体,为设置中文显示 x = [1,2,3,4,5,6] data1 = [1,1.3,1.39,1.41,1.42,1.40] data2

如何在iphon IOS设备上使用二维码

下面给大家介绍下二维码简介 二维码 (2-dimensional bar code) 是用某种特定的几何图形按一定规律在平面(二维方向上)分布的黑白相间的图形记录数据符号信息的:在代码编制上巧妙地利用构成计算机内部逻辑基础的"0"."1"比特流的概念,使用若干个与二进制相对应的几何形体来表示文字数值信息,通过图象输入设备或光电扫描设备自动识读以实现信息自动处理: 二维条码/二维码能够在横向和纵向两个方位同时表达信息,因此能在很小的面积内表达大量的信息. 下面介绍下如

批处理制作二维码生成器

这个程序不能直接支持 Unicode, 同样不能直接支持任何双字节或多字节字符(包括汉字), 但可以用十六进制转码的方式生成包含 Unicode (或其他任何编码)字符的二维码图形. 如果数据含有UTF-8 Unicode 字符时, 在数据头部加上 BOM (\xEF\xBB\xBF) 即可. 例如: \xEF\xBB\xBF\xE6\xB1\x89\xE5\xAD\x97 上面的代码表示中文字符 "汉字" 任何 ASCII 字符(\x00 到 \xFF)都可以用十六进制转码方式输入,

Android平台生成二维码并实现扫描 & 识别功能

1.二维码的前世今生 "二维条码/二维码(2-dimensional bar code)是用某种特定的几何图形按一定规律在平面(二维方向上)分布的黑白相间的图形记录数据符号信息的:在代码编制上巧妙地利用构成计算机内部逻辑基础的"0"."1"比特流的概念,使用若干个与二进制相对应的几何形体来表示文字数值信息,通过图象输入设备或光电扫描设备自动识读以实现信息自动处理:它具有条码技术的一些共性:每种码制有其特定的字符集:每个字符占有一定的宽度:具有一定的校验功能

Android基于zxing的二维码(网格)扫描 仿支付宝网格扫描

前言:对于二维码扫描我们使用的是开源框架Zxing或者Zbar,这里使用基于zxing的二维码扫描,类似支付宝网格扫描. 二维码原理介绍: 二维码是用某种特定的几何图形按一定的规律在平面上分布的黑白相间的图形记录数据符号信息的,在代码编制上巧妙的利用构成计算机内部逻辑基础的0/1比特流的概念,使用若干个与二进制相对应的几何形体来表示文字数值信息,通过图像输入设备或光电扫描设备自动识读以实现信息自动处理:二维码能够在横向和纵向两个方位同时表达信息,因此能在很小的面积内表达大量的信息. 效果: 真机

利用java生成二维码工具类示例代码

二维码介绍 二维条形码最早发明于日本,它是用某种特定的几何图形按一定规律在平面(二维方向上)分布的黑白相间的图形记录数据符号信息的,在代码编制上巧妙地利用构成计算机内部逻辑基础的"0"."1"比特流的概念,使用若干个与二进制相对应的几何形体来表示文字数值信息,通过图象输入设备或光电扫描设备自动识读以实现信息自动处理. 如下为java生成二维码工具类,可以选择生成文件,或者直接在页面生成,话不多说了,来一起看看详细的示例代码吧. 示例代码 import java.aw

Java 二维码,QR码,J4L-QRCode 的资料整理

  开源码 Java 解码器 (编码解码)下载:http://sourceforge.jp/projects/qrcode/downloads/28391/qrcode.zip Java QR Code Open Source Decoder (只有编码)下载:http://www.java4less.com/qrcoded.zip J4L-QRCode 1.0 - Java component to create QR Code barcodes http://www.mayacode.com

iOS 定制多样式二维码

二维码/条形码是按照某种特定的几何图形按一定规律在平台(一维/二维方向上)分布的黑白相间的图形纪录符号信息.使用若干个与二进制对应的几何形体来表示文字数值信息. 最常见的二维码功能包括信息获取.网站跳转.电商交易.手机支付等等,其拥有密度小.信息容量大.容错能力强.成本低.制作难度低等优点.在移动开发中,二维码的地位也越来越重要,掌握二维码的基本操作是重要的本领之一. 在iOS7之后,苹果自身集成了二维码的生成和读取功能.生成二维码包括以下步骤 导入CoreImage/CoreImage.h头文

iOS开发生成二维码图片(附中间带有小图标二维码)

生成二维码图片也是项目中常用到的,二维码的扫描Git上有很多好用的,这里主要说下二维码的生成 1.普通二维码 1.1 方法 /** 生成二维码 QRStering:字符串 imageFloat:二维码图片大小 */ + (UIImage *)createQRCodeWithString:(NSString *)QRStering withImgSize:(CGFloat)imageFloat; 1.2 方法实现 /** 生成二维码 QRStering:字符串 imageFloat:二维码图片大小