存档

文章标签 ‘hash’

Bloom Filter算法简介

2012年10月13日 6 条评论

Bloom Filter的中文翻译叫做布隆过滤器,是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

在正式介绍Bloom Filter算法之前,先来看看什么时候需要用到Bloom Filter算法。
1. HTTP缓存服务器、Web爬虫等
主要工作是判断一条URL是否在现有的URL集合之中(可以认为这里的数据量级上亿)。
对于HTTP缓存服务器,当本地局域网中的PC发起一条HTTP请求时,缓存服务器会先查看一下这个URL是否已经存在于缓存之中,如果存在的话就没有必要去原始的服务器拉取数据了(为了简单起见,我们假设数据没有发生变化),这样既能节省流量,还能加快访问速度,以提高用户体验。
对于Web爬虫,要判断当前正在处理的网页是否已经处理过了,同样需要当前URL是否存在于已经处理过的URL列表之中。[......]

HDU 1880 魔咒词典

2011年4月3日 没有评论

做这些题,主要是复习STL。我用map写的,结果超内存了,非常郁闷。思路是这样的:用两个map,一个存咒语-意思,另一个存意思-咒语。于是我只用一个map,存咒语-意思,只有一个的话,value就要自己找了,没规律,只能暴力搜索,超时。
传送:http://acm.hdu.edu.cn/showproblem.php?pid=1880
后来,我还是用两个map,提交语言改为G++,结果就AC了。另外,自己试着用两个vector,然后快排,然后二分搜索,也行;不过还是必须G++,否则MLE。两个程[......]

继续阅读

分类: HDOJ解题报告 标签: , , , , ,

USACO The Clocks|BFS

2010年12月1日 3 条评论

The Clocks一题看完之后第一个想到的就是BFS(其实很有多方法可以解决,有兴趣可以去参考参考NOCOW的解题代码)。对于这样的BFS,我都是定义结构体来作为节点,像本题中使用一个state字符串来记录当前的状态,然后最开始用了一个vector来记录已经出现过的状态,结果在提交的时候悲剧的TLE了。
于是各种加优化,想了想,中间产生大量状态,然后每次都从头到尾的搜索vector效率是低了点(对于vector来说,全局的find函数是O(N)的复杂度),于是改用map,map排序了,复杂度O[......]

继续阅读

分类: USACO题解 标签: , , , , ,