1、题目要求
有A、B两个文件，文件格式相同，均为每行一个十进制整型数字，两个文件的行数不一定相等但均在一千万行左右。A文件中的数字两两不等，B文件中的数字两两不等，请用一个算法找出A和B两文件中所有相同的数，并且从小到大有序输出
2、程序分析
2.1 bitmap
这种问题，如果使用集合，则是非常容易的，但既是一个算法题目，自然不能如此简单，通常，考察算法时，一般来说，除了数组外，其他诸如字典，集合就不要使用了
考察算法时，重点是考察时间复杂度和空间复杂度，一千万int整数，大于38M，两个文件加一起是76M，如果用bitmap来存储，则是2M多一点
一个int类型的数值，有4个字节，32位，就可以表示32个数字的存在与否，比如8，就可以标识为3是存在的，因为8 = 1<<3
使用这种方法，程序只需要很小的空间，就可以表示许多数的存在情况，假设数据范围是1到100，那么只需要一个list，list里有4个int类型的数值，每个数值表示32个数值存在与否的情况
具体到本题，还不能用一个int类型数值来表示32个数存在与否的情况，而是要用一个int类型的数值表示16个数字存在与否的情况
2.2 解题思路
为了分析方便，我把题目简化，两个文件里的数值范围是1~100
1、令lst = [0,0,0,0,0,0,0]
2、从A文件中读出一个3，则3 / 16 = 0,3这个数值存在与否的情况用lst[0]来表示
3、3 % 16 = 3 ，3 * 2 = 6，将lst[0] 的二进制中的第6位设置为1 ,lst[0] = lst[0] & (1<<6),这里说的第6个bit位是从0开始计数的
4、A文件里的其他数值也这样做处理，A文件读取结束后，再读取B文件
5、如果从B文件里读取到了一个数值3，这应该清楚，判断A文件里是不是也有3，就看lst[0]的二进制的第6位是否为0，如果为0，则将第7个bit位也设置为0，这样，就表明，B文件里也有3
6、两份文件都去以后，从1遍历到100，当遍历到3时，则查看lst[0]的第7个bit位是否为1，如果是，则输出3
3、 示例代码
#coding=utf-8
'''
有A、B两个文件，文件格式相同，均为每行一个十进制整型数字，两个文件的行数不一定相等，
但均在一千万行左右。A文件中的数字两两不等，B文件中的数字两两不等，
请用一个算法找出A和B两文件中所有相同的数，并且从小到大有序输出
'''
import random
#获得一个随机序列,最大值为max,共count个元素
def get_random_lst(max,count):
lst = []
while len(lst) < count:
r_int = random.randint(1,max)
if not r_int in lst:
lst.append(r_int)
return lst
left_lst = get_random_lst(100,50)
right_lst = get_random_lst(100,50)
print set(left_lst).intersection(set(right_lst))
store_lst = [0,0,0,0,0,0,0]
for item in left_lst:
lst_index = item / 16
bit_index = (item % 16)*2
store_lst[lst_index] = store_lst[lst_index] | (1 << bit_index)
for item in right_lst:
lst_index = item / 16
bit_index = (item % 16)*2
exist = (store_lst[lst_index] >> bit_index) & 1
if exist:
store_lst[lst_index] = store_lst[lst_index] | (1 << (item % 16)*2 + 1)
for item in range(101):
lst_index = item / 16
bit_index = (item % 16)*2 + 1
exist = (store_lst[lst_index] >> bit_index) & 1
if exist:
print item