c - C 中每 N 个元素中出现次数最多的元素

Question

我有一个大小为 [0, 8388608] 的大数组 A，其中包含“相对较小”的整数 A[i] = [0, 131072]，我想找到每个 N=32 个元素中最常出现的元素。

什么会更快，

A.创建一个大小为 131072 的关联数组 B，迭代 32 个元素，递增 B[A[i]]，然后迭代 B，找到最大值，将 B 中的所有元素重置为 0，重复 |A|/32 次。

B.每 32 个元素进行排序，找到 A[i] == A[i-1] 的最大范围(因此是最频繁的元素)，重复 |A|/32 次。

(编辑)C.其他东西。

Answer 1

对第一种方法的改进是可能的。不需要遍历B。并且它可以是大小为131072的数组

每次递增 B[A[i]] 时，请查看该单元格中的新值。然后，有一个全局的highest_Frequency_found_far。它从零开始，但每次增量后，新值都应与该全局值进行比较。如果它更高，则替换全局。

您还可以有一个全局value_that_was_linked_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]; }
}