• 隐藏侧边栏
  • 展开分类目录
  • 关注微信公众号
  • 我的GitHub
  • QQ:1753970025
Chen Jiehua

容斥原理性能分析 

在之前, 我们利用容斥原理实现了hyperloglog的intersect, 接着我们继续分析一下其实现的整体性能.

Hyperloglog分析

测试中,我们采用的日志数据格式如下:

原始输入数据: 16505217行, 统计得独立用户数: 4114406 .

统计了日志中的字段有: product, pid, app, brd, tc, apn, nt, region, cityc, sv, osv, sw, sh, portal, endpoint, drt, ifa, ei.

存储到reids的hyperloglog的key数:9893个,占用内存: 16.64MB .

对于上面benchmark的结果中, traffic_uv:sh:*, traffic_uv:sw:*, traffic_uv:cityc:* 的key数量级均为10^2, 而耗时却相差较大, 其原因在于用户在 cityc 字段的分布比较均匀, 导致 traffic_uv:cityc:* 每个key需要分配更多的桶来标记用户.

递归分析

在后续的测试中我们发现,通过利用容斥原理来计算多个hyperloglog的交集,其计算耗时主要在 recurse_intersect上, 随着组合条件的增多, 递归深度剧增。

我们的测试数据:

当然,以上的每一个条件我们根据筛选参数先pfmerge为一个key, 如: traffic_uv:pid, traffic_uv:nt ……

我们根据容斥原理进行理论上的分析, 设N为组合条件个数, P为pfcount的次数, Q为pfcount的总keys数, 则有:

N=1时, P=1, Q=1

N=2时, P=3, Q=4

N=3时, P=7, Q=12

N=4时, P=15, Q=32

N=5时, P=31, Q=80

N=6时, P=63, Q=92

N=7时, P=127, Q=448

N=8时, P=255, Q=1024

N=9时, P=511, Q=2304

………..

在上面的分析中, 我们已经采用了缓存来减少重复计算量(但仍然存在对对函数的调用和对缓存的读取, 而事实上, 但递归的加深, 这部分的耗时也是不容忽视的, 甚至占用了大部分的耗时).

在接下来的测试中,我们采用了三组数据进行分析, 数据量均为: 原始输入数据: 1600W, 独立用户数: 400W .

8个组合条件:

pid=3&nt=1,2,4&sv_max=511&osv_min=2.3.2&sw_max=1080&sh_max=1920&region=11,12,13,33,34,35,41,42,44&brd=10,11,12,13,21,22,23

三次测试中, recurse_intersect调用总的耗时分别为482ms, 554ms, 521ms.其中pfcount操作的总耗时分别为:153ms, 197ms, 170ms ; pfmerge操作耗时: 17ms, 12ms, 16ms

7个组合条件:

pid=3&nt=1,2,4&sv_max=511&osv_min=2.3.2&sw_max=1080&sh_max=1920&region=11,12,13,33,34,35,41,42,44

三次测试中, recurse_intersect调用总的耗时分别为212ms, 192ms, 200ms.其中pfcount操作的总耗时分别为:92ms, 73ms, 80ms ; pfmerge操作耗时: 15ms, 22ms, 15ms

6个组合条件:

pid=3&nt=1,2,4&sv_max=511&osv_min=2.3.2&sw_max=1080&sh_max=1920
三次测试中, recurse_intersect调用总的耗时分别为63ms, 83ms, 65ms.其中pfcount操作的总耗时分别为:24ms, 41ms, 28ms ; pfmerge操作耗时: 11ms, 15ms, 18ms

5个组合条件:

pid=3&nt=1,2,4&sv_max=511&osv_min=2.3.2&sw_max=1080
三次测试中, recurse_intersect调用总的耗时分别为40ms, 25ms, 26ms.其中pfcount操作的总耗时分别为:22ms, 14ms, 15ms ; pfmerge操作耗时: 8ms, 8ms, 10ms

4个组合条件:

pid=3&nt=1,2,4&sv_max=511&osv_min=2.3.2
三次测试中, recurse_intersect调用总的耗时分别为6ms, 14ms, 10ms.其中pfcount操作的总耗时分别为:4ms, 11ms, 7ms ; pfmerge操作耗时: 7ms, 8ms, 10ms

在组合条件少于等于4个的时候,耗时已经是比较小了.

码字很辛苦,转载请注明来自ChenJiehua《容斥原理性能分析》

评论