C语言快速提取仅含字母数字的有效子串的优化方法

• 单次循环内多次执行O(n)操作：每次循环都调用wcslen计算当前有效字符串长度，随着有效字符增多，这一步的耗时线性增长，整体时间复杂度达到O(n²)，是性能下降的核心原因
• 频繁堆内存重分配：每新增一个字符就调用一次realloc，堆内存分配/重分配本身有固定开销，频繁操作还会加剧内存碎片，进一步降低性能
• 冗余的字符串拼接操作：用wcscat拼接单个字符，内部会重复执行找末尾、拷贝的逻辑，完全可以用直接指针赋值替代

1. 预计算有效字符长度：先遍历一遍源字符串，统计连续有效字符的总长度，一次性分配对应大小的内存，完全避免频繁realloc
2. 用计数变量替代wcslen：单独维护写入位置的偏移量，不需要每次遍历已生成的字符串
3. 直接赋值字符：无需调用字符串拼接函数，直接给目标字符串对应位置赋值即可

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <wchar.h>

// 对应原validstr功能
wchar_t* validstr_optimized(wchar_t* src, wchar_t* cc, unsigned int* index) {
    // 第一步：统计连续有效字符长度
    unsigned int len = 0;
    unsigned int temp_idx = *index;
    wchar_t temp_cc = *cc;
    while (iswalpha(temp_cc) || iswdigit(temp_cc)) {
        len++;
        temp_idx++;
        temp_cc = src[temp_idx];
    }
    if (len == 0) {
        wchar_t* empty = calloc(1, sizeof(wchar_t));
        return empty;
    }
    // 一次性分配内存，多留一位存终止符
    wchar_t* valid = malloc((len + 1) * sizeof(wchar_t));
    // 第二步：拷贝有效字符
    for (unsigned int i = 0; i < len; i++) {
        valid[i] = src[*index + i];
    }
    valid[len] = L'\0';
    // 更新index和current char
    *index += len;
    *cc = src[*index];
    return valid;
}

// 对应原validstr2功能
wchar_t* validstr2_optimized(wchar_t* src) {
    if (src == NULL) return NULL;
    // 第一步：统计连续有效字符长度
    wchar_t* p = src;
    while (iswalpha(*p) || iswdigit(*p)) {
        p++;
    }
    unsigned int len = p - src;
    if (len == 0) {
        wchar_t* empty = calloc(1, sizeof(wchar_t));
        return empty;
    }
    // 一次性分配内存拷贝
    wchar_t* valid = malloc((len + 1) * sizeof(wchar_t));
    wcsncpy(valid, src, len);
    valid[len] = L'\0';
    return valid;
}

int main() {
    wchar_t* str = L"valid10+(notvalidanymore";

    // validstr_optimized 用法
    wchar_t current = str[0];
    unsigned int index = 0;
    wchar_t* res1 = validstr_optimized(str, &current, &index);
    printf("%ls\n", res1);
    free(res1); // 注意用完释放内存，原代码也存在内存泄漏问题，优化版同样需要调用方释放

    // validstr2_optimized 用法
    wchar_t* res2 = validstr2_optimized(str);
    printf("%ls\n", res2);
    free(res2);

    return 0;
}

• 原代码使用的isalpha/isdigit是针对单字节字符的函数，处理宽字符应该用iswalpha/iswdigit，否则会出现非ASCII字符判断错误的问题，优化版已修正
• 原实现存在内存泄漏风险，返回的堆内存需要调用方手动free，优化版保留了相同的内存管理逻辑，使用完记得释放即可
• 优化后的实现时间复杂度为O(n)，长字符串场景下性能提升会非常明显，没有冗余的内存操作和遍历操作

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