假設(shè)我們有一個(gè)1億個(gè)數(shù)據(jù)，其中數(shù)據(jù)的范圍是0~1億，也就是100M的數(shù)據(jù)。但是這個(gè)數(shù)組中丟了一些數(shù)據(jù)，比如說(shuō)少了5啊，少了10啊，那么有什么辦法可以把這些丟失的數(shù)據(jù)找回來(lái)呢？這個(gè)題目不難，但是它可以幫助我們拓展思路，不斷提高算法的運(yùn)行效率。

對(duì)于這個(gè)問(wèn)題，我們一個(gè)最簡(jiǎn)單的思路就是對(duì)各個(gè)數(shù)據(jù)進(jìn)行flag判斷，然后依次輸出數(shù)據(jù)。

void get_lost_number(int data[], int length)  
{  
    int index;  

    assert(NULL != data && 0 != length);  
    unsigned char* pFlag = (unsigned char*)malloc(length * sizeof(unsigned char));  
    memset(pFlag, 0, length * sizeof(unsigned char));  

    for(index = 0; index < length; index ++){  
        if(0 == pFlag[data[index]])  
            pFlag[data[index]] = 1;  
    }  

    for(index = 0; index < length; index++){  
        if(0 == pFlag[index])  
            printf("%d\n", index);  
    }  

    free(pFlag);  
    return;  
}  

可能朋友也看到了，上面的代碼需要分配和原來(lái)數(shù)據(jù)一樣length的空間。其實(shí)我們可以用bit進(jìn)行訪問(wèn)標(biāo)志的設(shè)定，所以我們申請(qǐng)的空間還可以減少。

void get_lost_number(int data[], int length)  
{  
    int index;  

    assert(NULL != data && 0 != length);  
    unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3);  
    memset(pFlag, 0, length * sizeof(unsigned char));  

    for(index = 0; index < length; index ++){  
        if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))  
            pFlag[data[index] >> 3] |= 1 << (data[index] % 8);  
    }  

    for(index = 0; index < length; index++){  
        if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))  
            printf("%d\n", index);  
    }  

    free(pFlag);  
    return;  
}  

上面的代碼已經(jīng)在空間上面有所減小，那么有什么辦法并行運(yùn)算這些數(shù)據(jù)呢？

void get_lost_number(int data[], int length)  
{  
    int index;  
    RANGE range[4] = {0};  

    assert(NULL != data && 0 != length);  
    unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3);  
    memset(pFlag, 0, length * sizeof(unsigned char));  

    range[0].start = 0,               range[0].end = length >> 2;  
    range[1].start = length >> 2 ,    range[1].end = length >> 1;  
    range[2].start = length >> 1 ,    range[2].end = length >> 2 * 3;  
    range[3].start = length >> 2 * 3, range[3].end = length;  

#pragma omp parallel for  
    for(index = 0; index < 4; index ++){  
        _get_lost_number(data, range[index].start, range[index].end, pFlag);  
    }  

    for(index = 0; index < length; index++){  
        if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))  
            printf("%d\n", index);  
    }  

    free(pFlag);  
    return;  
}  

為了多核的并行計(jì)算，我們添加了子函數(shù)_get_lost，我們進(jìn)一步補(bǔ)充完整。

typedef struct _RANGE  
{  
    int start;  
    int end;  
}RANGE;  

void _get_lost_number(int data[], int start, int end, unsigned char pFlag[])  
{  
    int index;  

    for(index = start; index < end; index++){  
        if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))  
            pFlag[data[index] >> 3] |= 1 << (data[index] % 8);  
    }  
}  

工作總結(jié)：

(1）代碼的優(yōu)化是可以不斷進(jìn)行得，但是不見(jiàn)得適用于所有的場(chǎng)景

(2）目前的cpu已經(jīng)開(kāi)始從2核->4核->8核轉(zhuǎn)變，朋友們?cè)诳赡艿那闆r下盡量多掌握一些多核編程的知識(shí)。