零陵网站建设,邯郸市地图高清版最新,做网站编辑工作好不好,wordpress skype插件链式结构
上一节讲到了支持随机访问的线性结构#xff0c;这次我们开始讲链式结构, 视频里我会说下这两种结构的区别#xff0c;然后讲解最常见的单链表和双链表。 之前在专栏文章那些年#xff0c;我们一起跪过的算法题[视频]里实现过一个 lru_cache#xff0c; 使用到的…链式结构
上一节讲到了支持随机访问的线性结构这次我们开始讲链式结构, 视频里我会说下这两种结构的区别然后讲解最常见的单链表和双链表。 之前在专栏文章那些年我们一起跪过的算法题[视频]里实现过一个 lru_cache 使用到的就是循环双端链表如果感觉这篇文章有点难理解我们这里将会循序渐进地来实现。 后边讲到哈希表的冲突解决方式的时候我们会再次提到链表。
上一节我们分析了 list 的各种操作是如何实现的如果你还有印象的话list 在头部进行插入是个相当耗时的操作需要把后边的元素一个一个挪个位置。假如你需要频繁在数组两头增删list 就不太合适。 今天我们介绍的链式结构将摆脱这个缺陷当然了链式结构本身也有缺陷比如你不能像数组一样随机根据下标访问你想查找一个元素只能老老实实从头遍历。 所以嘛学习和了解数据结构的原理和实现你才能准确地选择到底什么时候该用什么数据结构而不是瞎选导致代码性能很差。
单链表
和线性结构不同链式结构内存不连续的而是一个个串起来的这个时候就需要每个链接表的节点保存一个指向下一个节点的指针。 这里可不要混淆了列表和链表它们的中文发音类似但是列表 list 底层其实还是线性结构链表才是真的通过指针关联的链式结构。 看到指针你也不用怕这里我们用的 python你只需要一个简单赋值操作就能实现不用担心 c 语言里复杂的指针。
先来定义一个链接表的节点刚才说到有一个指针保存下一个节点的位置我们叫它 next 当然还需要一个 value 属性保存值
class Node(object):def __init__(self, value, nextNone):self.value valueself.next next然后就是我们的单链表 LinkedList ADT:
class LinkedList(object): 链接表 ADT[root] - [node0] - [node1] - [node2]实现我们会在视频中用画图来模拟并且手动代码实现代码里我们会标识每个步骤的时间复杂度。这里请高度集中精力 虽然链表的思想很简单但是想要正确写对链表的操作代码可不容易稍不留神就可能丢失一些步骤。 这里我们还是会用简单的单测来验证代码是否按照预期工作。
来看下时间复杂度
链表操作平均时间复杂度linked_list.append(value)O(1)linked_list.appendleft(value)O(1)linked_list.find(value)O(n)linked_list.remove(value)O(n)
双链表
上边我们亲自实现了一个单链表但是能看到很明显的问题单链表虽然 append 是 O(1)但是它的 find 和 remove 都是 O(n)的 因为删除你也需要先查找而单链表查找只有一个方式就是从头找到尾中间找到才退出。 这里我之前提到过如果要实现一个 lru 缓存访问时间最久的踢出我们需要在一个链表里能高效的删除元素 并把它追加到访问表的最后一个位置这个时候单链表就满足不了了 因为缓存在 dict 里查找的时间是 O(1)你更新访问顺序就 O(n)了缓存就没了优势。
这里就要使用到双链表了相比单链表来说每个节点既保存了指向下一个节点的指针同时还保存了上一个节点的指针。
class Node(object):# 如果节点很多我们可以用 __slots__ 来节省内存把属性保存在一个 tuple 而不是 dict 里# 感兴趣可以自行搜索 python __slots____slots__ (value, prev, next)def __init__(self, valueNone, prevNone, nextNone):self.value, self.prev, self.next value, prev, next对 就多了 prev有啥优势嘛
看似我们反过来遍历双链表了。反过来从哪里开始呢我们只要让 root 的 prev 指向 tail 节点不就串起来了吗直接删除节点当然如果给的是一个值我们还是需要查找这个值在哪个节点 - 但是如果给了一个节点我们把它拿掉直接让它的前后节点互相指过去不就行了哇欧删除就是 O(1) 了两步操作就行啦
好废话不多说我们在视频里介绍怎么实现一个双链表 ADT。你可以直接在本项目的 docs/03_链表/double_link_list.py 找到代码。 最后让我们看下它的时间复杂度:(这里 CircularDoubleLinkedList 取大写字母缩写为 cdll)
循环双端链表操作平均时间复杂度cdll.append(value)O(1)cdll.appendleft(value)O(1)cdll.remove(node)注意这里参数是 nodeO(1)cdll.headnode()O(1)cdll.tailnode()O(1)
源码
double_link_list.py
# -*- coding: utf-8 -*-class Node(object):__slots__ (value, prev, next) # save memorydef __init__(self, valueNone, prevNone, nextNone):self.value, self.prev, self.next value, prev, nextclass CircularDoubleLinkedList(object):循环双端链表 ADT多了个循环其实就是把 root 的 prev 指向 tail 节点串起来def __init__(self, maxsizeNone):self.maxsize maxsizenode Node()node.next, node.prev node, nodeself.root nodeself.length 0def __len__(self):return self.lengthdef headnode(self):return self.root.nextdef tailnode(self):return self.root.prevdef append(self, value): # O(1), 你发现一般不用 for 循环的就是 O(1)有限个步骤if self.maxsize is not None and len(self) self.maxsize:raise Exception(LinkedList is Full)node Node(valuevalue)tailnode self.tailnode() or self.roottailnode.next nodenode.prev tailnodenode.next self.rootself.root.prev nodeself.length 1def appendleft(self, value):if self.maxsize is not None and len(self) self.maxsize:raise Exception(LinkedList is Full)node Node(valuevalue)if self.root.next is self.root: # emptynode.next self.rootnode.prev self.rootself.root.next nodeself.root.prev nodeelse:node.prev self.rootheadnode self.root.nextnode.next headnodeheadnode.prev nodeself.root.next nodeself.length 1def remove(self, node): # O(1)传入node 而不是 value 我们就能实现 O(1) 删除remove:param node # 在 lru_cache 里实际上根据key 保存了整个node:if node is self.root:returnelse: #node.prev.next node.nextnode.next.prev node.prevself.length - 1return nodedef iter_node(self):if self.root.next is self.root:returncurnode self.root.nextwhile curnode.next is not self.root:yield curnodecurnode curnode.nextyield curnodedef __iter__(self):for node in self.iter_node():yield node.valuedef iter_node_reverse(self):相比单链表独有的反序遍历if self.root.prev is self.root:returncurnode self.root.prevwhile curnode.prev is not self.root:yield curnodecurnode curnode.prevyield curnodedef test_double_link_list():dll CircularDoubleLinkedList()assert len(dll) 0dll.append(0)dll.append(1)dll.append(2)assert list(dll) [0, 1, 2]assert [node.value for node in dll.iter_node()] [0, 1, 2]assert [node.value for node in dll.iter_node_reverse()] [2, 1, 0]headnode dll.headnode()assert headnode.value 0dll.remove(headnode)assert len(dll) 2assert [node.value for node in dll.iter_node()] [1, 2]dll.appendleft(0)assert [node.value for node in dll.iter_node()] [0, 1, 2]if __name__ __main__:test_double_link_list()linked_list.py
# -*- coding: utf-8 -*-class Node(object):def __init__(self, valueNone, nextNone): # 这里我们 root 节点默认都是 None所以都给了默认值self.value valueself.next nextdef __str__(self):方便你打出来调试复杂的代码可能需要断点调试return Node: value: {}, next{}.format(self.value, self.next)__repr__ __str__class LinkedList(object): 链接表 ADT[root] - [node0] - [node1] - [node2]def __init__(self, maxsizeNone)::param maxsize: int or None, 如果是 None无限扩充self.maxsize maxsizeself.root Node() # 默认 root 节点指向 Noneself.tailnode Noneself.length 0def __len__(self):return self.lengthdef append(self, value): # O(1)if self.maxsize is not None and len(self) self.maxsize:raise Exception(LinkedList is Full)node Node(value) # 构造节点tailnode self.tailnodeif tailnode is None: # 还没有 append 过length 0 追加到 root 后self.root.next nodeelse: # 否则追加到最后一个节点的后边并更新最后一个节点是 append 的节点tailnode.next nodeself.tailnode nodeself.length 1def appendleft(self, value):if self.maxsize is not None and len(self) self.maxsize:raise Exception(LinkedList is Full)node Node(value)if self.tailnode is None: # 如果原链表为空插入第一个元素需要设置 tailnodeself.tailnode nodeheadnode self.root.nextself.root.next nodenode.next headnodeself.length 1def __iter__(self):for node in self.iter_node():yield node.valuedef iter_node(self):遍历 从 head 节点到 tail 节点curnode self.root.nextwhile curnode is not self.tailnode: # 从第一个节点开始遍历yield curnodecurnode curnode.next # 移动到下一个节点if curnode is not None:yield curnodedef remove(self, value): # O(n) 删除包含值的一个节点将其前一个节点的 next 指向被查询节点的下一个即可:param value:prevnode self.root #for curnode in self.iter_node():if curnode.value value:prevnode.next curnode.nextif curnode is self.tailnode: # NOTE: 注意更新 tailnodeif prevnode is self.root:self.tailnode Noneelse:self.tailnode prevnodedel curnodeself.length - 1return 1 # 表明删除成功else:prevnode curnodereturn -1 # 表明删除失败def find(self, value): # O(n) 查找一个节点返回序号从 0 开始:param value:index 0for node in self.iter_node(): # 我们定义了 __iter__这里就可以用 for 遍历它了if node.value value:return indexindex 1return -1 # 没找到def popleft(self): # O(1) 删除第一个链表节点if self.root.next is None:raise Exception(pop from empty LinkedList)headnode self.root.nextself.root.next headnode.nextself.length - 1value headnode.valueif self.tailnode is headnode: # 勘误增加单节点删除 tailnode 处理self.tailnode Nonedel headnodereturn valuedef clear(self):for node in self.iter_node():del nodeself.root.next Noneself.length 0self.tailnode Nonedef reverse(self):反转链表curnode self.root.nextself.tailnode curnode # 记得更新 tailnode多了这个属性处理起来经常忘记prevnode Nonewhile curnode:nextnode curnode.nextcurnode.next prevnodeif nextnode is None:self.root.next curnodeprevnode curnodecurnode nextnodedef test_linked_list():ll LinkedList()ll.append(0)ll.append(1)ll.append(2)ll.append(3)assert len(ll) 4assert ll.find(2) 2assert ll.find(-1) -1assert ll.remove(0) 1assert ll.remove(10) -1assert ll.remove(2) 1assert len(ll) 2assert list(ll) [1, 3]assert ll.find(0) -1ll.appendleft(0)assert list(ll) [0, 1, 3]assert len(ll) 3headvalue ll.popleft()assert headvalue 0assert len(ll) 2assert list(ll) [1, 3]assert ll.popleft() 1assert list(ll) [3]ll.popleft()assert len(ll) 0assert ll.tailnode is Nonell.clear()assert len(ll) 0assert list(ll) []def test_linked_list_remove():ll LinkedList()ll.append(3)ll.append(4)ll.append(5)ll.append(6)ll.append(7)ll.remove(7)print(list(ll))def test_single_node():# https://github.com/PegasusWang/python_data_structures_and_algorithms/pull/21ll LinkedList()ll.append(0)ll.remove(0)ll.appendleft(1)assert list(ll) [1]def test_linked_list_reverse():ll LinkedList()n 10for i in range(n):ll.append(i)ll.reverse()assert list(ll) list(reversed(range(n)))def test_linked_list_append():ll LinkedList()ll.appendleft(1)ll.append(2)assert list(ll) [1, 2]if __name__ __main__:test_single_node()test_linked_list()test_linked_list_append()test_linked_list_reverse()lru_cache.py python3 only
LRU cachefrom collections import OrderedDict
from functools import wrapsdef fib(n):if n 1: # 0 or 1return nreturn f(n - 1) f(n - 2) # 由于涉及到重复计算这个递归函数在 n 大了以后会非常慢。 O(2^n)
下边就来写一个缓存装饰器来优化它。传统方法是用个数组记录之前计算过的值但是这种方式不够 Pythonic
def cache(func):先引入一个简单的装饰器缓存其实原理很简单就是内部用一个字典缓存已经计算过的结果store {}wraps(func)def _(n): # 这里函数没啥意义就随便用下划线命名了if n in store:return store[n]else:res func(n)store[n] resreturn resreturn _cache
def f(n):if n 1: # 0 or 1return nreturn f(n - 1) f(n - 2)
问题来了假如空间有限怎么办我们不可能一直向缓存塞东西当缓存达到一定个数之后我们需要一种策略踢出一些元素
用来给新的元素腾出空间。
一般缓存失效策略有
- LRU(Least-Recently-Used): 替换掉最近请求最少的对象实际中使用最广。cpu缓存淘汰和虚拟内存效果好web应用欠佳
- LFU(Least-Frequently-Used): 缓存污染问题(一个先前流行的缓存对象会在缓存中驻留很长时间)
- First in First out(FIFO)
- Random Cache: 随机选一个删除LRU 是常用的一个比如 redis 就实现了这个策略这里我们来模拟实现一个。
要想实现一个 LRU我们需要一种方式能够记录访问的顺序并且每次访问之后我们要把最新使用到的元素放到最后表示最新访问。
当容量满了以后我们踢出最早访问的元素。假如用一个链表来表示的话[1] - [2] - [3]假设最后边是最后访问的当访问到一个元素以后我们把它放到最后。当容量满了我们踢出第一个元素就行了。
一开始的想法可能是用一个链表来记录访问顺序但是单链表有个问题就是如果访问了中间一个元素我们需要拿掉它并且放到链表尾部。
而单链表无法在O(1)的时间内删除一个节点必须要先搜索到它但是双端链表可以因为一个节点记录了它的前后节点
只需要把要删除的节点的前后节点链接起来就行了。
还有个问题是如何把删除后的节点放到链表尾部如果是循环双端链表就可以啦我们有个 root 节点链接了首位节点
只需要让 root 的前一个指向这个被删除节点然后让之前的最后一个节点也指向它就行了。使用了循环双端链表之后我们的操作就都是 O(1) 的了。这也就是使用一个 dict 和一个 循环双端链表 实现LRU 的思路。
不过一般我们使用内置的 OrderedDict(原理和这个类似)就好了要实现一个循环双端链表是一个不简单的事情因为链表操作很容易出错。补充其实 lru 有个缺点就是额外的链表比较占用空间如果你感兴趣的话可以看看 redis 如何实现的 lru 算法
class LRUCache:def __init__(self, capacity128):self.capacity capacity# 借助 OrderedDict 我们可以快速实现一个 LRUCacheOrderedDict 内部其实也是使用循环双端链表实现的# OrderedDict 有两个重要的函数用来实现 LRU一个是 move_to_end一个是 popitem请自己看文档self.od OrderedDict()def get(self, key, defaultNone):val self.od.get(key, default) # 如果没有返回 default保持 dict 语义self.od.move_to_end(key) # 每次访问就把key 放到最后表示最新访问return valdef add_or_update(self, key, value):if key in self.od: # updateself.od[key] valueself.od.move_to_end(key)else: # insertself.od[key] valueif len(self.od) self.capacity: # fullself.od.popitem(lastFalse)def __call__(self, func):一个简单的 LRU 实现。有一些问题需要思考下- 这里为了简化默认参数只有一个数字 n假如可以传入多个参数如何确定缓存的key 呢- 这里实现没有考虑线程安全的问题要如何才能实现线程安全的 LRU 呢当然如果不是多线程环境下使用是不需要考虑的- 假如这里没有用内置的 dict你能使用 redis 来实现这个 LRU 吗如果使用了 redis我们可以存储更多数据到服务器。而使用字典实际上是缓存了Python进程里(localCache)。- 这里只是实现了 lru 策略你能同时实现一个超时 timeout 参数吗比如像是memcache 实现的 lazy expiration 策略- LRU有个缺点就是对于周期性的数据访问会导致命中率迅速下降有一种优化是 LRU-K访问了次数达到 k 次才会将数据放入缓存def _(n):if n in self.od:return self.get(n)else:val func(n)self.add_or_update(n, val)return valreturn _LRUCache(10)
def f_use_lru(n):if n 1: # 0 or 1return nreturn f_use_lru(n - 1) f_use_lru(n - 2)def test():import timebeg time.time()for i in range(34):print(f(i))print(time.time() - beg)beg time.time()for i in range(34):print(f_use_lru(i))print(time.time() - beg)# TODO 要怎么给 lru 写单测if __name__ __main__:test()######################################### 使用双链表实现 LRUcache ####################################################一般面试中不会让我们直接用内置结构所以这里提供一个自己实现的双链表map lru 缓存。这也是力扣上的一道真题
[146] LRU 缓存 https://leetcode-cn.com/problems/lru-cache/description/
class ListNode:def __init__(self, keyNone, valueNone):self.key keyself.value valueself.prev self.next Noneclass List:def __init__(self):循环双链表。注意增加了虚拟头尾结点 head,tail 方便处理self.head ListNode()self.tail ListNode()self.head.prev self.head.next self.tailself.tail.next self.tail.prev self.headdef delete_node(self, node): # 删除指定节点node.prev.next node.nextnode.next.prev node.prevdef add_to_head(self, node): # 指定节点添加到 self.head 后nextnode self.head.nextnode.next nextnodenode.prev self.headself.head.next nodenextnode.prev nodeclass LRUCache(object):def __init__(self, capacity):思路循环双链表 字典:type capacity: intself.map dict()self.ll List()self.capacity capacitydef get(self, key)::type key: int:rtype: intif key not in self.map:return -1node self.map[key]self.ll.delete_node(node)self.ll.add_to_head(node)return node.valuedef put(self, key, value)::type key: int:type value: int:rtype: Noneif key in self.map: # 更新不会改变元素个数这里不用判断是否需要剔除node self.map[key]node.value value # 修改结构体会也会修改 map 对应 value 的引用self.ll.delete_node(node)self.ll.add_to_head(node)else:if len(self.map) self.capacity: # 直接用 len(self.map) 不需要self.size 字段了tailnode self.ll.tail.prevself.ll.delete_node(tailnode)del self.map[tailnode.key]node ListNode(key, value)self.map[key] nodeself.ll.add_to_head(node)小问题
这里单链表我没有实现 insert 方法你能自己尝试实现吗 insert(value, new_value)我想在某个值之前插入一个值。你同样需要先查找所以这个步骤也不够高效。你能尝试自己实现个 lru cache 吗需要使用到我们这里提到的循环双端链表借助内置的 collections.OrderedDict它有两个方法 popitem 和 move_to_end我们可以迅速实现一个 LRU cache。请你尝试用 OrderedDict 来实现。python 内置库的哪些数据结构使用到了本章讲的链式结构
相关阅读
那些年我们一起跪过的算法题- Lru cache[视频]
勘误
视频中 LinkedList.remove 方法讲解有遗漏 linked_list.py 文件已经修正请读者注意。具体请参考 fix linked_list add gitigonre。视频最后增加了一段勘误说明。
Leetcode
反转链表 reverse-linked-list
这里有一道关于 LRU 的练习题你可以尝试下。 LRU Cache
合并两个有序链表 merge-two-sorted-lists
