一步步寫算法：尋找丟失數字的多階段優化之路

問題背景

給定包含 1 億個整數的陣列，數值範圍 0~1 億，但其中缺失了部分數字。如何高效找出所有丟失的數字？本文將從基礎解法出發，逐步優化空間與時間效率，並引入多核並行計算。

第一階段：位元組標記法

最直觀的思路：分配與數據等長的標記陣列，遍歷輸入設置標記，再掃描輸出未標記索引。

void get_lost_number(int data[], int length) {
    assert(data != NULL && length > 0);
    unsigned char *pFlag = malloc(length * sizeof(unsigned char));
    memset(pFlag, 0, length);
    
    for (int i = 0; i < length; i++) {
        if (pFlag[data[i]] == 0) pFlag[data[i]] = 1;
    }
    for (int i = 0; i < length; i++) {
        if (pFlag[i] == 0) printf("%d\n", i);
    }
    free(pFlag);
}

空間複雜度：O(N) bytes。對於 1 億數據需約 100 MB。

第二階段：位圖優化

利用每個 byte 的 8 個 bit，將空間壓縮 8 倍：

void get_lost_number(int data[], int length) {
    assert(data != NULL && length > 0);
    unsigned char *pFlag = malloc((length + 7) >> 3);
    memset(pFlag, 0, (length + 7) >> 3);
    
    for (int i = 0; i < length; i++) {
        int idx = data[i] >> 3;
        int bit = data[i] & 7;
        if ((pFlag[idx] & (1 << bit)) == 0) 
            pFlag[idx] |= (1 << bit);
    }
    for (int i = 0; i < length; i++) {
        int idx = i >> 3;
        int bit = i & 7;
        if ((pFlag[idx] & (1 << bit)) == 0) 
            printf("%d\n", i);
    }
    free(pFlag);
}

空間複雜度：O(N/8) bytes。1 億數據僅需 ~12.5 MB。

第三階段：OpenMP 多核並行

現代 CPU 多核普及，將標記階段並行化：

typedef struct { int start, end; } RANGE;

void _get_lost_number(int data[], int start, int end, unsigned char pFlag[]) {
    for (int i = start; i < end; i++) {
        int idx = data[i] >> 3;
        int bit = data[i] & 7;
        if ((pFlag[idx] & (1 << bit)) == 0)
            pFlag[idx] |= (1 << bit);
    }
}

void get_lost_number(int data[], int length) {
    assert(data != NULL && length > 0);
    unsigned char *pFlag = malloc((length + 7) >> 3);
    memset(pFlag, 0, (length + 7) >> 3);
    
    RANGE ranges[4];
    ranges[0] = {0, length >> 2};
    ranges[1] = {length >> 2, length >> 1};
    ranges[2] = {length >> 1, (length >> 2) * 3};
    ranges[3] = {(length >> 2) * 3, length};
    
    #pragma omp parallel for
    for (int i = 0; i < 4; i++) {
        _get_lost_number(data, ranges[i].start, ranges[i].end, pFlag);
    }
    // 輸出階段保持串行（或可進一步並行）
    for (int i = 0; i < length; i++) { ... }
    free(pFlag);
}

注意：位圖操作涉及同一 byte 內不同 bit，若多線程操作相鄰索引可能發生緩存行爭用。實際部署時可考慮：

• 每線程使用私有位圖，最後合併
• 使用原子操作 __sync_fetch_and_or
• 將範圍劃分按 byte 對齊，減少偽共享

總結與思考

1. 算法優化無止境：從 O(N) 空間到 O(N/8)，再到並行加速，每一步都有適用場景
2. 多核編程是必修課：CPU 核心數持續增長，掌握 OpenMP、pthread、C++17 平行算法等技能至關重要
3. 大數據場景下的權衡：若 N 極大（超過記憶體），需考慮外部排序、布隆過濾器、分治+磁盤等方案