如何优化大数模式筛选算法？目标提速10倍及支持1e15级运算

DevOps 小满

2026-6-18

问题描述

我需要开发一个算法筛选含特定模式的大数（例如101010101010101这类数字）。目前处理1亿条数据耗时4-5秒，其中约9950万条会被过滤。我的目标是能处理1e15级别的数据，同时把1亿数据的处理耗时降到0.4秒以内。我已经尝试了多线程优化、将int替换为unsigned long long等手段，让代码提速了约10倍，但还需要至少再提速10倍。也可以更换开发语言，希望得到帮助。

当前代码

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <windows.h>

#define NUM_THREADS 8
#define MAX_NUM 100000ULL  

typedef struct {
    unsigned long long int start;
    unsigned long long int end;
    unsigned long long int count;
} ThreadData;

// 检查是否存在连续递增或递减的数位
bool has_consecutive_digits(const char* password, int length) {
    int len = strlen(password);
    for (int i = 0; i <= len - length; i++) {
        bool increasing = true, decreasing = true;
        for (int j = 0; j < length; j++) {
            if (password[i+j] != password[i] + j) increasing = false;
            if (password[i+j] != password[i] - j) decreasing = false;
        }
        if (increasing || decreasing) return true;
    }
    return false;
}

// 检查是否存在重复次数过多的数位
bool has_repeated_digits(const char* password, int max_repeats) {
    int counts[10] = {0};
    int len = strlen(password);
    for (int i = 0; i < len; i++) {
        counts[password[i] - '0']++;
        if (counts[password[i] - '0'] > max_repeats) return true;
    }
    return false;
}

// 检查是否存在回文模式
bool has_palindromic_pattern(const char* password, int length) {
    int len = strlen(password);
    for (int i = 0; i <= len - length; i++) {
        bool is_palindrome = true;
        for (int j = 0; j < length / 2; j++) {
            if (password[i+j] != password[i+length-1-j]) {
                is_palindrome = false;
                break;
            }
        }
        if (is_palindrome) return true;
    }
    return false;
}

// 检查是否包含常见模式子串
bool is_substring_of_common_patterns(const char* password) {
    const char* common_patterns[] = {
        "123456", "654321", "111111", "222222", "333333",
        "012345", "543210", "987654", "000000", "999999"
    };
    for (int i = 0; i < 10; i++) {
        if (strstr(password, common_patterns[i])) return true;
    }
    return false;
}

// 检查是否存在交替数位模式
bool has_alternating_digits(const char* password, int length) {
    int len = strlen(password);
    for (int i = 0; i <= len - length; i++) {
        bool valid = true;
        for (int j = 0; j < length; j++) {
            if ((j % 2 == 0 && password[i+j] != password[i]) ||
                (j % 2 == 1 && password[i+j] == password[i])) {
                valid = false;
                break;
            }
        }
        if (valid) return true;
    }
    return false;
}

// 检查是否存在连续的递增/递减块
bool has_increasing_or_decreasing_blocks(const char* password, int block_size) {
    int len = strlen(password);
    for (int i = 0; i <= len - block_size; i += block_size) {
        if (has_consecutive_digits(password + i, block_size)) return true;
    }
    return false;
}

// 检查是否存在镜像块
bool has_mirrored_blocks(const char* password, int block_size) {
    int len = strlen(password);
    for (int i = 0; i <= len - 2 * block_size; i += block_size) {
        bool mirrored = true;
        for (int j = 0; j < block_size; j++) {
            if (password[i + j] != password[i + block_size * 2 - 1 - j]) {
                mirrored = false;
                break;
            }
        }
        if (mirrored) return true;
    }
    return false;
}

// 检查数字是否包含过简单的模式
bool is_pattern_too_simple(const char* password) {
    return has_consecutive_digits(password, 3) ||
           has_repeated_digits(password, 1) ||
           has_palindromic_pattern(password, 4) ||
           is_substring_of_common_patterns(password) ||
           has_alternating_digits(password, 4) ||
           has_increasing_or_decreasing_blocks(password, 2) ||
           has_mirrored_blocks(password, 4);
}

// 验证数字是否合法（不包含简单模式）
bool is_valid_password(const char* password) {
    return !is_pattern_too_simple(password);
}

DWORD WINAPI check_passwords(LPVOID arg) {
    ThreadData* data = (ThreadData*)arg;
    char password[7];  // 存储6位数字+结束符
    data->count = 0;

    for (unsigned long long int i = data->start; i < data->end; i++) {
        sprintf(password, "%06llu", i);  // 生成6位数字字符串
        if (is_valid_password(password)) {
            data->count++;
        }
    }

    return 0;
}

int main() {
    HANDLE threads[NUM_THREADS];
    ThreadData thread_data[NUM_THREADS];
    unsigned long long int range = MAX_NUM / NUM_THREADS;
    unsigned long long total_count = 0;

    // 创建线程
    for (int i = 0; i < NUM_THREADS; i++) {
        thread_data[i].start = i * range;
        thread_data[i].end = (i + 1) * range;
        threads[i] = CreateThread(NULL, 0, check_passwords, &thread_data[i], 0, NULL);
        if (threads[i] == NULL) {
            fprintf(stderr, "Error creating thread %d\n", i);
            return 1;
        }
    }

    // 等待线程完成并汇总结果
    for (int i = 0; i < NUM_THREADS; i++) {
        WaitForSingleObject(threads[i], INFINITE);
        DWORD exit_code;
        if (GetExitCodeThread(threads[i], &exit_code)) {
            total_count += thread_data[i].count;
        } else {
            fprintf(stderr, "Error getting thread exit code %d\n", i);
        }
        CloseHandle(threads[i]);
    }

    // 输出合法数字总数
    printf("Anzahl der gültigen Zahlen: %llu\n", total_count);

    return 0;
}

优化建议

彻底移除字符串转换：当前最大性能瓶颈是sprintf的字符串转换及后续字符串操作。直接通过取模、除法运算提取数字的每一位，完全避免字符串的内存分配与操作开销，这能至少节省50%以上的耗时。
调整检查顺序：在is_pattern_too_simple中，把触发概率最高的检查（比如has_repeated_digits，毕竟99.5%的数据会被过滤）放在最前面，利用逻辑或的短路特性，提前终止不必要的后续检查。
用数学运算替代字符串匹配：把常见模式（如123456、111111）转换成数字，直接通过数学方法判断数字是否包含这些连续数位。比如检查三位连续数位时，直接提取三位数字判断是否满足递增/递减关系，而非调用字符串处理函数。
SIMD指令集优化：利用x86平台的SSE/AVX指令集，批量处理多个数字的数位检查，同时对多组数字进行模式判断，大幅提升并行处理效率。
从过滤转向生成合法数：由于合法数字占比仅0.5%，直接通过组合数学生成所有符合要求的数字，而非遍历所有数再过滤。这种方式处理1e15级数据时，无需遍历海量无效数据，效率会指数级提升。
开启编译器最高优化：编译时添加-O3选项，让编译器进行循环展开、函数内联、死代码消除等深度优化，能带来显著的性能提升。
更换语言的选择：如果继续使用编译型语言，C++的模板元编程和高效标准库可以进一步优化；Rust的零成本抽象和安全并发模型，性能接近C且能简化并行逻辑的开发。

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