两个算法题

号码去查重

现在有两批QQ号，每批大约40亿个，每批可能存在重复的数据，但记录着不同的数据，我们有两个iterator，都可以通过iterator.nextuint获得下一个QQ号，数据类型为unsigned int，即每个QQ好最大不超过2^32-1[当然目前我所见过的QQ号，连30亿都没超过]，现在设计算法，使用内存不超过1G，找出两批QQ号公共QQ号的个数？这个问题有许多衍生，但我们选取了最简单的一部分。
我也不卖关子，直接说算法了，这题的关键在于QQ号是有序的，同时我们只关心是否有这个QQ号，虽然可以使用bool数组，但在C里它占用一个字节，不能充分利用空间，我们需要的是用bit(一个二进制位)来存储bool，这样才能最大限度的利用空间。同时QQ号是有序的，于是我们可以通过内存地址上的排序来映射相应QQ号的位置。我们举一个简单例子来说明，比如一个char总共有8个二进制位，比如00001010则表示2和4存在，其它不存在。进一步char[2]则有16个二进制位，01000000 00100010则表示2,6,15存在，其它不存在。然后我们需要判断的QQ号的最大值为2^32-1，计算一下可得，需要大概512M内存，因为数组只能传有符号的int，所以我们不推荐使用char数组，而使用unsigned int的数组。我们来写一个函数，用来判断传入的unsigned int是否存在于传入的unsigned int里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int isInBit(unsigned int* nums, unsigned int num) {
	//不考虑0
	if(num == 0)
	    return 0;
	//得到商和余数，除数为32
	unsigned int location = num >> 5;
	unsigned int rest = num & 0x1F;
	//对于rest为0，特殊处理
	if(!rest) {
	    location -= 1;
	    rest = 8;
	}
	//rest用于位移
	rest -= 1;
	//返回对于bit
	return (int)(nums[location]>>rest&0x00000001);
}

然后我们再写一个存入的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int storeInBit(unsigned int* nums, unsigned int num) {
	//不考虑0
	if(num == 0)
	    return 0;
	//得到商和余数，除数为32
	unsigned int location = num >> 5;
	unsigned int rest = num & 0x1F;
	//对于rest为0，特殊处理
	if(!rest) {
	    location -= 1;
	    rest = 8;
	}
	//rest用于位移
	rest -= 1;
	nums[location] |= 1<<rest;
	return 1;
}

当然，我们发现了与之前重复的部分，本应分离出来，还有重复存入的问题，但我们只讲算法，细节就不关注了。最后再写一个删除函数，也使用类似的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int removeInBit(unsigned int* nums, unsigned int num) {
	//不考虑0
	if(num == 0)
	    return 0;
	//得到商和余数，除数为32
	unsigned int location = num >> 5;
	unsigned int rest = num & 0x1F;
	//对于rest为0，特殊处理
	if(!rest) {
	    location -= 1;
	    rest = 8;
	}
	//rest用于位移
	rest -= 1;
	nums[location] &= ~(1<<rest);
	return 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
int main() {
	   //拨出512M来存储结果 2^29bit
    unsigned int res[1<<27];
    //缓存数据
    unsigned int cache;
    //个数统计
    unsigned int count = 0;
    //遍历第一批QQ号，并存入res
    while((cache = iterator1.nextuint) != 0) {
    	storeInBit(res, cache);
    }
    //遍历第二批QQ号
    while((cache = iterator2.nextuint) != 0) {
    	//如果没有直接跳过
    	if(isInBit(res, cache)) {
    		continue;
    	} else {
    		//count+1
    		count += 1;
    		//删除数据，防止重复计算
    		removeInBit(res, cache);
    	}
    }
    //输出结果
    printf("公共QQ号的个数为：%u", count);
}

兔子试毒

有1000瓶药水，其中有一瓶是毒药，只要喝了一滴一天后必死，现在要用最合适的兔子和时间试出哪瓶是毒药？这里有两个隐性条件要看出来，就是一只兔子可以同时喝多瓶毒药和一瓶毒药可以被多只兔子尝试。当然我这里给了合适一词，因为最少的兔子是1只兔子试1000天，最少的天数是使用1000只兔子1天内试出结果，使用一一对应的做法，大家都懂。
2^10>1000，所以我们只要10只兔子就足够了。我们将药水从0-999编号，并将其转化为二进制，哪个位置上有1就让哪一只兔子喝一滴，如0不会被任何兔子喝，101会被3号和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
//生成毒药
void randomSet(int* drugs, int num) {
	//设置种子
	srand((unsigned)time(NULL));
	//位置从0开始，故末尾不是num
	int res = rand()%num;
	//设置毒药位置
	drugs[res] = 1;
}
//兔子试毒算法
void testDrug(int* rabbit, int* drugs) {
	//对药进行遍历，注意药的编号从零开始
	for(int i = 0; i < 1000; i++) {
		//总共10个二进制位
		for(int j = 0; j < 10; j++) {
			//将药喂给兔子
			if(i>>j&0x00000001)
			    rabbit[j] |= drugs[i];
		}
	}
}
int main() {
	//药水集合
	int drugs[1000] = {0};
	//随机初始化毒药的位置
	randomSet(drugs, sizeof(drugs)/sizeof(drugs[0]));
	
	//看看毒药在哪
	for(int i=0;i<1000;i++) {
	    if(drugs[i]) {
	        printf("毒药在%d位置\n",i+1);	
	    }	
	}
	
	//10只兔子是否死亡
	int rabbit[10] = {0};
	//给兔子喂药
	testDrug(rabbit, drugs);
	
	//保存结果
	int res = 0;
	printf("死去的兔子有：");
	//根据兔子来看毒药的编号
	for(int i = 0; i < 10; i++) {
		//记录到res
		res |= rabbit[i]<<i;
		if(rabbit[i])
		    printf("%d号 ", i+1);
	}
	printf("\n");
	printf("试出毒药的位置在%d", res+1);
}

整体不算复杂，我们不过多说明，重在学会其中的思想。

大整数存储

最后我们再来讲讲大整数的存储问题，通过之前的研究我们可以很容易地知道，我们可以通过bit来存储序数。比如每个int可以存储上限为2^32-1的整数，int[2]存储2^32的方式就可以是int[1]=1,int[0]=0。
在java里的BigInteger采用的就是上述方式，它使用int[]来存储大整数，数组的上限是private static final int MAX_MAG_LENGTH = Integer.MAX_VALUE / Integer.SIZE + 1; // (1 << 26)总共才64M，虽然看起来不是很大，但实际上，我们一般通过String来初始化BigInteger，如果每秒输入一个字符，也要输2年多才能输满，这是你可能会告诉我使用pow函数来产生大的BigInteger。其实为什么设这个上限我也不太明白，可能因为它是运行在java虚拟机上，需要对内存稍做管理吧，其实数组可以传入的最大值应该是int即2^31-1，不过也可以通过链表进行实现，这样就可以无限申请内存了，这实际上是python内部大整数的实现方式。这是你可能会稍微疑惑为什么不使用long数组，这大概是java的倔强，它的加减乘除运算都是在java虚拟机层实现的，为了保证加法的进位不丢失，每次运算前它会使用final static long LONG_MASK = 0xffffffffL;先对一块int进行数据类型转化，再通过long的运算得到结果，最后分别取出进位继续运算，取一段加法稍微看看。

1
2
3
4
5
while (yIndex > 0) {
                sum = (x[--xIndex] & LONG_MASK) +
                      (y[--yIndex] & LONG_MASK) + (sum >>> 32);
                result[xIndex] = (int)sum;
            }

sum是一个long用来缓存中间结果，x和y是两个加数，result用来存储最后的结果。
说到java，我们还要提一下android的java api，谷歌是我十分佩服的公司，安卓的javaapi虽然与java的许多部分都基本一致，但实现的方式却大有不同，比如这个BigInteger，首先它并不是在类似java虚拟机的delvik虚拟机上运行，而是通过jni来运行在native层的相关代码。从安卓在java层源码，我们可以看到BigInteger还有两个相关类，分别是BigInt和NativeBN，NativeBN用来申明Native方法，加减乘除幂等都在这申明，实现的话是在native层，BigInt则是真正处理BigInteger相关事务的类，比如构造函数初始化数据等，BigInteger则是为了保留java接口，本质是使用BigInt实现相同于java的功能，当然安卓SDK只保留了BigInteger的使用，所有用起来与java基本没有区别就是了。
最后或许要讲讲python，但实际上已经没什么好说的了，python3之前有对大整数和小整数进行分类存储，可能一定程度有提高效率，但python3则一律存储为大整数的方式，底层实现类似于bit存储的思想，但是因为python的原始解释器是C系列的语言，就可以直接操作内存，因此可以不受数组申明长度的限制，实现真正意义上的无限大整数，不过物理空间的限制和时间的限制已经超出软件的范畴了，不是我们应该考虑的。
这次我对大整数的实现，并没有带读者直接去读源码，有了之前lua的经验，我发现这样的意义，实际是不大的。其实，一旦我们可以理解其中的思想的话，读源码实际上就是水到渠成的，读源码的最大障碍就是不能理解，为什么要什么这个变量？为什么要如此回调？等。“授人以鱼不如授人以渔”，所以这次我先从某种思想的使用先讲清它的基本内容，再稍微提了一下，其它源码是如何使用这种思想又有哪些不同的地方。这实际是一种引导式的阅读，理解思想的读者其实读不读源码已经不重要了，读源码的目的则从学习方法变成了验证方法。
就到这里吧，明天也该开始把lua的坑给填了。