> For better reading experience in Chinese, please refer to: [LeetCode](https://leetcode.cn/discuss/post/3746464).↵
↵
# Preface↵
↵
This article introduces techniques to reduce runtime in competitive programming using Python, under the premise that the complexity remains **correct** and **unchanged**. Each technique is accompanied by a Speedup on CPython 3.11.5 / PyPy 3.10.13.↵
↵
↵
# I/O↵
↵
### Use fast input↵
↵
Replace the built-in `input` with `sys.stdin.readline`. Each `input()` call incurs prompt handling and a `sys.stdin` lookup, while `readline()` reads a line directly. The more input lines, the larger the gap.↵
↵
Speedup: CPython ~×4.2; PyPy ~×16.4.↵
↵
~~~~~↵
import sys↵
input = lambda: sys.stdin.readline().rstrip() # strip the trailing newline↵
II = lambda: int(input())↵
LII = lambda: list(map(int, input().split()))↵
~~~~~↵
↵
### Read all input at once↵
↵
Use `sys.stdin.read().split()` to read everything into memory once, then consume as needed. This avoids calling the read function repeatedly.↵
↵
Speedup: CPython ~×1.7; PyPy ~×1.0, since the JIT optimizes line-by-line reading to about the same speed.↵
↵
~~~~~↵
import sys↵
# input contains only integers↵
it = map(int, sys.stdin.read().split())↵
II = lambda: next(it)↵
# input contains strings↵
it = iter(sys.stdin.read().split())↵
SI = lambda: next(it)↵
II = lambda: int(SI())↵
~~~~~↵
↵
### Buffer output and print once↵
↵
Store all answers in a list and print them at once with `print(*output)`, instead of calling `print` each time, reducing the number of output calls. Output is usually not the bottleneck, though.↵
↵
Speedup: CPython ~×1.1; PyPy ~×1.0.↵
↵
~~~~~↵
output = []↵
for _ in range(n):↵
ans = solve()↵
output.append(ans)↵
print(*output, sep='\n')↵
~~~~~↵
↵
↵
# Data Types↵
↵
## `int`↵
↵
### Optimizing modulo↵
↵
Integer modulo is essentially division, far more expensive than addition/subtraction/multiplication. So for adding/subtracting two integers within the `MOD` range, conditional branches might replace modulo. However, measurement contradicts this guess entirely! `%` is a fast C-level operation, while conditional branches are Python-bytecode-level and carry their own overhead; PyPy's JIT optimizes straight-line `%` even better, so branches are slower. Wrapping it in functions adds call overhead that is not worthwhile either.↵
↵
Speedup: CPython ~×1.0; PyPy ~×0.20.↵
↵
~~~~~↵
# Before↵
def add(x, y): return (x + y) % MOD↵
def sub(x, y): return (x - y) % MOD↵
# After↵
def add(x, y):↵
x += y↵
if x >= MOD: x -= MOD↵
return x↵
def sub(x, y):↵
x -= y↵
if x < 0: x += MOD↵
return x↵
~~~~~↵
↵
### Take modulo once at the end↵
↵
If intermediate results do not grow too large (e.g. within `long long` range), do not take modulo at every step; take it once at the end.↵
↵
Speedup: CPython ~×2.0; PyPy ~×3.3.↵
↵
~~~~~↵
# Before↵
ans = 0↵
for i in range(n):↵
ans = (ans + comb(n, i) * pow(2, i, MOD) % MOD) % MOD↵
# After↵
ans = 0↵
for i in range(n):↵
ans += comb(n, i) * pow(2, i, MOD)↵
ans %= MOD↵
~~~~~↵
↵
## `str`↵
↵
### Use bytearray for mutable strings↵
↵
Use `bytearray(s, encoding)` to create a C++-like mutable string, modify it in place, then `decode`, avoiding the round-trip of `list(s)`, modifying a char, and `join`.↵
↵
Speedup: CPython ~×1.0; PyPy ~×1.75, only useful when frequently modifying characters in place.↵
↵
~~~~~↵
# Before↵
t = list(s)↵
t[0] = 'a'↵
s = ''.join(t)↵
# After↵
t = bytearray(s, encoding='ascii')↵
t[0] = ord('a')↵
s = t.decode('ascii')↵
~~~~~↵
↵
## `list`↵
↵
###Use enumerate foPrefer iterators over index and valueccess↵
↵
Whenyou need bothiterating a container, fetch values through an iterator directly rather thean index and the value while iterating, use `enumerate` instead of `ing. If a built-in (such as `enumerate`) or an iterator (such as `reversed`, `zip`) can do the job, do not write `for i in range(len)` then indexing. This avoids an extra random access(nums))`. Each `nums[i]` is a separate index lookup (the `BINARY_SUBSCR` bytecode, with a bounds check and integer unboxing), whereas direct iteration follows the iterator protocol and reads sequentially, saving bytecode and improving cache locality.↵
↵
Speedup: `enumerate` CPython ~×1.0; PyPy ~×1.2.↵
↵
~~~~~↵
# Before↵
for i in range(len(nums)):↵
x = nums[i]↵
...↵
# After↵
for i, x in enumerate(nums, PyPy ~×1.2; `reversed` CPython ~×1.5, PyPy ~×1.5; `zip` CPython ~×1.2, PyPy ~×1.0.↵
↵
~~~~~↵
# Before↵
for i in range(len(nums)):↵
x = nums[i]↵
...↵
for i in range(len(nums) - 1, -1, -1):↵
x = nums[i]↵
...↵
for i in range(len(a)):↵
x, y = a[i], b[i]↵
...↵
# After↵
for i, x in enumerate(nums):↵
...↵
for x in reversed(nums):↵
...↵
for x, y in zip(a, b):↵
...↵
~~~~~↵
↵
### Preallocate list space↵
↵
When the final length is known, allocate space with `[0] * n` and assign by index, instead of `append`-ing from an empty list. `append` triggers resizing and copying when capacity is insufficient; preallocation avoids repeated resizes.↵
↵
Speedup: CPython ~×1.6; PyPy ~×5.0.↵
↵
~~~~~↵
# Before↵
nums = []↵
for _ in range(n):↵
nums.append(x)↵
# After↵
nums = [0] * n↵
for i in range(n):↵
nums[i] = x↵
~~~~~↵
↵
### Put the larger dimension inside↵
↵
When constructing a multi-dimensional `list`, make the longer dimension the inner list. This both reduces the number of `list` objects created and improves memory continuity.↵
↵
Speedup: CPython ~×1.05; PyPy ~×1.5.↵
↵
~~~~~↵
n, k = 10**5, 20↵
# Before↵
dp = [[0] * k for _ in range(n)]↵
# After↵
dp = [[0] * n for _ in range(k)]↵
~~~~~↵
↵
### Flatten multi-dimensional indices to one dimension↵
↵
Flatten a multi-dimensional array into one dimension; for a 2D array, encode/decode indices manually with `i * n + j`. This removes one level of list indirection and is more cache-friendly.↵
↵
Speedup: CPython ~×1.1; PyPy ~×1.1.↵
↵
~~~~~↵
# Before↵
dp = [[0] * n for _ in range(m)]↵
# After↵
dp = [0] * (m*n)↵
compress = lambda i, j: i*n+j↵
decompress = lambda k: divmod(k, n)↵
~~~~~↵
↵
### Use slicing↵
↵
When operating on a sub-array of a list, slice out the sub-array and process it directly, instead of accessing elements one by one by index. Slicing copies out the sub-array in one C-level operation, and built-in `sum` / `max` also traverse in C, so the whole thing is far faster than a Python-bytecode index loop.↵
↵
Speedup: for `sum`, CPython ~×2.0, PyPy ~×0.72; for `max`, CPython ~×2.3, PyPy ~×1.8. Note that on PyPy, the cost of slicing can outweigh the JIT's optimization of the loop.↵
↵
~~~~~↵
# Before↵
s = sum(nums[i] for i in range(l, r))↵
mx = 0↵
for i in range(l, r): mx = max(mx, nums[i])↵
# After↵
s = sum(nums[l:r])↵
mx = max(nums[l:r])↵
~~~~~↵
↵
### Use array.array instead of list↵
↵
Replace a `list` of fixed-length integers needing frequent access and modification with `array.array('i', ...)`. `array` stores C integers compactly in memory, saving space. However, each access to an `array` requires converting between Python int and C integer, which can be more expensive than the list itself.↵
↵
Speedup: CPython ~×0.58; PyPy ~×0.73. This holds only for the memory-footprint scenario, not for high-frequency random access.↵
↵
~~~~~↵
# Before↵
nums = [0] * n↵
# After↵
from array import array↵
nums = array('i', [0] * n)↵
~~~~~↵
↵
### Use bytearray instead of a boolean array↵
↵
Replace `[False] * n` with `bytearray(n)`. A boolean array is still a list, whereas `bytearray` stores one byte per element, compactly.↵
↵
Speedup: CPython ~×1.7; PyPy ~×0.9. PyPy's list is already highly optimized, so bytearray is slower.↵
↵
~~~~~↵
# Before↵
vis = [False] * n↵
# After↵
vis = bytearray(bytes(n))↵
~~~~~↵
↵
### Use a ctypes C array instead of list↵
↵
Replace `list` with a `ctypes` `c_int32` array. Each index into a `ctypes` array is a C call, with huge overhead.↵
↵
Speedup: CPython ~×0.65; PyPy ~×0.003. This is only suitable for interop with C libraries, never as a frequently-accessed container.↵
↵
~~~~~↵
# Before↵
rank = [0] * n↵
pa = list(range(n))↵
# After↵
from ctypes import c_int32↵
rank = (c_int32 * n)()↵
pa = (c_int32 * n)(*range(n))↵
~~~~~↵
↵
## `tuple`↵
↵
### Use a structure of arrays instead of an array of structures↵
↵
Instead of combining multiple fields into a `tuple` and putting them in a `list`, use multiple `list`s to store the fields separately.↵
↵
Speedup: CPython ~×0.75; PyPy ~×1.5.↵
↵
~~~~~↵
# Before↵
items = [(w1, v1), (w2, v2), ...]↵
# After↵
weights = [w1, w2, ...]↵
values = [v1, v2, ...]↵
~~~~~↵
↵
## `dict`↵
↵
### Use list instead of dict / set↵
↵
When the data range allows, replace key-accessed `dict` / `set` with index-accessed `list`. Hash-table access requires hashing and may trigger resize, far slower than direct array indexing.↵
↵
Speedup: CPython ~×1.8; PyPy ~×1.6.↵
↵
~~~~~↵
# Before↵
g = defaultdict(list)↵
# After↵
g = [[] for _ in range(n)]↵
~~~~~↵
↵
### Use dict.items for both key and value↵
↵
When iterating a dict and needing both keys and values, use `for k, v in mp.items()` instead of `for k in mp: v = mp[k]`. The latter needs an extra hash lookup each time.↵
↵
Speedup: CPython ~×1.2; PyPy ~×2.9.↵
↵
~~~~~↵
# Before↵
for k in mp:↵
v = mp[k]↵
...↵
# After↵
for k, v in mp.items():↵
...↵
~~~~~↵
↵
### Use .get for possibly-missing keys↵
↵
For a `defaultdict`, when querying a key that may be missing, use `mp.get(k, default)` instead of `mp[k]`. `mp[k]` triggers `__missing__` and inserts a new entry when the key is missing; `get` only reads and does not insert. The difference is notable when many queried keys are missing.↵
↵
Speedup: CPython ~×1.3; PyPy ~×1.35.↵
↵
~~~~~↵
mp = defaultdict(int)↵
# Before↵
x = mp[k]↵
# After↵
x = mp.get(k, 0)↵
~~~~~↵
↵
↵
# Functions↵
↵
### Use built-in functions instead of handwritten loops↵
↵
For reductions like max or sum, use built-in `max` / `sum` directly, not handwritten loops. Built-ins traverse in C, far faster than Python-bytecode loops.↵
↵
Speedup: `max` CPython ~×1.4, PyPy ~×2.1; `sum` CPython ~×1.5, PyPy ~×1.0, since PyPy's JIT optimizes the handwritten sum loop to match the built-in. Reductions with a transform are an exception; see the next item.↵
↵
~~~~~↵
# Before↵
mx = 0↵
for x in nums:↵
if x > mx: mx = x↵
# After↵
mx = max(nums)↵
~~~~~↵
↵
### Use a handwritten loop for reductions with a transform↵
↵
For reductions with a transform or filter, use a handwritten loop instead of a built-in, e.g. `sum(x*x for x in nums)` or `sum(x for x in nums if cond)`. The reason: a generator goes through the yield protocol element by element, and each element round-trips between the generator and `sum`, which is more expensive than a tight handwritten loop.↵
↵
Speedup: sum of squares CPython ~×1.35, PyPy ~×1.14; filtered sum with `if` CPython ~×1.18, PyPy ~×2.30.↵
↵
~~~~~↵
# Before↵
s = sum(x for x in nums if x & 1)↵
# After↵
s = 0↵
for x in nums:↵
if x & 1:↵
s += x↵
~~~~~↵
↵
### Handwritten min/max↵
↵
When comparing only two numbers, use `x if x < y else y` instead of `min(x, y)`, and similarly for `max`. Since built-in `min/max` handle variadic arguments and type checking with extra overhead, the guess is that handwriting is faster.↵
↵
Speedup: CPython ~×1.9; PyPy ~×0.83, where in fact the JIT optimizes built-in `min/max` to be faster than a lambda call.↵
↵
~~~~~↵
# Before↵
x, y = min(x, y), max(x, y)↵
# After↵
fmin = lambda x, y: x if x < y else y↵
fmax = lambda x, y: x if x > y else y↵
x, y = fmin(x, y), fmax(x, y)↵
~~~~~↵
↵
### Handwritten fast exponentiation↵
↵
When you need modular fast exponentiation, handwrite fast exponentiation instead of using `pow(x, -1, MOD)` (or `pow(x, MOD-2, MOD)`). The built-in `pow`'s extended-Euclidean inverse path may be slower.↵
↵
Measured result: CPython ~×0.20, because `pow(x, -1, MOD)` are single C calls, far faster than a Python loop; PyPy ~×1.8.↵
↵
~~~~~↵
MOD = 10**9+7↵
# Before↵
inv = pow(x, -1, MOD)↵
# After↵
def qpow(x, k):↵
res = 1↵
while k:↵
if k & 1:↵
res = res * x % MOD↵
x = x * x % MOD↵
k >>= 1↵
return res↵
inv = qpow(x, MOD-2)↵
~~~~~↵
↵
### Handwritten memo instead of @cache↵
↵
For memoized search, do not use `functools.cache`; use an explicit memo array. `@cache` packs parameters into a tuple, hashes them, and stores results in a hash table plus a doubly linked list (LRU), which is costly; a handwritten array can be indexed directly.↵
↵
Speedup: CPython ~×1.17; PyPy ~×2.6.↵
↵
~~~~~↵
# Before↵
@cache↵
def dp(i: int, pre: int, islim: bool, isnum: bool) -> int:↵
...↵
# After↵
memo = [[-1] * 10 for _ in range(n)]↵
def dp(i: int, pre: int, islim: bool, isnum: bool) -> int:↵
if not islim and not isnum and memo[i][pre] != -1:↵
return memo[i][pre]↵
...↵
~~~~~↵
↵
### Use yield to produce results one by one↵
↵
Change a function that collects results and returns them all at once into a generator that yields results one by one, saving the intermediate list allocation.↵
↵
Speedup: CPython ~×1.2; PyPy ~×14.↵
↵
~~~~~↵
# Before↵
def all_subsets(mask):↵
subs = []↵
cur = mask↵
while cur:↵
subs.append(cur)↵
cur = (cur - 1) & mask↵
return subs↵
# After↵
def all_subsets(mask):↵
cur = mask↵
while cur:↵
yield cur↵
cur = (cur - 1) & mask↵
~~~~~↵
↵
### Pass a generator instead of a list comprehension↵
↵
For functions accepting an iterable, pass a generator expression directly instead of building a `list` first, saving the intermediate list allocation.↵
↵
Speedup: CPython ~×1.13; PyPy ~×0.48, likely because a list comprehension plus `sum` takes a fast path, making the generator slower.↵
↵
~~~~~↵
# Before↵
s = sum([x**2 for x in range(n)])↵
# After↵
s = sum(x**2 for x in range(n))↵
~~~~~↵
↵
### Wrap the main program in a function↵
↵
Write the main logic inside `main()` and call it, making variables local. Local variables use `LOAD_FAST`, globals use `LOAD_GLOBAL`; the former is slightly faster.↵
↵
Speedup: CPython ~×1.1; PyPy ~×1.0.↵
↵
~~~~~↵
def main():↵
...↵
main()↵
~~~~~↵
↵
↵
# Classes↵
↵
### Declare members with __slots__↵
↵
List member variable names with `__slots__` in the class, removing each instance's `__dict__`; attribute access is faster and memory is saved.↵
↵
Speedup: CPython ~×1.18; PyPy ~×1.43.↵
↵
~~~~~↵
# Before↵
class DSU:↵
def __init__(self, n: int):↵
self.parent = list(range(n))↵
self.size = [1] * n↵
# After↵
class DSU:↵
__slots__ = 'parent', 'size'↵
def __init__(self, n: int):↵
self.parent = list(range(n))↵
self.size = [1] * n↵
~~~~~↵
↵
### Cache member variables into locals↵
↵
For a `self.x` accessed frequently inside a method, assign it to a local variable first; the former is `LOAD_ATTR`, the latter `LOAD_FAST`.↵
↵
Speedup: CPython ~×1.56; PyPy ~×1.0.↵
↵
~~~~~↵
# Before↵
class DSU:↵
def find(self, u: int):↵
while u != self.parent[u]:↵
u = self.parent[u]↵
return u↵
# After↵
class DSU:↵
def find(self, u: int):↵
parent = self.parent↵
while u != parent[u]:↵
u = parent[u]↵
return u↵
~~~~~↵
↵
### Use arrays instead of class instances↵
↵
Use arrays instead of class instances, e.g. for tries, segment trees, etc. Class-instance creation and attribute access are both slow.↵
↵
Speedup: CPython ~×0.97; PyPy ~×1.83.↵
↵
~~~~~↵
# Before↵
class TrieNode:↵
def __init__(self):↵
self.children = [None] * 26↵
self.isend = False↵
self.cnt = 0↵
class Trie:↵
def __init__(self):↵
self.root = TrieNode()↵
...↵
# After↵
class StaticTrie:↵
def __init__(self, lengths):↵
lengths += 1↵
self.children = [[-1] * lengths for _ in range(26)]↵
self.isend = [False] * lengths↵
self.cnt = [0] * lengths↵
self.ptr = 1↵
...↵
~~~~~↵
↵
↵
# Miscellaneous↵
↵
### Simulate recursion with an explicit stack↵
↵
When recursion is deep, simulate it with an explicit stack, or use an infinite-recursion decorator[^1]; `sys.setrecursionlimit` is not fully reliable. The reason is that function frames have overhead, and overly deep recursion overflows the stack, causing `RE` or `MLE`. Below is a pre-order traversal of a tree; a post-order traversal is obtained by reversing the pre-order result.↵
↵
Speedup: CPython ~×0.85; PyPy ~×1.36.↵
↵
~~~~~↵
order = []↵
# Before↵
def dfs(u: int, pa: int):↵
order.append(u)↵
for v in tree[u]:↵
if v != pa:↵
dfs(v, u)↵
# After↵
parents = [-1] * len(tree)↵
stk = [root]↵
while stk:↵
u = stk.pop()↵
order.append(u)↵
for v in g[u]:↵
if parents[u] != v:↵
parents[v] = u↵
stk.append(v)↵
~~~~~↵
↵
### Use a chained forward star instead of an adjacency list↵
↵
When building a graph, do not use `g = [[] for _ in range(n)]` with `append`; use a chained forward star with four fixed-length arrays `head / to / weight / nxt` and head insertion.↵
↵
Speedup: CPython ~×2.6; PyPy ~×7.9.↵
↵
~~~~~↵
# Before↵
g = [[] for _ in range(n)]↵
def add_edge(u: int, v: int, w: int):↵
g[u].append((v, w))↵
# After↵
head = [-1] * n↵
to = [-1] * m↵
weight = [0] * m↵
nxt = [-1] * m↵
ptr = 0↵
def add_edge(u: int, v: int, w: int):↵
nonlocal ptr↵
to[ptr] = v↵
weight[ptr] = w↵
nxt[ptr] = head[u]↵
head[u] = ptr↵
ptr += 1↵
~~~~~↵
↵
↵
# Summary↵
↵
## Seize real optimizations, avoid negative ones↵
↵
Most techniques in this article are significantly effective on at least one of CPython and PyPy, and the main theme — **reduce object allocation and reduce the amount of Python bytecode executed** — benefits both engines. Conversely, some taken-for-granted optimizations do not hold or are even slower on both engines. The core reason is that **the dominant costs at the Python-bytecode level are branches, function calls, and attribute access**; any so-called optimization that increases these tends to do more harm than good.↵
↵
## Each engine has its strengths↵
↵
CPython has no hot-loop optimization and interprets bytecode line by line, so anything that pushes work down to the C level in one shot wins. PyPy has a JIT that compiles tight, type-stable Python loops to near-machine-code speed. Therefore: techniques that **replace C built-ins with handwritten loops or plain containers** are often ineffective or even slower on CPython, but may be faster on PyPy; conversely, techniques that **rely on C built-ins or compact structures** benefit CPython, while on PyPy they are often slower due to other overhead.↵
↵
## On the language itself↵
↵
Python's nature determines that no matter how it is optimized, it cannot pass problems with large data ranges and high complexity. Moreover, the time spent writing Python and then optimizing it afterward is not necessarily faster than directly using C++. So although Python has some excellent language features, if you want to engage in professional competitive programming, it is better to drop the obsession with Python and learn C++.↵
↵
↵
# References↵
↵
[^1]: PyRival. https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/bootstrap.py↵
↵
# Preface↵
↵
This article introduces techniques to reduce runtime in competitive programming using Python, under the premise that the complexity remains **correct** and **unchanged**. Each technique is accompanied by a Speedup on CPython 3.11.5 / PyPy 3.10.13.↵
↵
↵
# I/O↵
↵
### Use fast input↵
↵
Replace the built-in `input` with `sys.stdin.readline`. Each `input()` call incurs prompt handling and a `sys.stdin` lookup, while `readline()` reads a line directly. The more input lines, the larger the gap.↵
↵
Speedup: CPython ~×4.2; PyPy ~×16.4.↵
↵
~~~~~↵
import sys↵
input = lambda: sys.stdin.readline().rstrip() # strip the trailing newline↵
II = lambda: int(input())↵
LII = lambda: list(map(int, input().split()))↵
~~~~~↵
↵
### Read all input at once↵
↵
Use `sys.stdin.read().split()` to read everything into memory once, then consume as needed. This avoids calling the read function repeatedly.↵
↵
Speedup: CPython ~×1.7; PyPy ~×1.0, since the JIT optimizes line-by-line reading to about the same speed.↵
↵
~~~~~↵
import sys↵
# input contains only integers↵
it = map(int, sys.stdin.read().split())↵
II = lambda: next(it)↵
# input contains strings↵
it = iter(sys.stdin.read().split())↵
SI = lambda: next(it)↵
II = lambda: int(SI())↵
~~~~~↵
↵
### Buffer output and print once↵
↵
Store all answers in a list and print them at once with `print(*output)`, instead of calling `print` each time, reducing the number of output calls. Output is usually not the bottleneck, though.↵
↵
Speedup: CPython ~×1.1; PyPy ~×1.0.↵
↵
~~~~~↵
output = []↵
for _ in range(n):↵
ans = solve()↵
output.append(ans)↵
print(*output, sep='\n')↵
~~~~~↵
↵
↵
# Data Types↵
↵
## `int`↵
↵
### Optimizing modulo↵
↵
Integer modulo is essentially division, far more expensive than addition/subtraction/multiplication. So for adding/subtracting two integers within the `MOD` range, conditional branches might replace modulo. However, measurement contradicts this guess entirely! `%` is a fast C-level operation, while conditional branches are Python-bytecode-level and carry their own overhead; PyPy's JIT optimizes straight-line `%` even better, so branches are slower. Wrapping it in functions adds call overhead that is not worthwhile either.↵
↵
Speedup: CPython ~×1.0; PyPy ~×0.20.↵
↵
~~~~~↵
# Before↵
def add(x, y): return (x + y) % MOD↵
def sub(x, y): return (x - y) % MOD↵
# After↵
def add(x, y):↵
x += y↵
if x >= MOD: x -= MOD↵
return x↵
def sub(x, y):↵
x -= y↵
if x < 0: x += MOD↵
return x↵
~~~~~↵
↵
### Take modulo once at the end↵
↵
If intermediate results do not grow too large (e.g. within `long long` range), do not take modulo at every step; take it once at the end.↵
↵
Speedup: CPython ~×2.0; PyPy ~×3.3.↵
↵
~~~~~↵
# Before↵
ans = 0↵
for i in range(n):↵
ans = (ans + comb(n, i) * pow(2, i, MOD) % MOD) % MOD↵
# After↵
ans = 0↵
for i in range(n):↵
ans += comb(n, i) * pow(2, i, MOD)↵
ans %= MOD↵
~~~~~↵
↵
## `str`↵
↵
### Use bytearray for mutable strings↵
↵
Use `bytearray(s, encoding)` to create a C++-like mutable string, modify it in place, then `decode`, avoiding the round-trip of `list(s)`, modifying a char, and `join`.↵
↵
Speedup: CPython ~×1.0; PyPy ~×1.75, only useful when frequently modifying characters in place.↵
↵
~~~~~↵
# Before↵
t = list(s)↵
t[0] = 'a'↵
s = ''.join(t)↵
# After↵
t = bytearray(s, encoding='ascii')↵
t[0] = ord('a')↵
s = t.decode('ascii')↵
~~~~~↵
↵
## `list`↵
↵
###
↵
When
↵
Speedup: `enumerate` CPython ~×1.0
↵
~~~~~↵
# Before↵
for i in range(len(nums)):↵
x = nums[i]↵
...↵
# After↵
for i, x in enumerate(nums
↵
~~~~~↵
# Before↵
for i in range(len(nums)):↵
x = nums[i]↵
...↵
for i in range(len(nums) - 1, -1, -1):↵
x = nums[i]↵
...↵
for i in range(len(a)):↵
x, y = a[i], b[i]↵
...↵
# After↵
for i, x in enumerate(nums):↵
...↵
for x in reversed(nums):↵
...↵
for x, y in zip(a, b):↵
...↵
~~~~~↵
↵
### Preallocate list space↵
↵
When the final length is known, allocate space with `[0] * n` and assign by index, instead of `append`-ing from an empty list. `append` triggers resizing and copying when capacity is insufficient; preallocation avoids repeated resizes.↵
↵
Speedup: CPython ~×1.6; PyPy ~×5.0.↵
↵
~~~~~↵
# Before↵
nums = []↵
for _ in range(n):↵
nums.append(x)↵
# After↵
nums = [0] * n↵
for i in range(n):↵
nums[i] = x↵
~~~~~↵
↵
### Put the larger dimension inside↵
↵
When constructing a multi-dimensional `list`, make the longer dimension the inner list. This both reduces the number of `list` objects created and improves memory continuity.↵
↵
Speedup: CPython ~×1.05; PyPy ~×1.5.↵
↵
~~~~~↵
n, k = 10**5, 20↵
# Before↵
dp = [[0] * k for _ in range(n)]↵
# After↵
dp = [[0] * n for _ in range(k)]↵
~~~~~↵
↵
### Flatten multi-dimensional indices to one dimension↵
↵
Flatten a multi-dimensional array into one dimension; for a 2D array, encode/decode indices manually with `i * n + j`. This removes one level of list indirection and is more cache-friendly.↵
↵
Speedup: CPython ~×1.1; PyPy ~×1.1.↵
↵
~~~~~↵
# Before↵
dp = [[0] * n for _ in range(m)]↵
# After↵
dp = [0] * (m*n)↵
compress = lambda i, j: i*n+j↵
decompress = lambda k: divmod(k, n)↵
~~~~~↵
↵
### Use slicing↵
↵
When operating on a sub-array of a list, slice out the sub-array and process it directly, instead of accessing elements one by one by index. Slicing copies out the sub-array in one C-level operation, and built-in `sum` / `max` also traverse in C, so the whole thing is far faster than a Python-bytecode index loop.↵
↵
Speedup: for `sum`, CPython ~×2.0, PyPy ~×0.72; for `max`, CPython ~×2.3, PyPy ~×1.8. Note that on PyPy, the cost of slicing can outweigh the JIT's optimization of the loop.↵
↵
~~~~~↵
# Before↵
s = sum(nums[i] for i in range(l, r))↵
mx = 0↵
for i in range(l, r): mx = max(mx, nums[i])↵
# After↵
s = sum(nums[l:r])↵
mx = max(nums[l:r])↵
~~~~~↵
↵
### Use array.array instead of list↵
↵
Replace a `list` of fixed-length integers needing frequent access and modification with `array.array('i', ...)`. `array` stores C integers compactly in memory, saving space. However, each access to an `array` requires converting between Python int and C integer, which can be more expensive than the list itself.↵
↵
Speedup: CPython ~×0.58; PyPy ~×0.73. This holds only for the memory-footprint scenario, not for high-frequency random access.↵
↵
~~~~~↵
# Before↵
nums = [0] * n↵
# After↵
from array import array↵
nums = array('i', [0] * n)↵
~~~~~↵
↵
### Use bytearray instead of a boolean array↵
↵
Replace `[False] * n` with `bytearray(n)`. A boolean array is still a list, whereas `bytearray` stores one byte per element, compactly.↵
↵
Speedup: CPython ~×1.7; PyPy ~×0.9. PyPy's list is already highly optimized, so bytearray is slower.↵
↵
~~~~~↵
# Before↵
vis = [False] * n↵
# After↵
vis = bytearray(bytes(n))↵
~~~~~↵
↵
### Use a ctypes C array instead of list↵
↵
Replace `list` with a `ctypes` `c_int32` array. Each index into a `ctypes` array is a C call, with huge overhead.↵
↵
Speedup: CPython ~×0.65; PyPy ~×0.003. This is only suitable for interop with C libraries, never as a frequently-accessed container.↵
↵
~~~~~↵
# Before↵
rank = [0] * n↵
pa = list(range(n))↵
# After↵
from ctypes import c_int32↵
rank = (c_int32 * n)()↵
pa = (c_int32 * n)(*range(n))↵
~~~~~↵
↵
## `tuple`↵
↵
### Use a structure of arrays instead of an array of structures↵
↵
Instead of combining multiple fields into a `tuple` and putting them in a `list`, use multiple `list`s to store the fields separately.↵
↵
Speedup: CPython ~×0.75; PyPy ~×1.5.↵
↵
~~~~~↵
# Before↵
items = [(w1, v1), (w2, v2), ...]↵
# After↵
weights = [w1, w2, ...]↵
values = [v1, v2, ...]↵
~~~~~↵
↵
## `dict`↵
↵
### Use list instead of dict / set↵
↵
When the data range allows, replace key-accessed `dict` / `set` with index-accessed `list`. Hash-table access requires hashing and may trigger resize, far slower than direct array indexing.↵
↵
Speedup: CPython ~×1.8; PyPy ~×1.6.↵
↵
~~~~~↵
# Before↵
g = defaultdict(list)↵
# After↵
g = [[] for _ in range(n)]↵
~~~~~↵
↵
### Use dict.items for both key and value↵
↵
When iterating a dict and needing both keys and values, use `for k, v in mp.items()` instead of `for k in mp: v = mp[k]`. The latter needs an extra hash lookup each time.↵
↵
Speedup: CPython ~×1.2; PyPy ~×2.9.↵
↵
~~~~~↵
# Before↵
for k in mp:↵
v = mp[k]↵
...↵
# After↵
for k, v in mp.items():↵
...↵
~~~~~↵
↵
### Use .get for possibly-missing keys↵
↵
For a `defaultdict`, when querying a key that may be missing, use `mp.get(k, default)` instead of `mp[k]`. `mp[k]` triggers `__missing__` and inserts a new entry when the key is missing; `get` only reads and does not insert. The difference is notable when many queried keys are missing.↵
↵
Speedup: CPython ~×1.3; PyPy ~×1.35.↵
↵
~~~~~↵
mp = defaultdict(int)↵
# Before↵
x = mp[k]↵
# After↵
x = mp.get(k, 0)↵
~~~~~↵
↵
↵
# Functions↵
↵
### Use built-in functions instead of handwritten loops↵
↵
For reductions like max or sum, use built-in `max` / `sum` directly, not handwritten loops. Built-ins traverse in C, far faster than Python-bytecode loops.↵
↵
Speedup: `max` CPython ~×1.4, PyPy ~×2.1; `sum` CPython ~×1.5, PyPy ~×1.0, since PyPy's JIT optimizes the handwritten sum loop to match the built-in. Reductions with a transform are an exception; see the next item.↵
↵
~~~~~↵
# Before↵
mx = 0↵
for x in nums:↵
if x > mx: mx = x↵
# After↵
mx = max(nums)↵
~~~~~↵
↵
### Use a handwritten loop for reductions with a transform↵
↵
For reductions with a transform or filter, use a handwritten loop instead of a built-in, e.g. `sum(x*x for x in nums)` or `sum(x for x in nums if cond)`. The reason: a generator goes through the yield protocol element by element, and each element round-trips between the generator and `sum`, which is more expensive than a tight handwritten loop.↵
↵
Speedup: sum of squares CPython ~×1.35, PyPy ~×1.14; filtered sum with `if` CPython ~×1.18, PyPy ~×2.30.↵
↵
~~~~~↵
# Before↵
s = sum(x for x in nums if x & 1)↵
# After↵
s = 0↵
for x in nums:↵
if x & 1:↵
s += x↵
~~~~~↵
↵
### Handwritten min/max↵
↵
When comparing only two numbers, use `x if x < y else y` instead of `min(x, y)`, and similarly for `max`. Since built-in `min/max` handle variadic arguments and type checking with extra overhead, the guess is that handwriting is faster.↵
↵
Speedup: CPython ~×1.9; PyPy ~×0.83, where in fact the JIT optimizes built-in `min/max` to be faster than a lambda call.↵
↵
~~~~~↵
# Before↵
x, y = min(x, y), max(x, y)↵
# After↵
fmin = lambda x, y: x if x < y else y↵
fmax = lambda x, y: x if x > y else y↵
x, y = fmin(x, y), fmax(x, y)↵
~~~~~↵
↵
### Handwritten fast exponentiation↵
↵
When you need modular fast exponentiation, handwrite fast exponentiation instead of using `pow(x, -1, MOD)` (or `pow(x, MOD-2, MOD)`). The built-in `pow`'s extended-Euclidean inverse path may be slower.↵
↵
Measured result: CPython ~×0.20, because `pow(x, -1, MOD)` are single C calls, far faster than a Python loop; PyPy ~×1.8.↵
↵
~~~~~↵
MOD = 10**9+7↵
# Before↵
inv = pow(x, -1, MOD)↵
# After↵
def qpow(x, k):↵
res = 1↵
while k:↵
if k & 1:↵
res = res * x % MOD↵
x = x * x % MOD↵
k >>= 1↵
return res↵
inv = qpow(x, MOD-2)↵
~~~~~↵
↵
### Handwritten memo instead of @cache↵
↵
For memoized search, do not use `functools.cache`; use an explicit memo array. `@cache` packs parameters into a tuple, hashes them, and stores results in a hash table plus a doubly linked list (LRU), which is costly; a handwritten array can be indexed directly.↵
↵
Speedup: CPython ~×1.17; PyPy ~×2.6.↵
↵
~~~~~↵
# Before↵
@cache↵
def dp(i: int, pre: int, islim: bool, isnum: bool) -> int:↵
...↵
# After↵
memo = [[-1] * 10 for _ in range(n)]↵
def dp(i: int, pre: int, islim: bool, isnum: bool) -> int:↵
if not islim and not isnum and memo[i][pre] != -1:↵
return memo[i][pre]↵
...↵
~~~~~↵
↵
### Use yield to produce results one by one↵
↵
Change a function that collects results and returns them all at once into a generator that yields results one by one, saving the intermediate list allocation.↵
↵
Speedup: CPython ~×1.2; PyPy ~×14.↵
↵
~~~~~↵
# Before↵
def all_subsets(mask):↵
subs = []↵
cur = mask↵
while cur:↵
subs.append(cur)↵
cur = (cur - 1) & mask↵
return subs↵
# After↵
def all_subsets(mask):↵
cur = mask↵
while cur:↵
yield cur↵
cur = (cur - 1) & mask↵
~~~~~↵
↵
### Pass a generator instead of a list comprehension↵
↵
For functions accepting an iterable, pass a generator expression directly instead of building a `list` first, saving the intermediate list allocation.↵
↵
Speedup: CPython ~×1.13; PyPy ~×0.48, likely because a list comprehension plus `sum` takes a fast path, making the generator slower.↵
↵
~~~~~↵
# Before↵
s = sum([x**2 for x in range(n)])↵
# After↵
s = sum(x**2 for x in range(n))↵
~~~~~↵
↵
### Wrap the main program in a function↵
↵
Write the main logic inside `main()` and call it, making variables local. Local variables use `LOAD_FAST`, globals use `LOAD_GLOBAL`; the former is slightly faster.↵
↵
Speedup: CPython ~×1.1; PyPy ~×1.0.↵
↵
~~~~~↵
def main():↵
...↵
main()↵
~~~~~↵
↵
↵
# Classes↵
↵
### Declare members with __slots__↵
↵
List member variable names with `__slots__` in the class, removing each instance's `__dict__`; attribute access is faster and memory is saved.↵
↵
Speedup: CPython ~×1.18; PyPy ~×1.43.↵
↵
~~~~~↵
# Before↵
class DSU:↵
def __init__(self, n: int):↵
self.parent = list(range(n))↵
self.size = [1] * n↵
# After↵
class DSU:↵
__slots__ = 'parent', 'size'↵
def __init__(self, n: int):↵
self.parent = list(range(n))↵
self.size = [1] * n↵
~~~~~↵
↵
### Cache member variables into locals↵
↵
For a `self.x` accessed frequently inside a method, assign it to a local variable first; the former is `LOAD_ATTR`, the latter `LOAD_FAST`.↵
↵
Speedup: CPython ~×1.56; PyPy ~×1.0.↵
↵
~~~~~↵
# Before↵
class DSU:↵
def find(self, u: int):↵
while u != self.parent[u]:↵
u = self.parent[u]↵
return u↵
# After↵
class DSU:↵
def find(self, u: int):↵
parent = self.parent↵
while u != parent[u]:↵
u = parent[u]↵
return u↵
~~~~~↵
↵
### Use arrays instead of class instances↵
↵
Use arrays instead of class instances, e.g. for tries, segment trees, etc. Class-instance creation and attribute access are both slow.↵
↵
Speedup: CPython ~×0.97; PyPy ~×1.83.↵
↵
~~~~~↵
# Before↵
class TrieNode:↵
def __init__(self):↵
self.children = [None] * 26↵
self.isend = False↵
self.cnt = 0↵
class Trie:↵
def __init__(self):↵
self.root = TrieNode()↵
...↵
# After↵
class StaticTrie:↵
def __init__(self, lengths):↵
lengths += 1↵
self.children = [[-1] * lengths for _ in range(26)]↵
self.isend = [False] * lengths↵
self.cnt = [0] * lengths↵
self.ptr = 1↵
...↵
~~~~~↵
↵
↵
# Miscellaneous↵
↵
### Simulate recursion with an explicit stack↵
↵
When recursion is deep, simulate it with an explicit stack, or use an infinite-recursion decorator[^1]; `sys.setrecursionlimit` is not fully reliable. The reason is that function frames have overhead, and overly deep recursion overflows the stack, causing `RE` or `MLE`. Below is a pre-order traversal of a tree; a post-order traversal is obtained by reversing the pre-order result.↵
↵
Speedup: CPython ~×0.85; PyPy ~×1.36.↵
↵
~~~~~↵
order = []↵
# Before↵
def dfs(u: int, pa: int):↵
order.append(u)↵
for v in tree[u]:↵
if v != pa:↵
dfs(v, u)↵
# After↵
parents = [-1] * len(tree)↵
stk = [root]↵
while stk:↵
u = stk.pop()↵
order.append(u)↵
for v in g[u]:↵
if parents[u] != v:↵
parents[v] = u↵
stk.append(v)↵
~~~~~↵
↵
### Use a chained forward star instead of an adjacency list↵
↵
When building a graph, do not use `g = [[] for _ in range(n)]` with `append`; use a chained forward star with four fixed-length arrays `head / to / weight / nxt` and head insertion.↵
↵
Speedup: CPython ~×2.6; PyPy ~×7.9.↵
↵
~~~~~↵
# Before↵
g = [[] for _ in range(n)]↵
def add_edge(u: int, v: int, w: int):↵
g[u].append((v, w))↵
# After↵
head = [-1] * n↵
to = [-1] * m↵
weight = [0] * m↵
nxt = [-1] * m↵
ptr = 0↵
def add_edge(u: int, v: int, w: int):↵
nonlocal ptr↵
to[ptr] = v↵
weight[ptr] = w↵
nxt[ptr] = head[u]↵
head[u] = ptr↵
ptr += 1↵
~~~~~↵
↵
↵
# Summary↵
↵
## Seize real optimizations, avoid negative ones↵
↵
Most techniques in this article are significantly effective on at least one of CPython and PyPy, and the main theme — **reduce object allocation and reduce the amount of Python bytecode executed** — benefits both engines. Conversely, some taken-for-granted optimizations do not hold or are even slower on both engines. The core reason is that **the dominant costs at the Python-bytecode level are branches, function calls, and attribute access**; any so-called optimization that increases these tends to do more harm than good.↵
↵
## Each engine has its strengths↵
↵
CPython has no hot-loop optimization and interprets bytecode line by line, so anything that pushes work down to the C level in one shot wins. PyPy has a JIT that compiles tight, type-stable Python loops to near-machine-code speed. Therefore: techniques that **replace C built-ins with handwritten loops or plain containers** are often ineffective or even slower on CPython, but may be faster on PyPy; conversely, techniques that **rely on C built-ins or compact structures** benefit CPython, while on PyPy they are often slower due to other overhead.↵
↵
## On the language itself↵
↵
Python's nature determines that no matter how it is optimized, it cannot pass problems with large data ranges and high complexity. Moreover, the time spent writing Python and then optimizing it afterward is not necessarily faster than directly using C++. So although Python has some excellent language features, if you want to engage in professional competitive programming, it is better to drop the obsession with Python and learn C++.↵
↵
↵
# References↵
↵
[^1]: PyRival. https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/bootstrap.py↵
