求解Project Euler第43题时，为何遍历362万次的for循环运行极快？

我在求解Project Euler第43题时写了一段Python代码，遍历0-9的所有10位全排列（共3628800次）并完成多组整除校验，却仅耗时1.34秒，完全超出预期，想知道原因。

代码实现 #

from itertools import permutations
def main():
    numbers1_9 = [0,1,2,3,4,5,6,7,8,9]
    list_of_all_permutations = list(permutations(numbers1_9, 10))
    length_of_my_list = len(list_of_all_permutations)
    number_of_times_it_ran=0
    result = []
    for n in list_of_all_permutations:
        number_of_times_it_ran+=1
        if n[0] == 0:
            continue
        elif n[3] % 2 == 0 and (n[2]+n[3]+n[4]) % 3 == 0 and n[5] % 5 ==0 and int(str(n[4])+str(n[5])+str(n[6])) % 7 == 0 and (n[5]+n[7]-n[6]) % 11 == 0 and int(str(n[6])+str(n[7])+str(n[8])) % 13 == 0 and int(str(n[7])+str(n[8])+str(n[9])) % 17 == 0:
            temp_list = []
            for digits_of_n in n:
                temp_list.append(str(digits_of_n))
            result.append(int("".join(temp_list)))
            print(f"Added {temp_list}, Remaining: {length_of_my_list-number_of_times_it_ran}")
    print(f"The code ran {number_of_times_it_ran} times and the result is {sum(result)}")

if __name__ == "__main__":
    main()

运行结果 #

Added ['1', '4', '0', '6', '3', '5', '7', '2', '8', '9'], Remaining: 3142649
Added ['1', '4', '3', '0', '9', '5', '2', '8', '6', '7'], Remaining: 3134251
Added ['1', '4', '6', '0', '3', '5', '7', '2', '8', '9'], Remaining: 3124649
Added ['4', '1', '0', '6', '3', '5', '7', '2', '8', '9'], Remaining: 2134649
Added ['4', '1', '3', '0', '9', '5', '2', '8', '6', '7'], Remaining: 2126251
Added ['4', '1', '6', '0', '3', '5', '7', '2', '8', '9'], Remaining: 2116649
The code ran 3628800 times, and the result is 16695334890

速度快的核心原因 #

• itertools.permutations是C底层实现：Python标准库的permutations不是纯Python代码编写，而是基于C实现的，生成全排列的速度比手动用Python实现快几个数量级，这是性能的基础保障。
• 短路求值大幅减少计算量：用and连接的校验条件会从左到右依次判断，只要有一个条件不满足就直接终止后续判断：
  • 首字符为0的排列直接跳过，筛掉1/10的循环（约36万次）；
  • n[3]%2==0又筛掉一半不符合条件的排列；
  • n[5]%5==0再筛掉80%的剩余排列；
    经过前几步筛选后，真正需要执行后续复杂判断的循环次数已经极少。
• 核心操作都是高效整数运算：循环内的大部分校验是简单的整数取模、加减运算，这些操作在Python底层经过高度优化，执行速度极快。只有极少数符合所有条件的排列才会执行字符串拼接和转整数的操作，这部分开销可以忽略。
• 循环逻辑简单无冗余：整个循环仅涉及元组索引访问、基础算术运算，没有复杂的数据结构操作或冗余计算，进一步降低了执行开销。

内容的提问来源于stack exchange，提问作者Mikuláš Borek