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:
- 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()}));
}
}
- 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>);
Now you have tools to do more experiments and select best solution.
1,3,4,3
?I need an efficient way
- do you have own solution which works? Did you write performance test to verify which solution is best?