选择排序微优化后计时结果不符预期，寻求技术分析

核心原因 #

Python对内置方法的属性访问已经做了深度优化，你做的微优化（把append/pop赋值给局部变量）带来的收益，完全被绑定方法调用的额外间接开销抵消了，甚至在中小数据量下会拖慢速度。

具体分析 #

1. 内置方法的访问优化：
   直接调用newArr.append()时，Python解释器会通过LOAD_METHOD字节码直接定位到列表的内置append方法，这个过程经过了专门优化，速度极快。而把na = newArr.append赋值给局部变量后，na是一个绑定方法对象，调用na()时需要额外处理self参数的传递，反而多了一层间接调用的开销。

2. 数据量的影响：
   你测试的10000元素属于中小规模，微优化的收益（减少属性查找次数）在这个量级下完全可以忽略，反而被方法调用的额外开销盖过。只有当循环次数达到百万级以上时，这种微优化才可能体现出微弱优势，但前提是没有其他更显著的开销（比如你的代码中arr.pop()的O(n)操作）。

3. 算法本身的低效：
   你的选择排序实现存在根本性的效率问题：每次arr.pop(smallest)需要移动列表中从smallest位置到末尾的所有元素，这是O(n)操作。加上findSmallest的O(n)循环，整体时间复杂度是O(n²)，且常数项极大。这种情况下，微优化的影响远不如算法本身的低效明显。

验证与改进 #

1. 字节码对比：
   用dis模块查看字节码可以直观看到差异：

   • 对于selectionSort1中的newArr.append(arr.pop(smallest))，关键字节码是：

     LOAD_FAST                1 (newArr)
     LOAD_METHOD              0 (append)
     LOAD_FAST                0 (arr)
     LOAD_METHOD              1 (pop)
     LOAD_FAST                2 (smallest)
     CALL_METHOD              1
     CALL_METHOD              1
     

   • 对于selectionSort2中的na(arr.pop(smallest))，关键字节码是：

     LOAD_FAST                2 (na)
     LOAD_FAST                0 (arr)
     LOAD_METHOD              0 (pop)
     LOAD_FAST                3 (smallest)
     CALL_METHOD              1
     CALL_FAST                1
     

   现代Python中LOAD_METHOD + CALL_METHOD的组合针对实例方法做了专门优化，效率比调用局部变量绑定方法的CALL_FAST更高。

2. 更高效的选择排序实现：
   改成原地排序的版本，避免pop操作的O(n)开销，效率会提升一个量级：

   def selectionSortInPlace(arr):
       n = len(arr)
       for i in range(n):
           min_idx = i
           # 找到未排序部分的最小值索引
           for j in range(i + 1, n):
               if arr[j] < arr[min_idx]:
                   min_idx = j
           # 交换当前位置和最小值位置的元素
           arr[i], arr[min_idx] = arr[min_idx], arr[i]
       return arr
   

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