这是一个创建于 1001 天前的主题，其中的信息可能已经有所发展或是发生改变。
问：如何用 512MB 内存对 4 亿个银行卡号（每个卡号 16 位阿拉伯数字）进行搜索？
第 1 条附言 · 2022-02-11 12:14:05 +08:00
4 亿个数据存放到 512MB 中，每个数据也就有 10 bit 的存储空间，10bit 如何存储 16 位数字呢？
第 2 条附言 · 2022-02-11 16:04:15 +08:00
谢谢各位热烈的讨论。此题是发散思维的开放性题目，鉴于越来越多的人进行讨论，我再次重申一下条件。
1. 一共 4 亿个卡号，每个卡号 16 位阿拉伯数字存放在磁盘上。
2. 设计一个搜索算法，返回 true/false ，表示此卡号是否已经被申请。
3. 算法运行阶段不允许再次访问磁盘。
我自己的思路：这个题目演变成了如何把 16 位阿拉伯数字，用 10bits 来表示的问题。大家可以搜一搜 roaring bitmap 获取点思路，但是也不一定对。
1. 一共 4 亿个卡号，每个卡号 16 位阿拉伯数字存放在磁盘上。
2. 设计一个搜索算法，返回 true/false ，表示此卡号是否已经被申请。
3. 算法运行阶段不允许再次访问磁盘。
我自己的思路：这个题目演变成了如何把 16 位阿拉伯数字，用 10bits 来表示的问题。大家可以搜一搜 roaring bitmap 获取点思路，但是也不一定对。
 |
1
lululau 2022-02-11 10:36:38 +08:00 via iPhone
硬盘多大？
|
 |
2
himarrin 2022-02-11 11:04:15 +08:00
忙猜 bitmap
|
 |
3
Jooooooooo 2022-02-11 11:05:29 +08:00
搜索指的是?
|
 |
4
cnoder 2022-02-11 11:22:43 +08:00
找最大 /最小的 n 个是经典题
|
 |
5
siriussilen 2022-02-11 11:27:13 +08:00
字典树呗…
|
 |
6
xiao109 2022-02-11 11:27:57 +08:00
我感觉这些算法题都是三板斧，就那几个固定的套路
|
 |
7
stone666 2022-02-11 11:36:35 +08:00  2
布隆过滤器
|
 |
8
williamjing OP @lululau 不允许用其他条件，只能在内存中操作。
|
|
9
williamjing OP @Jooooooooo 给定一个卡号，查看是否在其中。
|
|
10
williamjing OP @siriussilen 具体讲讲？
|
|
11
williamjing OP @xiao109 给个思路？
|
|
12
williamjing OP @stone666 有误识别率，有没有一个完全准确的算法？
|
 |
13
TomVista 2022-02-11 11:54:48 +08:00 1
一个深度 16 的 10 叉 树,
|
|
14
Jooooooooo 2022-02-11 12:09:20 +08:00
@williamjing 噢, 搜下布隆过滤器.
|
|
15
williamjing OP 我觉得这个问题可以转换为两个子问题，1. 4 亿个卡号如何存储； 2. 查找。解决了存储问题也就解决了查找问题。
|
 |
16
sNullp 2022-02-11 12:15:20 +08:00
512M = 512*1024*1024*8 = 4294967296bits
|
|
17
williamjing OP @himarrin 为了解决存储问题，看来只能往 bitmap 方向考虑。
|
|
18
williamjing OP @sNullp 对，每个卡号最多只能用 10 bits 来存储。
|
 |
19
sadfQED2 2022-02-11 12:17:49 +08:00 via Android
字典树+1
|
|
20
sNullp 2022-02-11 12:19:49 +08:00 via iPhone
@williamjing 每个卡号明明只占 1bit
|
|
21
williamjing OP @TomVista 没那么大内存，你这个都到 10^17bits 了
|
|
22
williamjing OP @sNullp Roaring BitMap
|
 |
23
gps949 2022-02-11 12:25:43 +08:00
感觉问题很多信息都没说，在缺信息的情况下甚至搞不懂为什么要用 512MB 那么大内存。比如假设搜索空间 4 亿个卡号一个挨一个连续存放在硬盘上，每个卡号是 16 个 char （单字节）连续存放。所谓搜索只是判断是否存在而不用给出其他信息。
那么，不考虑程序自身运行需要，仅考虑存放数据，实际使用内存有 1 （ char ）+16 （目标卡号 16 位）+1/8=17.125B 就够了啊？ |
 |
24
ynyounuo 2022-02-11 12:29:00 +08:00
如果保证全部卡号都是 valid 的情况下
前 6 - 8 位的 BIN/IIN 进行重编码，末位 Luhn 算法验证直接省略； 这样就只剩下中间的 7 - 9 位数字了 |
|
25
gps949 2022-02-11 12:29:19 +08:00
|
|
26
TomVista 2022-02-11 12:32:17 +08:00
银行卡号的前 11 位组成 是有限的,远小于 10^11,
|
 |
27
kimera 2022-02-11 13:55:30 +08:00
可以利用哈希函数的均匀分布特性
每个卡号 16 位，40 亿个总共 3.7G ，限制内存 512M 1 ，哈希函数把 4 亿份数据分为 N 份，使得每一份内存不会超。这里取 N=10 2 ，计算 hash （ cardno ）%10, 把所有的卡号分为 10 份，每份大约 4 亿个卡号，占用内存 0.37G 3 ，根据待查找 cardno2, 找到对应是属于 10 份中第几份，把数据加载到内存，验证是否存在就可以了 |
 |
28
freelancher 2022-02-11 14:40:37 +08:00
512MB 内存*1024*1024*8=4294,967,296 字节。42 亿个 bit 。 16 位数字用 10bit 存储。数据格式用 int 长整形。 只要 8bit.
数值太接近了。感觉就是大学的作业题目。 放到内存一般用 redis 或者其它数据库。 可以先用冒泡排序从小到大排列，再用数据库自己带的索引来查找，效率也不会低。 |
 |
29
Morton996 2022-02-11 14:41:04 +08:00
听说过基数树没有呢？这还要叫大神
|
|
30
freelancher 2022-02-11 14:41:51 +08:00
或者用二分查找法。应该能明白吧。我怎么感觉好像在做作业？
|
|
31
freelancher 2022-02-11 14:50:31 +08:00
首先是解决如何存。4 亿数据，每个用 10bit.那就只能用数据库里的 long int （ 8K ）长整形存在内存里了。
存好了之后，要如何找呢？就可以用冒泡排序自己用顺序排列到数据库里，用索引来查找。 或者瞎存。用二分查找的递归来找对应的数据。 大概思路就是这样。也不知道说得对吗？ |
|
32
freelancher 2022-02-11 14:52:56 +08:00
最后二句错了。二分查找适合有序的数据。
|
|
33
williamjing OP @gps949 没说就是没有其余信息啊，不让用磁盘。
|
|
34
gps949 2022-02-11 15:20:10 +08:00
@williamjing 那我问你，4 亿条数据最开始在哪里？比如，在纸上，然后呢，从纸上如何录入到的计算机？
数据的全流程存在三个阶段：计算机外、进入计算机（ I/O ）、计算机内。第一个阶段可以不考虑，不属于计算机范畴。 如果你说系统是无盘（硬盘）的，那么，有没有 I/O ？如果也没 I/O ，那说明数据没有从计算机外进入计算机，天生在计算机内产生的，那就得说明直接在计算机内产生的方式和形式。 |
|
35
gps949 2022-02-11 15:23:06 +08:00
续#34
想问“4 亿条 16 位数字信用卡号如何完全存储在 512M 内存中”就直接问，别问“如何用 512MB 内存对 4 亿个银行卡号（每个卡号 16 位阿拉伯数字）进行搜索”。两个问题无论本身的清晰程度还是含义都是有区别的 |
|
36
williamjing OP @kimera 不允许使用磁盘。
|
|
37
williamjing OP @gps949 #34 #35 ，本题是开放性试题，数据本身在磁盘上，但是要求在算法运行阶段，不允许再次读取硬盘，也就是说相当于一次性全部读到内存中。
|
|
38
williamjing OP @freelancher #28 计算过程不允许再次访问磁盘，要一次性加载到内存中。4 亿数据用冒泡？
|
 |
39
Marinata 2022-02-11 15:58:04 +08:00
@freelancher 8bit 最高 11111111 ，老哥，8byte （ 64bit ）才能存长整形
|
|
40
williamjing OP @Morton996 是个可行方案，但是基数选择多少呢？建树指针也算内存哦。
|
|
41
freelancher 2022-02-11 16:06:56 +08:00
@Marinata 可能我记错了。
|
 |
42
kalsosadie165123 2022-02-11 16:28:18 +08:00
可以用布隆过滤器，不过有一定误差率。
布隆过滤器判断值存在，则很有可能存在； 判断不存在则一定不存在。 |
 |
43
lis66951735 2022-02-11 17:42:48 +08:00
布隆过滤器啊
|
 |
44
kalago 2022-02-11 18:57:58 +08:00 1
看了下楼主说的 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 级索引？ |
 |
45
2dot71828 2022-02-11 20:19:09 +08:00
布隆过滤器不行吧？空间浪费太严重，试试布谷鸟过滤器？
|
 |
46
lrjia 2022-02-11 20:29:35 +08:00 2
从信息论的角度估算一下，如果认为卡号在 10^16 次方范围内随机分布需要空间大约为 2500MB
$log_2((10^{16})^{4 * 10 ^ 8})= 21260339807 \ bit = 2534MB$ |
 |
47
misdake 2022-02-11 21:41:14 +08:00 1
@kalago 每个 bucket 后 8 位十进制应该用长度 10^8 的 bitmap 来存储吧，存在添 1 ，不存在添 0 ，这样才是 bitmap 。27bit 只能存储 1 个 8 位十进制数字。
我看的 roaring bitmap 例子里，就是给后 16 位 2 进制数分配了长度 2^16(即 65536)的 bitmap 来存储。 |
 |
48
StrorageBox 2022-02-11 22:22:01 +08:00 via iPhone
典型 bitmap 问题啊
|
 |
49
raycool 2022-02-11 23:18:27 +08:00
卡号的前几位肯定是固定的吧
所以可以进一步节省空间 |
 |
50
binux 2022-02-12 01:27:44 +08:00 via Android
@lrjia 同意信息论的分析，即使考虑数据没有重复，C(10^16, 4*10^8) 的量级上差太多，结果量级没什么区别。
也就是说，假如卡号没规律，这 4 亿的组合放在 512M 空间中一定会有歧义。 |
|
51
misdake 2022-02-12 02:25:52 +08:00
我现在设计的最小需要 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 |
 |
52
macg0406 2022-02-12 07:18:28 +08:00 via Android
接信息论的分析，假如卡号前 9 位互不相同，如 1 到 4 亿，那么后 7 位就满足的随机分布，这种情况表示 4 亿个卡号需要的空间是 4e8 * log 2(10^7)，约 1.16G 。所以 512M 肯定是不够的。
|
 |
53
dujiaoxi 2022-02-12 08:58:42 +08:00
假如已有的卡号和要判断的卡号都在 10^16 空间上随机分布没有规律，题目上已有的 4 亿个数字占整个 10^16 比例是亿分之 4 ，那么就有一个很好的解决方法了，直接 return false ，时间复杂度 O(1)，不需要读取硬盘，不需要额外内存，误判率只有亿分之 4 ，基本可以满足生产需求了（雾）
|
 |
54
xuanbg 2022-02-12 09:55:51 +08:00
4 亿地址要用去 29 位，如果是 32 位系统，剩下 3 位只够 0-7 。所以如果是 32 位系统就没戏。
64 位的话就可以随便搞了，可以表示 20 位的 10 进制数字，16 位卡号离上限还差远着呢。一个 LONG 数组把 4 亿卡号作为 10 进制数字怼进去，挨个比对就行了。 |
|
55
williamjing OP @misdake #51 我觉得还是没有解决稀疏性这个问题，其实 10^7 个 bucket 是相当稀疏的，比如中国的卡都是 62 开头。空的 bucket 后面的 30bits 甚至不用创建。
|
|
56
williamjing OP @binux 而现实是卡号是有规律的，单纯用信息论分析有点脱离实际。卡号空间 10^17 ，但是全球才不到 100 亿人即 10^10 ，相当稀疏。
|
|
57
williamjing OP @xuanbg 好家伙，合着服务器单独为了一个查询算法要时刻保持 4* 10^8 * 8B 这么大内存？然后还是 O(n)的效率...
|
|
58
williamjing OP @dujiaoxi 误判率很低，但是 F1-score 完犊子了...
|
|
59
williamjing OP @macg0406 信息论可以给我们提供数据分布的描述，但是本题已经分析很多了，现在最重要的是解决数据表示问题。用 10 进制表示是不够的，只能考虑 bitmap 。
|
|
60
binux 2022-02-12 10:41:37 +08:00 via Android
@williamjing 那什么规律你说啊，实际有效的卡号空间有多少？即使全球 100 亿人，但是卡号是随机生成的，一样百搭。
|
|
61
williamjing OP @binux 银联都是 62 开头，算不算规律？
|
 |
62
winnie2012 2022-02-12 11:02:04 +08:00
排序好，使用差值来做 bitmap 存储吧
|
|
63
dujiaoxi 2022-02-12 11:46:16 +08:00
@williamjing 也就是你出了个残缺的需求让开发去实现算法呗。卡号的生成方式，有效取值范围，什么都没说，上来就 16 位 10 进制，还🦐限定 512mb 内存。然后一点一点的加限定条件补完需求改题目，不如直接加个允许有亿分之 4 的误判率好了。建议题目改成 4 亿个 16 位 10 进制的数，无压缩的编码在 512 兆储存空间，求允许数最杂乱的规律是什么。参考其他人的解法，全随机分布目前最少的需要 1.43g ，然后如果都是同一个值只要 54bit
|
|
64
dujiaoxi 2022-02-12 11:55:07 +08:00
看了上面人对信息的分析，也可以建议把题目改成如何用 1bit 区分 012 这三个数，解决了可以干翻香农公式了
|
|
65
misdake 2022-02-12 12:25:07 +08:00
作为算法问题，最好是能把所有的前提都说明。让人自己摸索规律的话，这就是一个工程问题了，不同的人心中的规律不同，难以形成共识，结论的含金量也就大大降低。
|
 |
66
MegrezZhu 2022-02-12 12:33:08 +08:00
直接用卡号数字做 offset ，每个卡号在对应的 offset 上用 1bit 标记是否存在，这样就只需要 4 亿多 bit……
|
|
67
MegrezZhu 2022-02-12 12:34:10 +08:00
啊，看错题了，原来四亿是卡号数量不是总可能数量……告辞
|
 |
68
hefish 2022-02-12 12:44:59 +08:00
谢谢 ls 的大神们帮大学生完成了一个课题的思路。
|
|
69
williamjing OP @misdake #65 为什么总觉题是我条件没说够？都说了啊，这就是所有条件。第二，这个确实是个开放性的算法题，如果有一个好的解决方案，那不就称为经典算法了吗？还用得着讨论吗？
|
 |
70
moshiyeap100 2022-02-12 16:02:38 +08:00
512MB 大小足够标识所有 QQ 号码的存在，QQ 号码的理论最大值为 2^32 - 1 ，大概是 43 亿左右。
|
|
71
binux 2022-02-13 00:42:59 +08:00 via Android
@williamjing 既然你坚持这是全部条件，那就不能假设卡号的规律了，也就不能降低卡号空间了；既然是开放性问题，证明无解也是答案啊。
怎么？你一边说这是所有条件，一边加条件，一边开放，又不接受无解？你想要五彩斑斓的黑吗？ |
 |
72
wa007 2022-02-13 10:20:46 +08:00 via iPhone
@williamjing 字典数是一种数据结构，你了解下就知道怎么用在这个问题上了
|
|
73
williamjing OP @binux 你应该去工地，正好缺个抬杠的。
|
|
74
williamjing OP @wa007 #72 谢谢 我去了解一下
|
 |
75
KousukeSakurako 2022-02-15 11:36:41 +08:00 via iPhone
普通的字典树很有可能会超出内存，因为无论是 map ，还是 hash map 的内存开销都非常大， 我认为 Succinct Trie 值得一试
正巧最近写了一个 Succinct Trie 的 Golang 实现，楼主愿意的话可以看看 https://github.com/NobeKanai/sutrie 思路是来自于这个博客 http://stevehanov.ca/blog/index.php?id=120 |
|
76
williamjing OP @KousukeSakurako #75 感谢
|
Select Language