Python迭代速度10秒后骤降的瓶颈排查及搜索优化求助

问题描述 #

我正在用Python编写代码，想找出在π的前10亿位中未出现的第一个自然数。以下是我的代码：

import datetime
from tqdm import tqdm
def findpi(end):
    notin = []
    stop = 0
    s1 = datetime.datetime.now()
    with open(r"C:\Users\shamm\Desktop\Text Documents\1 BILLION Digits of pi.txt", 'rt') as p:
        pi = str(p.read())
        for i in tqdm(range(1,end+1)):
            if str(i) not in pi:
                if notin == []:
                    stop = i
                notin.append(i)
    s2 = datetime.datetime.now()
    tdelta = s2 - s1
    ts = tdelta.total_seconds()
    return [notin, stop, ts]

pi = findpi(1000000)
print("Not in:", pi[0])
print("Last:", pi[1])
print("Time taken:", pi[2])

小范围测试时代码运行正常，但当我尝试检查前100万个自然数时，代码出现了明显的性能骤降：前10秒以约1万次迭代/秒的速度运行，之后突然降到1千次/秒；当我尝试检查1000万个自然数时，同样前10秒保持1万次/秒，30多分钟后甚至降到100次/秒。

这是因为内存或算力的瓶颈限制，还是我的代码存在问题？

编辑： 看起来问题出在随着数字位数增加，搜索的字符串长度越来越长，导致搜索速度变慢。如何优化这个搜索逻辑，避免随着数字位数增加而速度暴跌？

瓶颈分析 #

你的代码性能暴跌的核心原因是低效的字符串查找逻辑，具体来说：

1. 重复全量搜索：对于每个自然数i，你都要执行str(i) in pi的检查——这个操作本质上是在10亿字符的大字符串中从头开始搜索str(i)，每次搜索的时间复杂度是O(π的长度)，也就是10亿次字符比较。
2. 搜索成本随位数递增：当i是1位数时，搜索短字符串速度较快；但当i变成2位、3位...直到7位（当end=1e6时），搜索长字符串的时间会显著增加——匹配长字符串需要更多的字符对比，导致每次迭代的耗时越来越长，宏观上就表现为每秒迭代数暴跌。
3. 冗余计算：你的代码会遍历所有1到end的数，哪怕第一个缺失的数在很靠前的位置，也会继续检查后面的所有数，做了大量无用功。

优化方案 #

我们可以反转思路：不再逐个检查每个自然数是否在π中，而是从π字符串中提取所有可能的自然数子串，按位数批量验证，直到找到第一个缺失的数。这种方法的时间复杂度会从O(end * len(pi))骤降到O(len(pi) * k)（k是第一个缺失数的位数），性能提升几个数量级。

具体步骤：

1. 一次性加载π的字符串（这一步和你的代码一致）。
2. 从1位数开始，依次处理2位、3位...的自然数：
   • 对于k位数，遍历π字符串，提取所有连续的k位数字，转成整数存入集合（集合的查找是O(1)）。
   • 检查该范围内的所有自然数（10^(k-1) 到 10^k -1）是否都在集合中。
   • 如果找到缺失的数，直接返回最小的那个，无需继续处理更高位数。
3. 这种方法可以提前终止，一旦找到第一个缺失的数就停止，避免冗余计算。

优化后的代码示例 #

import datetime
from tqdm import tqdm

def find_missing_pi_number(pi_str):
    start_time = datetime.datetime.now()
    k = 1  # 从1位数开始检查
    while True:
        min_num = 10 ** (k - 1)
        max_num = (10 ** k) - 1
        # 提取所有k位数的子串，存入集合
        seen = set()
        # 遍历pi字符串，提取连续k位的子串
        for i in tqdm(range(len(pi_str) - k + 1), desc=f"Processing {k}-digit numbers"):
            substr = pi_str[i:i+k]
            # 跳过以0开头的数（自然数不会以0开头，比如012不是有效自然数）
            if substr[0] == '0':
                continue
            num = int(substr)
            if min_num <= num <= max_num:
                seen.add(num)
        # 检查当前位数的所有自然数是否都存在
        for num in range(min_num, max_num + 1):
            if num not in seen:
                end_time = datetime.datetime.now()
                time_taken = (end_time - start_time).total_seconds()
                return {
                    "first_missing": num,
                    "time_taken": time_taken,
                    "checked_digits": k
                }
        # 如果当前位数的所有数都存在，继续检查下一位数
        print(f"All {k}-digit numbers are present in pi.")
        k += 1

# 加载π的字符串（注意：去掉小数点和非数字字符）
with open(r"C:\Users\shamm\Desktop\Text Documents\1 BILLION Digits of pi.txt", 'rt') as f:
    pi_str = f.read().replace('.', '')

result = find_missing_pi_number(pi_str)
print(f"第一个未出现在π中的自然数：{result['first_missing']}")
print(f"耗时：{result['time_taken']} 秒")
print(f"检查到的位数：{result['checked_digits']} 位")

额外优化建议 #

1. 预处理π字符串：确保加载的π字符串只包含数字，去掉开头的"3."或其他非数字字符，避免提取无效子串。
2. 内存优化：如果π的字符串太大（10亿字符占约1GB内存），可以考虑分块处理，但现代电脑的内存通常可以直接容纳。
3. 并行处理：对于提取k位数子串的步骤，可以用多进程/多线程并行处理，进一步提升速度（不过单线程对于10亿字符的k位数提取也能在合理时间内完成）。

备注：内容来源于stack exchange，提问作者PanC