算法问题，大神进！

[williamjing]

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

4 亿个数据存放到 512MB 中，每个数据也就有 10 bit 的存储空间，10bit 如何存储 16 位数字呢？

谢谢各位热烈的讨论。此题是发散思维的开放性题目，鉴于越来越多的人进行讨论，我再次重申一下条件。
1. 一共 4 亿个卡号，每个卡号 16 位阿拉伯数字存放在磁盘上。
2. 设计一个搜索算法，返回 true/false ，表示此卡号是否已经被申请。
3. 算法运行阶段不允许再次访问磁盘。

我自己的思路：这个题目演变成了如何把 16 位阿拉伯数字，用 10bits 来表示的问题。大家可以搜一搜 roaring bitmap 获取点思路，但是也不一定对。

[lululau]

硬盘多大？

[himarrin]

忙猜 bitmap

[Jooooooooo]

搜索指的是?

[cnoder]

找最大 /最小的 n 个是经典题

[siriussilen]

字典树呗…

[xiao109]

我感觉这些算法题都是三板斧，就那几个固定的套路

[stone666]

布隆过滤器

[williamjing]

@lululau 不允许用其他条件，只能在内存中操作。

[williamjing]

@Jooooooooo 给定一个卡号，查看是否在其中。

[williamjing]

@siriussilen 具体讲讲？

[williamjing]

@xiao109 给个思路？

[williamjing]

@stone666 有误识别率，有没有一个完全准确的算法？

[TomVista]

一个深度 16 的 10 叉 树,

[Jooooooooo]

@williamjing 噢, 搜下布隆过滤器.

[williamjing]

我觉得这个问题可以转换为两个子问题，1. 4 亿个卡号如何存储； 2. 查找。解决了存储问题也就解决了查找问题。

[sNullp]

512M = 512*1024*1024*8 = 4294967296bits

[williamjing]

@himarrin 为了解决存储问题，看来只能往 bitmap 方向考虑。

[williamjing]

@sNullp 对，每个卡号最多只能用 10 bits 来存储。

[sadfQED2]

字典树+1

[sNullp]

@williamjing 每个卡号明明只占 1bit

[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 是个可行方案，但是基数选择多少呢？建树指针也算内存哦。

[freelancher]

@Marinata 可能我记错了。

[kalsosadie165123]

可以用布隆过滤器，不过有一定误差率。
布隆过滤器判断值存在，则很有可能存在；
判断不存在则一定不存在。

[lis66951735]

布隆过滤器啊

[kalago]

看了下楼主说的 roaring bitmap 方式：
1. 银行卡前 8 位划分 1 0000 0000 个桶;
2. 后 8 位用 bitmap 来存储，申请 27 bit 大小空间，最大无符号整数 1 3421 7728;
3. 理想情况下就是占用了 27 0000 0000 的大小空间。
4. 这种方式纯存储占用 322mb 大小。
不知道描述的对不对。以前不知道 Roaring Bitmap 这个操作，感觉是对 bitmap 做了 2 级索引？

[2dot71828]

布隆过滤器不行吧？空间浪费太严重，试试布谷鸟过滤器？

[lrjia]

从信息论的角度估算一下，如果认为卡号在 10^16 次方范围内随机分布需要空间大约为 2500MB
$log_2((10^{16})^{4 * 10 ^ 8})= 21260339807 \ bit = 2534MB$

[misdake]

@kalago 每个 bucket 后 8 位十进制应该用长度 10^8 的 bitmap 来存储吧，存在添 1 ，不存在添 0 ，这样才是 bitmap 。27bit 只能存储 1 个 8 位十进制数字。
我看的 roaring bitmap 例子里，就是给后 16 位 2 进制数分配了长度 2^16(即 65536)的 bitmap 来存储。

[StrorageBox]

典型 bitmap 问题啊

[raycool]

卡号的前几位肯定是固定的吧
所以可以进一步节省空间

[binux]

@lrjia 同意信息论的分析，即使考虑数据没有重复，C(10^16, 4*10^8) 的量级上差太多，结果量级没什么区别。
也就是说，假如卡号没规律，这 4 亿的组合放在 512M 空间中一定会有歧义。

[misdake]

我现在设计的最小需要 1.43GB ，平均下来每个卡号使用了 30.725bit
把 10^16 的空间分成 10^7 个 bucket ，卡号剩余 9 位数，用 30bit 来覆盖。卡号排序后，将这 4*10^8 个卡号的 30bit 数据紧密排列，4*10^8*30bit
bucket 数据，每个 bucket 存储起始 index ，index 最大 4*10^8 ，用 29bit 来覆盖，这部分是 10^7*29bit
两项加一起 1.43GB

另外沿着信息的那条路去估算 log2(C(10^16, 4*10^8))，我把分子的里面改成 10^16-4*10^8 找下限，再用积分模拟分母，最后得到的下限大约 1.21156GB

[macg0406]

接信息论的分析，假如卡号前 9 位互不相同，如 1 到 4 亿，那么后 7 位就满足的随机分布，这种情况表示 4 亿个卡号需要的空间是 4e8 * log 2(10^7)，约 1.16G 。所以 512M 肯定是不够的。

[dujiaoxi]

假如已有的卡号和要判断的卡号都在 10^16 空间上随机分布没有规律，题目上已有的 4 亿个数字占整个 10^16 比例是亿分之 4 ，那么就有一个很好的解决方法了，直接 return false ，时间复杂度 O(1)，不需要读取硬盘，不需要额外内存，误判率只有亿分之 4 ，基本可以满足生产需求了（雾）

[xuanbg]

4 亿地址要用去 29 位，如果是 32 位系统，剩下 3 位只够 0-7 。所以如果是 32 位系统就没戏。

64 位的话就可以随便搞了，可以表示 20 位的 10 进制数字，16 位卡号离上限还差远着呢。一个 LONG 数组把 4 亿卡号作为 10 进制数字怼进去，挨个比对就行了。

[williamjing]

@misdake #51 我觉得还是没有解决稀疏性这个问题，其实 10^7 个 bucket 是相当稀疏的，比如中国的卡都是 62 开头。空的 bucket 后面的 30bits 甚至不用创建。

[williamjing]

@binux 而现实是卡号是有规律的，单纯用信息论分析有点脱离实际。卡号空间 10^17 ，但是全球才不到 100 亿人即 10^10 ，相当稀疏。

[williamjing]

@xuanbg 好家伙，合着服务器单独为了一个查询算法要时刻保持 4* 10^8 * 8B 这么大内存？然后还是 O(n)的效率...

[williamjing]

@dujiaoxi 误判率很低，但是 F1-score 完犊子了...

[williamjing]

@macg0406 信息论可以给我们提供数据分布的描述，但是本题已经分析很多了，现在最重要的是解决数据表示问题。用 10 进制表示是不够的，只能考虑 bitmap 。

[binux]

@williamjing 那什么规律你说啊，实际有效的卡号空间有多少？即使全球 100 亿人，但是卡号是随机生成的，一样百搭。

[williamjing]

@binux 银联都是 62 开头，算不算规律？

[winnie2012]

排序好，使用差值来做 bitmap 存储吧

[dujiaoxi]

@williamjing 也就是你出了个残缺的需求让开发去实现算法呗。卡号的生成方式，有效取值范围，什么都没说，上来就 16 位 10 进制，还🦐限定 512mb 内存。然后一点一点的加限定条件补完需求改题目，不如直接加个允许有亿分之 4 的误判率好了。建议题目改成 4 亿个 16 位 10 进制的数，无压缩的编码在 512 兆储存空间，求允许数最杂乱的规律是什么。参考其他人的解法，全随机分布目前最少的需要 1.43g ，然后如果都是同一个值只要 54bit

[dujiaoxi]

看了上面人对信息的分析，也可以建议把题目改成如何用 1bit 区分 012 这三个数，解决了可以干翻香农公式了

[misdake]

作为算法问题，最好是能把所有的前提都说明。让人自己摸索规律的话，这就是一个工程问题了，不同的人心中的规律不同，难以形成共识，结论的含金量也就大大降低。

[MegrezZhu]

直接用卡号数字做 offset ，每个卡号在对应的 offset 上用 1bit 标记是否存在，这样就只需要 4 亿多 bit……

[MegrezZhu]

啊，看错题了，原来四亿是卡号数量不是总可能数量……告辞

[hefish]

谢谢 ls 的大神们帮大学生完成了一个课题的思路。

[williamjing]

@misdake #65 为什么总觉题是我条件没说够？都说了啊，这就是所有条件。第二，这个确实是个开放性的算法题，如果有一个好的解决方案，那不就称为经典算法了吗？还用得着讨论吗？

[moshiyeap100]

512MB 大小足够标识所有 QQ 号码的存在，QQ 号码的理论最大值为 2^32 - 1 ，大概是 43 亿左右。

[binux]

@williamjing 既然你坚持这是全部条件，那就不能假设卡号的规律了，也就不能降低卡号空间了；既然是开放性问题，证明无解也是答案啊。
怎么？你一边说这是所有条件，一边加条件，一边开放，又不接受无解？你想要五彩斑斓的黑吗？

[wa007]

@williamjing 字典数是一种数据结构，你了解下就知道怎么用在这个问题上了

[williamjing]

@binux 你应该去工地，正好缺个抬杠的。

[williamjing]

@wa007 #72 谢谢 我去了解一下

[KousukeSakurako]

普通的字典树很有可能会超出内存，因为无论是 map ，还是 hash map 的内存开销都非常大， 我认为 Succinct Trie 值得一试
正巧最近写了一个 Succinct Trie 的 Golang 实现，楼主愿意的话可以看看
https://github.com/NobeKanai/sutrie

思路是来自于这个博客
http://stevehanov.ca/blog/index.php?id=120

[williamjing]

@KousukeSakurako #75 感谢