我有一个大的数组A,大小为[0,8388608]的“相对较小”的整数A [i] = [0,131072],我想找到每个N = 32个元素中最常出现的元素。
什么会更快,
A.创建一个大小为131072的关联数组B,迭代32个元素,递增B [A [i]],然后迭代B,找到最大值,将B中的所有元素重置为0,重复| A | / 32次。
B. qsort每32个元素,找到A [i] == A [i-1]的最大范围(因此也是最常见的元素),重复| A | / 32次。
(编辑)C。别的。
可以对第一种方法进行改进。 没有必要迭代B.它可以是一个大小为131072的数组
每次增加B[A[i]]
,请查看该单元格中的新值。 然后,拥有一个全局highest_frequency_found_far
。 这从零开始,但在每次增量之后,应将新值与此全局值进行比较。 如果它更高,则全局被替换。
您还可以拥有全局值value_that_was_associated_with_the_highest_count
for each block of 32 members of A ... { size_t B [131072] = {0,0,...}; size_t highest_frequency_found_so_far = 0; int value_associated_with_that = 0; for(a : A) { // where A just means the current 32-element sub-block const int new_frequency = ++B[a]; if (new_frequency > highest_frequency_found_so_far) { highest_frequency_found_so_far = new_frequency; value_associated_with_that = a; } } // now, 'value_associated_with_that' is the most frequent element // Thanks to @AkiSuihkonen for pointing out a really simple way to reset B each time. // B is big, instead of zeroing each element explicitly, just do this loop to undo // the ++B[a] from earlier: for(a : A) { --B[a]; } }
什么是btree? 您最多只需要32个节点,并且可以预先声明它们。
以上就是c/c++开发分享C中每N个元素中最常见的相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/549623.html