Return to discussion

#include "integer_counting.h"
#include <array>

using namespace std;

static constexpr size_t max_number = 999;

optional<uint16_t>
get_most_common_number(const uint16_t *numbers, size_t len)
{
    array<size_t, max_number + 1> counts{};

    for (size_t i = 0; i < len; ++i) {
        ++counts[numbers[i]];
    }

    size_t max_count = 0;
    uint16_t idx_max_count = 0;
    for (uint16_t idx = 0; idx < max_number; ++idx) {
        if (counts[idx] > max_count) {
            max_count = counts[idx];
            idx_max_count = idx;
        }
    }

    // Check if maximum count occurs for more than one number.
    for (uint16_t idx = idx_max_count + 1; idx < max_number; ++idx) {
        if (counts[idx] == max_count) {
            return {};
        }
    }

    return make_optional(idx_max_count);
}

$ ./benchmark_integer_counting
2025-10-01T01:13:16+02:00
Running ./benchmark_integer_counting
Run on (32 X 5700 MHz CPU s)
CPU Caches:
  L1 Data 48 KiB (x16)
  L1 Instruction 32 KiB (x16)
  L2 Unified 2048 KiB (x16)
  L3 Unified 36864 KiB (x1)
Load Average: 0.19, 0.15, 0.09
--------------------------------------------------------------------
Benchmark                          Time             CPU   Iterations
--------------------------------------------------------------------
BM_get_most_common_number     192218 ns       191999 ns         3472

#include "integer_counting.h"
#include <array>

using namespace std;

static constexpr size_t max_number = 999;

optional<uint16_t>
get_most_common_number(const uint16_t *numbers, size_t len)
{
    array<size_t, max_number + 1> counts{};

    for (size_t i = 0; i < len; ++i) {
        ++counts[numbers[i]];
    }

    size_t max_count = 0;
    uint16_t idx_max_count = 0;
    for (uint16_t idx = 0; idx <= max_number; ++idx) {
        if (counts[idx] > max_count) {
            max_count = counts[idx];
            idx_max_count = idx;
        }
    }

    // Check if maximum count occurs for more than one number.
    for (uint16_t idx = idx_max_count + 1; idx <= max_number; ++idx) {
        if (counts[idx] == max_count) {
            return {};
        }
    }

    return make_optional(idx_max_count);
}

$ ./benchmark_integer_counting
2025-10-01T01:13:16+02:00
Running ./benchmark_integer_counting
Run on (32 X 5700 MHz CPU s)
CPU Caches:
  L1 Data 48 KiB (x16)
  L1 Instruction 32 KiB (x16)
  L2 Unified 2048 KiB (x16)
  L3 Unified 36864 KiB (x1)
Load Average: 0.03, 0.06, 0.08                                                                                 
--------------------------------------------------------------------
Benchmark                          Time             CPU   Iterations
--------------------------------------------------------------------
BM_get_most_common_number     193105 ns       192908 ns         3606

After we need another iteration on the counter array to ensure there exists a unique number appearing most often than others because there could have been several numbers with same number of occurrence as in the provided list of 100 integers. This final loop can be only partial, beginning after the minimum index of maximum count computed in the previous loop, nevertheless its worst case is in 999 iterations, with the first iteration at index 1.

After, we need another iteration on the counter array to ensure there exists a unique number appearing most often than others because there could have been several numbers with same number of occurrence as in the provided list of 100 integers. This final loop can be only partial, beginning after the minimum index of maximum count computed in the previous loop, nevertheless its worst case is in 999 iterations, with the first iteration at index 1.

The related include file with the prototype and its needed includes in `integer_counting.h`:

We could merge the first loop on the inputs with the second loop computing the max on the 1000 counters, but it leads to worst time result because as n is 1000 times greater than 1000 (number of counters), it implies 1000 times more comparisons in loops, whereas by computing the max in a separate loop, the loop of n iterations is kept without any comparison leading to more efficiency.

The related include file with the prototype and its needed includes in integer_counting.h: