1
zealic 2019-03-24 19:32:46 +08:00 2
Bitmap
|
2
CodeCommunist 2019-03-24 19:37:37 +08:00 via Android 2
空间与时间总要取舍,要看瓶颈在哪一块。持久化存取储是什么方式也没说,如果是分布式数据库能做到并行计算的话,就要看能有多少机器。另外 32 位怎么能表示百亿,你是说 32 个字符吧。
|
3
pixiaotiao 2019-03-24 19:39:11 +08:00 via Android 1
分段
|
4
stiekel OP @CodeCommunist 是的 ,每个 id 都是 32 位的字符串。
|
5
stiekel OP @CodeCommunist 是的 ,每个 id 都是长度为 32 的字符串。
|
6
AlisaDestiny 2019-03-24 19:57:45 +08:00 2
布隆过滤,有一定的误判几率,不过效率奇高。
|
7
wangluofansi 2019-03-24 20:10:11 +08:00 via Android 1
感觉布隆过滤器合适。
误判率的意思是:把 ID 放进布隆过滤器中,若 given_id not in bloom_filter,则该 id 一定不存在于你的 ID 集中;但若 given_id in bloom_filter,有一定可能实际上并不存在于你的 ID 集中,这一定可能就是误判率。 |
8
xern 2019-03-24 20:18:22 +08:00 via Android 1
字典树?
|
9
blacklee 2019-03-24 20:28:03 +08:00 1
凭感觉写。
先用楼上说的布隆过滤方法。 然后如果要完全精确,在建立集合的同时造一个子集合用来存所有的值,用来在通过布隆过滤后的精确确认。但这个数据量,对空间要求也是很高的。 |
10
9hills 2019-03-24 20:39:44 +08:00 2
其实 shell 一行就搞定了,而且也不占什么内存。如果要是嫌慢,就把文件用 split -l 拆分后,放到多台机器上执行。
不过不会太慢,因为基本可以达到 IO 满速 假如原始文件是 source,每个 id 是一行,几百亿行,要比对的 id 文件是 target awk 'ARGIND==1{a[$0]} ARGIND>1&&($0 in a){print $0}' target source > jiaoji # awk 需要是 gnu-awk,mac 上默认的不行,如果是 mac,可以用 brew install gawk jiaoji 就是两个文件的交集 这个问题是我常备的基础面试题,数百亿 id 存到 Hash 表内存不够,反过来思考下,把 10000 条 id 塞到 hash 表里,然后数百亿的 id 一条条查不就完了。 |
11
9hills 2019-03-24 20:41:09 +08:00 1
当然 source 和 target 都非常大,就只能用 MapReduce 或者别的分布式计算的方式分而治之了
|
12
abcbuzhiming 2019-03-24 20:43:54 +08:00 1
要求很精确不,不是很精确就用布隆,要求很精确那就没办法了,空间不可少的。速度的话,首先用个 hash 算法,分个组,分而治之
|
13
herozhang 2019-03-24 21:37:23 +08:00 1
如果百亿 id 不是经常变化的,可以先把百亿 id 排序,然后查找就很快了
|
14
WordTian 2019-03-24 21:42:18 +08:00 via Android 1
百亿级的 32B 长度字符串,按百亿算,也有 320G 原始数据啊
还要快速,那就只能空间换时间了呗 |
15
stiekel OP @AlisaDestiny
@wangluofansi @blacklee @abcbuzhiming 好的,我试试布隆过滤。 @xern 请问能否详细点?毕竟数量师有点大。 @9hills MapReduce 也是一个方案,我找时间试试。 @herozhang 会变化,比如发现一个不存在,那就先存到库里,再需要添加进去。 @WordTian 是的,就是数据量太大了。 |
16
lyjr 2019-03-24 23:20:25 +08:00 1
32b 的长度只能表达大小为 2^32 的集合,也就是只有 42 亿多的字符串,哪来的百亿?问题本身就有毛病。。。
|
17
doraemon0711 2019-03-24 23:26:01 +08:00 1
@lyjr 可能是说位数吧
|
18
tony601818 2019-03-24 23:48:06 +08:00 1
Redis 的 BloomFilter 了解下?
|
19
zealic 2019-03-25 00:55:34 +08:00 1
详细说下我在一楼说的算法
(Bitmap + 二叉树) x 链表 空间最小化,根据已知条件,最坏的情况下内存占用为 645K,计算量也不大 算法细节为, BitmapBinaryTree,六级,1->2-4->8->16->32 然后循环所有 ID,每个 ID 置位 Bitmap,发现重复的 ID 就创建一个新的 BitmapBinaryTree 并置位 如此循环最多创建 10000 个 BitmapBinaryTree 因为大多数 ID 不重复,大部分数据位只会存在于第一个 BitmapBinaryTree 那么最终数据结构应该叫做 BinaryTreeChain,数据结构如下 type BinaryTreeChain struct { Left *Bitmap128 Right *Bitmap128 Next *BinaryTreeChain // 二分查找对应的 Bitmap8 并置位,若设置成功返回,否则代表重复 // 重复需要创建或查找 Next 链并置位 SetByID(id int256) bool //获取值 GetByID(id int256) bool // 计算总数 CountByID(id int256) bool } type Bitmap128 struct { Left *Bitmap64 Right *Bitmap64 } type Bitmap64 struct { Left *Bitmap32 Right *Bitmap32 } type Bitmap32 struct { Left *Bitmap16 Right *Bitmap16 } type Bitmap16 struct { Left *Bitmap8 Right *Bitmap8 } type Bitmap8 = byte |
20
zealic 2019-03-25 01:06:49 +08:00 1
上面的算
首次读取需要读取所有数据,以后增量数据就极其方便,开销几乎可以忽视 如果对于读取数据有比较高的要求,也可以 MapReduce 并行运行 完成后的也可以通过 Redis 做一二级缓存,完成后可以直接判断 ID 是否存在,以及 ID 总数 落地磁盘做三级缓存,这样以后都不用再次统计数据 |
21
stiekel OP |
22
hugee 2019-03-25 09:08:46 +08:00 via Android 1
这是要做特征库?
|
23
tony601818 2019-03-25 09:20:20 +08:00 1
@stiekel Redis 有官方支持的 ReBloom 模块: https://redislabs.com/redis-best-practices/bloom-filter-pattern/
当然你也可以自己在应用层写一个…… |
24
sujin190 2019-03-25 09:52:17 +08:00 1
trie 树存储呗,内存不够就序列化到磁盘,看你这个 32 位字符串都是 16 进制编码的吧,直接解码成 16 字节,查找磁盘最差也就 16 次,缓存开始几层,应该不慢
|
25
stiekel OP |
26
lujinang 2019-03-25 10:29:03 +08:00 1
bloomfilter
|
27
sujin190 2019-03-25 10:41:30 +08:00 1
@stiekel #25 想了下,如果 500 亿的话,极限情况估计需要 6.2T 磁盘不小啊,前四到五层也许可以直接放到内存里,但是查询是稳定可靠的
排序后遍历 16 次就可以完成 trie 树构建,还是有点麻烦的,如果频繁查询也许还是不错,偶然用一下感觉还是 grep 来的更快更简洁吧 如果想读磁盘更少的话,可以每层保存两字节,8 次就可以,单每次读取量大大上涨了 |