V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
nekolr
V2EX  ›  问与答

关于 Bitmap 的疑惑

  •  
  •   nekolr · 2019-08-28 10:58:26 +08:00 · 1748 次点击
    这是一个创建于 1899 天前的主题,其中的信息可能已经有所发展或是发生改变。

    看了好多博客,很多博客都举了类似这么一个例子:有 40 亿个不重复且无序的无符号整数,如何判断一个整数是否在这 40 亿个整数中,要求使用的内存不超过 2GB。

    分析中指出:

    要使用 Bitmap 算法,在 java 中一个 int 类型占用 4 个字节,因此需要申请一个 int 数组为长度为 1 + N/32 即可存储完这些数据,其中 N 代表数据的总量。

    这里有一个疑惑就是,Bitmap 存储时,元素的本身应该就是 key,value 值为 1 或者 0。那么如果这 40 亿个数,在没有说明最大值的情况下,如何得出的所需容量呢?难道不是应该根据最大值来分配容量的么?

    16 条回复    2019-08-28 12:09:35 +08:00
    nekolr
        1
    nekolr  
    OP
       2019-08-28 11:13:19 +08:00
    哭了,憋得难受
    Mutoo
        2
    Mutoo  
       2019-08-28 11:19:03 +08:00
    一个无符号整型占 32bits ( 4bytes ),即可以表示 32 个数字是否存在,同理 N 个数只要 ceil(N/32) 个 int 来表示。
    Lime
        3
    Lime  
       2019-08-28 11:20:00 +08:00
    你理解的没错, 是要根据最大值. 别人 blog 可以借鉴, 但不一定都是正确的.
    nekolr
        4
    nekolr  
    OP
       2019-08-28 11:23:56 +08:00
    @Mutoo 我知道一个字节可以表示 32 个数字是否存在,但是怎么确定映射关系呢?就是说怎么知道你每一位上存放的是哪个整数?
    misaka19000
        5
    misaka19000  
       2019-08-28 11:24:19 +08:00
    整数指的是 int 类型的数字,2 ^ 3 = 4294967296 > 40 亿
    misaka19000
        6
    misaka19000  
       2019-08-28 11:24:40 +08:00
    上面写错了,是 2 ^ 32
    nekolr
        7
    nekolr  
    OP
       2019-08-28 11:26:34 +08:00
    @misaka19000 没明白您的意思,能麻烦说详细一点吗,谢谢啦
    EminemW
        8
    EminemW  
       2019-08-28 11:27:43 +08:00 via iPhone
    用 hash 不就能确定位置了
    nekolr
        9
    nekolr  
    OP
       2019-08-28 11:28:38 +08:00
    @Mutoo 难道不应该是根据下标确定是哪个整数吗?比如数字 4,则放在第 4 个 bit 位上,将值置为 1
    misaka19000
        10
    misaka19000  
       2019-08-28 11:28:45 +08:00
    不清楚你看的是什么介绍,我建议你看一下吴军的这篇博客,讲的很清晰

    https://china.googleblog.com/2007/07/bloom-filter_7469.html
    nekolr
        11
    nekolr  
    OP
       2019-08-28 11:30:01 +08:00
    @misaka19000 谢谢!
    Mutoo
        12
    Mutoo  
       2019-08-28 11:36:41 +08:00
    @nekolr 题目里有几个数字:40 亿 < 无符号整型(最大为 2^32) < 内存限制 2GB=2*1024*1024*1024*8bits=(2^34bits )
    其实就是考你怎么在 2GB 里放下最多 2^32 个数字。
    Mutoo
        13
    Mutoo  
       2019-08-28 11:37:21 +08:00
    @Mutoo 准确的说不是放下“数字”本身,而是标记这个数字是否存在。
    nekolr
        14
    nekolr  
    OP
       2019-08-28 11:43:51 +08:00
    @Mutoo 有点明白了,我没从题意出发,只是老是从 bitmap 的角度出发了,谢谢!
    Mithril
        15
    Mithril  
       2019-08-28 11:54:52 +08:00   ❤️ 2
    - 简单的说就是你得设计一个算法,将这 40 亿的数字唯一映射到 40 亿 bit 上。
    - 也就是一个特化过的无冲突 hash 算法,给每个数字分配了一个 index。
    - 实际上你这个算法在做的就是压缩数据
    - 本质上是你先把数据集合做一遍压缩,并且把你的目标数据也压缩一下,然后在压缩过的数据集合里找你这个目标数据。
    然而这个压缩过程必须是无损的,否则会有概率误判。除非你的数据集合特征非常良好,不然设计不出来无损压缩算法,也就没办法真正准确判断是否存在。
    但是,你既然都能无损压缩了,最开始为啥非得存储这没压缩过的原始数据来着?一般来说这种情况下存储原始数据无非是用空间换时间,可你也根本没换出来。
    这种东西看看扩展一下思路就可以了,多数都跟国内数学教材一样,为了解释一个概念编造几道例题。但这些例题都是特化过的,没必要纠结它们究竟有用没用。
    nekolr
        16
    nekolr  
    OP
       2019-08-28 12:09:35 +08:00
    @Mithril 非常谢谢!解惑了!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2823 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 02:17 · PVG 10:17 · LAX 18:17 · JFK 21:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.