17370845950

Python列表是底层用C实现的动态数组，以指针数组存储对象引用，其性能由扩容机制、引用特性、内存连续性共同决定：append均摊O(1)但单次可能O(n)，索引访问O(1)而中间增删平均O(n)，存储开销固定，遍历缓存友好但对象内存不连续。

Python列表不是简单的数组，而是一个动态数组（Dynamic Array），底层用C语言实现，内部维护一个指针数组，指向实际存储的Python对象。它的性能表现和内存布局直接取决于这个设计——扩容机制、对象引用、内存连续性共同决定了增删查改的快慢。

扩容机制：时间复杂度不总是O(1)

列表在追加元素（append）时，如果当前空间已满，会触发扩容：分配一块更大的连续内存，把原有元素复制过去。CPython中采用“乘数增长”策略（约1.125倍），保证均摊时间复杂度为O(1)。但单次append可能因复制引发O(n)开销，尤其在反复小步扩容时（如从1扩到2、再到3……）更明显。

• 避免循环中逐个append大量数据；可预先估算长度，用[None] * n初始化，再按索引赋值
• list.extend()比多次append更高效——它一次计算所需总容量，减少中间扩容次数
• 用sys.getsizeof()可观察实际分配内存大小，比如len(lst)=100时，getsizeof(lst)常显示容纳128个指针的空间

索引访问快，但“中间插入/删除”代价高

因为底层是连续内存的指针数组，按索引读写（lst[i]）是纯O(1)操作；但insert(i, x)或pop(i)（i不是末尾）需移动i之后所有指针，平均O(n)。例如在万级列表开头插入一个元素，要平移上万个指针。

• 优先用append() / pop()（末尾操作），它们是真正的O(1)
• 若需频繁首尾增删，改用collections.deque——基于双向链表，首尾操作均为O(1)
• 删除多个元素时，避免循环调用remove()；可用列表推导式重建：new_lst = [x for x in lst if not condition(x)]

存储的是对象引用，不是值本身

列表不保存整数、字符串等实际数据，只保存指向这些对象的指针（8字节/指针，64位系统）。这意味着：

• 无论存int还是大型dict，列表本身内存开销几乎一样（只差指针大小）
• 修改列表内可变对象（如lst[0].append(1)）不会改变列表结构，无额外开销
• 但浅拷贝（lst.copy()或lst[:]）只复制指针，新旧列表共享内部对象；深拷贝才真正复制内容，代价高

内存局部性好，但碎片化不可控

指针数组连续，CPU缓存友好，遍历速度很快。但Python对象本身分散在堆内存各处——比如列表存了1000个独立创建的字典，这些字典内存不连续，遍历时缓存命中率低。

• 对性能敏感场景（如数值计算），避免用list存大量同构小对象；改用array.array（基础类型）或numpy.ndarray（连续内存+向量化）
• 用__sizeof__() + sys.getsizeof(obj)组合可估算真实内存占用，区分“容器开销”和“内容开销”
• 列表过早释放（如函数返回后不再引用）能及时触发GC回收，但无法控制对象何时被销毁，也不保证立即归还物理内存

理解这四点，就能预判列表操作的真实成本，而不是凭直觉写代码。不复杂但容易忽略。