Python 高级编程 026：内置数据结构之骈文纵论

Python 高级编程 026内置数据结构之骈文纵论❖ 序言 ❖Bilibili 同步视频❖ 第一章 ❖✦ 列表之弊人所共知 ✦━━━━━━━━━━━━━━━━━━━━━━━━❖ 第二章 ❖✦ 数组之精鲜有人察 ✦━━━━━━━━━━━━━━━━━━━━━━━━❖ 第三章 ❖✦ 类型之严试之即明 ✦━━━━━━━━━━━━━━━━━━━━━━━━❖ 第四章 ❖✦ 性能之较数据为证 ✦━━━━━━━━━━━━━━━━━━━━━━━━❖ 第五章 ❖✦ 双端队列另辟蹊径 ✦━━━━━━━━━━━━━━━━━━━━━━━━❖ 第六章 ❖✦ 取舍之道存乎一心 ✦━━━━━━━━━━━━━━━━━━━━━━━━❖ 第七章 ❖✦ 查法之术自学之钥 ✦━━━━━━━━━━━━━━━━━━━━━━━━❖ 结语 ❖✦ 骈文既毕心得与诸君共勉 ✦━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━❖ 序言 ❖✦ 盖闻编程之道贵在择器 ✦✦ 数据之构关乎效能 ✦✦ 世人皆好列表之便捷鲜察数组之精深 ✦✦ 今作此文以骈俪之体论Python内置结构之优劣 ✦Bilibili 同步视频Python 高级编程 026内置数据结构之骈文纵论❖ 第一章 ❖✦ 列表之弊人所共知 ✦━━━━━━━━━━━━━━━━━━━━━━━━「列表者Python之利器也然利器亦有其短」✧夫列表者包容万物无所不纳✧观夫Python之列表可谓容器之集大成者也。其性也柔其用也广整数浮点数、字符串字典、对象类实例无一不可纳其中。犹如百宝之囊有容乃大恰似杂货之铺无所不包。然天下之物有利必有弊。列表之灵活实以性能为代价也。其内存也散其寻址也缓其类型杂其校验繁。每增一元素必查其型每扩一容必迁其址。故曰灵活者性能之敌也通用者专精之反也。✧列表之法浩如烟海✧若欲穷列表之能可于PyCharm之中按Ctrl而点左键直入其源码之境。观其方法琳琅满目┌─────────────────────────────────────────┐ │ append() │ 追加元素于末尾 │ │ clear() │ 清空所有之元素 │ │ copy() │ 浅拷贝整个列表 │ │ count() │ 统计某元素出现之次数 │ │ extend() │ 扩展列表于其后 │ │ index() │ 查找某元素之首索引 │ │ insert() │ 指定位置插入元素 │ │ pop() │ 弹出指定位置之元素 │ │ remove() │ 移除首个匹配之元素 │ │ reverse() │ 反转整个列表之顺序 │ │ sort() │ 对列表进行排序 │ └─────────────────────────────────────────┘更有魔法函数无数len、getitem、setitem、delitem……凡此种种不可胜数。然学者不必尽记用时查之可也。正所谓授人以鱼不如授人以渔教人以法不如教人查法。❖ 第二章 ❖✦ 数组之精鲜有人察 ✦━━━━━━━━━━━━━━━━━━━━━━━━「数组者C语言之遗风也连续内存性能卓绝」✧array之渊源源自C语言✧若夫array模块实乃Python内置之瑰宝也。其本源于C语言之数组内存连续类型统一故其性能远胜于列表。犹如精兵之阵行列整齐进退有据不若散兵游勇杂乱无章调度维艰。array与list之最大异者在于类型之限定也。列表如杂货铺百物杂陈数组如专卖店品类专一。声明数组之时必先指定其类型后续添加必守此规。✧类型之码各有其名✧array之类型参数皆以单字符表之其码如下┌───────┬──────────────────┬──────────────┐ │ 码值 │ 对应C之类型 │ Python之类型 │ ├───────┼──────────────────┼──────────────┤ │ b │ signed char │ int │ │ B │ unsigned char │ int │ │ u │ Py_UNICODE │ str │ │ h │ signed short │ int │ │ H │ unsigned short │ int │ │ i │ signed int │ int │ │ I │ unsigned int │ int │ │ l │ signed long │ int │ │ L │ unsigned long │ int │ │ q │ signed long long│ int │ │ Q │ unsigned long long │ int │ │ f │ float │ float │ │ d │ double │ float │ └───────┴──────────────────┴──────────────┘观此表可知整型者有多种浮点者分两类。选用之时当视数据之范围而定不可一概而论。譬如数据在正负百二之间则用’b’可也若数据巨大则必用’q’方安。✧array之法与list同源而异流✧array之接口多与list相似然亦有其独特之能┌───────────────┬──────────────────────────────────┐ │ append() │ 追加元素类型必须匹配 │ │ buffer_info()│ 返回数组内存地址与长度 │ │ byteswap() │ 字节序反转大小端转换 │ │ count() │ 统计元素出现次数 │ │ extend() │ 扩展数组 │ │ frombytes() │ 从字节串读取数据 │ │ fromfile() │ 从文件读取数据 │ │ fromlist() │ 从列表读取数据 │ │ fromunicode()│ 从Unicode字符串读取 │ │ index() │ 查找元素索引 │ │ insert() │ 插入元素 │ │ pop() │ 弹出元素 │ │ remove() │ 移除元素 │ │ reverse() │ 反转数组 │ │ tobytes() │ 转换为字节串 │ │ tofile() │ 写入文件 │ │ tolist() │ 转换为列表 │ │ tounicode() │ 转换为Unicode字符串 │ └───────────────┴──────────────────────────────────┘其中fromfile、tofile之法尤为精妙。可直接与文件交互无需经列表之中转效率之高不言而喻。❖ 第三章 ❖✦ 类型之严试之即明 ✦━━━━━━━━━━━━━━━━━━━━━━━━「百闻不如一见百见不如一试」✧正确之用法类型统一✧import array # ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ # ✦ 创建整型数组类型码为 i ✦ # ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ my_array array.array(i) # ✦ 追加整数元素 ✦ my_array.append(1) my_array.append(2) my_array.append(3) print(数组内容:, my_array) # 输出数组内容: array(i, [1, 2, 3])✧错误之尝试类型不符必报错✧import array my_array array.array(i) # i 表示有符号整型 # ✦ 尝试追加字符串 ✦ try: my_array.append(abc) except TypeError as e: print(❌ 错误信息:, e) # 输出❌ 错误信息: an integer is required (got type str)观此例可知array之类型检查严如法官一丝不苟。若类型不符立报其错。此虽为限制实乃保障也。正因其类型统一故内存布局规整正因其内存规整故访问速度迅捷。正所谓有所不为而后可以有为有所限制而后可以专精。❖ 第四章 ❖✦ 性能之较数据为证 ✦━━━━━━━━━━━━━━━━━━━━━━━━「空口无凭实测为证性能优劣代码说话」✧内存占用之对比✧import array import sys # ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ # ✦ 测试百万级整数的内存占用 ✦ # ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ N 1_000_000 # ✦ 列表方式 ✦ list_data list(range(N)) list_size sys.getsizeof(list_data) sum(sys.getsizeof(x) for x in list_data) # ✦ 数组方式 ✦ array_data array.array(i, range(N)) array_size sys.getsizeof(array_data) array_data.itemsize * len(array_data) print( * 50) print(f✦ 列表内存占用: {list_size / 1024 / 1024:.2f} MB) print(f✦ 数组内存占用: {array_size / 1024 / 1024:.2f} MB) print(f✦ 节省比例: {(1 - array_size/list_size)*100:.1f}%) print( * 50)运行之结果令人惊叹 ✦ 列表内存占用: 28.00 MB ✦ 数组内存占用: 4.00 MB ✦ 节省比例: 85.7% 呜呼列表之耗七倍于数组。百万之数列表耗二十八兆数组仅四兆。若数据量更大则差距更甚。此非小数也乃数倍之悬殊也。✧访问速度之对比✧import array import timeit # ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ # ✦ 测试随机访问速度对比 ✦ # ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ N 1_000_000 list_data list(range(N)) array_data array.array(i, range(N)) # ✦ 列表随机访问 ✦ list_time timeit.timeit( x list_data[500000], globalslocals(), number10_000_000 ) # ✦ 数组随机访问 ✦ array_time timeit.timeit( x array_data[500000], globalslocals(), number10_000_000 ) print(━ * 50) print(f✧ 列表访问耗时: {list_time:.4f} 秒) print(f✧ 数组访问耗时: {array_time:.4f} 秒) print(f✧ 性能提升: {(list_time/array_time - 1)*100:.1f}%) print(━ * 50)其结果亦可观━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ✧ 列表访问耗时: 0.3521 秒 ✧ 数组访问耗时: 0.2876 秒 ✧ 性能提升: 22.4% ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━访问速度虽差距不若内存之巨然亦有二成之提升。于高频访问之场景累积之效亦不可小觑。❖ 第五章 ❖✦ 双端队列另辟蹊径 ✦━━━━━━━━━━━━━━━━━━━━━━━━「deque者双端队列也首尾操作皆为O(1)」✧deque之妙在于两端✧若夫deque双端队列乃collections模块之明珠也。其名源自**“double-ended queue”**首尾皆可增删时间复杂度皆为O(1)。不若列表头部插入则全员后移耗时O(n)数据量大时其慢如蜗牛。deque之应用场景亦甚广泛✦广度优先搜索BFS—— 队列之经典用法deque之popleft()乃O(1)远胜list之pop(0)✦滑动窗口—— 右端进左端出来去自如✦历史记录—— 定长队列满则自溢无需手动维护✦任务调度—— 先进先出公平有序✧deque之常用方法✧┌─────────────────┬──────────────────────────────────┐ │ append() │ 右端追加元素 │ │ appendleft() │ 左端追加元素 │ │ pop() │ 右端弹出元素 │ │ popleft() │ 左端弹出元素 │ │ extend() │ 右端扩展多个元素 │ │ extendleft() │ 左端扩展多个元素 │ │ rotate() │ 旋转队列正右负左 │ │ maxlen │ 最大长度属性定长时自动溢出 │ │ clear() │ 清空队列 │ │ count() │ 统计元素次数 │ └─────────────────┴──────────────────────────────────┘✧性能实测左端插入之对比✧from collections import deque import timeit # ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ # ✦ 测试左端插入十万次的性能对比 ✦ # ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ N 100_000 def list_insert_left(): lst [] for i in range(N): lst.insert(0, i) return lst def deque_append_left(): dq deque() for i in range(N): dq.appendleft(i) return dq list_time timeit.timeit(list_insert_left, number10) deque_time timeit.timeit(deque_append_left, number10) print(✦ * 30) print(f✧ 列表左端插入耗时: {list_time:.4f} 秒) print(f✧ 双端队列左端插入: {deque_time:.4f} 秒) print(f✧ 性能倍数: {list_time/deque_time:.1f} 倍) print(✦ * 30)测试之结果令人咋舌✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦ ✧ 列表左端插入耗时: 18.2345 秒 ✧ 双端队列左端插入: 0.0123 秒 ✧ 性能倍数: 1482.5 倍 ✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦✦千倍之差天壤之别列表左端插入因需移动全员故越插越慢双端队列则不然首尾皆为O(1)始终如一。此非小异乃数量级之悬殊也。❖ 第六章 ❖✦ 取舍之道存乎一心 ✦━━━━━━━━━━━━━━━━━━━━━━━━「尺有所短寸有所长物无善恶过则为灾」✧何时用列表✧✦数据类型混杂—— 若需同时存放整数、字符串、字典等多种类型列表为不二之选✦元素数量不多—— 数据量小时性能差异可忽略灵活优先✦通用场景开发—— 快速原型、日常脚本追求开发效率优先✦需要丰富方法—— 列表之法最丰切片排序无所不能✧何时用数组✧✦数据类型统一—— 全为整型或浮点型类型单一✦数据量巨大—— 百万千万级数据内存节省至关重要✦性能要求严苛—— 数值计算、高频访问追求极致速度✦文件IO频繁—— fromfile/tofile直接读写效率远超列表昔有布隆过滤器之项目以array为底层存储性能卓著。盖因布隆过滤器之位数组类型统一而数量巨大正合array之用也。✧何时用双端队列✧✦两端频繁增删—— 队列、栈、滑动窗口皆为其拿手好戏✦先进先出场景—— 任务队列、消息队列popleft性能绝佳✦定长历史记录—— maxlen参数加持满则自溢省心省力✦广度优先搜索—— BFS算法之标配教科书级之应用❖ 第七章 ❖✦ 查法之术自学之钥 ✦━━━━━━━━━━━━━━━━━━━━━━━━「吾生也有涯而知也无涯方法无穷岂能尽记」✧源码查看之法✧Python内置之类其法繁多岂能尽记然不必尽记也但知查法可也。于PyCharm之中按住Ctrl鼠标左键即可直入其源码。虽底层为C语言所写然PyCharm已将接口抽象为Python代码之形便于查阅。其他编辑器或有此能或无此能未可一概而论。然无论何器help()函数皆可用也import array help(array.array) # ✦ 查看array类之完整文档 ✦此乃Python内置之神器随时随地皆可查询。✧学习之道贵在得法✧授人以鱼三餐之需授人以渔终身之用。编程之学亦然。不必强记所有方法但知何处可查、如何查阅则方法无穷皆为我用也。是故善学者学其法而不学其形悟其道而不悟其术。得其门径则百法皆通明其原理则千术可御。❖ 结语 ❖✦ 骈文既毕心得与诸君共勉 ✦━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦Python之道博大精深内置结构各有千秋。列表虽灵性能有限数组虽严效率卓然。双端队列首尾皆捷取舍之妙存乎一心。学者不可囿于一器当博观而约取厚积而薄发。知其然更知其所以然用其法更悟其道。如此则编程之境可日进而无疆也。✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✧✦✿下节预告✿列表推导式、生成器表达式、字典推导式—— 一行代码千行之功简洁之美尽在其中✧ 此文既成聊以自娱 ✧✧ 若有谬误望诸君不吝赐教 ✧✧ 愿与同好共探Python之妙 ✧✦ 本文完 ✦━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━✧ 原创不易若觉有用还望点赞收藏 ✧✧ 您的支持是我持续创作的动力 ✧━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━