C-数组出现次数算法

C-数组出现次数算法

虐人心 发布于 2016-12-09 字数 264 浏览 1197 回复 4

100个数组,每个数组里面的元素个数有10万个。元素值的范围是1到1千万之间的自然数。求在这100个数组里出现次数大于等于2次的自然数,以及他们出现的次数。要求尽量用并行算法。

补充一:一次计算100个数组。为了提高并行,可以同时进行多次计算。
补充二:数组内的元素是有序的。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

归属感 2017-10-05 4 楼

因数组内的元素是有序的,完全可以用一个数组来实现,在遍历数组的时候保存两个值:一个是数组中的一个数字,一个是次数。当我们遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则次数加1。否则对下一个数字进行统一。

瑾兮 2017-09-26 3 楼

这是一个典型模式的按照循环数值进行任务切分的并行计算问题,具体方法如下:
1. 找出100个数组中的最大和最小值分别记为Ma和Min,因为数组是有序的,所以只有在数组和头和尾进行比较即可。
2. 设step=10000,对Mi和Ma区间进行任务切分,step取值是调整并行算法效率的参数之一,可以参照并行算法的理论进行优化。具体的参照如下伪代码:

for(i=Mi; i<=Ma; i+=step){
thread_task(i, step);
}
//如上的thread_task(i, step)是寻找100个数组中数值在限制区间[i, i+step)内的结果

3. 将第二步的每个子任务的输出结果合并到一个结果文件中即是最终的结果,因为分区是不交的,所以可以简单的根据子任务的区间序号,把他们的结果从小到大合并到一起即可。

对于thread_task的具体实现,可以考虑用堆排序的方法,首先根据限制区间找到每个数组的工作区间,即数值在限制区间内的最长子数组,因为数组是有序的,所以可以用二分法很快地计算出工作子数组。然后对每个数组设置一个当前操作位置指针,开始的位置设在工作区间的最左边。然后根据每个数组的当前位置的数值,将他们放到堆中,如果数值一样,则放到相同的节点上。然后取出堆内的最小节点,如果该节点放置了多个数组,则该节点的数值就写入结果中,放置的数组个数就是重复的个数。对取出的数组将当前操作指针右移后,重新放入堆中,如果数组的工作区间已经处理完,则该数组不再放入堆中。重复以上步骤直到堆空为止。在具体实现时,需要考虑在一个数组中一个数值会重复出现多次的情况,对于这种特殊情况,只要在数组操作指针移位时考虑到,并且在堆节点上多增加一个计数器就可以很容易的解决。

(注:以上为了记述方便假设数组都是从小到大排列的)

偏爱自由 2017-07-21 2 楼

记四个数组分别为a,b,c,d,每个数组均为降序,i,j,k,l分别为遍历四个数组的当前下标,算法流程如下:
第一步:声明一个map用来保存统计结果,key为数组中的元素,value元素出现的次数,置i,j,k,l=0;
第二步:求出a[i],b[j],c[k],d[l]四个元素的最大值,若c[k]是最大的,则map[c[k]]++,k++;
重复第二步,直至所有的元素遍历完毕,map值大于等于2的key/value即为想要的结果;
暂时想到就这些,等有时间再补充。

夜无邪 2017-02-10 1 楼

归并算法,将这些数组保存到文件中,以每个元素作为一列,然后再两两文件进行归并运算并保存到一个新文件里,文件第一列为数组元素,第二列为元素对应出现的次数,依次归所有文件,最后就可以得出所有出现次数大于等于2次的自然数,以及他们出现的次数。

可同时进行多路归并,提高运行效率。