Python中如何实现比list.append速度更快的列表构建方法？

首先明确：你感知到的构建列表耗时过长，根本不是list.append()导致的。

• list.append()是Python内置C实现的均摊O(1)操作，哪怕单次构建100万元素的列表，整体操作耗时也仅在几十毫秒级别，完全达不到你感知到的“很慢”的程度
• 真正的性能杀手是你循环内写的new not in X判断：列表的in操作是线性遍历整个列表做匹配，时间复杂度是O(k)（k为当前列表长度）。当你的列表长度达到数万规模时，这一步的累计操作量会达到O(n²)级别——举个例子，当列表长度到8万时，每一次做存在性判断都要遍历全量8万个元素，累计下来的计算量是十亿级别的，这才是拖慢整体速度的核心原因。

1. 替换存在性检查的实现，从O(n)扫描降到O(1)哈希查询 #

单独维护一个和列表元素对应的set集合，专门用来做元素重复的存在性判断，完全抛弃用列表自身做in检查的写法。

2. 预分配列表内存，用索引赋值替代动态append #

如果能提前预知列表的最大长度（比如你这里的最大长度是n），直接用[0] * n初始化固定大小的列表，后续写值直接用索引定位写入，完全消除列表动态扩容过程中反复触发内存申请、全量元素拷贝的额外开销。

3. 减少循环内的冗余列表访问 #

不要每次算下一个值的时候都回头去X[i]取上一次的结果，直接用临时变量存当前计算值，减少不必要的列表索引访问耗时。

p = 1000003
q = 400003
M = p * q
n = 84480
# 按最大长度预分配列表内存，避免动态扩容
X = [0] * n
# 独立维护哈希集合做存在性检查，替代低效率的列表in查询
seen = set()
# 初始化首元素
X[0] = 6225 ** 2 % M
seen.add(X[0])
current_val = X[0] ** 2 % M
i = 1
# 两个循环终止条件：要么达到最大长度，要么遇到重复值
while i < n and current_val not in seen:
    X[i] = current_val
    seen.add(current_val)
    current_val = current_val ** 2 % M
    i += 1
# 裁掉预分配时多出来的空元素
X = X[:i]

经过上述修改，整体代码的时间复杂度从原来的O(n²)直接降到O(n)：

• 单步存在性判断的耗时从原来的和列表长度成正比，降到固定的哈希查找耗时，对于8万规模的列表，整体提速幅度可以达到两个数量级以上
• 全程无动态列表扩容的额外开销，写入操作的速度和原生append基本持平，但去掉了扩容带来的隐性耗时
• 冗余的列表索引访问全部替换成普通变量操作，进一步减少循环内的无效计算

额外补充：哪怕你不做预分配列表的优化，只要把存在性检查的逻辑从“查列表”改成“查配套的set集合”，哪怕继续用append写元素，代码速度也会比原来快几十倍——性能瓶颈从来不在append上。

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