张沈鹏,在路上...

期末迎考,忙碌中:)学习进度放缓

今天这篇文章和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[0]):
                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[mid]):
                        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[self.__false_index]
                if self.__true_index!=None:
                    self.__true_index_value=list[self.__true_index]

    @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()