Python代码的优化

输入输出

buffer.read() 字节流读入

data = sys.stdin.buffer.read().split()
ptr = 0
n = int(data[ptr])
m = int(data[ptr+1])
ptr += 2
# 后续所有数据均通过ptr指针从data列表中取数

• Python 原生 input() / sys.stdin.readline() 逐行读入的问题， 面对题目 m≤1e6 行数据读入，会触发1e6 + 次 IO 系统调用，而 Python 作为解释型语言，对「频繁系统调用」极度敏感；
• 普通sys.stdin.read()是字符流读取，buffer.read() 是字节流读取，跳过字符编码转换，速度更快。
• sys.stdin.buffer.read().split() 会把字节流按空白分割成字符串元素列表，ptr 是遍历这个列表的元素索引。

sys.stdout.write() 代替 print()

sys.stdout.write("-1\n")
sys.stdout.write(f"{res}\n")

Python 原生print()函数并非底层输出，包含大量冗余操作：

• 自动添加换行符、格式化校验；
• 内置输出缓冲机制，会额外占用内存并增加处理耗时。

BFS 相关

时间戳法复用vis访问数组

vis = [0] * (n + 1)  # 仅创建1次整数型数组，而非多次创建布尔数组
time_stamp = 1       # 全局时间戳，作为访问标记（替代True/False）
def bfs(mask):
    nonlocal time_stamp
    vis[a] = time_stamp  # 用当前时间戳标记「已访问」
    # 访问判断：vis[v] != time_stamp → 未访问
    if vis[v] != time_stamp and (w & mask) == 0:
        vis[v] = time_stamp
    # BFS成功/失败后，时间戳+1，为下一次BFS做准备
    time_stamp += 1

• 只创建一个，节省内存
• 只创建一次，节省时间
• 在 Python 中，int 在赋值、比较的时候比 bool 快

复用队列

q = deque()  # 仅创建1次队列实例
def bfs(mask):
    q.clear()  # 每次BFS清空队列元素，而非新建deque()
    q.append(a)

变量

局部变量比全局变量快

def main():
    time_stamp = 1    
	def bfs(mask):
    	nonlocal time_stamp
        ...

索引与解包

下面两种方式

# 解包
for u, v in edge:
    
# 索引
for e in edge:
    u = e[0]
    v = e[1]

AI 们说索引更快，但也和版本有关。

不过我测试了之后发现，

• 两种方法，3.14 都比 3.6 慢得多；
• 两种版本，索引都比解包慢得多。

其他

1

这样写

for i in range(n):
    for j in range(i + 1, n):
        if g[i][j]:
            for k in range(j + 1, n):
                if g[i][k] and g[j][k]:
                    ans += 1
        else:
            for k in range(j + 1, n):
                if not g[i][k] and not g[j][k]:
                    ans += 1

要比

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if g[i][j]:
                if g[i][k] and g[j][k]:
                    ans += 1
            else:
                if not g[i][k] and not g[j][k]:
                    ans += 1

以及把 g[i][k] 等赋给变量等要快。

原因：g[i][j] 在最内层循环中只读取了一次。