Kyle's Notebook

Python 数据结构应用

技术 Python
Word count: 3kReading time: 13 min
2019/09/19

Python 数据结构应用

当初能快速上手 Python 最重要的一点是其内置的数据结构非常强大，关于数据类型的差别作为基础的知识点在其他教程中已经有非常详细的介绍，所以这里就不再赘述了。

这次主要分享一些能提升开发效率的使用心得。

按特性对 Python 集合容器分类：

  • 容器序列：list，tuple，deque（可存放任意类型）

  • 扁平序列：str，bytes，bytearray，array.array（可for循环遍历，存放单一类型）

  • 可变序列：list，deque,bytearray,array

  • 不可变序列：str，tuple，bytes

有序结构

频繁插入操作

在频繁插入数据、同时要求有序的场合，使用 bisect、collections.deque 效率比较高。

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

# 用来处理已排序的序列，用来维持已排序的序列， 升序
# 二分查找
inter_list = deque()
bisect.insort(inter_list, 3)
bisect.insort(inter_list, 2)
bisect.insort(inter_list, 5)
bisect.insort(inter_list, 1)
bisect.insort(inter_list, 6)

print(bisect.bisect_left(inter_list, 3))    
print(inter_list)   # 插入操作完成后即是一个有序序列

array、deque

性能比 list 高很多（存储在一段连续的内存空间），但只能接收单一类型元素，在某些场景下比 list 更适用。

1
2
3
4
5
import array

my_array = array.array("i")
my_array.append(1)
my_array.append("abc")      # 报错，只接收int类型

自定义序列类

如要自己实现一个具备某种功能的类，应该实现其功能对应的魔术方法：

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
30
31
32
33
34
35
36
37
38
39
40
41
if xxx in yyy:          # __contains__
for i in xxx:           # __iter__
a + b                   # __add__
a += b                  # __iadd__
a[::]                   # __getitem__

import numbers

class Group:

    # 支持切片操作
    def __init__(self, group_name, company_name, staffs):
        self.group_name = group_name
        self.company_name = company_name
        self.staffs = staffs

    def __reversed__(self):
        self.staffs.reverse()

    # 实现切片功能
    def __getitem__(self, item):    # 传入的 item 实际上是一个 slice 对象，“:2”
        cls = type(self)        # 即 Group
        if isinstance(item, slice):
            return cls(group_name=self.group_name, company_name=self.company_name, staffs=self.staffs[item])
        elif isinstance(item, numbers.Integral):
            return cls(group_name=self.group_name, company_name=self.company_name, staffs=[self.staffs[item]])

    # 可以使用 len 函数获取其长度
    def __len__(self):
        return len(self.staffs)

    # 可以迭代
    def __iter__(self):
        return iter(self.staffs)

    # 可以使用 in 操作符判断元素是否在内
    def __contains__(self, item):
        if item in self.staffs:
            return True
        else:
            return False

无序结构

dict

dict 属于 MutableMapping 类型（可修改映射），查看源码：

1
2
3
4
5
from collections.abc import Mapping, MutableMapping
from _collections_abc import __all__

a = {}      # dict 实现了 MutableMapping 中的魔法函数
print (isinstance(a, MutableMapping))

常用方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
a = {
    "ywh1": {
        "company": "aimei"
    },
    "ywh2": {
        "company": "aimei2"
    }
}

new_dict = a.copy()     # 浅拷贝，如 value 中存放的是地址，则不会拷贝其所指的值
new_dict["ywh1"]["company"] = "aimei3"

new_list = ["ywh1", "ywh2"]
new_dict = dict.fromkeys(new_list, {"company": "aimei"})

new_dict.update((("ywh", "aimei"),))
new_dict.setdefault("hwy", {})

子类

  • 不建议继承 list 和 dict（这些是使用 C 实现的数据结构，可能不会执行继承后覆盖的父类方法）；

  • 如要扩展 dict 功能，可继承 collections.UserDict。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import UserDict
class Mydict(dict):
    def __setitem__(self, key, value):
        super().__setitem__(key, value*2)

my_dict = Mydict(one=1)
my_dict["one"] = 1
print (my_dict)

class Mydict(UserDict):
    def __setitem__(self, key, value):
        super().__setitem__(key, value*2)

my_dict = Mydict(one=1)
# my_dict["one"] = 1
print (my_dict)

from collections import defaultdict     # 在找不到某个 key 时会调用 __missing__ 方法，获取默认值

my_dict = defaultdict(dict)
my_value = my_dict["bobby"]

Set

常用方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# set 集合 fronzenset (不可变集合) 无序， 不重复
# s = set('abcdee')
# s = set(['a','b','c','d','e'])
s = {'a','b', 'c'}
# s = frozenset("abcde") # frozenset 可以作为 dict 的 key

# | & -  #集合运算
another_set = set("cef")
re_set = s.difference(another_set)
re_set = s - another_set
re_set = s & another_set
re_set = s | another_set

# set 性能很高
print(re_set)

print (s.issubset(re_set))
# if "c" in re_set:
#     print ("i am in set")

性能测试：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
from random import randint

def load_list_data(total_nums, target_nums):
    """
    从文件中读取数据，以 list 的方式返回
    :param total_nums: 读取的数量
    :param target_nums: 需要查询的数据的数量
    """
    all_data = []
    target_data = []
    file_name = "G:/test/AdvancePython/fbobject_idnew.txt"
    with open(file_name, encoding="utf8", mode="r") as f_open:
        for count, line in enumerate(f_open):
            if count < total_nums:
                all_data.append(line)
            else:
                break

    for x in range(target_nums):
        random_index = randint(0, total_nums)
        if all_data[random_index] not in target_data:
            target_data.append(all_data[random_index])
            if len(target_data) == target_nums:
                break

    return all_data, target_data

def load_dict_data(total_nums, target_nums):
    """
    从文件中读取数据，以dict的方式返回
    :param total_nums: 读取的数量
    :param target_nums: 需要查询的数据的数量
    """
    all_data = {}
    target_data = []
    file_name = "G:/dev/AdvancePython/fbobject_idnew.txt"
    with open(file_name, encoding="utf8", mode="r") as f_open:
        for count, line in enumerate(f_open):
            if count < total_nums:
                all_data[line] = 0
            else:
                break
    all_data_list = list(all_data)
    for x in range(target_nums):
        random_index = randint(0, total_nums-1)
        if all_data_list[random_index] not in target_data:
            target_data.append(all_data_list[random_index])
            if len(target_data) == target_nums:
                break

    return all_data, target_data


def find_test(all_data, target_data):
    # 测试运行时间
    test_times = 100
    total_times = 0
    import time
    for i in range(test_times):
        find = 0
        start_time = time.time()
        for data in target_data:
            if data in all_data:
                find += 1
        last_time = time.time() - start_time
        total_times += last_time
    return total_times/test_times


if __name__ == "__main__":
    # all_data, target_data = load_list_data(10000, 1000)
    # all_data, target_data = load_list_data(100000, 1000)
    # all_data, target_data = load_list_data(1000000, 1000)

    # all_data, target_data = load_dict_data(10000, 1000)
    # all_data, target_data = load_dict_data(100000, 1000)
    # all_data, target_data = load_dict_data(1000000, 1000)
    all_data, target_data = load_dict_data(2000000, 1000)
    last_time = find_test(all_data, target_data)

    #dict查找的性能远远大于list
    #在list中随着list数据的增大 查找时间会增大
    #在dict中查找元素不会随着dict的增大而增大
    print(last_time)

# 1.  dict的 key 或者 set 的值 都必须是可以 hash 的不可变对象 都是可 hash 的，str，fronzenset，tuple，自己实现的类 __hash__
# 2. dict 的内存花销大，但是查询速度快， 自定义的对象 或者 python 内部的对象都是用 dict 包装的
# 3. dict 的存储顺序和元素添加顺序有关
# 4. 添加数据有可能改变已有数据的顺序

应用：从列表、字典、集合筛选数据

列表生成式是一种很 Pythonic 的用法：

1
[x for x in data if x>=0]

仅一行代码就能从 可迭代对象data 中筛选出满足大于等于0条件的元素。它的迭代器版本为：

1
(x for x in data if x>=0)

区别在于返回的是一个满足筛选条件的 迭代器，当遍历时元素在当前循环中才产生所以能大量节省内存，但定义后只能使用一次。

其实字典和集合也可以使用推导式：

1
2
{k: v for k, v in data.iteritems() if v>=0 }    # iteritems 是 items 的迭代器版本
{x for x in s if x>=0}

返回的是 经过筛选的字典/集合，比使用 for 循环要简单直接得多。

  • 尽可能使用生成式，效率比较高；
  • 复杂的场景生成式可能会影响可读性，不建议使用。

应用：为元组元素命名

有 C/C++ 开发经验的朋友常常会用到： 

1
2
3
4
5
6
7
// 宏定义
#define NAME 0
#define AGE 1


// 枚举类型
enum Student{NAME, AGE}

我想说的是这里用到一种为元素命名的方法，直接通过名称能在顺序结构中以更快的速度访问元素（而不需要遍历整个对象）。

在Python中也可以通过名称（而不是下标）的方法访问列表/元组元素：

例如可以自己 定义“枚举类型”：

1
2
3
NAME, AGE, SEX, EMAIL = xrange(4)
student = ("Jim", 16, "male", "Jim418704@gmail.com")
print(student[NAME], student[AGE], student[SEX], student[EMAIL],)

另外也可以使用 collections 模块的 namedtuple：

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

# 先定义一个名为 Student 的 namedtuple
Student = namedtuple("Student", ["name", "age", "sex", "email"])

# 然后就可以使用自定义的 Student 类型创建 namedtuple 对象啦
s1 = Student(
    name="Jim",
    age=16,
    sex="male",
    email="Jim418704@gmail.com"
)
print(s1.name, s1.age, s1.sex, s1.email)

以上两种方法都可以实现通过名称访问元组/列表的元素哦~

应用：统计序列中元素的出现频度

有时需要统计列表/元组中某些元素出现的次数。
其中一种方法是使用字典来统计：

1
2
3
4
5
# 生成范围在1 ~9的元素共 100 个，并存放在字典中
li = [random.randrange(1, 10) for i in range(100)]  
di = dict.fromkeys(li, 0)
for i in li:
    di[i] += 1

这个时候更方便的方法是使用collections的Counter类型：

1
2
from collections import Counter
c = Counter(li)

这时候返回的是一个计数器对象，可以使用 dict 直接转换为以元素为 key、次数为 value 的字典。

而且还可以直接取出出现次数排名前三的元素，并组成新的字典：

1
c.most_common(3)

应用：把字典根据值的大小排序

字典也是可以排序、达到按序查找的效果：

对于一个随机的字典：

1
2
from random import randint
d = {x: randint(60, 100) for x in 'abcxyz'}

排序的方法是转化为一个元组列表，再对元组的项排序：

1
2
3
4
5
keys = d.iterkeys()    
values = d.itervalues()
# 分别取字典的键和值组成元组（Python3 中不支持，只能用 keys()、values()）
tu = zip(keys, values)
new_di = dict(sorted(tu))

更好的方法是利用sorted函数的第二个参数指定参与排序的项：

1
dict(sorted(d.items(), key=lambda x: x[1]))

应用：找到多个字典中的公共键

假设有多个字典，需要找到这些字典中都存在的 key：

1
2
3
di_a = {"a": 1, "b": 2, "c": 3}
di_b = {"a": 5, "d": 2, "e": 3}
di_c = {"a": -5, "f": 5, "g": 0}

可见公共键就是 “a”，但在比较大的字典中要迅速找到这个公共键，常见的方法是构造循环遍历 di_a，并在循环中判断di_a的键是否同时存在于 di_b 和 di_c……

有一种更简便的方法：

1
di_a.viewkeys() & di_b.viewkeys() & di_c.viewkeys()

di_a.viewkeys() 返回的是一个 view 对象，可以直接转化为存放字典 di_a 的列表，最重要的优点是 view 对象是支持集合运算的，上面这个语句返回的是同时存在于 di_a、di_b、di_c 中的元素（交集）的集合，即三个字典的公共键集合：

1
set(['a'])

应用：让字典保持有序

使用字典有时会碰上一种情景，要求让字典一直保持有序（例如比赛中统计名次和成绩），这时候使用 collections 的 OrderDict 类型就非常方便了，以下是一个模拟比赛的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from random import randint
from time import time
from collections import OrderedDict

d = OrderedDict()           # 存放选手成绩的有序字典
players = list('ABCDEFG')   # 模拟七个选手

start = time()
for i in xrange(8):
    input()     # 阻塞：每次输入回车随机弹出一个选手表示该选手完成比赛
    p = players.pop(randint(0, 7-i))    
    end = time()
    print(i+1, p, end-start)    # 输出名次、选手名、用时
    d[p] = (i+1, end-start)     # 把选手成绩计入有序字典

print()
for k in d:
    print(k, d[k])       # 根据进入字典的顺序打印元素

应用：实现用户的历史记录功能（最多 n 条）

很多时候需要让程序实现自动记录用户的历史数据和操作，达到缓存的效果（例如浏览器的搜索记录等）。

Python 的 collections 模块提供了双向队列，可以很方便的实现这个功能，以下是一个猜数游戏（用户每次输入数字，返回答案的取值范围，随着输入次数增多范围缩小，当用户输入与答案相同的数字时游戏结束）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from random import randint

N = randint(0, 100)     # 返回0~100范围内的数字

def guess(k):
    if k == N:
        print("Right!")
        return True
    elif k < N:
        print("{} < N...".format(k))
    else:
        print("{} > N...".format(k))

while 1:
    num = input("Please input a number:")
    if num:
        k = int(num)
        if guess(k):
            break

但有时随着输入的次数增多，就很容易忘记之前已经输入过的数字，这时候可以引入一个存放历史记录的队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from collections import deque
from pickle import dump, load		# 需要时可用 pickle 写入文件
history = deque([], 5)		# 空队列，长度为 5
# ...
while 1:
    num = input("Please input a number:")
    if num:
        k = int(num)
        history.append(k)
        # 当用户输入 ? 或 history 时返回历史输入提示
        if num in ['history', '?']: 
            print(list(history))
        if guess(k):
            break
CATALOG
  1. 1. Python 数据结构应用
    1. 1.1. 有序结构
      1. 1.1.1. 频繁插入操作
      2. 1.1.2. array、deque
      3. 1.1.3. 自定义序列类
    2. 1.2. 无序结构
      1. 1.2.1. dict
      2. 1.2.2. Set
    3. 1.3. 应用：从列表、字典、集合筛选数据
    4. 1.4. 应用：为元组元素命名
    5. 1.5. 应用：统计序列中元素的出现频度
    6. 1.6. 应用：把字典根据值的大小排序
    7. 1.7. 应用：找到多个字典中的公共键
    8. 1.8. 应用：让字典保持有序
    9. 1.9. 应用：实现用户的历史记录功能（最多 n 条）
Total : 78
2021
2020
2019
杂事 技术 算法 Java 数据库 大数据 设计 分布式系统 Docker Kubernetes Go 信息安全 Maven Nginx Linux OS Python Git 微服务 JavaScript MySQL Kafka Vue 前端
《数据密集型应用系统设计》阅读笔记 《凤凰架构》阅读笔记