第4章：数据结构选择——列表与元组、字典与集合、队列与栈、堆与优先队列

数据结构选对了，性能问题就解决了一半。这话我常跟团队里的新人讲。

很多人写Python，上来就是列表一把梭。能跑，但跑得慢。你想想看，一个列表里塞几万条数据，查找时挨个遍历，那效率能高吗？

这一章，我把Python里最常用的几组数据结构掰开揉碎了讲。咱们从底层实现聊到实战选型，帮你建立一套「看到场景就能选对结构」的本能反应。

4.1 列表 vs 元组：可变与不可变的博弈

列表和元组，长得像，脾气完全不同。

列表是动态数组，可以增删改。元组是固定序列，一旦创建就不能变。

我个人的习惯是：能用元组就别用列表。为什么？

• 内存占用：元组更小。Python为了支持列表的动态扩容，会预分配额外内存。元组不需要，所以省空间。
• 创建速度：元组比列表快5-10倍。不信你试试：timeit.timeit('()') 和 timeit.timeit('[]')。
• 哈希能力：元组可以当字典的键，列表不行。因为元组不可变，可哈希。

我在项目中遇到过一个问题：一个配置项列表，里面存了上千个IP地址。一开始用的列表，后来发现每次启动都要花几百毫秒去解析。改成元组后，启动时间直接砍半。嗯，就是省掉了动态扩容的开销。

避坑指南：列表的浅拷贝陷阱

4.2 字典 vs 集合：哈希表的两副面孔

字典和集合，底层都是哈希表。区别在于：字典存键值对，集合只存键。

哈希表的查找时间复杂度是 O(1)，这是它们最大的优势。但要注意，哈希表不是万能的。

操作	列表	字典/集合
查找元素	O(n)	O(1)
插入元素	O(1) 尾部 / O(n) 中间	O(1) 平均
删除元素	O(n)	O(1) 平均
内存占用	低	高（哈希表有额外开销）

说白了，如果你只需要判断「在不在」，用集合。如果你需要「根据键找值」，用字典。

我建议：去重操作优先用集合。很多人写 list(set(data)) 觉得多此一举，其实这比手动遍历去重要快一个数量级。

字典的默认值技巧

4.3 队列与栈：顺序就是一切

队列是先进先出（FIFO），栈是后进先出（LIFO）。

Python里，列表可以模拟栈：append() 入栈，pop() 出栈。但模拟队列就不行了，因为 pop(0) 是 O(n) 操作，每次都要移动所有元素。

我在项目中遇到过：一个消息处理系统，用列表当队列，处理10万条消息时，性能直接崩了。换成 collections.deque 后，处理速度提升了30倍。

deque 的妙用

deque 是双端队列，两端插入删除都是 O(1)。我常用它来实现滑动窗口、缓存淘汰（LRU）等场景。

from collections import deque

# 固定大小的滑动窗口
window = deque(maxlen=5)
for num in [1, 3, 5, 7, 9, 2, 4]:
    window.append(num)
    print(list(window))
# 输出：[1,3,5,7,9] → [3,5,7,9,2] → [5,7,9,2,4]

4.4 堆与优先队列：谁是最小（大）的那个

堆是一种特殊的树形数据结构。Python 的 heapq 模块实现的是最小堆。

堆的核心操作：

• heapq.heappush(heap, item)：插入元素，O(log n)
• heapq.heappop(heap)：弹出最小元素，O(log n)
• heapq.heapify(list)：将列表转为堆，O(n)

你想想看，如果要从100万个元素里找出最大的10个，用排序是 O(n log n)，用堆是 O(n log k)，k=10。差距有多大？

我曾经写一个实时排行榜系统，用户分数不断更新，需要快速获取前100名。用列表排序的话，每次更新都要全量排序，扛不住。换成堆后，每次只维护一个大小为100的堆，性能提升了两个数量级。

优先队列的实现

Python 的 queue.PriorityQueue 底层就是堆，但加了线程安全。单线程场景直接用 heapq 更轻量。

import heapq

class PriorityQueue:
    def __init__(self):
        self._heap = []
    
    def push(self, item, priority):
        heapq.heappush(self._heap, (priority, item))
    
    def pop(self):
        return heapq.heappop(self._heap)[1]

知识体系总览

下面这张图，帮你把本章的核心逻辑串起来：

---