深度解析Python中的数据结构和算法(一)

2024 年 8 月 8 日 8点热度 0人点赞 0条评论

python提供了大量的内置数据结构，包括列表、字典、元组、集合等。大多数情况下使用这些数据结构是很简单的。但是，我们经常会碰到诸如查询、排序、过滤等等这些普遍的问题。因此，本片博客主要分享比较常见的问题和算法，理解吃透这些问题，将会提升代码的健壮性和优化性。

1.解压序列赋值给多个变量

问题描述：有一个包含N个元素的元组或者序列，怎样将它里面的值解压后同时赋值给N个变量？

思路：任何序列，也可以理解成可迭代对象可以通过一个简单的赋值语句(=)解压并赋值给多个变量。唯一的前提就是序列里面的元素要和变量的数量一致。

代码实现：

p = (4,5)
x,y = p
print(x,y)
'''以上结果是4 5'''

延伸：有时候，我只想要解压一部分可迭代对象里面的元素，怎么办呢？

解答：对于这种情况python并没有提供特殊的语法去解决。但是我们可以使用任意变量名去占位。占位变量为不想要的元素即可。

代码实现：

data = [(4,5),"nihao",5,4]
_,x,_,y = data
print(x,y)
'''以上的结果是:nihao 4'''

注意：这种解压方式可以用在任何可迭代对象上面，不仅仅只能用在列表或者元组

2.解压可迭代对象赋值给多个变量

问题描述：如果一个可迭代对象的元素超过变量的个数，会抛出一个ValueEorror的异常。那么怎么才能从这个可迭代对象中解压出N个元素出来？

思路：Python的星号表达式即可解决这个问题

代码实现：

data = (1,2,3,4,5)
x,y,*z = data
print(x,y,z)
'''以上结果是:1 2 [3, 4, 5]'''

注意：可以观察到我们的z是一个列表，即不管可迭代对象的元素和变量个数是否相等，用星号之后变量返回的类型都是一个列表，包括0个也是。

延伸：星号表达式在迭代元素为可变长元组的序列时非常实用，举例。

代码实现：

info = [('name','张三','李四'),('action','伸出手','向'),('to','女朋友','打招呼')]
def do_name(x,y):
    print(x,y)

def do_action(z,m):
    print(z,m)

def do_to(s,h):
    print(s,h)

for tag,*args in info:
    if tag == "name":
        do_name(*args)
    if tag == "action":
        do_action(*args)
    if tag == "to":
        do_to(*args)
"""以上的结果是:
张三 李四
伸出手 向
女朋友 打招呼
"""

3.保留最后N个元素

问题：在迭代操作或者其他操作的时候，怎么只保留最后有限的几个元素的历史记录？

思路：python中collections.deque即可解决此问题。

代码实现：

from collections import deque
data = [1,2,5,6,4,5,6,8]
print(deque(data,maxlen=5))
"""以上的结果是:deque(data,maxlen=5)"""

延伸：当然deque类还可以被用在任何一个简答的队列数据结构的场合，其中包括我们经常用到的增删改查。

代码实现：

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.appendleft(4)
print(q)
'''以上的结果是:deque([4, 1, 2, 3])'''

4.查找最大或最小的N个元素

问题：怎么从一个集合中查找到最大或者最小的N个元素？

思路：heapq模块即可解决此问题。

代码实现：

import heapq
data = [1,6,56,43,13,1456,465,41,45,54,5,51,54,54,31]
print(heapq.nlargest(3,data))
print(heapq.nsmallest(3,data))
'''以上结果是:
[1456, 465, 56]
[1, 5, 6]
'''

单从字面意思不难理解，一个是larger取最大，一个是small取最小

延伸：heapq最底层的原理的是堆数据结构，是什么意思呢？就是heapq[0]永远都是最小的元素，其他元素的位置怎么排序不管，只管heapq[0]这个位置是最小的元素即可，可以通过heappop查看，每次弹出的元素，都是当前集合里最小的元素，这就是堆数据结构，好处就是减少时间复杂度。

代码实现：

data1 = [1,6,56,43,13,1456,465,41,45,54,5,51,54,54,31]
heapq.heapify(data1)
print(data1)
heapq.heappop(data1)
print(data1)
"""以上结果是:
[1, 5, 31, 41, 6, 51, 54, 43, 45, 54, 13, 1456, 54, 56, 465]
[5, 6, 31, 41, 13, 51, 54, 43, 45, 54, 465, 1456, 54, 56]
"""

可以发现除了0位置上的元素删除后下一次最小的元素就到这个位置了，而其他位置的元素没有规律。

5.实现一个优先级队列

问题：怎么实现一个按优先级排序的队列？并且在这个队列上面每次pop操作总是返回优先级最高的那个元素

思路：还是利用heapq模块去解决

代码实现：

class ProperQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self,item,priority):
        heapq.heappush(self._queue,(-priority,self._index,item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

class Item:
    def __init__(self,name):
        self.name = name
    def __repr__(self):
        return 'Item({!r})'.format(self.name)


q = ProperQueue()
q.push(Item('foo'),1)
q.push(Item('bar'),5)
q.push(Item('spam'),4)
q.push(Item('grok'),1)
print(q.pop())
print(q.pop())

简单解释：首先我们私有化一个队列和索引，push是将我们的元素推进列表，pop是将我们的元素弹出列表。其中priority是我们的优先级，这里需要大家看一下heappush的源码，如下图：

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)

我们的item里面有三个元素，分别是优先级，索引，内容。接着看_siftdowm源码：

def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

这几段代码的意思就是，首先我们队列里面是有一个0级的优先级，每当我们push进来一个元素之后，去判断当前优先级，当然第一个元素被pos - 1减掉了可以忽略，从第二个元素开始，如果push进来的优先级大于前面的优先级，那么就要交换位置，并且继续判断，知道找到合适的位置即可，也就是我们的_siftdowm源码的意思。所以，当我们给元素定了优先级以后，运用我们的heappush就可以保证，最里面的永远是优先级最小的，最外面的永远是优先级最大的。从而当我们pop队列索引为-1的元素时，永远都会pop出优先级最高的元素。解决！