算法问题，大神进！

[williamjing]

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

[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 亿人，但是卡号是随机生成的，一样百搭。