算法问题，大神进！

[williamjing]

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

[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 感谢