C:高效地循环大数组
C:高效地循环大数组
提问于 2012-10-15 20:38:15
我有一个包含大约500个数字的主列表整数数组。而且，我有一组100个随机化的数字，它是从主列表中挑选出来的，用来寻找丢失的数字。现在，我需要根据主列表来检查这个随机数字列表。在C编程中，最好的方法是在不挂起程序的情况下通过它。如果我在简单的' for‘循环中遍历500个元素，它将挂起，因为它需要遍历整个列表。有人能在这上面给我指路吗？
谢谢。
回答 2
Stack Overflow用户
回答已采纳
发布于 2012-10-15 20:51:46
首先，您应该对其进行分析。我们所说的是最大限度的500*100=50,000操作。一台普通的现代计算机能够在不到十分之一秒的时间内完成它，除非你的编码效率非常低。
假设您想要对其进行优化，则应该对主数组进行排序，并在其上为随机数组的每个元素运行binary search。这将把操作的数量从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;
}Stack Overflow用户
发布于 2012-10-15 21:07:00
N-随机数组长度。
M- Masterlist数组长度。
- 对随机数组进行排序。在排序数组中对主列表中的每个元素进行n*log(n)
- Binary搜索。因此，您将拥有所有缺少的元素。(m)*log(n)
整个操作的log (m+n) * => (N)。借助n=100和m=500，我们已经
600 * log(100)日志到基数2
与使用原始编码的50000次迭代相比，大约有3986次迭代。
PS:如果两个数组都排序，那么只需要比较O(m)就足够了。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12895843
复制相关文章
相似问题
腾讯云开发者
