最常见的每n个元素在C [英] Most Frequent of every N Elements in C

问题描述

我有规模的相对较小整数大型数组A [0，8388608] A [I] = [0，131072]我想找到每一个N = 32个元素中最频繁出现的元素。

I have a large array A of size [0, 8388608] of "relatively small" integers A[i] = [0, 131072] and I want to find the most frequently occurring element of every N=32 elements.

什么是速度更快，

一个。创建大小为131072的关联数组B，通过32个元素，增加乙迭代[A [I]，然后到B迭代，找到最大的价值，在B中的所有元素重置为0，重复| A | / 32倍

A. Create an associative array B of size 131072, iterate through 32 elements, increment B[A[i]], then iterate through B, find the largest value, reset all elements in B to 0, repeat |A|/32 times.

乙。每天的qsort 32个元素，找到最大的范围，其中A [I] == A [I-1]（因此最常见的元素），重复| A | / 32倍

B. qsort every 32 elements, find the largest range where A[i] == A[i-1] (and thus the most frequent element), repeat |A|/32 times.

（编辑）C.别的东西。

(EDIT) C. Something else.

推荐答案

在第一种方法的改进是可能的。没有必要通过B.迭代，它可以是大小131072阵列

An improvement over the first approach is possible. There is no need to iterate through B. And it can be an array of size 131072

您增加每次 B [A [I]] ，看在该单元格的新值。然后，有一个全局 highest_frequency_found_far 。这是从零开始，但每次递增后的新值应该与这个全球性相比。如果是更高的，那么全球将被替换。

Every time you increment B[A[i]], look at the new value in that cell. Then, have a global highest_frequency_found_far. This start at zero, but after every increment the new value should be compared with this global. If it's higher, then the global is replaced.

您也可以有一个全球性的 value_that_was_associated_with_the_highest_count

You could also have a global 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]; }
}

这篇关于最常见的每n个元素在C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！