Selecting 2 largest elements out of 4, preserving order

Question

I need an efficient way to select 2 largest integers from an array of 4, preserving the order.
E.g. 1,4,3,5 -> 4,5; 1,5,3,4 -> 5,4

What's the efficient way to do it (C/C++)?

I.e., with minimum conditionals (comparisons), or using min/max (assuming min/max have dedicated HW instructions and are not conditionals).

In ambiguous cases like 1,3,4,3 both 3,4 and 4,3 are acceptable answers.

Answer 1

This is summary of some others answers. I've changed code so it all have common API.

Basically when trying to provide optimal code there are two basic rules:

1. Code must work (so must be tested) https://godbolt.org/z/8hMKoGh5s

TEMPLATE_TEST_CASE("stable_largest_two", "[template]", 
    SimonGoater,
    trincot2,
    trincot1,
    chqrlie,
    isrnick,
    lastchance,
    TedLyngmo_1,
    TedLyngmo_2)
    /*, nicky_eyes fails) */ 
{
    SECTION("single solution")
    {
        auto [in, expected] = GENERATE(table<ArgType, ResultType>({
            { {}, {} },
            { { 0, 0, 1, 1 }, { 1, 1 } },
            { { 1, 0, 0, 1 }, { 1, 1 } },

            { { 1, 2, 3, 4 }, { 3, 4 } },
            { { 1, 2, 4, 3 }, { 4, 3 } },
            { { 1, 3, 2, 4 }, { 3, 4 } },
            { { 1, 3, 4, 2 }, { 3, 4 } },
            { { 1, 4, 2, 3 }, { 4, 3 } },
            { { 1, 4, 3, 2 }, { 4, 3 } },
            { { 2, 1, 3, 4 }, { 3, 4 } },
            { { 2, 1, 4, 3 }, { 4, 3 } },
            { { 2, 3, 1, 4 }, { 3, 4 } },
            { { 2, 3, 4, 1 }, { 3, 4 } },
            { { 2, 4, 1, 3 }, { 4, 3 } },
            { { 2, 4, 3, 1 }, { 4, 3 } },
            { { 3, 1, 2, 4 }, { 3, 4 } },
            { { 3, 1, 4, 2 }, { 3, 4 } },
            { { 3, 2, 1, 4 }, { 3, 4 } },
            { { 3, 2, 4, 1 }, { 3, 4 } },
            { { 3, 4, 1, 2 }, { 3, 4 } },
            { { 3, 4, 2, 1 }, { 3, 4 } },
            { { 4, 1, 2, 3 }, { 4, 3 } },
            { { 4, 1, 3, 2 }, { 4, 3 } },
            { { 4, 2, 1, 3 }, { 4, 3 } },
            { { 4, 2, 3, 1 }, { 4, 3 } },
            { { 4, 3, 1, 2 }, { 4, 3 } },
            { { 4, 3, 2, 1 }, { 4, 3 } },
        }));
        REQUIRE(TestType::stable_largest_two(in) == expected);
    }
    SECTION("mutiple solutions")
    {
        using Catch::Matchers::UnorderedEquals;
        auto [in, expected] = GENERATE(table<ArgType, ResultType>({
            { { 1, 3, 4, 3 }, { 3, 4 } },
            { { 3, 3, 4, 3 }, { 3, 4 } },
            { { 3, 4, 3, 1 }, { 3, 4 } },
            { { 3, 4, 1, 3 }, { 3, 4 } },
        }));
        auto result = TestType::stable_largest_two(in);
        REQUIRE_THAT((std::vector<int>{result.begin(), result.end()}), 
            UnorderedEquals(std::vector<int>{expected.begin(), expected.end()}));
    }
}

2. You need some measurement to make responsible decision which solution is fast:

constexpr auto TestData = std::to_array<std::array<int, 4>>({
    {},
    { 0, 0, 1, 1 },
    { 1, 0, 0, 1 },

    { 1, 2, 3, 4 },
    { 1, 2, 4, 3 },
    { 1, 3, 2, 4 },
    { 1, 3, 4, 2 },
    { 1, 4, 2, 3 },
    { 1, 4, 3, 2 },
    { 2, 1, 3, 4 },
    { 2, 1, 4, 3 },
    { 2, 3, 1, 4 },
    { 2, 3, 4, 1 },
    { 2, 4, 1, 3 },
    { 2, 4, 3, 1 },
    { 3, 1, 2, 4 },
    { 3, 1, 4, 2 },
    { 3, 2, 1, 4 },
    { 3, 2, 4, 1 },
    { 3, 4, 1, 2 },
    { 3, 4, 2, 1 },
    { 4, 1, 2, 3 },
    { 4, 1, 3, 2 },
    { 4, 2, 1, 3 },
    { 4, 2, 3, 1 },
    { 4, 3, 1, 2 },
    { 4, 3, 2, 1 },
});

template <typename Solution>
static void PerfCheck(benchmark::State& state)
{
    for (auto _ : state) {
        for (const auto& arr : TestData) {
            benchmark::DoNotOptimize(arr);
            auto result = Solution::stable_larget_two(arr);
            benchmark::DoNotOptimize(result);
        }
    }
}
BENCHMARK(PerfCheck<trincot>);
BENCHMARK(PerfCheck<lastchance>);
BENCHMARK(PerfCheck<TedLyngmo>);

• clang result
• gcc result

Now you have tools to do more experiments and select best solution.

Answer 2

Here is a simple approach to get the largest 2 elements n1 and n2 of an array of at least 2 values, preserving order:

• start with the first 2 elements.
• for each value x of the remaining elements:
  • if x >= n2, the new pair is { max(n1, n2), x }
  • otherwise, if x > n1, the new pair is { n2, x }.

typedef struct pair {
    int n1, n2;
} pair;

pair max_pair(int arr[static 2], size_t len) {
    pair res = { arr[0], arr[1] };
    for (size_t i = 2; i < len; i++) {
        int x = arr[i];
        if (x >= res.n2) {
            if (res.n1 < res.n2)
                res.n1 = res.n2;
            res.n2 = x;
        } else {
            if (x > res.n1) {
                res.n1 = res.n2;
                res.n2 = x;
            }
        }
    }
    return res;
}

If you can assume dedicated HW for the min and max functions, this translates to an even simpler loop:

• start with the first 2 elements.
• for each value x of the remaining elements:
  • if x > min(n1, n2), the new pair is { max(n1, n2), x }

typedef struct pair {
    int n1, n2;
} pair;

static inline int min(int a, int b) { return a <= b ? a : b; }
static inline int max(int a, int b) { return a >= b ? a : b; }

pair max_pair(int arr[static 2], size_t len) {
    pair res = { arr[0], arr[1] };
    for (size_t i = 2; i < len; i++) {
        int x = arr[i];
        if (x > min(res.n1, res.n2)) {
            res.n1 = max(res.n1, res.n2);
            res.n2 = x;
        }
    }
    return res;
}

For a set of 4 argument values, this simplifies into:

typedef struct pair {
    int n1, n2;
} pair;

static inline int min(int a, int b) { return a <= b ? a : b; }
static inline int max(int a, int b) { return a >= b ? a : b; }

pair max_pair4(int a, int b, int c, int d) {
    if (c > min(a, b)) {
        a = max(a, b);
        b = c;
    }
    if (d > min(a, b)) {
        a = max(a, b);
        b = d;
    }
    return (pair){ a, b };
}

Alternately, here are in place solutions:

static inline int min(int a, int b) { return a <= b ? a : b; }
static inline int max(int a, int b) { return a >= b ? a : b; }

void max_pair(int arr[static 2], size_t len) {
    int a = arr[0];
    int b = arr[1];
    for (size_t i = 2; i < len; i++) {
        int x = arr[i];
        if (x > min(a, b)) {
            a = max(a, b);
            b = x;
        }
    }
    arr[0] = a;
    arr[1] = b;
}

void max_pair4(int arr[static 4]) {
    if (arr[2] > min(arr[0], arr[1])) {
        arr[0] = max(arr[0], arr[1]);
        arr[1] = arr[2];
    }
    if (arr[3] > min(arr[0], arr[1])) {
        arr[0] = max(arr[0], arr[1]);
        arr[1] = arr[3];
    }
}