返回首页 一步一步写算法

寻找丢失的数

假设我们有一个1亿个数据,其中数据的范围是0~1亿,也就是100M的数据。但是这个数组中丢了一些数据,比如说少了5啊,少了10啊,那么有什么办法可以把这些丢失的数据找回来呢?这个题目不难,但是它可以帮助我们拓展思路,不断提高算法的运行效率。

对于这个问题,我们一个最简单的思路就是对各个数据进行flag判断,然后依次输出数据。

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;  
}  

可能朋友也看到了,上面的代码需要分配和原来数据一样length的空间。其实我们可以用bit进行访问标志的设定,所以我们申请的空间还可以减少。

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;  
}  

上面的代码已经在空间上面有所减小,那么有什么办法并行运算这些数据呢?

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;  
}  

为了多核的并行计算,我们添加了子函数_get_lost,我们进一步补充完整。

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);  
    }  
}  

工作总结:

(1)代码的优化是可以不断进行得,但是不见得适用于所有的场景

(2)目前的cpu已经开始从2核->4核->8核转变,朋友们在可能的情况下尽量多掌握一些多核编程的知识。

上一篇: prim算法 下 下一篇: 链表重合