前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >python实现高级算法与数据结构:如何实现搜索引擎的竞价排名2

python实现高级算法与数据结构:如何实现搜索引擎的竞价排名2

作者头像
望月从良
发布2021-09-16 17:29:32
4590
发布2021-09-16 17:29:32
举报
文章被收录于专栏:Coding迪斯尼

接上一篇内容,我们继续完善堆的相关操作实现。下面我们要看的是堆的插入操作,当添加一个新元素时,我们把它加到数组末尾,此时新加入的元素必然是一个叶子节点,然后使用bubble_up对堆进行调整,相关代码实现如下:

代码语言:javascript
复制
elements = [ Element('a', 1), Element('a', 8), Element('a', 5), Element('a', 7),
             Element('a', 2), Element('a', 4), Element('a', 3), Element('a', 6)
           ]
push_down(elements)

def  insert(elements : [Element], elem_insert : Element):
    elements.append(elem_insert)
    bubble_up(elements, len(elements) - 1)

elem = Element('a', 10)
insert(elements, elem)

print(elements)

这里代码接上一节末尾代码,push_down先把给定元素数组调整到符合规则的堆,insert函数用于往堆里插入节点,它首先把节点放到数组末尾,然后调用bubbole_up调整新加入数组的元素位置,代码加入一个新元素,其优先级为10,因此加入后它应该变成根节点,代码运行后结果如下:

代码语言:javascript
复制
[Element('a', 10), Element('a', 8), Element('a', 5), Element('a', 7), Element('a', 2),
 Element('a', 4), Element('a', 3), Element('a', 1), Element('a', 6)]

从输出看,新加入节点被调整到了正确位置。接着我们看另一个操作top,它把堆顶部元素弹出来。在根节点从堆中被挪走后,我们需要重新选择一个节点作为根节点,具体做法是,将数组中最后那个元素作为根节点,但这样可能会破坏堆的性质,也就是根节点必须是所有元素最大值,这时我们就可以调用push_down对它进行调整,代码如下:

代码语言:javascript
复制
def  top(elements : [Element]):
    if len(elements) == 0:
        raise ValueError("Heap is empty")

    last_element : Element = elements.pop()
    if len(elements) == 0:
        return last_element
    else:
        top_element : Element = elements.pop(0)
        elements.insert(0, last_element)
        push_down(elements, 0)
        return top_element

def  peek(elements : [Element]):
    if len(elements) == 0:
        raise ValueError("Heap is empty")

    peek_top_element : Element = copy.deepcopy(elements[0])
    return peek_top_element

top_element = top(elements)
print("top of heap is : ", top_element)
print("heap after top: ", elements)

调用top的代码接着前面的insert,执行上面代码后输出结果如下:

代码语言:javascript
复制
peek top element:  Element('a', 10)
top of heap is :  Element('a', 10)
heap after top:  [Element('a', 8), Element('a', 7), Element('a', 5), Element('a', 6), Element('a', 2), Element('a', 4), Element('a', 3), Element('a', 1)]

代码实现中的peek仅仅把根节点的信息返回而没有将其从堆中去除,因此逻辑比较简单。下面我们看看元素的更新操作,当一个元素的优先级发生变化后,堆的性质可能会被破坏,元素的值如果变大了,那么我们需要调用bubble_up来进行调整,如果是变小了,我们可能需要调用push_down进行调整,代码实现如下:

代码语言:javascript
复制
def  find(elements : [Element], content : str) -> int:
    for idx, element in enumerate(elements):
        if element.content == content:
            return idx
    return -1

def  update(elements : [Element], content : str, new_priority : int):
    idx : int = find(elements, content)

    if idx >= 0:
        old_priority = elements[idx].priority
        elements[idx].priority = new_priority
        if new_priority < old_priority:
            push_down(elements, idx)
        elif new_priority > old_priority:
            bubble_up(elements, idx)

elements = [Element('a', 8), Element('b', 7), Element('c', 5),
            Element('d', 6), Element('e', 2), Element('f', 4), 
            Element('g', 3), Element('h', 1)]

update(elements, "g", 9)
print("elements after update: ", elements)

find函数作用是根据给定内容查找对应元素,update函数实现中先查找,看数组中是否包含给定元素,如果存在则找到它对应数组下标, 然后判断元素对应的优先级是增大了还是减小了,如果增大了,那么使用bubble_up调整它与父节点,如果减小了,使用push_down调整它与子节点。

在调用update函数前,先修改元素g对应的优先级,然后使用update调整堆,由于我们把元素g的优先级调整到最大,因此update后,它应该作为堆的根节点,上面代码运行后结果如下: [Element('g', 9), Element('b', 7), Element('a', 8), Element('d', 6), Element('e', 2), Element('f', 4), Element('c', 5), Element('h', 1)]` 从结果上看,update的实现逻辑基本上是正确的。接下来我们看,如果给一个随机数组,我们如何将它构建成一个堆。从前面我们实现的push_down函数可以知道,如果堆的根节点优先级变小,那么调用push_down就能恢复堆的性质。对于一个数组,它后半部分的元素都对于叶子节点,因此他们本身就已经满足堆性质。

假设位于数组后半部分的元素下表为i,那么它对应的父节点下标为 int(i / 2),如果父节点的优先级比它大,那么以父节点为根节点的堆满足条件,但如果父节点的优先级比它小,我们就执行push_down进行调整,于是给定一个随机数组,我们只要对数组前半部分的元素依次调用push_down即可,代码如下:

代码语言:javascript
复制
import math
def  heapify(elements : [Element]):
    for index in range(math.ceil(len(elements) / 2) , -1, -1):
        push_down(elements, index)

elements = [ Element('a', 1), Element('a', 2), Element('a', 3), Element('a', 4),
             Element('a', 5), Element('a', 6), Element('a', 7), Element('a', 8)
           ]

heapify(elements)
print("heapify: ", elements)

上面代码运行后结果如下:

代码语言:javascript
复制
heapify:  [Element('a', 8), Element('a', 5), Element('a', 7), Element('a', 4), Element('a', 1), Element('a', 6), Element('a', 3), Element('a', 2)]

通过检验可以确定,输出的数组元素满足堆的性质。我们需要确认一下上面代码的时间复杂度,当堆的高度是h时,push_down运行所需要的复杂度是o(h),那么高度为h的节点能有多少个呢?

从parent函数的实现可以看到,当一个元素下标为i时,其父节点对应下标为 i/2,由此可以判断,高度每增加1,元素的个数相对于原来高度元素的个数就得少一半。于是高度为h的节点,对应个数最多为 n/(2^h)个,由于每个这样的元素在执行push_down时对应时间为o(h),因此高度为h的元素全都执行完push_down,对应时间就是 o( n/(2^h)*h)。由于h的值最大不会超过lg(n),因此总共的时间复杂度为:

上面公式中,右边式子还可以简化一下:

因此heapify运行时间最多不过O(2n),所以它对应线性复杂度的时间。有了以上理论准备后,我们看看如何实现竞价排名,假设一个关键词对应一百万个网页,但是首页最多能显示十个链接,我们如何快速将优先级最高的链接选出来呢。

通常做法就是先排序,然后选出最后十个元素,快速排序的复杂度是O(n*lg(n)),当n为一百万时,lg(n)约等于20,于是总共需要两千万次运算。反之,我们将一百万个网页中的前10个构建一个小堆,(注意这里与我们前面描述的大堆不一样,不过我们只要将元素值取负值,然后按照大堆的操作就可以得到小堆。),然后从第11个开始,用每个元素与堆的头结点元素进行比较,如果元素的优先级大于小堆的头结点,那么我们一定能确定,小堆头结点对应的元素一定不再前10个元素范围内,于是我们把堆的头结点去除,将新的节点插入,这样遍历一次所有元素后,堆中的元素就是我们需要的元素。

这种做法时间复杂度为O(n*lg(k) + k*lg(k)),因为k是一个常值,因此nlg(k)等价于O(n),于是这么做的时间复杂度就是o(n + k\lg(k)),于是一百万个网页,其运算效率也就一百万次左右,相对于前面做法的两千万次运算,其在效率上的改进是相当明显,特别是随着n值得增大,同时k值远远小于n值时,效率的提升就是本质性的,感兴趣的读者可以自己尝试实现一下。

请点击->更多精彩内容

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-09-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Coding迪斯尼 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档