看了好多博客,很多博客都举了类似这么一个例子:有 40 亿个不重复且无序的无符号整数,如何判断一个整数是否在这 40 亿个整数中,要求使用的内存不超过 2GB。
分析中指出:
要使用 Bitmap 算法,在 java 中一个 int 类型占用 4 个字节,因此需要申请一个 int 数组为长度为 1 + N/32 即可存储完这些数据,其中 N 代表数据的总量。
这里有一个疑惑就是,Bitmap 存储时,元素的本身应该就是 key,value 值为 1 或者 0。那么如果这 40 亿个数,在没有说明最大值的情况下,如何得出的所需容量呢?难道不是应该根据最大值来分配容量的么?
1
nekolr OP 哭了,憋得难受
|
2
Mutoo 2019-08-28 11:19:03 +08:00
一个无符号整型占 32bits ( 4bytes ),即可以表示 32 个数字是否存在,同理 N 个数只要 ceil(N/32) 个 int 来表示。
|
3
Lime 2019-08-28 11:20:00 +08:00
你理解的没错, 是要根据最大值. 别人 blog 可以借鉴, 但不一定都是正确的.
|
4
nekolr OP @Mutoo 我知道一个字节可以表示 32 个数字是否存在,但是怎么确定映射关系呢?就是说怎么知道你每一位上存放的是哪个整数?
|
5
misaka19000 2019-08-28 11:24:19 +08:00
整数指的是 int 类型的数字,2 ^ 3 = 4294967296 > 40 亿
|
6
misaka19000 2019-08-28 11:24:40 +08:00
上面写错了,是 2 ^ 32
|
7
nekolr OP @misaka19000 没明白您的意思,能麻烦说详细一点吗,谢谢啦
|
8
EminemW 2019-08-28 11:27:43 +08:00 via iPhone
用 hash 不就能确定位置了
|
10
misaka19000 2019-08-28 11:28:45 +08:00
|
11
nekolr OP @misaka19000 谢谢!
|
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 个数字。 |
15
Mithril 2019-08-28 11:54:52 +08:00 2
- 简单的说就是你得设计一个算法,将这 40 亿的数字唯一映射到 40 亿 bit 上。
- 也就是一个特化过的无冲突 hash 算法,给每个数字分配了一个 index。 - 实际上你这个算法在做的就是压缩数据 - 本质上是你先把数据集合做一遍压缩,并且把你的目标数据也压缩一下,然后在压缩过的数据集合里找你这个目标数据。 然而这个压缩过程必须是无损的,否则会有概率误判。除非你的数据集合特征非常良好,不然设计不出来无损压缩算法,也就没办法真正准确判断是否存在。 但是,你既然都能无损压缩了,最开始为啥非得存储这没压缩过的原始数据来着?一般来说这种情况下存储原始数据无非是用空间换时间,可你也根本没换出来。 这种东西看看扩展一下思路就可以了,多数都跟国内数学教材一样,为了解释一个概念编造几道例题。但这些例题都是特化过的,没必要纠结它们究竟有用没用。 |