Chapter1：python数据结构与算法

1.python数据结构与算法

本篇博客依托书籍《Python Cookbook》展开对python的学习

1.0 列表、元组、集合、字典

1.1 序列分解为单独变量

问题：我们有一个包含 N 个元素的元组或序列，现在想将它分解为N个单独的变量
解决方案：任何序列（或可迭代的对象）都可以通过一个简单的赋值操作来分解为单独的变量。唯一的要求是变量的总数和结构要与序列相吻合

列表分解序列

list1 = [1, 1, 'a', 3.14] #允许重复、支持不同类型
x,y,z,n = list1
print("列表元素:",list1)
print("第一个元素修改前:", x)
list1[0] = 2              #允许修改
print("第一个元素修改后:", list1[0])
-------------------
列表元素: [1, 1, 'a', 3.14]
第一个元素修改前: 1
第一个元素修改后: 2

元组分解序列

tuple1 = (1, 1, 'a', 3.14) #允许重复、支持不同类型
x,y,z,n = tuple1
print("元组元素:",tuple1)
print("第一个元素修改前:", x)
tuple1[0] = 2 #不允许修改
print("第一个元素修改后:", tuple1[0])
-------------------
元组元素: (1, 1, 'a', 3.14)
第一个元素修改前: 1
Traceback (most recent call last):
  File "~/PycharmProjects/pythonpractice/datastructure.py", line 11, in <module>
    tuple1[0] = 2
TypeError: 'tuple' object does not support item assignment

集合分解序列

set1 = {1, 'a', 3.14}  #不允许重复、支持不同类型
x, y, _ = set1 #分解操作中如想丢弃某些特定值可以选一个用不到的变量名作为要丢弃值的名称，例如：_
print("集合元素:",set1)
print("第一个元素修改前:", x)
set1[0] = 2  #不允许修改
print("第一个元素修改后:", set1[0])
------------------------
集合元素: {1, 3.14, 'a'} #重复元素被删除
第一个元素修改前: 1
Traceback (most recent call last):
  File "/home/wxy/PycharmProjects/pythonpractice/datastructure.py", line 19, in <module>
    set1[0] = 2  #不允许修改
TypeError: 'set' object does not support item assignment

字典分解序列

dict1 = {'a': 1, 'b': 1, 'c': 'a', 'd': 3.14}  # key不允许重复、值可重复、支持不同类型
x, y, z, n = dict1
print("修改前:", x)
dict1['a'] = 2  # 允许修改
print("修改后:", dict1['a'])
--------------------
修改前: a
修改后: 2

集合中数据元素不允许重复、不允许修改
元组中数据元素不允许修改
字典key不允许重复
其他均可重复、可修改

只要对象恰好是可迭代的（可以逐个返回其元素的对象）即只要是可迭代对象就可以执行分解操作
python中的可迭代对象


可迭代对象：字典

dict1 = {'a': 1, 'b': 1, 'c': 'a', 'd': 3.14}  # key不允许重复、支持不同类型
for k in dict1:
    print(k,dict1[k])
------------------
a 1
b 1
c a
d 3.14

可迭代对象：文件对象

file_path = '/home/..../Downloads/command.txt'
with open(file_path, 'r') as file:
    for line in file:
        print(line, '\n')
------------------
aaaabbbb

可迭代对象：生成器（使用yield函数，返回一个迭代器，可以逐个生成值）

def my_generator():
    yield 'a'
    yield 2
    yield 3.14


for value in my_generator(): # def my_generator() -> Generator[str | int | float, Any, None]
    print(value)
---------------------
a
2
3.14

可迭代对象：范围对象（range() 函数返回一个可迭代的对象，可以用于生成整数序列）

for i in range(1, 6, 1):
    print(i)
---------------------
1
2
3
4
5

可迭代对象：numpy数组

import numpy as np
# arr = [1, 2, 3]
# n_arr = np.array(arr)
n_arr = np.array([1, 2, 3])
for i in n_arr:
    print(i)
-------------------------
1
2
3    

可迭代对象：自定义可迭代对象

class MyInterable: #定义一个名为 MyIterable 的类
    def __init__(self): #定义类的构造函数，当实例化该类时自动调用
        self.data=[1,2,3] #在构造函数中定义一个列表属性 data，其中包含元素 [1, 2, 3]
    def __iter__(self): #使对象成为一个可迭代对象
        self.index = 0; #初始化一个索引变量 index 为 0，用于指示当前迭代的位置
        return self #返回自身实例，使得 MyIterable 类对象可以用于 for 循环等迭代操作
    def __next__(self): #使该对象支持逐步返回元素。
        if self.index < len(self.data): #判断当前索引是否在 data 列表长度范围内，确保不会越界。
           result = self.data[self.index] #取得 data 列表中当前位置 index 处的元素并存入
           self.index += 1 #将 index 递增1，为下一次迭代做准备
           return result #返回当前位置的元素值 result
        else:
           raise StopIteration #如果索引超出范围，抛出 StopIteration 异常，通知 Python 结束迭代

for item in MyInterable(): #使用 for 循环迭代 MyIterable 类的实例，并将每个返回的元素赋值给 item
    print(item) #print(item) #将每个元素 item 输出到控制台
-----------------------
1
2
3

1.2 从任意长度的可迭代对象中分解元素

问题：需要从某个可迭代对象中分解出 N 个元素，但是这个可迭代对象的长度可能超过 N，这会导致出现“分解的值过多（too many values to unpack）”的异常
解决方案：Python 的 *表达式 可以用来解决这个问题

假设有一些用户记录，记录由姓名和电子邮件地址组成，后面跟着任意数量的电话号码。则可以像这样分解记录：

record = ['Irving', '[e-mail]', '725-123', '653-1234']
name, mail, *telphone = record
print(name)
print(mail)
print(*telphone)
----------------------
Irving
[e-mail]
725-123 653-1234

特定的字符串拆分

line = 'nobody:*:-2:-2:Unprivileged:User:/var/empty:/usr/bin/false'
uname, *field, home_dir,sh = line.split(':')
print(uname)
print(*field)
print(home_dir)
print(sh)
-------------------
nobody
* -2 -2 Unprivileged User
/var/empty
/usr/bin/false

1.3 保存最后N个元素

问题：对一系列文本行做简单的文本匹配操作，当发现有匹配时就输出当前的匹配行以及最后检查过的N行文本
解决方案：有限长度的队列

from collections import deque
'''
def search(lines: {__iter__},
           pattern: Any,
           history: Any) -> Generator[tuple[Any, deque], Any, No
'''
def search(lines, pattern, history):
    previous_lines = deque(maxlen=history) #deque(maxlen=N)创建了一个固定长度的队列。当有新记录加入而队列已满时会自动移除最旧的那条记录
    for line in lines:  # 每行逐个进队列
        if pattern in line:  # 该行包含pattern字符串
            yield line, previous_lines  # 生成该行和队列内容(历史记录)
        previous_lines.append(line)  # 将该行添加到队列


if __name__ == '__main__' :
    with open('/home/irving/Downloads/command.txt') as f: #`f` 是文件对象的变量名。这行代码使用open函数打开文件,并将文件对象赋值给变量 `f`。在 `with` 语句块中，可以使用 `f` 来读取或操作文件内容。`with` 语句确保在代码块执行完毕后，文件会被正确关闭。
        for line, prelines in search(f, 'build', 5): 
            for pline in prelines:  # 打印队列内容(历史记录)
                print(pline, end='')
            print(line, end='')  # 打印匹配行
            print('-'*20)

1.4 找到最大或最小的N个元素

问题：在某个集合中找出最大或最小的N个元素
解决方案：heapq 模块的 nlargest 和 nsmallest 函数

import heapq

portfolio = [
    {'name': 'IBM', 'shares': 100, 'price': 91.1},
    {'name': 'AAPL', 'shares': 50, 'price': 543.22},
    {'name': 'FB', 'shares': 200, 'price': 21.09},
    {'name': 'HPQ', 'shares': 35, 'price': 31.75},
    {'name': 'YHOO', 'shares': 45, 'price': 16.35},
    {'name': 'ACME', 'shares': 75, 'price': 115.65}
]
'''
1. 第一个`s`是`lambda`表达式的参数。`lambda s: s['price']`定义了一个匿名函数，这个函数接受一个参数`s`，并返回`s`的`price`属性。
2. 第二个`s`是`lambda`表达式内部的变量，表示传递给匿名函数的每个`portfolio`中的元素（即每个字典）。
'''
# `heapq.nsmallest`函数使用这个`lambda`函数来比较`portfolio`中每个元素的`price`属性，以找到价格最便宜的三个元素
cheap = heapq.nsmallest(3, portfolio, lambda s: s['price'])
print(cheap)
expensive = heapq.nlargest(2, portfolio, lambda s: s['price'])
print(expensive)
---------------------------------
[{'name': 'YHOO', 'shares': 45, 'price': 16.35}, {'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'HPQ', 'shares': 35, 'price': 31.75}]
[{'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}]

情况一：如果只是简单地想找到最小或最大的元素（N=1时），那么用min()和max()会更加快
情况二：当所要找的元素数量相对较小时，函数nlargest()和nsmallest()才是最适用的
情况三：如果要找的元素数量N和集合本身的大小差不多大，通常更快的方法是先对集合排序，然后做切片操作（例如，使用sorted(items)[:N]或者sorted(items)[-N:]）

补充lambda

#补充lambda知识
def fun1(x,y):
    return x+y

fun2 = lambda x,y: x+y
# lambda简单功能的匿名函数 lambda 输入参数: 返回值
print(fun1(1,2))
print(fun2(1,2))
==============
3
3

1.5 实现优先级队列

问题：我们想要实现一个队列，它能够以给定的优先级来对元素排序，且每次pop操作时都会返回优先级最高的那个元素
解决方案：优先级队列

#实现一个队列，它能够以给定的优先级来对元素排序，且每次pop操作时都会返回优先级最高的那个元素。
import heapq

'''
在 Python 中，加下划线通常有以下几种含义：
1. **单下划线前缀 (`_variable`)**：表示这是一个内部变量或方法，建议不要在类或模块外部使用。
2. **双下划线前缀 (`__variable`)**：触发名称改写（name mangling），用于避免子类覆盖，通常用于类的私有属性。
3. **单下划线后缀 (`variable_`)**：避免与 Python 关键字冲突。
4. **单独的下划线 (`_`)**：在交互式解释器中，表示上一个表达式的结果；在循环或解包中，表示一个临时变量或不需要的值。
5. **双下划线前后缀 (`__variable__`)**：表示特殊方法或属性，通常由 Python 内部使用，如 `__init__`、`__str__` 等。
`self._queue` 和 `self._index` 使用了单下划线前缀，表示这些属性是内部使用的，不建议在类外部直接访问。
'''


class PriorityQueue:
    def __init__(self):  # 双下划线前后缀表示特殊方法或属性，通常由Python内部使用
        self._queue = []  # 单下划线前缀是一个内部变量或方法，建议不要在类或模块外部使用
        self._index = 0

    def push(self, item, priority):
    # 把priority取负值是为了让队列能够按元素的优先级从高到低的顺序排列
    # 变量index的作用是为了将具有相同优先级的元素以适当的顺序排列,通过维护一个不断递增的索引，元素将以它们入队列时的顺序来排列
        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):
        # {!r}` 是格式化字符串的一部分，用于调用对象的 `__repr__` 方法。
        # `__repr__` 方法返回一个对象的“官方”字符串表示，通常可以用来重新创建这个对象
        # `{!r}` 会将 `self.name` 的 `__repr__` 表示插入到字符串中
        return 'Item({!r})'.format(self.name)


q = PriorityQueue()
q.push(Item('foo'), 1)
q.push(Item('bar'), 5)
q.push(Item('spam'), 4)
q.push(Item('grok'), 1)
#循环pop队列元素
for i in range(4):
    print(f"第{i+1}次出队元素：{q.pop()}")

-------------------------
第1次出队元素：Item('bar')
第2次出队元素：Item('spam')
第3次出队元素：Item('foo')
第4次出队元素：Item('grok')
# 拥有相同优先级的两个元素（foo和grok）返回的顺序同它们插入到队列时的顺序相同。
# 如果想将这个队列用于线程间通信，还需要增加适当的锁和信号机制

1.6 在字典中将键映射到多个值上

如果想让键映射到多个值，需要将这多个值保存到另一个容器如列表或集合中
如果希望保留元素插入的顺序，就用列表。
如果希望消除重复元素（且不在意它们的顺序），就用集合

from collections import defaultdict
d = defaultdict(list) # d = defaultdict(set)
d['a'].append(1)
d['a'].append(2)
d['a'].append(3)
d['b'].append(4)
d['b'].append(5)
print(d)
------------------
defaultdict(<class 'list'>, {'a': [1, 2, 3], 'b': [4, 5]