pylons建站日记4_边界检测类
期末迎考,忙碌中:)学习进度放缓今天这篇文章和pylons没有什么关系,不过也算是建站的一部分.
前面说过,我是打算写一个抓新闻的网站.
但是,每次抓取时如何区分哪些是更新了,哪些是已经抓取的网页呢?
我的思路是判断页面地址.
但是每抓取一个网页就要去查询一次数据库,判断是该网址是否已存在否存在不免有点低效.
其实这应该并非性能瓶颈,只是C++的效率优先的惯性思维,写完了才发现可能是过早最优化了:)
罪过,罪过...
不过既然已经写了,那就用着吧.
算法假定了这样的一个事实,更新的新闻的链接总是出现在已抓取新闻之前.
我们只需要寻找到最后一条更新过的新闻,然后就可以通过切片获得更新的网址的列表.
而边界可以通过两分法获得,复杂度是O(log2(n)),比逐条查询的O(n)快一点.
class Bound(object): class NoneError(LookupError): pass """ 用途:查找有序对列 满足 与 不满足 函数的边界. >>> print Bound(range (100),lambda x:x>12).false_true_index (12, 13) >>> print Bound(range (10),lambda x:x>12).false_true_index (0, None) >>> print Bound(range (100),lambda x:x>-1).false_true_index (None, 0) >>> print Bound(range (100),lambda x:x<12).false_true_index (12, 11) """ def __init__(self,list,func): self.__true_index=None self.__false_index=None length=len(list) if length: if func(list[-1]): self.__true_index=length-1 else: self.__false_index=length-1 if func(list): self.__true_index=0 else: self.__false_index=0 if self.__false_index!=None and self.__true_index!=None: if self.__true_index>self.__false_index: get_diff=lambda:self.__true_index-self.__false_index get_mid=lambda diff:diff/2+self.__false_index else: get_diff=lambda:self.__false_index-self.__true_index get_mid=lambda diff:diff/2+self.__true_index diff=get_diff() while diff>1: if func(list): self.__true_index=mid else: self.__false_index=mid diff=get_diff() mid=get_mid(diff) if self.__false_index!=None: self.__false_index_value=list if self.__true_index!=None: self.__true_index_value=list @property def true_index(self): return self.__true_index @property def false_index(self): return self.__false_index @property def false_true_index(self): return (self.false_index,self.true_index) @property def true_value(self): if self.__true_index_value==None: raise NoneError,'True bound not exist' return self.__true_index_value @property def false_value(self): if self.__false_index==None: raise NoneError,'False bound not exist' return self.__false_index_value @property def false_true_value(self): return (self.false_value,self.true_value) if "__main__"==__name__: import doctest doctest.testmod()
页:
[1]