我刚刚编写了一个算法,该算法在输入整数数组中查找具有最大/最小出现次数的值。 我的想法是对数组进行排序(所有出现的顺序都是按顺序排列)并使用对来为每个值存储相应的出现次数。
它应该是O(nlogn)
复杂度,但我认为有一些常数乘数。 我该怎么做才能提高性能?
#include #include #include "e7_8.h" #define N 20 /*Structure for pair*/ typedef struct { int value; int freq; } VAL_FREQ; void get_freq(int *v, int n, int *most_freq, int *less_freq) { int v_i, vf_i, current_value, current_freq; VAL_FREQ* sp = malloc(n*sizeof(VAL_FREQ)); if(sp == NULL) exit(EXIT_FAILURE); mergesort(v,n); vf_i = 0; current_value = v[0]; current_freq = 1; for(v_i=1; v_i<n+1; v_i++) { if(v[v_i] == current_value) current_freq++; else{ sp[vf_i].value = current_value; sp[vf_i++].freq = current_freq; current_value = v[v_i]; current_freq = 1; } } /*Finding max,min frequency*/ int i, max_freq_val, max_freq, min_freq_val, min_freq; max_freq = sp[0].freq; max_freq_val = sp[0].value; min_freq = sp[0].freq; min_freq_val = sp[0].value; for(i=1; i max_freq) { max_freq = sp[i].freq; max_freq_val = sp[i].value; } if(sp[i].freq < min_freq) { min_freq = sp[i].freq; min_freq_val = sp[i].value; } } *most_freq = max_freq_val; *less_freq = min_freq_val; free(sp); }
让我们从你的算法已经是O(n * log(n))这一事实开始,因为每一步都是O(n),排序是O(n * log(n))。 如果它可以显着改善取决于您期望的输入类型。 编辑:除非,并且似乎是这种情况,它不是要求在过程结束时对值进行排序(无论如何通过值,而不是出现次数)的要求的一部分,在这种情况下不要错过Oli查尔斯沃思的答案。
实地有两个概念:第一个是你将获得多少样本(n); 第二个是它们的值“有多集中”,这些值可以分布的范围有多窄或多(w = MAX_VALUE – MIN_VALUE)。
如果n小于w(因此您的值很稀疏),那么您的方法已经是最优的并且几乎没有改进的空间。
但是如果w很小并且n很大,那么使用以下方法可以获得很多好处。
假设你知道你不能得到任何低于MIN_VALUE的值,也没有超过MAX_VALUE的值。 然后,您可以使用value作为收集频率的数组的索引。 这样,您跳过排序步骤(O(n * log(n))),并以O(n)计算频率。
int buffer_frequencies[MAX_VALUE - MIN_VALUE + 1]; //Now reset the array with some convenient function like memset int* value_frequencies = buffer_frequencies; value_frequencies -= MIN_VALUE; //Shift the beginning of the array, so that //you can use the value directly as the array index //You are allowed to use negative indexes for(v_i=0; v_i < n; v_i++) { value_frequencies[v[v_i]]++; }
或者甚至(可能是更快版本的for循环,但通常一个好的编译器已经在最有效的版本中转换它):
int* p_v = v; int* end_p_v = v+n; for(; p_v < end_p_v; p_v++) { value_frequencies[*p_v]++; }
请注意,此方法(两个版本)对输入值非常敏感,即如果得到的值超出MIN_VALUE或MAX_VALUE,则会破坏内存边界
然后是算法的第二部分:
//First cycle could be optimized, but it has no impact int i = MIN_VALUE; max_freq = value_frequencies[i]; max_freq_val = i; min_freq = value_frequencies[i]; min_freq_val = i; for(; i max_freq) ? i : max_freq_val; max_freq = (value_frequencies[i] > max_freq) ? value_frequencies[i] : max_freq; min_freq_val = (value_frequencies[i] < min_freq) ? i : min_freq_val; min_freq = (value_frequencies[i] < min_freq) ? value_frequencies[i] : min_freq; } }
使用哈希表来实现键值映射? 这应该给你O(n)预期的时间。 *
*但是,请注意,在最坏的情况下它是O(n 2 )。 只有当所有条目都散列到同一个存储桶时才会出现这种情况,并且您有效地最终会在每次迭代时搜索链接列表! 对于合适的散列表实现,发生这种情况的可能性非常低。
以上就是c/c++开发分享在整数数组中查找最大/最小出现次数相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/549999.html