第 4 章Python 数据结构实现4.1 list (动态数组)原理讲解Python 的 list 是过度分配的动态数组。┌─────────────────────────────────────────────────────────┐ │ list 内存布局 │ ├─────────────────────────────────────────────────────────┤ │ │ │ PyListObject 结构 │ │ ┌──────────────────────────────────────────┐ │ │ │ ob_refcnt (引用计数) │ │ │ │ ob_type (类型指针) │ │ │ │ ob_size (元素数量) │ │ │ │ allocated (分配的容量) │ │ │ │ *items (指向元素数组的指针) │ │ │ └──────────────────────────────────────────┘ │ │ ↓ │ │ ┌──────────────────────────────────────────┐ │ │ │ [item0][item1][item2][item3][ ][ ]... │ │ │ │ ↑ ↑ │ │ │ │ ob_size2 allocated8 │ │ │ └──────────────────────────────────────────┘ │ │ │ │ 过度分配策略 │ │ new_allocated (new_size 3) (3 if new_size 9 else 6) │ │ │ └─────────────────────────────────────────────────────────┘过度分配策略# CPython 源码中的增长策略# 新容量 当前大小 (当前大小 3) 常数# 大约是 1.125 倍增长# 实际容量增长序列# 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...append 的摊销复杂度┌─────────────────────────────────────────────────────────┐ │ append 操作分析 │ ├─────────────────────────────────────────────────────────┤ │ │ │ 情况 1: 有剩余空间 │ │ ┌─────────────────────────────────┐ │ │ │ [A][B][C][D][ ][ ][ ][ ] │ │ │ │ ↑ │ │ │ │ append(E) │ │ │ │ 操作直接放入O(1) │ │ │ └─────────────────────────────────┘ │ │ │ │ 情况 2: 需要扩容 │ │ ┌─────────────────────────────────┐ │ │ │ [A][B][C][D][E][F][G][H] │ 满了 │ │ │ ↓ │ │ │ │ 1. 分配新数组 (1.125 倍) │ │ │ │ 2. 复制所有元素 │ │ │ │ 3. 添加新元素 │ │ │ │ 操作O(n), 但摊销后 O(1) │ │ │ └─────────────────────────────────┘ │ │ │ └─────────────────────────────────────────────────────────┘list 的内存布局// CPython 源码 (Include/cpython/listobject.h)typedefstruct{PyObject_VAR_HEAD// ob_refcnt, ob_type, ob_sizePyObject**ob_item;// 指向元素数组Py_ssize_t allocated;// 分配的容量}PyListObject;查看 list 内部信息importsys lst[1,2,3]print(flist 对象大小{sys.getsizeof(lst)})print(f元素数量{len(lst)})# 计算容量通过添加元素测试test_list[]foriinrange(1000):size_beforesys.getsizeof(test_list)test_list.append(i)size_aftersys.getsizeof(test_list)ifsize_after!size_before:print(f添加第{i}个元素时扩容{size_before}→{size_after})4.2 dict (哈希表)哈希表实现Python 3.6 的紧凑 dict┌─────────────────────────────────────────────────────────┐ │ Python 3.6 dict 结构 │ ├─────────────────────────────────────────────────────────┤ │ │ │ 传统 dict (3.5 及之前): │ │ ┌─────────────────────────────────────────┐ │ │ │ [hash1, key1, value1] │ │ │ │ [hash2, key2, value2] │ │ │ │ [hash3, key3, value3] │ │ │ │ ... (稀疏浪费空间) │ │ │ └─────────────────────────────────────────┘ │ │ │ │ 紧凑 dict (3.6): │ │ ┌─────────────────────────────────────────┐ │ │ │ indices (索引数组) │ │ │ │ [2, 0, 1, -1, -1, ...] │ │ │ └─────────────────────────────────────────┘ │ │ ↓ │ │ ┌─────────────────────────────────────────┐ │ │ │ entries (紧凑数组) │ │ │ │ ┌─────────────────────────────────┐ │ │ │ │ │ [hash0, key0, value0] │ │ │ │ │ │ [hash1, key1, value1] │ │ │ │ │ │ [hash2, key2, value2] │ │ │ │ │ └─────────────────────────────────┘ │ │ │ └─────────────────────────────────────────┘ │ │ │ │ 优势 │ │ - 节省 20-25% 内存 │ │ - 保持插入顺序 │ │ - 迭代更快 │ │ │ └─────────────────────────────────────────────────────────┘哈希冲突解决开放寻址法# 伪代码展示查找过程defdict_lookup(key):hash_valuehash(key)indexhash_valuemask# mask size - 1whileTrue:entrytable[index]ifentryisEMPTY:returnNOT_FOUNDifentry.keykey:returnentry.value# 冲突使用扰动函数找下一个位置indexperturb(index,hash_value)dict 结构// CPython 源码 (Include/cpython/dictobject.h)typedefstruct{PyObject_HEAD Py_ssize_t ma_used;// 使用中的条目数Py_ssize_t ma_version;// 版本号用于迭代检查PyDictKey*ma_keys;// 键数组PyObject**ma_values;// 值数组}PyDictObject;哈希冲突解决┌─────────────────────────────────────────────────────────┐ │ 哈希冲突解决示例 │ ├─────────────────────────────────────────────────────────┤ │ │ │ 假设hash(apple) % 8 3 │ │ hash(orange) % 8 3 (冲突!) │ │ │ │ 使用扰动函数找新位置 │ │ perturb perturb 5 | perturb * 0x9e3779b9 │ │ │ │ 索引表 │ │ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ │ │ │ │ │ 0 │ │ │ 1 │ │ │ │ │ │ │ │↑ │ │ │↑ │ │ │ │ │ │ │ ││ │ │ ││ │ │ │ │ │ │ │ │apple │ │orange │ │ │ └───┴───┴───┴───┴───┴───┴───┴───┘ │ │ │ │ apple 在位置 3 │ │ orange 冲突扰动后放到位置 6 │ │ │ └─────────────────────────────────────────────────────────┘4.3 set 和 tupleset 的哈希表实现set 与 dict 的关系# set 本质上是只有 key 的 dictmy_set{1,2,3}# 内部实现类似# {1: None, 2: None, 3: None}set 的特性无序Python 3.7 保持插入顺序用于迭代但不保证元素必须可哈希成员测试 O(1)# set 的内存效率importsys lst[1,2,3,4,5]st{1,2,3,4,5}print(flist 大小{sys.getsizeof(lst)})print(fset 大小{sys.getsizeof(st)})# set 通常比 list 大因为有哈希表开销tuple 的不可变性tuple 结构// CPython 源码typedefstruct{PyObject_VAR_HEAD PyObject*ob_item[1];// 变长数组}PyTupleObject;不可变性的优势┌─────────────────────────────────────────────────────────┐ │ tuple vs list │ ├─────────────────────────────────────────────────────────┤ │ │ │ tuple (不可变): │ │ - 内存紧凑不需要额外空间用于增长 │ │ - 可哈希可用作 dict 的 key │ │ - 创建更快 │ │ - 线程安全不需要锁 │ │ │ │ list (可变): │ │ - 需要过度分配 │ │ - 不可哈希 │ │ - 支持增删改 │ │ - 更灵活 │ │ │ │ 性能对比 │ │ - tuple 创建比 list 快约 30% │ │ - tuple 迭代略快 │ │ - tuple 内存占用更小 │ │ │ └─────────────────────────────────────────────────────────┘4.4 实践对比不同数据结构的性能实验代码# examples/chapter-04/data_structure_performance.pyimportsysimporttimeitimportrandomprint(*70)print(Python 数据结构性能对比实验)print(*70)# 1. 内存对比 print(\n【实验 1】内存占用对比)print(-*50)sizes[100,1000,10000]forninsizes:datalist(range(n))lstlist(data)tpltuple(data)stset(data)dct{i:iforiindata}print(f\nn {n}:)print(f list:{sys.getsizeof(lst):8}bytes)print(f tuple:{sys.getsizeof(tpl):8}bytes)print(f set:{sys.getsizeof(st):8}bytes)print(f dict:{sys.getsizeof(dct):8}bytes)# 2. 查找性能 print(\n【实验 2】查找性能对比 (10000 次查找))print(-*50)n10000datalist(range(n))search_targets[random.randint(0,n-1)for_inrange(10000)]lstdata stset(data)dct{i:iforiindata}# list 查找time_listtimeit.timeit(lambda:[xforxinsearch_targetsifxinlst],number1)# set 查找time_settimeit.timeit(lambda:[xforxinsearch_targetsifxinst],number1)# dict 查找time_dicttimeit.timeit(lambda:[dct[x]forxinsearch_targetsifxindct],number1)print(f list:{time_list*1000:8.2f}ms (O(n) 查找))print(f set:{time_set*1000:8.2f}ms (O(1) 查找))print(f dict:{time_dict*1000:8.2f}ms (O(1) 查找))print(f 加速比set 比 list 快{time_list/time_set:.0f}x)# 3. append 性能 print(\n【实验 3】append 性能对比 (追加 10000 个元素))print(-*50)time_list_appendtimeit.timeit(lambda:[lst:[]][lst.append(i)foriinrange(10000)],number10)/10print(f list.append:{time_list_append*1000:8.2f}ms)print(f 平均每次 append:{time_list_append*1000/10000:.4f}ms)# 4. 创建性能 print(\n【实验 4】创建性能对比)print(-*50)time_list_createtimeit.timeit(lambda:list(range(10000)),number100)time_tuple_createtimeit.timeit(lambda:tuple(range(10000)),number100)time_set_createtimeit.timeit(lambda:set(range(10000)),number100)time_dict_createtimeit.timeit(lambda:{i:iforiinrange(10000)},number100)print(f list:{time_list_create*10:8.2f}ms)print(f tuple:{time_tuple_create*10:8.2f}ms (快{time_list_create/time_tuple_create:.2f}x))print(f set:{time_set_create*10:8.2f}ms)print(f dict:{time_dict_create*10:8.2f}ms)# 5. 迭代性能 print(\n【实验 5】迭代性能对比 (遍历 10000 个元素))print(-*50)n10000lstlist(range(n))tpltuple(range(n))stset(range(n))time_list_itertimeit.timeit(lambda:sum(lst),number100)time_tuple_itertimeit.timeit(lambda:sum(tpl),number100)time_set_itertimeit.timeit(lambda:sum(st),number100)print(f list:{time_list_iter*10:8.2f}ms)print(f tuple:{time_tuple_iter*10:8.2f}ms)print(f set:{time_set_iter*10:8.2f}ms)# 6. dict 扩容测试 print(\n【实验 6】dict 扩容观察)print(-*50)d{}prev_sizesys.getsizeof(d)foriinrange(1000):d[i]i curr_sizesys.getsizeof(d)ifcurr_size!prev_size:print(f 插入第{i}个元素时扩容{prev_size}→{curr_size}bytes)prev_sizecurr_size实验练习练习 1观察 list 扩容行为importsysdefobserve_list_growth():观察 list 的过度分配lst[]prev_sizesys.getsizeof(lst)prev_capacity0foriinrange(100):lst.append(i)curr_sizesys.getsizeof(lst)ifcurr_size!prev_size:# 估算容量每个指针 8 字节curr_capacity(curr_size-56)//8print(f长度{i1:3}| 大小{curr_size:4}| f容量≈{curr_capacity:3}| 利用率{100*(i1)/curr_capacity:.1f}%)prev_sizecurr_size observe_list_growth()练习 2测试哈希冲突对性能的影响importtimeit# 创建一个有哈希冲突的场景classBadHash:所有对象哈希值相同def__init__(self,val):self.valvaldef__hash__(self):return42# 故意返回相同值def__eq__(self,other):returnisinstance(other,BadHash)andself.valother.val# 创建 dictbad_dict{BadHash(i):iforiinrange(1000)}normal_dict{i:iforiinrange(1000)}# 测试查找性能bad_timetimeit.timeit(lambda:sum(bad_dict.get(BadHash(500),0)),number1000)normal_timetimeit.timeit(lambda:sum(normal_dict.get(500,0)),number1000)print(f哈希冲突 dict:{bad_time*1000:.2f}ms)print(f正常 dict:{normal_time*1000:.2f}ms)print(f性能下降{bad_time/normal_time:.1f}x)练习 3比较不同大小 dict 的内存效率importsysdefdict_memory_efficiency():测试 dict 的内存效率sizes[10,100,1000,10000]print(dict 内存效率分析:)print(大小\tdict 大小\t每条目\t负载因子)print(-*50)forninsizes:d{i:iforiinrange(n)}sizesys.getsizeof(d)per_itemsize/n# 估算容量简化# 实际需要使用更复杂的方法print(f{n}\t{size}\t{per_item:.1f}\t-)dict_memory_efficiency()常见问题Q1: 为什么 list 查询是 O(n) 而 dict 是 O(1)A:list 是数组需要线性搜索dict 是哈希表通过哈希函数直接计算位置# list: 需要遍历5in[1,2,3,4,5]# 最坏检查所有元素# dict: 直接计算位置5in{1,2,3,4,5}# 计算 hash(5)直接访问Q2: 为什么 tuple 比 list 快A:tuple 不需要过度分配tuple 不需要检查可变性tuple 内存布局更紧凑tuple 可以被优化如常量折叠Q3: dict 保持顺序是从哪个版本开始的A:Python 3.6: CPython 实现细节Python 3.7: 语言规范保证Q4: 如何选择使用 list 还是 tupleA:# 使用 tuple 当-数据不应该改变-用作dict的 key-需要哈希-性能敏感# 使用 list 当-需要增删元素-需要排序-需要切片赋值Q5: set 和 dict 的哈希表实现有什么区别A:set 只存储 key类似 dict 的 keysdict 存储 key-value 对底层哈希算法相同set 的 value 是固定的存在性本章小结list 是过度分配的动态数组append 摊销 O(1)dict 在 3.6 使用紧凑布局节省内存并保持顺序哈希表使用开放寻址法解决冲突set 是只有 key 的哈希表tuple 是不可变数组更紧凑更高效选择合适的数据结构对性能至关重要下一章预告第 5 章将深入探讨字符串与编码包括 Unicode、UTF-8 和字符串驻留机制。