跳到内容

quadratic-list-summation (RUF017)

修复总是可用的。

作用

检查是否使用 sum() 来展平列表的列表，这种操作具有平方复杂度。

为什么这不好？

使用 sum() 展平列表的列表，其复杂度是列表中列表数量的平方，因为 sum() 会为求和中的每个元素创建一个新列表。

相反，考虑使用其他展平列表的方法，以避免平方复杂度。以下方法都是列表中列表数量的线性复杂度：

  • functools.reduce(operator.iadd, lists, [])
  • list(itertools.chain.from_iterable(lists))
  • [item for sublist in lists for item in sublist]

在修复相关违规时，Ruff 默认使用 functools.reduce 形式，该形式在 微基准测试 中优于其他方法。

示例

lists = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
joined = sum(lists, [])

建议改为

import functools
import operator


lists = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
functools.reduce(operator.iadd, lists, [])

修复安全性

此修复始终被标记为不安全，因为 sum 使用 __add__ 魔术方法，而 operator.iadd 使用 __iadd__ 魔术方法，并且它们在列表上的行为有所不同。前者要求右边的加数必须是列表，而后者允许任何可迭代对象。因此，此修复可能会无意中导致以前引发错误的代码静默成功。此外，此修复可能会删除原始代码中的注释。

参考