【python】进阶之数据结构（二）

2 数据结构

2.1基本数据结构

可变：列表、字典、集合

不可变：数字、浮点、字符串、元组（需元组内无可变）

直接访问：数字

顺序访问（序列类型）：字符串、列表、元组

Key值访问（映射关系）：字典

2.2 深浅拷贝

【什么是拷贝】：原封不动地复制一份新的，在不同的内存地址上，修改旧的不会影响新的。

变量赋值不是拷贝

image-20220419175739670.png

  • 变量赋值不是拷贝操作，因为变量名list1和变量名list2指向的是一块相同的内存地址

  • 赋值操作后，无论是通过list1还是list2修改列表的元素，都会影响对方。

  • 浅拷贝修改原始数据会影响对方

1
2
3
4
list1 = [1, 2, [11, 22]]
list2 = list1.copy()		# 使用列表的copy方法或使用copy模块中的copy方法，都是浅拷贝

# 浅拷贝后：id(list1) 不等于 id(list2)，说明拷贝了一个新列表。

image-20220419180226331

  • 执行浅拷贝操作，将在开辟一块新的内存空间，然后将list2绑定到这块内存空间上。
  • 新内存空间中有三个位置用来存放其三个元素的内存地址。
  • 新拷贝的列表的三个位置分别绑定旧列表三个位置上的元素的内存地址。
  • 所以修改旧列表的中的字列表时，会影响新列表中的值，因为它们还同步一部分内存空间。

【深拷贝】：使用copy.deepcopy()

1
2
3
import copy			# 导入内置copy模块
list1 = [1, 2, [11, 22]]
list2 = copy.deepcopy(list1)	# 调用deepcopy()实现深拷贝

image-20220419180757393

  • 深拷贝时，当元素是可变数据类型时，会重新开辟一块内存空间，存放这个元素对象的内存地址，且该元素内部的可变数据类型也会再重新开辟内存空间，层层检测，层层拷贝。
  • 此时，新旧列表的子元素都不会共享内存地址，所有不会相互影响。

深拷贝不会，互相独立的

【总结】

  • 深浅拷贝讨论的拷贝对象是可变数据类型
  • 深浅拷贝的区别在于：是否区分元素的可变还是不可变类型的判断;
  • 列表的切片也是浅拷贝，copy模块的copy.copy()函数是浅拷贝操作，和列表的内置方法copy()功能相同。
  • 容器型数据类型的拷贝都存在深浅拷贝问题。
  • 深浅拷贝没有有优缺点。

2.3 推导式

【推导式】也成生成式（comprehensions）是 Python 独有的一种高级特性，它可以使用简单的一行代码实现列表、字典等数据类型的创建或数据类型的转换等任务。

1
2
3
4
5
6
7
# 普通写法：
nums = []
for i in range(1, 101):
    nums.append(i*i)

# 推导式写法：
nums = [i*i for i in range(1, 101)]

【列表推导式】

1
2
3
4
5
6
7
# 【列表推导式】
# 方式1
nums = [i for i in range(10) if i % 2 == 0]

# 方式2
a = {"name":"jack", "age": 18}
keys = [key for key in a]

【字段推导式】

1
2
3
4
5
6
# 方式1
nums = {i: i*2 for i in range(5)}

# 方式2
li = [[1,2], (3,4)]
dict(x for x in li)			# {1: 2, 3: 4}

【集合推导式】

1
2
3
4
5
# 方式1
b = {i for i in range(1,5)}

# 方式2
a = set(i for i in range(1,5))

【元组推导式】

1
2
3
4
5
6
7
8
9
# 方式1
tuple(x for x in range(1,5))		# (1, 2, 3, 4)

# 数据类型转换
nums = [3,4,5,6]
tuple(x for x in nums)				# (3, 4, 5, 6)

# 元组推导式，按理说应该使用()定义，括号内循环的方式生成元组生成式，
# 但是()被python中的生成器占用，所以只能使用tuple

list_a = [m for i in iterable for m in i ]

2.4.1 三元表达式

在Python中，三元表达式是一种简洁的条件表达式，用于根据条件选择不同的值。它的语法形式如下：

1
value_if_true if condition else value_if_false

其中，condition 是一个条件表达式，如果条件为真，则返回 value_if_true；否则返回 value_if_false。

1
2
3
4
5
x = 10
y = 20

max_value = x if x > y else y
print(max_value)  # 输出 20

三元表达式通常用于简单的条件选择，可以在一行代码中快速进行条件判断和值的选择。它比使用完整的 if-else 语句更为简洁和紧凑。

2.4 namedtuple 有名元组【重点】

可以想象成一个元组但是他有名字，也叫具名元组

兼顾元组的特性，一旦定义不能被修改

可以通过对象点的方式访问，。

1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])		# 新建一个Point类型，具有x y两个字段
p = Point(11, y=22)			# 实例化p  11赋值给x, 22赋值给y

print(p[0], p[1])
print(p.x, p.y)				# 属性取值
print(p._asdict())			# 返回一个字典：{"x": 11, "y": 22}

d = {"x": 11, "y": 22}
print(Point(**d))		# 通过字典新建 这个好用

p._replace(x=100)		# 返回一个新namedtuple
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import namedtuple

# 定义有名元组的类
Person = namedtuple('Person', ['name', 'age', 'city'])

# 原始字典
person_dict = {
    'name': 'Alice',
    'age': 25,
    'city': 'New York'
}

# 将字典转换为有名元组
person_tuple = Person(**person_dict)

print(person_tuple.name)  # 输出 'Alice'
print(person_tuple.age)   # 输出 25
print(person_tuple.city)  # 输出 'New York'

首先通过 namedtuple 函数定义了一个名为 Person 的有名元组类，它有三个字段：name、age 和 city。然后，定义了一个字典 person_dict，包含了相应的字段值。接下来，使用 ** 运算符将字典中的键值对作为参数传递给 Person 类的构造函数，创建了一个有名元组对象 person_tuple。

优点：通过访问有名元组对象的字段，可以获取字典中对应的值。

缺点：

1、不可变性（定义了就不能变）

2、额外的内存消耗：需要开辟额外的内存空间来存储字段名称和值，大规模数据时可能会影响性能

3、有限的功能：轻量级，缺乏灵活性，

4、不支持动态字段操作：不可以动态添加和删除

2.5 OrderedDict 顺序字典

python3.6之前的字典是不按插入先后顺序排序的，但是可以实现这种功能，就是OrderedDict类型字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class OrderedDict(dict):
    'Dictionary that remembers insertion order'
    pass
# 示例1：基本使用
from collections import OrderedDict

# 初始化时可以传键值对参数
order_dict = OrderedDict(name="jack", age=18)
print(order_dict)

for k, v in order_dict.items():
    print(k, v)

for i in range(5):						# 也可以循环插入键值对
    order_dict[i] = i * 10

for k, v in order_dict.items():
    print(k, v)
    
# 示例2：独有方法move_to_end()
def move_to_end(self, key, last=True):
    """
    Move an existing element to the end (or beginning if last is false).
    Raise KeyError if the element does not exist.
    """

# 将age这个key移动到最后
order_dict.move_to_end("age")
print(order_dict.keys())

python3.6之后的字典默认按照插入的先后顺序展示

2.6 defaultdict 不会错误的字典

普通的字典访问不存在的键时会抛出keyError异常

defaultdict类型字典在访问不存在的key时不会异常，会返回default

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
示例1：基本使用
from collections import defaultdict


dd = defaultdict()		# 因为没有default_factory，所以此时dd和普通dict没有区别

dd = defaultdict(int)	# default_factory为int
d[1] = 100
print(d[1])
print(d[2])		# 因为不存在2这个key，所以返回int的默认值，即0


dd = defaultdict(list)	# default_factory为list
print(d[2])		# 因为不存在2这个key，所以返回list的默认值，即[]
示例2：default_factory可以为可调用对象
from collections import defaultdict


def default_value():
    return 500


dd = defaultdict(default_value)
v1 = dd[1]
print(v1)

2.7 deque 双向队列

deque双向队列（double-end queue）类似于list的容器

deque 可以快速的在队列的头部和尾部添加、删除元素

list只能在尾部追加，不可以从头部加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
dq = deque()
dq.append(100)
dq.appendleft(300) # 从左边加元素
dq.pop()
dq.popleft() # 从左边弹出元素
for i in dq:
    print(i)

print(dq.pop())
print(dq.popleft())		# 从左边弹出元素

dq.rotate(2)            # 把右边2个元素依次放在左边, 默认1，复数则相反方向
# 示例2：将可迭代对象变成双向队列
from collections import deque

ll = [1, 2, 3, 4, 5]

dq = deque(ll)
print(dq.popleft())

2.8 二分查找

  • 最简单的查找算法是遍历，但遍历的效率太低了。
  • 二分查找（也叫折半查找）
  • 二分查找的原理是，选择一个有序列表，确定最左边的值和最右边的值和最中间的位置值，比较待查元素和中间位置值，这样每次比较就可以排除一般的查找范围。
  • 二分查找的前提是有序，特点是速度快，大数据查找的时候快一点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 实现方式： 
# 1、定义最左侧和最右侧的下标，
# 2、开始循环，
# 3、定义 中间值的下标
# 4、如果中间值大于查找值，那么就缩小范围，最右侧结束下标变成中间值-1 
# 5、反之，如果中间值小于查找值，那么就缩小范围，最左侧下标变成中间值+1
# 返回 -1 查找到了，就返回-1，如果没找到会一直找，
def query_target(list_test ,target):
    left = 0
    right = len(list_test)-1
    wile left<=right:
        mid = (left+right)//2
        if list_test[mid]==target:
            return mid
        elif list_test[mid]>target:
            right=mid-1
        else:
            left=mid+1
    return -1

优点：简单，高效快速

缺点：要求被查列表必须有序、递归占用空间、不适合动态数据

应用场景：有序列表、静态数据、快速查找

2.9 冒泡排序

实现的逻辑：从第一个元素开始，逐个比对每一个元素，如果自己比对比的元素大，那么自己的索引就前进一个

image-20220419211719385

1
2
3
4
5
6
7
8
9
10
a = [1, 56, 65, 23, 12, 23, 5, 7, 3, 9]
print(a)
l = len(a) # 10个元素，l就是10，但列表索引是0-9
# 第一层遍历列表的总长度
for i in range(0,l): # 注意，range里面第一个参为0时可不写,所以这里是0-10，就是i就是1-9
    # 第二层，遍历列表的长度减去当前的位置减去1,比如说现在i是在1你range里面就是0-8
	for j in range(0,l-i-1): # l-i-1的目的是只需要遍历当前位置往后的位置上的数，不需要与当前位置往前的数作对比
		if a[j]>a[j+1]: # 如果当前位置比后面位置的大，就交换位置
			a[j],a[j+1]=a[j+1],a[j]
print(a)

优点：简单易懂，稳定，原地排序，不会生成新的列表，不改变相等值的位置

缺点：性能差，不适合大规模数据排序

应用场景：小规模排序，

2.10 选择排序

实现逻辑：

1、找到数据中最小的元素，将这个元素与第一个元素交换位置

2、在剩下元素中找最小的元素，将这个元素与剩余元素中的第一个元素交换位置

3、循环

1
2
3
4
5
6
7
8
def selection_sort(list1):
    n=len(list1)
    for i in range(n-1):
        min_index = i
        for j in range(i+1,n):
            if list[j]<list1[min_index]:
                min_index = j
        arr[i],arr[min_index]=arr[min_index],arr[i]

【代码实现v2】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 参考冒泡排序的原地交换思路，实现原地交换的选择排序
# 首先默认min_index等于无序区第一个位置，如果后面位置上的数比默认位置上的数小，即重置最小数的位置，
# 这样每趟循环后，min_index都是无序区最小数的位置。
# 将无序区第一个位置的数和min_index上的数交换，实现原地交换


def select_sort(li):
    for i in range(len(li) - 1):    # i表示循环趟数
        min_index = i               # 默认无序区的第一个位置上的元素最小，最为比较的参考对象
        for j in range(i+1, len(li)):    # j比较的起始位置，可以从i+1开始，减少一次和自己比较的循环
            if li[j] < li[min_index]:
                min_index = j               # 记录最小数的位置
        # 一趟循环后，找到无序区最小数的位置，交换无序区第一个位置的数和无序区最小的数
        li[i], li[min_index] = li[min_index], li[i]

2.11 python内置排序算法

sort() 原地排序，不会生成新的数据，只对列表用

sorted() ，生成一份新数据，对所有可迭代对象都用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 示例1：基本使用
l1 = [5, 2, 8, 1, 4, 5]
l2 = [6, 1, 7, 3, 9, 2]
l1.sort(reverse=True)		# reverse=True降序排

l2 = sorted(l2)
# 示例2：高级用法
# key指定排序规则
def my_sort(x):
    return x["id"]
ll.sort(key=my_sort)
# 匿名函数
ll = [{"id": 5}, {"id": 1}, {"id": 3}]
ll.sort(key=lambda x: x["id"])

readonly option is set (add! tooverride)
# 按权重排序
# id=3排第一位，id=5排第二位， id=1排第三位
weights = {3: 1, 5: 2, 1: 3}

ll.sort(key=lambda x: weights[x["id"]])
python
#python #笔记
【python】进阶之数据结构（二）
http://example.com/2024/03/18/602python进阶之数据结构（二）/
作者
Wangxiaowang
发布于
2024年3月18日
许可协议