预计算与查表法：用空间换时间

说到性能优化，有个老生常谈但极其有效的招数——预计算与查表法。说白了，就是把那些计算起来费劲、调用又频繁的结果，提前算好存起来。用的时候直接取，不用再算一遍。

我刚开始做嵌入式开发时，总觉得内存是稀缺资源，能省则省。后来在一个电机控制项目里，被三角函数拖慢了整个控制周期，才真正体会到什么叫「该花的钱不能省」。嗯，今天我们就聊聊这个。

核心思想：空间换时间

查表法的本质很简单：用存储空间换取计算时间。

你想想看，有些计算虽然数学上不复杂，但每次调用都要走一遍完整的运算流程。比如三角函数、CRC校验、素数判定。如果这些函数在程序里被调用了成千上万次，那累积的时间开销就很可观了。

预计算的思路就是：在程序初始化阶段，或者编译阶段，把结果算好存到数组里。运行时直接索引取值，复杂度从 O(n) 甚至 O(n²) 降到 O(1)。

案例一：预计算三角函数表

我在一个无刷电机FOC控制项目里遇到过这个问题。控制算法里要频繁计算 sin 和 cos，每次调用标准库函数，少说几十个微秒。控制周期只有100微秒，根本扛不住。

解决方案很简单：预计算一个正弦表。

// 预计算正弦表，精度0.1度
#define TABLE_SIZE 3600  // 0~359.9度
float sin_table[TABLE_SIZE];

void init_sin_table(void) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        float angle = i * 0.1f * 3.14159265f / 180.0f;
        sin_table[i] = sinf(angle);
    }
}

// 查表获取sin值
inline float fast_sin(float degree) {
    int idx = (int)(degree * 10.0f) % TABLE_SIZE;
    return sin_table[idx];
}

查表比调用 sinf() 快了将近20倍。代价呢？3600个float，大约14KB内存。对于现在的MCU来说，这点空间完全值得。

案例二：CRC查表法

CRC校验在通信协议里太常见了。Modbus、CAN、以太网，到处都有它的身影。标准CRC算法是逐位计算的，每个字节要循环8次。数据量一大，CPU就吃不消。

查表法是怎么做的？把每个字节对应的CRC结果提前算好。查一次表，相当于算完一个字节。

// CRC-16查表法
uint16_t crc16_table[256];

void init_crc16_table(void) {
    for (int i = 0; i < 256; i++) {
        uint16_t crc = i;
        for (int j = 0; j < 8; j++) {
            if (crc & 0x0001)
                crc = (crc >> 1) ^ 0xA001;
            else
                crc >>= 1;
        }
        crc16_table[i] = crc;
    }
}

uint16_t crc16_compute(uint8_t *data, uint16_t len) {
    uint16_t crc = 0xFFFF;
    for (uint16_t i = 0; i < len; i++) {
        uint8_t index = (crc ^ data[i]) & 0xFF;
        crc = (crc >> 8) ^ crc16_table[index];
    }
    return crc;
}

你看，每个字节只需要一次查表、一次异或、一次移位。比逐位计算快了8倍以上。我曾经在一个CAN总线项目中，把CRC计算从主循环里解放出来，整个系统的实时性提升了一大截。

案例三：素数表

素数判定在加密算法、哈希表设计里经常用到。最笨的办法是从2试除到sqrt(n)，复杂度O(√n)。如果只是偶尔判断一两个数还好，但如果你要生成一个素数池，或者频繁检查大数，那就太慢了。

我的做法是：预先生成一个素数表，用筛法把一定范围内的素数全部算出来。

// 预计算10000以内的素数表
#define MAX_NUM 10000
#define PRIME_COUNT 1229  // 10000以内有1229个素数

int prime_table[PRIME_COUNT];
bool is_prime[MAX_NUM + 1];

void init_prime_table(void) {
    // 埃拉托斯特尼筛法
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    
    for (int i = 2; i * i <= MAX_NUM; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= MAX_NUM; j += i)
                is_prime[j] = 0;
        }
    }
    
    int idx = 0;
    for (int i = 2; i <= MAX_NUM; i++) {
        if (is_prime[i])
            prime_table[idx++] = i;
    }
}

// O(1)判断素数
inline int is_prime_number(int n) {
    if (n <= MAX_NUM)
        return is_prime[n];
    // 超出范围，用素数表辅助判定
    for (int i = 0; i < PRIME_COUNT && prime_table[i] * prime_table[i] <= n; i++) {
        if (n % prime_table[i] == 0)
            return 0;
    }
    return 1;
}

这个表只有1229个int，不到5KB。但换来的是O(1)的素数判定速度。对于10000以内的数，查表比试除法快了上百倍。

查表法的设计原则

做了这么多年优化，我总结了几条查表法的设计原则：

1. 表的大小要合理：不是越大越好。根据精度需求和内存限制，找到平衡点。
2. 索引计算要快：查表本身不能太慢。如果索引计算比直接计算还复杂，那就得不偿失了。
3. 考虑缓存友好：表尽量连续存放，避免随机访问导致缓存miss。对于大表，可以考虑分块。
4. 初始化时机：可以在编译时生成（用脚本），也可以在运行时初始化。运行时初始化要注意启动时间。
5. const关键字：如果表在运行时不改变，加上const，让编译器优化到flash/ROM中。

查表法的变种：混合策略

有时候，纯查表法太占内存，纯计算又太慢。这时候可以折中一下：部分预计算 + 运行时计算。

举个例子，我曾经做过一个音频处理算法，需要计算大量指数函数。如果全用查表，表太大；全用计算，速度太慢。最后我用了查表+线性插值的方案：

• 预计算256个点的指数值
• 查表得到相邻两个点的值
• 用线性插值得到精确结果

这样，精度达到了0.1%，速度比直接计算快了15倍，内存只用了1KB。嗯，这就是工程上的权衡。

SVG：预计算与查表法知识体系

避坑指南

查表法虽然好用，但也不是银弹。我踩过几个坑，分享给你：

• 表太大导致缓存miss：我曾经做了一个16KB的查找表，结果频繁的随机访问导致CPU缓存命中率暴跌，性能反而下降了。后来把表拆成小块，按需加载，才解决问题。
• 浮点数索引陷阱：用浮点数做索引时要小心精度问题。比如 0.1 在二进制里是无限循环小数，直接取整可能得到错误结果。建议用整数索引，或者先做四舍五入。
• 初始化时间被忽略：有些嵌入式系统对启动时间有严格要求。如果表很大，初始化可能占用几百毫秒。我建议在编译时用脚本生成表，直接烧录到flash里。
• 多线程安全问题：如果表在运行时被修改（比如动态更新），要注意加锁或使用原子操作。不过大多数情况下，查表法都是只读的，不存在这个问题。

好了，关于预计算与查表法，就聊这么多。记住一句话：能用空间解决的问题，尽量别用时间。在嵌入式世界里，时间往往比空间更宝贵。