免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: spike8800

URL过滤 内核空间还是用户空间 [复制链接]

论坛徽章:
0
发表于 2009-12-17 10:40 |显示全部楼层
原帖由 duanjigang 于 2009-12-17 09:59 发表

白金兄,不知道hash1和hash2总的CPU占用跟一个md5比起来如何??
如果数量级上小于md5的话,这是很不错的一个方法,另外,现在key和value相同的几率已经很小了。
如果在千万级的URL上能出现重复的话,也可以 ...

段兄,用 MD5 来实现应该是怎样的?只需 MD5 一次即可,无需像我这样既算一次 key 再算一次 value 吗?

我没有严格比对 hash2 与 md5 的算法,所以具体性能差异我不太清楚

针对 value 的问题,我昨天换成 __u64 变量,千万级的随机数,碰撞概率是 0%
当然,换成 value1 = hash2(url); value2 = hash3(url); 也可以,但代价要比一个 __u64 的 value 大一些

[ 本帖最后由 platinum 于 2009-12-17 10:45 编辑 ]

论坛徽章:
0
发表于 2009-12-17 10:43 |显示全部楼层
原帖由 Godbach 于 2009-12-17 10:28 发表


key还是16bit吗,只是数据改成64bit?

对,value 验证数据改成了 64bit,key 还是 16bit
key 的大小只影响到 bucket 的多少,只影响到冲突链的长度

昨天为了验证一千万数据的冲突率,我把 bucket 设置成 65536 * 1024 个了,key 自然换成了 32bit 变量
value = hash1(string) & (BUCKETS - 1);

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-12-17 11:06 |显示全部楼层
32bit的可以和16bit的可以对于验证结果有多大影响啊

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-12-17 11:11 |显示全部楼层
如果说我知道了所有URL的IP,用IP做key应该是个不错的方法。

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-12-17 11:36 |显示全部楼层
高亮一把,欢迎大家多参与讨论。

论坛徽章:
0
发表于 2009-12-17 13:45 |显示全部楼层
原帖由 platinum 于 2009-12-17 10:40 发表

段兄,用 MD5 来实现应该是怎样的?只需 MD5 一次即可,无需像我这样既算一次 key 再算一次 value 吗?

我没有严格比对 hash2 与 md5 的算法,所以具体性能差异我不太清楚

针对 value 的问题,我昨天换 ...

如果URL很长的话,用md5计算一下,生成一个32位的字符串,key用URL的前两位或者前四位。比较时直接比较md5值,
晕了,计算完md5再比较32位字符串,这样快还是直接比较完整字符串快呢
还不如在冲突链上直接strcmp呢
另外,这样貌似是一个精确匹配。。。。。但是感觉现实中模糊匹配的比较多。md5的算法效率我也不清楚
你的做法:一个hash生成key,一个hash生成value已经不错了,我的意思是说,如果出现重复时,可以再搞个value2.

[ 本帖最后由 duanjigang 于 2009-12-17 13:50 编辑 ]

论坛徽章:
0
发表于 2009-12-17 13:49 |显示全部楼层
发重了

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-12-17 13:49 |显示全部楼层

回复 #26 duanjigang 的帖子

对,白金兄的方式确实不错。并且value可以考虑用64位的,这样减少冲突。

如果在搞一个value2的话,value1+vaul2的计算效率是否高于MD5就得测试了

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-12-17 13:52 |显示全部楼层
另外,这样貌似是一个精确匹配。。。。。但是感觉现实中模糊匹配的比较多。md5的算法效率我也不清楚

恩,这样实现应该算是精确匹配了。
可以考虑用一些模糊匹配的算法

论坛徽章:
0
发表于 2009-12-17 13:57 |显示全部楼层
我现在采用的做法就是:URL的前两字节做key,这样几乎不需要计算,
然后冲突链上直接基于KMP的strcmp了,也算模糊匹配了
如果用户定义串是URL的字串就认为命中。。。。白金这个方法可以对比测试下。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP