C++中频繁创建销毁的对象如何存储序列比对得分表？

我正在实现自定义的两两（蛋白质/DNA/RNA）序列比对代码。针对蛋白质，有一个20×20的字符配对得分矩阵，比如(C,C)对应得分9。我打算用unordered_map存储所有配对（以拼接字符或元组为键）实现*O(1)*查找，但不确定这个map的创建时机和存储位置。

我定义的PairwiseAligner类如下：

class PairwiseAligner{
    std::string algorithm = "needleman_wunsch";
    std::string query_sequence;
    std::string target_sequence;

    int gap_penalty;
    int score;

    int **F;
    direction **pointers;
public:
    PairwiseAligner(){};
    void set_algorithm(std::string alg) {algorithm = alg;}
    std::string get_algorithm() {return algorithm;}
    void set_query(std::string query_) {query_sequence = query_;}
    std::string get_query(){return query_sequence;}
    void set_target(std::string target_) {target_sequence = target_;}
    std::string get_target(){return target_sequence;}

    void align(){
        if (query_sequence.size() == 0 || target_sequence.size() == 0) throw "query or target not set";

        const int n = query_sequence.size() + 1;
        const int m = target_sequence.size() + 1;

        // allocate memory for F and pointers
        F = new int*[n];
        for (auto t : F){
            new int[m];
        }

        pointers = new direction*[n];
        for (auto t : pointers){
            new direction[m];
        }

        if (algorithm.compare("needleman_wunsch")==0) needleman_wunsch();
    }

    void needleman_wunsch(){
        ... run algorithm ...
    }

    ~PairwiseAligner(){
        for (auto t : F){
            delete t;
        }
        delete F;

        for (auto t : pointers){
            delete t;
        }
        delete pointers;
    }
};

在PairwiseAligner::needleman_wunsch方法中需要进行N²次得分表查找，且该类对象会被频繁创建和销毁，次数可达1-2百万次。我考虑了三种方案，想寻求最优解：

• 方案1：将unordered_map放在单独.hpp文件中作为全局变量引入？
• 方案2：复用PairwiseAligner对象，根据序列大小重新分配二维数组F和pointers的内存？
• 方案3：其他方案？

方案分析与优化建议 #

得分矩阵存储：放弃unordered_map，用静态二维数组更高效

20×20的蛋白质得分矩阵总共只有400个条目，用unordered_map完全是冗余设计——哈希计算、冲突处理的开销远大于直接数组查表。更优的实现方式是：

1. 把氨基酸字符映射为0-19的整数（比如用一个静态数组char aa_list[] = "ACDEFGHIKLMNPQRSTVWY";，再用一个小的unordered_map<char, int>做字符到索引的映射，这个映射只初始化一次）
2. 用静态二维数组存储得分，比如BLOSUM62矩阵：

static const int blosum62[20][20] = {
    {4, -1, -2, -2, 0, -1, -1, 0, -2, -1, -1, -1, -1, -2, -1, 1, 0, -3, -2, 0},
    // 剩余行省略...
};

查找时直接通过索引访问：blosum62[aa_to_idx[a]][aa_to_idx[b]]，真正的*O(1)*且无额外开销。

如果坚持要用键值对，也应该用静态局部变量在第一次调用时初始化，避免全局变量的命名污染：

int get_aa_score(char a, char b) {
    static const std::unordered_map<std::string, int> score_map = [](){
        std::unordered_map<std::string, int> m;
        m["CC"] = 9;
        // 初始化所有配对得分
        return m;
    }();
    return score_map.at(std::string(1,a)+std::string(1,b));
}

静态局部变量只会初始化一次，所有PairwiseAligner对象复用同一个实例，效率远高于每个对象创建自己的map。

对象频繁创建销毁：优先复用PairwiseAligner对象

1-2百万次的对象构造/析构会带来巨大的内存开销，方案2是最优选择：

• 在类中添加私有成员int current_n = 0; int current_m = 0;，记录当前分配的F和pointers的大小
• 修改align方法，先检查现有内存是否满足当前序列的需求，不满足再重新分配，否则复用内存并重置内容：

void align(){
    if (query_sequence.empty() || target_sequence.empty()) throw "query or target not set";

    const int n = query_sequence.size() + 1;
    const int m = target_sequence.size() + 1;

    // 检查内存是否足够，不足则重新分配
    if (current_n < n || current_m < m) {
        // 释放旧内存
        if (F != nullptr) {
            for (int i = 0; i < current_n; ++i) delete[] F[i];
            delete[] F;
        }
        if (pointers != nullptr) {
            for (int i = 0; i < current_n; ++i) delete[] pointers[i];
            delete[] pointers;
        }
        // 分配新内存
        F = new int*[n];
        for (int i = 0; i < n; ++i) F[i] = new int[m]();
        pointers = new direction*[n];
        for (int i = 0; i < n; ++i) pointers[i] = new direction[m]();
        current_n = n;
        current_m = m;
    } else {
        // 复用内存时重置数据
        for (int i = 0; i < n; ++i) {
            memset(F[i], 0, sizeof(int)*m);
            // 重置pointers为默认方向，比如初始化为NONE或LEFT等
        }
    }

    if (algorithm == "needleman_wunsch") needleman_wunsch();
}

额外优化建议

• 用std::vector<std::vector<int>>代替int**，手动管理二维数组容易出现内存泄漏，vector会自动处理内存释放，代码更简洁可靠
• Needleman-Wunsch算法可以优化空间复杂度：只保留当前行和上一行，不需要存储整个二维数组，内存开销从O(NM)降到O(min(N,M))*，对于长序列来说能大幅减少内存占用

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