算法问题，大神进！

[williamjing]

问：如何用 512MB 内存对 4 亿个银行卡号（每个卡号 16 位阿拉伯数字）进行搜索？

[williamjing]

@TomVista 没那么大内存，你这个都到 10^17bits 了

[williamjing]

@sNullp Roaring BitMap

[gps949]

感觉问题很多信息都没说，在缺信息的情况下甚至搞不懂为什么要用 512MB 那么大内存。比如假设搜索空间 4 亿个卡号一个挨一个连续存放在硬盘上，每个卡号是 16 个 char （单字节）连续存放。所谓搜索只是判断是否存在而不用给出其他信息。
那么，不考虑程序自身运行需要，仅考虑存放数据，实际使用内存有 1 （ char ）+16 （目标卡号 16 位）+1/8=17.125B 就够了啊？

[ynyounuo]

如果保证全部卡号都是 valid 的情况下

前 6 - 8 位的 BIN/IIN 进行重编码，末位 Luhn 算法验证直接省略；

这样就只剩下中间的 7 - 9 位数字了

[gps949]

@gps949 #23
嗯，应该还需要 1 个字节的搜索到目标卡号哪一位的指示变量。应该是 18.125B
当然，这里包括卡号、指示变量还可以压缩，所以目测内存使用可以不超过 10 字节

[TomVista]

银行卡号的前 11 位组成 是有限的,远小于 10^11,

[kimera]

可以利用哈希函数的均匀分布特性

每个卡号 16 位，40 亿个总共 3.7G ，限制内存 512M
1 ，哈希函数把 4 亿份数据分为 N 份，使得每一份内存不会超。这里取 N=10
2 ，计算 hash （ cardno ）%10, 把所有的卡号分为 10 份，每份大约 4 亿个卡号，占用内存 0.37G
3 ，根据待查找 cardno2, 找到对应是属于 10 份中第几份，把数据加载到内存，验证是否存在就可以了

[freelancher]

512MB 内存*1024*1024*8=4294,967,296 字节。42 亿个 bit 。 16 位数字用 10bit 存储。数据格式用 int 长整形。 只要 8bit.

数值太接近了。感觉就是大学的作业题目。

放到内存一般用 redis 或者其它数据库。 可以先用冒泡排序从小到大排列，再用数据库自己带的索引来查找，效率也不会低。

[Morton996]

听说过基数树没有呢？这还要叫大神

[freelancher]

或者用二分查找法。应该能明白吧。我怎么感觉好像在做作业？

[freelancher]

首先是解决如何存。4 亿数据，每个用 10bit.那就只能用数据库里的 long int （ 8K ）长整形存在内存里了。

存好了之后，要如何找呢？就可以用冒泡排序自己用顺序排列到数据库里，用索引来查找。

或者瞎存。用二分查找的递归来找对应的数据。

大概思路就是这样。也不知道说得对吗？

[freelancher]

最后二句错了。二分查找适合有序的数据。

[williamjing]

@gps949 没说就是没有其余信息啊，不让用磁盘。

[gps949]

@williamjing 那我问你，4 亿条数据最开始在哪里？比如，在纸上，然后呢，从纸上如何录入到的计算机？
数据的全流程存在三个阶段：计算机外、进入计算机（ I/O ）、计算机内。第一个阶段可以不考虑，不属于计算机范畴。
如果你说系统是无盘（硬盘）的，那么，有没有 I/O ？如果也没 I/O ，那说明数据没有从计算机外进入计算机，天生在计算机内产生的，那就得说明直接在计算机内产生的方式和形式。

[gps949]

续#34
想问“4 亿条 16 位数字信用卡号如何完全存储在 512M 内存中”就直接问，别问“如何用 512MB 内存对 4 亿个银行卡号（每个卡号 16 位阿拉伯数字）进行搜索”。两个问题无论本身的清晰程度还是含义都是有区别的

[williamjing]

@kimera 不允许使用磁盘。

[williamjing]

@gps949 #34 #35 ，本题是开放性试题，数据本身在磁盘上，但是要求在算法运行阶段，不允许再次读取硬盘，也就是说相当于一次性全部读到内存中。

[williamjing]

@freelancher #28 计算过程不允许再次访问磁盘，要一次性加载到内存中。4 亿数据用冒泡？

[Marinata]

@freelancher 8bit 最高 11111111 ，老哥，8byte （ 64bit ）才能存长整形

[williamjing]

@Morton996 是个可行方案，但是基数选择多少呢？建树指针也算内存哦。