V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
williamjing
V2EX  ›  算法

算法问题,大神进!

  •  
  •   williamjing · 2022-02-11 10:30:36 +08:00 · 4612 次点击
    这是一个创建于 777 天前的主题,其中的信息可能已经有所发展或是发生改变。
    问:如何用 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 获取点思路,但是也不一定对。
    76 条回复    2022-02-19 12:39:39 +08:00
    lululau
        1
    lululau  
       2022-02-11 10:36:38 +08:00 via iPhone
    硬盘多大?
    himarrin
        2
    himarrin  
       2022-02-11 11:04:15 +08:00
    忙猜 bitmap
    Jooooooooo
        3
    Jooooooooo  
       2022-02-11 11:05:29 +08:00
    搜索指的是?
    cnoder
        4
    cnoder  
       2022-02-11 11:22:43 +08:00
    找最大 /最小的 n 个是经典题
    siriussilen
        5
    siriussilen  
       2022-02-11 11:27:13 +08:00
    字典树呗…
    xiao109
        6
    xiao109  
       2022-02-11 11:27:57 +08:00
    我感觉这些算法题都是三板斧,就那几个固定的套路
    stone666
        7
    stone666  
       2022-02-11 11:36:35 +08:00   ❤️ 2
    布隆过滤器
    williamjing
        8
    williamjing  
    OP
       2022-02-11 11:42:27 +08:00
    @lululau 不允许用其他条件,只能在内存中操作。
    williamjing
        9
    williamjing  
    OP
       2022-02-11 11:42:59 +08:00
    @Jooooooooo 给定一个卡号,查看是否在其中。
    williamjing
        10
    williamjing  
    OP
       2022-02-11 11:43:16 +08:00
    @siriussilen 具体讲讲?
    williamjing
        11
    williamjing  
    OP
       2022-02-11 11:43:26 +08:00
    @xiao109 给个思路?
    williamjing
        12
    williamjing  
    OP
       2022-02-11 11:46:20 +08:00
    @stone666 有误识别率,有没有一个完全准确的算法?
    TomVista
        13
    TomVista  
       2022-02-11 11:54:48 +08:00   ❤️ 1
    一个深度 16 的 10 叉 树,
    Jooooooooo
        14
    Jooooooooo  
       2022-02-11 12:09:20 +08:00
    @williamjing 噢, 搜下布隆过滤器.
    williamjing
        15
    williamjing  
    OP
       2022-02-11 12:12:02 +08:00
    我觉得这个问题可以转换为两个子问题,1. 4 亿个卡号如何存储; 2. 查找。解决了存储问题也就解决了查找问题。
    sNullp
        16
    sNullp  
       2022-02-11 12:15:20 +08:00
    512M = 512*1024*1024*8 = 4294967296bits
    williamjing
        17
    williamjing  
    OP
       2022-02-11 12:16:47 +08:00
    @himarrin 为了解决存储问题,看来只能往 bitmap 方向考虑。
    williamjing
        18
    williamjing  
    OP
       2022-02-11 12:17:37 +08:00
    @sNullp 对,每个卡号最多只能用 10 bits 来存储。
    sadfQED2
        19
    sadfQED2  
       2022-02-11 12:17:49 +08:00 via Android
    字典树+1
    sNullp
        20
    sNullp  
       2022-02-11 12:19:49 +08:00 via iPhone
    @williamjing 每个卡号明明只占 1bit
    williamjing
        21
    williamjing  
    OP
       2022-02-11 12:22:08 +08:00
    @TomVista 没那么大内存,你这个都到 10^17bits 了
    williamjing
        22
    williamjing  
    OP
       2022-02-11 12:24:35 +08:00
    @sNullp Roaring BitMap
    gps949
        23
    gps949  
       2022-02-11 12:25:43 +08:00
    感觉问题很多信息都没说,在缺信息的情况下甚至搞不懂为什么要用 512MB 那么大内存。比如假设搜索空间 4 亿个卡号一个挨一个连续存放在硬盘上,每个卡号是 16 个 char (单字节)连续存放。所谓搜索只是判断是否存在而不用给出其他信息。
    那么,不考虑程序自身运行需要,仅考虑存放数据,实际使用内存有 1 ( char )+16 (目标卡号 16 位)+1/8=17.125B 就够了啊?
    ynyounuo
        24
    ynyounuo  
       2022-02-11 12:29:00 +08:00
    如果保证全部卡号都是 valid 的情况下

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

    这样就只剩下中间的 7 - 9 位数字了
    gps949
        25
    gps949  
       2022-02-11 12:29:19 +08:00
    @gps949 #23
    嗯,应该还需要 1 个字节的搜索到目标卡号哪一位的指示变量。应该是 18.125B
    当然,这里包括卡号、指示变量还可以压缩,所以目测内存使用可以不超过 10 字节
    TomVista
        26
    TomVista  
       2022-02-11 12:32:17 +08:00
    银行卡号的前 11 位组成 是有限的,远小于 10^11,
    kimera
        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 份中第几份,把数据加载到内存,验证是否存在就可以了
    freelancher
        28
    freelancher  
       2022-02-11 14:40:37 +08:00
    512MB 内存*1024*1024*8=4294,967,296 字节。42 亿个 bit 。 16 位数字用 10bit 存储。数据格式用 int 长整形。 只要 8bit.

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

    放到内存一般用 redis 或者其它数据库。 可以先用冒泡排序从小到大排列,再用数据库自己带的索引来查找,效率也不会低。
    Morton996
        29
    Morton996  
       2022-02-11 14:41:04 +08:00
    听说过基数树没有呢?这还要叫大神
    freelancher
        30
    freelancher  
       2022-02-11 14:41:51 +08:00
    或者用二分查找法。应该能明白吧。我怎么感觉好像在做作业?
    freelancher
        31
    freelancher  
       2022-02-11 14:50:31 +08:00
    首先是解决如何存。4 亿数据,每个用 10bit.那就只能用数据库里的 long int ( 8K )长整形存在内存里了。

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

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

    大概思路就是这样。也不知道说得对吗?
    freelancher
        32
    freelancher  
       2022-02-11 14:52:56 +08:00
    最后二句错了。二分查找适合有序的数据。
    williamjing
        33
    williamjing  
    OP
       2022-02-11 15:10:11 +08:00
    @gps949 没说就是没有其余信息啊,不让用磁盘。
    gps949
        34
    gps949  
       2022-02-11 15:20:10 +08:00
    @williamjing 那我问你,4 亿条数据最开始在哪里?比如,在纸上,然后呢,从纸上如何录入到的计算机?
    数据的全流程存在三个阶段:计算机外、进入计算机( I/O )、计算机内。第一个阶段可以不考虑,不属于计算机范畴。
    如果你说系统是无盘(硬盘)的,那么,有没有 I/O ?如果也没 I/O ,那说明数据没有从计算机外进入计算机,天生在计算机内产生的,那就得说明直接在计算机内产生的方式和形式。
    gps949
        35
    gps949  
       2022-02-11 15:23:06 +08:00
    续#34
    想问“4 亿条 16 位数字信用卡号如何完全存储在 512M 内存中”就直接问,别问“如何用 512MB 内存对 4 亿个银行卡号(每个卡号 16 位阿拉伯数字)进行搜索”。两个问题无论本身的清晰程度还是含义都是有区别的
    williamjing
        36
    williamjing  
    OP
       2022-02-11 15:45:23 +08:00
    @kimera 不允许使用磁盘。
    williamjing
        37
    williamjing  
    OP
       2022-02-11 15:47:58 +08:00
    @gps949 #34 #35 ,本题是开放性试题,数据本身在磁盘上,但是要求在算法运行阶段,不允许再次读取硬盘,也就是说相当于一次性全部读到内存中。
    williamjing
        38
    williamjing  
    OP
       2022-02-11 15:52:22 +08:00
    @freelancher #28 计算过程不允许再次访问磁盘,要一次性加载到内存中。4 亿数据用冒泡?
    Marinata
        39
    Marinata  
       2022-02-11 15:58:04 +08:00
    @freelancher 8bit 最高 11111111 ,老哥,8byte ( 64bit )才能存长整形
    williamjing
        40
    williamjing  
    OP
       2022-02-11 16:00:07 +08:00
    @Morton996 是个可行方案,但是基数选择多少呢?建树指针也算内存哦。
    freelancher
        41
    freelancher  
       2022-02-11 16:06:56 +08:00
    @Marinata 可能我记错了。
    kalsosadie165123
        42
    kalsosadie165123  
       2022-02-11 16:28:18 +08:00
    可以用布隆过滤器,不过有一定误差率。
    布隆过滤器判断值存在,则很有可能存在;
    判断不存在则一定不存在。
    lis66951735
        43
    lis66951735  
       2022-02-11 17:42:48 +08:00
    布隆过滤器啊
    kalago
        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 级索引?
    2dot71828
        45
    2dot71828  
       2022-02-11 20:19:09 +08:00
    布隆过滤器不行吧?空间浪费太严重,试试布谷鸟过滤器?
    lrjia
        46
    lrjia  
       2022-02-11 20:29:35 +08:00   ❤️ 2
    从信息论的角度估算一下,如果认为卡号在 10^16 次方范围内随机分布需要空间大约为 2500MB
    $log_2((10^{16})^{4 * 10 ^ 8})= 21260339807 \ bit = 2534MB$
    misdake
        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 来存储。
    StrorageBox
        48
    StrorageBox  
       2022-02-11 22:22:01 +08:00 via iPhone
    典型 bitmap 问题啊
    raycool
        49
    raycool  
       2022-02-11 23:18:27 +08:00
    卡号的前几位肯定是固定的吧
    所以可以进一步节省空间
    binux
        50
    binux  
       2022-02-12 01:27:44 +08:00 via Android
    @lrjia 同意信息论的分析,即使考虑数据没有重复,C(10^16, 4*10^8) 的量级上差太多,结果量级没什么区别。
    也就是说,假如卡号没规律,这 4 亿的组合放在 512M 空间中一定会有歧义。
    misdake
        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
    macg0406
        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 肯定是不够的。
    dujiaoxi
        53
    dujiaoxi  
       2022-02-12 08:58:42 +08:00
    假如已有的卡号和要判断的卡号都在 10^16 空间上随机分布没有规律,题目上已有的 4 亿个数字占整个 10^16 比例是亿分之 4 ,那么就有一个很好的解决方法了,直接 return false ,时间复杂度 O(1),不需要读取硬盘,不需要额外内存,误判率只有亿分之 4 ,基本可以满足生产需求了(雾)
    xuanbg
        54
    xuanbg  
       2022-02-12 09:55:51 +08:00
    4 亿地址要用去 29 位,如果是 32 位系统,剩下 3 位只够 0-7 。所以如果是 32 位系统就没戏。

    64 位的话就可以随便搞了,可以表示 20 位的 10 进制数字,16 位卡号离上限还差远着呢。一个 LONG 数组把 4 亿卡号作为 10 进制数字怼进去,挨个比对就行了。
    williamjing
        55
    williamjing  
    OP
       2022-02-12 10:05:30 +08:00
    @misdake #51 我觉得还是没有解决稀疏性这个问题,其实 10^7 个 bucket 是相当稀疏的,比如中国的卡都是 62 开头。空的 bucket 后面的 30bits 甚至不用创建。
    williamjing
        56
    williamjing  
    OP
       2022-02-12 10:07:16 +08:00
    @binux 而现实是卡号是有规律的,单纯用信息论分析有点脱离实际。卡号空间 10^17 ,但是全球才不到 100 亿人即 10^10 ,相当稀疏。
    williamjing
        57
    williamjing  
    OP
       2022-02-12 10:09:44 +08:00
    @xuanbg 好家伙,合着服务器单独为了一个查询算法要时刻保持 4* 10^8 * 8B 这么大内存?然后还是 O(n)的效率...
    williamjing
        58
    williamjing  
    OP
       2022-02-12 10:11:44 +08:00
    @dujiaoxi 误判率很低,但是 F1-score 完犊子了...
    williamjing
        59
    williamjing  
    OP
       2022-02-12 10:14:05 +08:00
    @macg0406 信息论可以给我们提供数据分布的描述,但是本题已经分析很多了,现在最重要的是解决数据表示问题。用 10 进制表示是不够的,只能考虑 bitmap 。
    binux
        60
    binux  
       2022-02-12 10:41:37 +08:00 via Android
    @williamjing 那什么规律你说啊,实际有效的卡号空间有多少?即使全球 100 亿人,但是卡号是随机生成的,一样百搭。
    williamjing
        61
    williamjing  
    OP
       2022-02-12 10:44:37 +08:00
    @binux 银联都是 62 开头,算不算规律?
    winnie2012
        62
    winnie2012  
       2022-02-12 11:02:04 +08:00
    排序好,使用差值来做 bitmap 存储吧
    dujiaoxi
        63
    dujiaoxi  
       2022-02-12 11:46:16 +08:00
    @williamjing 也就是你出了个残缺的需求让开发去实现算法呗。卡号的生成方式,有效取值范围,什么都没说,上来就 16 位 10 进制,还🦐限定 512mb 内存。然后一点一点的加限定条件补完需求改题目,不如直接加个允许有亿分之 4 的误判率好了。建议题目改成 4 亿个 16 位 10 进制的数,无压缩的编码在 512 兆储存空间,求允许数最杂乱的规律是什么。参考其他人的解法,全随机分布目前最少的需要 1.43g ,然后如果都是同一个值只要 54bit
    dujiaoxi
        64
    dujiaoxi  
       2022-02-12 11:55:07 +08:00
    看了上面人对信息的分析,也可以建议把题目改成如何用 1bit 区分 012 这三个数,解决了可以干翻香农公式了
    misdake
        65
    misdake  
       2022-02-12 12:25:07 +08:00
    作为算法问题,最好是能把所有的前提都说明。让人自己摸索规律的话,这就是一个工程问题了,不同的人心中的规律不同,难以形成共识,结论的含金量也就大大降低。
    MegrezZhu
        66
    MegrezZhu  
       2022-02-12 12:33:08 +08:00
    直接用卡号数字做 offset ,每个卡号在对应的 offset 上用 1bit 标记是否存在,这样就只需要 4 亿多 bit……
    MegrezZhu
        67
    MegrezZhu  
       2022-02-12 12:34:10 +08:00
    啊,看错题了,原来四亿是卡号数量不是总可能数量……告辞
    hefish
        68
    hefish  
       2022-02-12 12:44:59 +08:00
    谢谢 ls 的大神们帮大学生完成了一个课题的思路。
    williamjing
        69
    williamjing  
    OP
       2022-02-12 15:17:49 +08:00
    @misdake #65 为什么总觉题是我条件没说够?都说了啊,这就是所有条件。第二,这个确实是个开放性的算法题,如果有一个好的解决方案,那不就称为经典算法了吗?还用得着讨论吗?
    moshiyeap100
        70
    moshiyeap100  
       2022-02-12 16:02:38 +08:00
    512MB 大小足够标识所有 QQ 号码的存在,QQ 号码的理论最大值为 2^32 - 1 ,大概是 43 亿左右。
    binux
        71
    binux  
       2022-02-13 00:42:59 +08:00 via Android
    @williamjing 既然你坚持这是全部条件,那就不能假设卡号的规律了,也就不能降低卡号空间了;既然是开放性问题,证明无解也是答案啊。
    怎么?你一边说这是所有条件,一边加条件,一边开放,又不接受无解?你想要五彩斑斓的黑吗?
    wa007
        72
    wa007  
       2022-02-13 10:20:46 +08:00 via iPhone
    @williamjing 字典数是一种数据结构,你了解下就知道怎么用在这个问题上了
    williamjing
        73
    williamjing  
    OP
       2022-02-13 16:31:41 +08:00
    @binux 你应该去工地,正好缺个抬杠的。
    williamjing
        74
    williamjing  
    OP
       2022-02-13 16:32:33 +08:00
    @wa007 #72 谢谢 我去了解一下
    KousukeSakurako
        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
    williamjing
        76
    williamjing  
    OP
       2022-02-19 12:39:39 +08:00
    @KousukeSakurako #75 感谢
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5301 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 07:17 · PVG 15:17 · LAX 00:17 · JFK 03:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.