c - C：有效循环大数组

Question

我有一个包含大约 500 个数字的主列表整数数组。而且，我有一组 100 个随机数字，这些数字是从主列表中挑选出来的，以查找丢失的数字。现在，我需要对照主列表检查这个随机数列表。在不挂起程序的情况下，C 编程中最好的方法是什么？如果我对 500 个元素进行简单的“for”循环，它将挂起，因为它需要遍历整个列表。有人可以指导我吗？

谢谢。

Answer 1

首先，您应该对其进行概要分析。我们所说的最多只有 500*100=50,000 次操作。一台普通的现代计算机能够在不到十分之一秒的时间内完成它，除非你的编码效率很低。

假设您无论如何都想优化它，您应该对主数组进行排序，并对随机数组的每个元素运行二进制搜索。这会将操作次数从 50,000 减少到最多 900，因为对 500 个数字进行二分查找最多需要 9 次比较。

这是一个使用标准 C 库的内置排序和二进制搜索函数（qsort和）的实现：bsearch

int less_int(const void* left, const void* right) {
    return *((const int*)left) - *((const int*)right);
}

int main(void) {
    size_t num_elements = 500;
    int* a = malloc(num_elements*sizeof(int));
    for(size_t i=0 ; i<num_elements ; i++) {
        a[i] = rand() % num_elements;
    }
    qsort(a, num_elements, sizeof(int), less_int);
    size_t num_rand = 100;
    int* r = malloc(num_rand*sizeof(int));
    for(size_t i=0 ; i < num_rand ; i++) {
        r[i] = rand() % num_rand;
    }

    for (size_t i = 0 ; i != num_rand ; i++) {
        int *p = (int*) bsearch (&r[i], a, num_elements, sizeof(int), less_int);
        if (p) {
            printf ("%d is in the array.\n", *p);
        } else {
            printf ("%d is not in the array.\n", r[i]);
        }
    }

    free(a);
    free(r);
    return 0;
}

这是ideone 上这个正在运行的程序的链接。

Answer 2

n - 随机数组长度。

m - 主列表数组长度。

1. 对随机数组进行排序。n*log(n)
2. 在排序数组中对主列表中的每个元素进行二进制搜索。因此，您将拥有所有缺失的元素。(m)*log(n)

=> (m+n) * log(n)表示整个操作。在n=100和m=500的情况下，我们有

600 * log(100)以 2 为底的日志

与原始编码的 50000 次迭代相比，大约 3986 次迭代。

PS：如果两个数组都已排序，只需比较 O(m) 就足够了。