列表推导式比for循环快3倍——list/dict/set底层原理

list的底层——动态数组

# list底层是一个C语言的动态数组（PyObject*指针数组）
# 存储的是对象的引用（指针），不是对象本身
 
nums = [1, 2, 3, 4, 5]
# 内存布局：[ptr1, ptr2, ptr3, ptr4, ptr5, _, _, _]
# 每个ptr指向一个Python int对象
# 预分配了额外空间（_），用于append时不频繁扩容
 
# 时间复杂度：
# 随机访问 nums[i]: O(1)（指针数组直接索引）
# append: O(1)均摊（偶尔扩容是O(N)）
# insert(0, x): O(N)（所有元素后移）
# x in nums: O(N)（线性查找！）
# 删除 remove(x): O(N)
 
# 扩容策略：约1.125倍（比Java ArrayList的1.5倍更保守）
# 8个元素时预分配到8+8//8+6=9个位置

dict的底层——哈希表

# dict底层是开放地址法的哈希表
# CPython 3.6+保证了插入顺序（实现细节变成了语言规范3.7+）
 
user = {'name': 'Wood', 'age': 30, 'city': 'Shanghai'}
 
# 内部结构（CPython 3.6+优化后）：
# 索引表（紧凑数组）: [_, 0, _, 2, 1, _, _, _]
# 数据表（有序数组）: [(hash, 'name', 'Wood'),
#                     (hash, 'age', 30),
#                     (hash, 'city', 'Shanghai')]
 
# 时间复杂度：
# 查找 user['name']: O(1)（hash定位）
# 插入 user['x'] = y: O(1)
# 删除 del user['x']: O(1)
# 遍历: O(N)（按插入顺序）
 
# dict比list的查找快100倍！
# 100万个元素：list查找约50ms，dict查找约0.05ms

set的底层——无值的哈希表

# set底层和dict几乎一样（哈希表），只是没有value
# 所以set的查找也是O(1)
 
unique_ids = {1001, 1002, 1003, 1004}
 
# set的核心用途：
# 1. 去重
unique = set(id_list)  # 比用list去重快100倍
 
# 2. 成员判断（in操作）
if user_id in blocked_set:  # O(1)
    pass
# vs
if user_id in blocked_list:  # O(N) 慢！
    pass
 
# 3. 集合运算（交集/并集/差集）
common = set_a & set_b      # 交集
all_users = set_a | set_b   # 并集
new_users = set_a - set_b   # 差集

列表推导式为什么比for循环快？

# for循环（慢）
result = []
for x in range(1000000):
    if x % 2 == 0:
        result.append(x * 2)
# 耗时约120ms
 
# 列表推导式（快3倍）
result = [x * 2 for x in range(1000000) if x % 2 == 0]
# 耗时约40ms
 
# 为什么快？
# 1. 列表推导式在CPython内部有专门的字节码优化
#    不需要每次循环都查找append方法
# 2. 减少了Python字节码的LOAD/STORE指令数量
# 3. 内存预分配更智能（知道大概要生成多少元素）
 
# 字典推导式和集合推导式也一样快
d = {k: v for k, v in pairs}
s = {x for x in data if x > 0}