Jinyue Chen

My awesome biography constrained to a sentence or two goes here.

1 minute read

常数优化虽然在普通算法题里并非必要，但在刁钻的题目和未来大数据计算节省性能时很重要，因此结合目前刷的题目整理了一些常用技巧：

1. 快速 I/O

场景示例：在输入规模达到几十万甚至上百万时，例如：

  • 题目要求读取 10^6 个整数并统计出现频率。
  • 如果使用默认输入方式（如 Python 的 input() 或 C++ 的同步 iostream），会因为频繁系统调用导致 TLE。

伪代码：

initialize buffer
function fast_read():
read from buffer directly

2. 用数组代替映射

场景示例：

  • 频率统计题：输入一个长度为 10^5 的数组，数值范围只有 0~10000。
  • 若使用哈希表存储频率，每次查找都有额外开销；
  • 改用数组直接下标访问，可以大幅减少常数。

伪代码：

count = array of size [max_value+1] initialized to 0
for each number x in input:
count[x] += 1

3. 前缀和 / 预处理表

场景示例：

  • 多次查询区间和，例如：给定数组，要求回答 10^5 次区间 [l,r] 的总和。
  • 如果每次循环计算，复杂度太高；
  • 使用前缀和预处理后，查询只需 O(1)，节省大量常数。

伪代码：

prefix[0] = 0
for i in 1..n:
prefix[i] = prefix[i-1] + arr[i]
answer query(l,r) = prefix[r] - prefix[l-1]

4. 避免循环内重复调用函数

场景示例：

  • 在循环中反复调用 length(arr)、pow(x,2) 或类似函数。
  • 当循环次数达到 10^6 时，这些调用的开销不可忽视。
  • 将不变的结果提前存入变量，可显著降低常数。

伪代码：

n = length(arr)
for i in 1..n:
use arr[i] without calling length() repeatedly

5. 减少不必要的拷贝

场景示例：

  • 递归或分治题目中，传递子数组时如果用切片，会不断产生新数组。
  • 在 Python 或 Java 中，这类拷贝可能导致性能大幅下降。
  • 改为传索引范围，避免重复开销。

伪代码：

function process(arr, left, right):
operate on arr between [left,right] without creating subarray

6. 注意访问顺序（缓存友好）

场景示例：

  • 矩阵题目：例如对 1000x1000 的二维数组进行遍历求和。
  • 如果按列优先访问，会频繁跳转内存行，缓存不命中率高。
  • 按行优先访问，与内存存储顺序一致，能大幅降低常数。

伪代码：

for i in 1..rows:
for j in 1..cols:
access matrix[i][j] in row-major order

7. 用位运算替代取模或分支

场景示例：

  • 判断数字奇偶：在循环 10^7 次的题目中，x % 2 的开销比 x & 1 更大。
  • 统计满足条件的数量时，用布尔表达式转整数可以避免 if-else 分支。

伪代码：

if (x & 1) then mark as odd
count += (condition is true ? 1 : 0)

8. 容器预分配

场景示例：

  • 在动态增长的数组或字符串拼接场景（例如构造一个长结果字符串）。
  • 如果不预分配，每次扩容都可能触发重新分配和拷贝。
  • 提前分配好容量，可以显著减少常数。

伪代码：

initialize array with reserved size n
for i in 1..n:
array[i] = value

You May Also Enjoy