从40亿个整数中找到不存在的一个

前言

给定一个最多包含40亿个随机排列的32位的顺序整数的顺序文件,找出一个不在文件中的32位整数。(在文件中至少确实一个这样的数-为什么?)。在具有足够内存的情况下,如何解决该问题?如果有几个外部的“临时”文件可用,但是仅有几百字节的内存,又该如何解决该问题?

分析

这仍然是《编程珠玑》中的一个问题。前面我们曾经提到过《位图法》,我们使用位图法解决了这个问题。32位整型最多有4294967296个整数,而很显然40亿个数中必然会至少缺一个。我们同样也可以尝试使用位图法解决该问题,使用536 870 912个字节,约512M内存存储这40亿整数,存在该整数的位置1,最后遍历比特位,输出第一个比特位为0的位置即可。那如果仅借助几个“临时”文件,使用几百字节的内存的情况下该如何处理呢?

能否使用二分搜索呢?这40亿个整数是随机排列的,因此普通的二分搜索不能找到那个不存在的数。但是我们可以基于二分搜索的思想。

一个整数有32位,我们按照每个比特位是0还是1,将要查找的数据范围一分为二。从最高比特位开始:

  • 将最高比特位为0的放在一堆,为1的放在另外一堆
  • 如果一样多,则随意选择一堆,例如选0,则该位为0
  • 如果不一样多,选择少的一堆继续,如1更少,则该位为1

这里需要做一些解释:

  • 由于2^32个整数中,每一个比特位是1还是0的个数是相同的。如果在这40亿个整数中,某比特位为1和0的个数是相同的,则说明两边都有不存在的数。因此选择任意一堆即可。
  • 如果比特位1的整数比0的整数多,则说明,比特位为0的一堆数中,肯定缺少了一些数。而比特位为1的一堆数中,可能缺少一些数。因此,我们选择少的,也就是比特位为0的那一堆数。
  • 每一次选择,都记录选择的是0还是1,最多32次选择后,便可以至少找到一个整数,不存在这40亿数中。

实例说明

由于32位的整型数据量太多,不便说明,我们用一个4比特的数据对上面的思路再做一个说明。4比特最多有16个数。
假设有以下源数据:

1
3 5 2 6 7 -1 -4 -6 -3 1 -5

对应二进制形式如下(负数在内存中以补码形式存储):

1
0011 0101 0010 0110 0111 1111 1100 1010 1101 0001 1011

1.处理第1比特位被分为两部分数据,分别为:

  • 比特位为0的
1
0011 0101 0010 0110 0111 0001
  • 比特位为1的
1
1111 1100 1010 1101 1011

可以看到,第一比特位为1的数为5个,比比特位为0的数要少,因此选择比特位为1的数,继续处理。且第一比特位,获得1.

3.处理第2比特位仍然分为两部分数据,分别为:

  • 比特位为0的
1
1010 1011
  • 比特位为1的
1
1111 1100  1101

可以看到,第一比特位为1的数为3个,比比特位为0的数要多,因此选择比特位为0的数,继续处理。且第二比特位,获得0

2.处理第3比特位仍然被分为两部分数据,分别为:

  • 比特位为0的
1

  • 比特位为1的
1
1010 1011

明显看到第三比特位为0的数没有,因此选择比特位0,获得0。至此,已经没有必要继续查找了。

我们最终得到了前三个比特位100,因此不存在于这些数中至少有1000,1001,即-8,-7。

代码实现

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
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
//binarySearch.c
#include <stdio.h>
#include <stdlib.h>

#define MAX_STR 10
#define SOURCE_FILE "source.txt" //最原始文件,需要保留
#define SRC_FILE "src.txt" //需要分类的文件
#define BIT_1_FILE "bit1.txt"
#define BIT_0_FILE "bit0.txt"
#define INT_BIT_NUM 32
/*
FILE *src 源数据文件指针
FILE *fpBit1 存储要处理的比特位为1的数据
FILE *fpBit0 存储要处理的比特位为0的数据
int bit 要处理的比特位
返回值
0:选择比特位为0的数据继续处理
1:选择比特位为1的数据继续处理
-1:出错
*/
int splitByBit(FILE *src,FILE *fpBit1,FILE *fpBit0,int bit,int *nums)
{
/*入参检查*/
if(NULL == src || NULL == fpBit1 || NULL == fpBit0 || NULL == nums)
{
printf("input para is NULL");
return -1;
}
/*bit位检查*/
if(bit < 0 || bit > INT_BIT_NUM )
{
printf("the bit is wrong");
return -1;
}
char string[MAX_STR] = {0};
int mask = 1<< bit;
int bit0num = 0;
int bit1num = 0;
int num = 0;
//printf("mask is %x\n",mask);
/*循环读取源数据*/
while(fgets(string, MAX_STR, src ) != NULL)
{
num = atoi(string);
//printf("%d&%d %d\n",num,mask, num&mask);
/*根据比特位的值,将数据写到不同的位置,注意优先级问题*/
if(0 == (num&mask))
{
//printf("bit 0 %d\n",num);
fprintf(fpBit0, "%d\n", num);
bit0num++;
}
else
{
//printf("bit 1 %d\n",num);
fprintf(fpBit1, "%d\n", num);
bit1num++;
}
}
//printf("bit0num:%d,bit1num:%d\n",bit0num,bit1num);
if(bit0num > bit1num)
{
/*说明比特位为1的数少*/
*nums = bit1num;
return 1;
}
else
{
*nums = bit0num;
return 0;
}
}
/***
*关闭所有文件描述符
*
* **/
void closeAllFile(FILE **src,FILE **bit0,FILE **bit1)
{
if(NULL != src && NULL != *src)
{
fclose(*src);
*src = NULL;
}
if(NULL != bit1 && NULL != *bit1)
{
fclose(*bit1);
*bit1 = NULL;
}
if(NULL != bit0 && NULL != *bit0)
{
fclose(*bit0);
*bit0 = NULL;
}
}
int findNum(int *findNum)
{
int loop = 0;
/*打开最原始文件*/
FILE *src = fopen(SOURCE_FILE,"r");
if(NULL == src)
{
printf("failed to open %s",SOURCE_FILE);
return -1;
}
FILE *bit1 = NULL;
FILE *bit0 = NULL;
int num = 0;
int bitNums = 0; //得到比特位的数字数量
int findBit = 0; //当前得到的比特位
for(loop = 0; loop < INT_BIT_NUM;loop++)
{
/*第一次循环不会打开,保留源文件*/
if(NULL == src)
{
src = fopen(SRC_FILE,"r");
}
if(NULL == src)
{
return -1;
}

/**打开失败时,注意关闭所有打开的文件描述符**/
bit1 = fopen(BIT_1_FILE,"w+");
if(NULL == bit1)
{
closeAllFile(&src,&bit1,&bit0);
printf("failed to open %s",BIT_1_FILE);
return -1;
}
bit0 = fopen(BIT_0_FILE,"w+");
if(NULL == bit0)
{
closeAllFile(&src,&bit1,&bit0);
printf("failed to open %s",BIT_0_FILE);
return -1;
}
findBit = splitByBit(src,bit1,bit0,loop,&bitNums);
if(-1 == findBit)
{
printf("process error\n");
closeAllFile(&src,&bit1,&bit0);
return -1;
}
closeAllFile(&src,&bit1,&bit0);
//printf("find bit %d\n",findBit);
/*将某比特位数量少的文件重命名为新的src.txt,以便进行下一次处理*/
if(1 == findBit)
{
rename(BIT_1_FILE,SRC_FILE);
num |= (1 << loop);
printf("mv bit1 file to src file\n");
}
else
{
printf("mv bit0 file to src file\n");
rename(BIT_0_FILE,SRC_FILE);
}

/*如果某个文件数量为0,则没有必要继续寻找下去*/
if(0 == bitNums)
{
printf("no need to continue\n");
break;
}
}
*findNum = num;
return 0;
}
int main()
{
int num = 0;
findNum(&num);
printf("final num is %d or 0x%x\n",num,num);
return 0;
}

代码说明:

  • 这里的splitByBit函数根据比特位将数据分为两部分
  • closeAllFile用于关闭文件描述符
  • findNum函数循环32个比特位,每处理一次得到一个比特位,最终可以得到不存在其中的整数。

利用脚本产生了约2000万个整数:

1
2
wc -l source.txt 
20000001 source.txt

编译运行:

1
2
3
4
5
6
7
$ gcc -o binarySearch binarySearch.c
$ time ./binarySearch
final num is 18950401 or 0x1212901

real 0m8.001s
user 0m6.466s
sys 0m0.445s

程序的主要时间花在了读写文件,且占用内存极小。

总结

本文从一个特别的角度用最常见的二分搜索解决了该问题,最多拆分32次,便可从中找到不存在的整数。你有什么更好的思路或优化点,欢迎留言。

守望 wechat
关注公众号[编程珠玑]获取更多原创技术文章
出入相友,守望相助!