Python列表与array对比：insert操作性能差异及相关疑问

问题描述 #

给定整数数组nums，返回整数数组counts，其中counts[i]是nums[i]右侧比它小的元素数量

两种解法对比 #

性能优异解法（耗时1300毫秒） #

import bisect
import array

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        ns = array.array('h')
        # ns = list()
        ans = [0] * len(nums)
        for i in range(len(nums) - 1, -1, -1):
            x = nums[i]
            l = bisect.bisect_left(ns, x)
            ans[i] = l
            ns.insert(l, x)
        return ans 

性能较差解法（耗时5000毫秒） #

import bisect
import array

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        # ns = array.array('h')
        ns = list()
        ans = [0] * len(nums)
        for i in range(len(nums) - 1, -1, -1):
            x = nums[i]
            l = bisect.bisect_left(ns, x)
            ans[i] = l
            ns.insert(l, x)
        return ans 

两者唯一区别在于：前者使用array.array('h')存储元素，后者使用Python内置列表list()。

我的疑问与认知 #

我认为如果重复执行的是.insert操作，Python array静态存储的优势无法体现，每次插入都需要重新分配空间（是否正确？）。至少列表是动态分配的，性能至少应该和array持平。

问题解答 #

1. 该算法的时间复杂度是O(n²)吗？因为我要对nums中的每个元素执行一次insert操作
   是的，这个算法的时间复杂度确实是O(n²)。因为insert操作需要将插入位置后的所有元素向后移动，单次insert的时间复杂度为O(k)（k为当前容器的元素数量）。遍历n个元素的过程中，总操作次数为1+2+...+n = n(n+1)/2，属于O(n²)级别。

2. 性能提升仅因为array指定了dtype导致索引更快？还是有其他原因？
   性能提升主要来自两点：

• 更高的内存密度：array.array('h')存储的是16位整数，每个元素仅占2字节；而Python列表存储的是对象指针（64位系统下每个指针占8字节）。相同元素数量下，array占用内存远小于列表，缓存命中率更高，内存访问速度更快。
• 类型一致性优化：array中元素类型统一，底层操作无需处理对象的类型检查、引用计数等额外开销，无论是bisect_left的二分查找还是insert的元素移动，效率都比列表更高。
  索引更快只是表象，核心是内存布局和类型统一带来的整体性能提升。

3. 纠正错误认知
   你的核心错误在于对Python array存储特性的理解：

• Python array不是静态存储容器，它和列表一样是动态扩容的，当空间不足时会重新分配内存。但由于存储的是原生数据而非对象指针，扩容时的内存复制成本更低（直接复制原始数据，而非对象指针）。
• 列表的动态分配并没有性能优势，反而因为存储对象的额外开销，在元素移动、内存访问上都不如array高效。即使是insert操作，array的元素移动是原生数据的批量拷贝，比列表移动对象指针的操作更快。

内容的提问来源于stack exchange，提问作者figs_and_nuts