C语言银行交易总额查询程序百万级数据超时问题求助

问题根源 #

原代码采用双重循环遍历处理查询，时间复杂度为O(N*M)（N为交易记录数，M为查询数）。当N和M均达到1e6时，总操作量高达1e12次，完全超出时间限制。此外，scanf/printf的默认IO效率不足以应对百万级数据的读写，进一步拖慢了程序运行速度。

核心优化：哈希表预存账户累计转出金额 #

提前遍历所有交易数据，用哈希表构建转出账户→累计转出金额的映射，后续每个查询直接查表即可，时间复杂度降至O(N+M)，这是解决百万级数据查询的最优方案。

简易哈希表实现示例 #

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 哈希表节点结构
typedef struct HashNode {
    char account[21];
    int total;
    struct HashNode* next;
} HashNode;

// 哈希函数：将账户字符串转为哈希值
unsigned int hash(const char* str) {
    unsigned int hash_val = 0;
    while (*str) {
        hash_val = hash_val * 31 + *str++;
    }
    return hash_val % 100003; // 用大质数作为哈希表大小，减少冲突
}

// 插入哈希表，累计账户转出金额
void hash_insert(HashNode** table, const char* account, int money) {
    unsigned int idx = hash(account);
    HashNode* p = table[idx];
    
    // 查找已有账户，累加金额
    while (p) {
        if (strcmp(p->account, account) == 0) {
            p->total += money;
            return;
        }
        p = p->next;
    }
    
    // 无该账户则新建节点
    HashNode* new_node = (HashNode*)malloc(sizeof(HashNode));
    strcpy(new_node->account, account);
    new_node->total = money;
    new_node->next = table[idx];
    table[idx] = new_node;
}

// 查询账户累计转出金额
int hash_query(HashNode** table, const char* account) {
    unsigned int idx = hash(account);
    HashNode* p = table[idx];
    while (p) {
        if (strcmp(p->account, account) == 0) {
            return p->total;
        }
        p = p->next;
    }
    return 0; // 无匹配账户返回0
}

// 销毁哈希表释放内存
void hash_destroy(HashNode** table) {
    for (int i = 0; i < 100003; i++) {
        HashNode* p = table[i];
        while (p) {
            HashNode* tmp = p;
            p = p->next;
            free(tmp);
        }
    }
    free(table);
}

// 优化输入：整行读取后解析，减少IO系统调用
void read_transactions(HashNode** table) {
    char buf[1024];
    while (fgets(buf, sizeof(buf), stdin)) {
        buf[strcspn(buf, "\n")] = '\0'; // 去除换行符
        if (strcmp(buf, "#") == 0) break;
        
        char fAccount[21];
        int money;
        // 只读取需要的转出账户和金额，丢弃其他无关字段
        sscanf(buf, "%*s %*s %d %*s %*s", fAccount, &money);
        hash_insert(table, fAccount, money);
    }
}

// 处理查询
void process_queries(HashNode** table) {
    char buf[1024];
    while (fgets(buf, sizeof(buf), stdin)) {
        buf[strcspn(buf, "\n")] = '\0';
        if (strcmp(buf, "#") == 0) break;
        
        char account[21];
        sscanf(buf, "%*s %s", account);
        printf("%d\n", hash_query(table, account));
    }
}

int main() {
    HashNode** hash_table = (HashNode**)calloc(100003, sizeof(HashNode*));
    read_transactions(hash_table);
    process_queries(hash_table);
    hash_destroy(hash_table);
    return 0;
}

辅助优化：提升IO效率 #

1. 替换scanf/printf：用fgets整行读取后再用sscanf解析，减少系统调用次数
2. 批量输出：可将查询结果先存入缓冲区，再通过fwrite批量输出，进一步降低IO开销
3. 丢弃无关字段：读取交易数据时，只保留转出账户和金额，忽略转入账户、交易时间、ATM编号，节省内存和解析时间

备选方案：排序+二分查找 #

若无法使用哈希表，可采用排序+二分查找的方案，时间复杂度为O(N log N + M log N)：

1. 将交易记录按转出账户字符串排序（用qsort自定义比较函数）
2. 对每个查询账户，用bsearch找到第一个匹配的位置，向后遍历直到账户不匹配，累加金额

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