C中每N个元素中最常见的
我有一个大的数组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个节点，并且可以预先声明它们。