从最多包含40亿个随机排列的32位整数的顺序文件中寻找一个不存在的数—--分块位图法、二分搜索

本文尝试解决《编程珠玑》第2章问题A:给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在其中的32位整数。

这里考虑到数据量的问题,改为1680万个随机排列的24位整数。分别尝试了分块位图法、二分搜索两个算法,并分析了时间和空间复杂度。

1.数据文件准备

  • 这里使用C++生成了需要的数据,并写入了source.txt文件。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include<iostream>
    #include<fstream>
    #include<stdlib.h>
    using namespace std;

    const int maxNum = 16777216;

    int main(){
    ofstream file("source.txt", ofstream::out);
    for(int i = 0; i < 16800000; ++i){
    file << random() % maxNum << endl;
    }
    file.close();
    return 0;
    }

2.二分搜索

  • 对一个24位整数,从最高位开始按每个比特位是0还是1来进行划分:

    • 将是0的放在一堆,是1的放在一堆,并分别写入一个文件。
    • 如果两堆一样多,则任意选择一堆继续。
    • 如果不一样多,则选择较少的一堆继续。
  • 我的代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    #include<iostream>
    #include<fstream>
    using namespace std;

    #define BIT0_FILE "bit0.txt"
    #define BIT1_FILE "bit1.txt"
    #define SOUR_FILE "sour.txt"
    const int BIT_NUM = 24;

    //按照特定bit位上的值划分数据
    int splitByBit(FILE *sour, FILE *fbit0, FILE *fbit1, const int bit, int &nums){
    char numStr[10];
    int MASK = 1 << bit;
    int bit0Num = 0, bit1Num = 0;
    while(fgets(numStr, 10, sour)){
    int num = atoi(numStr);
    if((num & MASK) == 0){
    fprintf(fbit0, "%d\n", num);
    ++bit0Num;
    } else{
    fprintf(fbit1, "%d\n", num);
    ++bit1Num;
    }
    }
    fclose(sour);fclose(fbit0);fclose(fbit1);
    if(bit0Num < bit1Num){
    nums = bit0Num;
    return 0;
    } else{
    nums = bit1Num;
    return 1;
    }
    }

    //寻找没有出现的数
    void findNum(int &num){
    FILE *sour = fopen("source.txt", "r");
    FILE *fbit0, *fbit1;
    int fileLine = 0;
    for(int i = 0; i < BIT_NUM; ++i){
    if(i != 0){
    sour = fopen(SOUR_FILE, "r");
    }
    fbit0 = fopen(BIT0_FILE, "w+");
    fbit1 = fopen(BIT1_FILE, "w+");
    int findBit = splitByBit(sour, fbit0, fbit1, i, fileLine);
    if(findBit == 1){
    rename(BIT1_FILE, SOUR_FILE);
    num |= (1 << i);
    printf("move bit1 file\n");
    } else{
    rename(BIT0_FILE, SOUR_FILE);
    printf("move bit0 file\n");
    }
    if(fileLine == 0)
    break;
    }
    }

    int main(){
    int num = 0;
    findNum(num);
    cout << num << endl;
    return 0;
    }
  • 时间复杂度如下:

    time

    分析时间主要浪费在了对文件的读写上了。

  • 最大使用内存空间为360KB

3.分块位图法

3.1 位图法

  • 位图法是一种高效的数据查找算法。假设有海量的小于的整数,现在使用一个具有比特位的位向量来表示它们,其中当且仅当整数存在时,第1
  • 我们知道一个char是占1B8 bit的,所以可以表示8个整数。假设有数,那么计算可以得到所在的字符,计算可以得到在对应字符上的对应的比特位。
  • 因为,所以可以将右移3位得到,将0x7运算得到

下面是我的实现代码(bitArray.c文件):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*
位图法:
一个char是1B, 即 8bit, 可以表示8个整数
3位2进制数最大可以表示7
假设有数num, 那么num/8(代码里通过右移3位得到)可以得到num应该在char数组的哪个位置上(假设是c)
接下来需要确定在c的哪个比特位上, 这个可以由num/8的余数来确定, 即num & 0x7
*/
#define SHIFT 3
#define MASK 0x7

//初始化指定大小的bit数组
char* init_bitArray(int size){
char *arr;
arr = (char*)malloc(size / 8 + 1); //分配内存
memset(arr, 0, size / 8 + 1); //设置每一位上的初始值
return arr;
}

//设置num在对应bit位上的状态
void set_bitArray(char *arr, int num){
arr[num >> SHIFT] |= (1 << (num & MASK));
}

//清除num在对应bit位上的状态
void clear_bitArray(char* arr, int num){
arr[num >> SHIFT] &= ~(1 << (num & MASK));
}

//测试num是否存在
int is_in_bitArray(char* arr, int num){
return arr[num >> SHIFT] & (1 << (num & MASK));
}

3.2 分块位图

  • 虽然有了位图法的实现,但我们还不能简单套用,因为个比特位的数据会占用2MB的空间。这里不妨采用分块法,将0~16777215分成16个区间,每个区间有1048576个数。设定一个长度为16的数组用于后面的计数,下标为的位置代表有个数落在了对应的区间。
  • 首先遍历全部的数,判断落在哪个区间,并把数组里对应位置的数加1。
  • 接着选择一个没有装满的区间(区间里肯定有不存在的数),假设位置是。设置一个能代表1048576个数的比特数组,再次遍历所有的数,对于落在区间上的数,将设置为1。
  • 最后遍历,如果位置为0,那么说明数不存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<fstream>
#include"bitArray.c"
using namespace std;

const int SIZE = 1048576;

//分块位图法
int main(){
FILE *file = fopen("source.txt", "r");
char numStr[10];
//所有24位整数划分为16个区间, 每个区间524288个数
int count[16] = {0};
while(fgets(numStr, 10, file)){
//统计num落在每个区间里的个数
int num = atoi(numStr);
++count[ num / SIZE];
}
fclose(file);
for(int i = 0; i < 16; ++i){
//没有装满的区间里肯定有不存在的数
if(count[i] < SIZE){
char* arr = init_bitArray(SIZE);
FILE *file = fopen("source.txt", "r");
//再次遍历所有的数
while(fgets(numStr, 10, file)){
int num = atoi(numStr);
//num落在第i个区间
if(num / SIZE == i){
//设置对应的bit位
set_bitArray(arr, num - SIZE * i);
}
}
//bit为0的肯定不存在
for(int j = 0; j < SIZE; ++j){
if(is_in_bitArray(arr, j) == 0){
cout << SIZE * i + j << endl;
return 0; //因为数太多, 这里找到一个就结束程序
}
}
}
}
return 0;
}
  • 运行时间如下:

    bit

  • 占用内存为480KB,这里使用了更多的空间但换取了更快的速度。

------------- 本文结束 感谢您的阅读 -------------

本文标题:从最多包含40亿个随机排列的32位整数的顺序文件中寻找一个不存在的数—--分块位图法、二分搜索

文章作者:Perry

发布时间:2019年07月19日 - 09:12

最后更新:2019年09月19日 - 13:48

原始链接:https://perry96.com/archives/27392ff.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%