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

算法问题,大神进!

  •  
  •   williamjing · 134 天前 · 3800 次点击
    这是一个创建于 134 天前的主题,其中的信息可能已经有所发展或是发生改变。
    问:如何用 512MB 内存对 4 亿个银行卡号(每个卡号 16 位阿拉伯数字)进行搜索?
    第 1 条附言  ·  134 天前
    4 亿个数据存放到 512MB 中,每个数据也就有 10 bit 的存储空间,10bit 如何存储 16 位数字呢?
    第 2 条附言  ·  134 天前
    谢谢各位热烈的讨论。此题是发散思维的开放性题目,鉴于越来越多的人进行讨论,我再次重申一下条件。
    1. 一共 4 亿个卡号,每个卡号 16 位阿拉伯数字存放在磁盘上。
    2. 设计一个搜索算法,返回 true/false ,表示此卡号是否已经被申请。
    3. 算法运行阶段不允许再次访问磁盘。

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

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

    这样就只剩下中间的 7 - 9 位数字了
    gps949
        25
    gps949  
       134 天前
    @gps949 #23
    嗯,应该还需要 1 个字节的搜索到目标卡号哪一位的指示变量。应该是 18.125B
    当然,这里包括卡号、指示变量还可以压缩,所以目测内存使用可以不超过 10 字节
    TomVista
        26
    TomVista  
       134 天前
    银行卡号的前 11 位组成 是有限的,远小于 10^11,
    kimera
        27
    kimera  
       134 天前
    可以利用哈希函数的均匀分布特性

    每个卡号 16 位,40 亿个总共 3.7G ,限制内存 512M
    1 ,哈希函数把 4 亿份数据分为 N 份,使得每一份内存不会超。这里取 N=10
    2 ,计算 hash ( cardno )%10, 把所有的卡号分为 10 份,每份大约 4 亿个卡号,占用内存 0.37G
    3 ,根据待查找 cardno2, 找到对应是属于 10 份中第几份,把数据加载到内存,验证是否存在就可以了
    freelancher
        28
    freelancher  
       134 天前
    512MB 内存*1024*1024*8=4294,967,296 字节。42 亿个 bit 。 16 位数字用 10bit 存储。数据格式用 int 长整形。 只要 8bit.

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

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

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

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

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

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