I'm implementing the Max-Profit Algorithm in C++.
Find the Maximum Profit for a given stock trading day. Solution should be O(N) in Time and O(1) in Space requirements. You're allowed to purchase once in the day, and sell once in the day.
And I originally implemented like:
int maxprofit_int(vector<int> const& v) {
int resProfit = 0;
int minPrice = v[0];
for (auto i = 1; i < v.size(); i++) {
auto price = v[i];
minPrice = min(minPrice, price);
auto profit = price - minPrice;
resProfit = max(resProfit, price);
}
return resProfit;
}
Nothing unusual.
I thought to myself - "The STL typically gives the same or better performance, what would that look like?" Also "can I make this generic too?"
template <class itr>
auto maxprofit_generic(itr begin, itr end) -> typename std::iterator_traits<itr>::value_type {
using v_t = typename iterator_traits<itr>::value_type;
return std::accumulate(next(begin, 1), end, v_t{0},
[minPrice = *begin](auto const& maximumProfit, auto const& price) mutable {
minPrice = std::min(minPrice, price);
auto const profit = price - minPrice;
return std::max(maximumProfit, profit);
});
}
The accumulate acts as a fold operation, I use the first value of the container as the minPrice, which can be updated every pass. The starting value is always the same type as the return value. From everything I can gather, these two algorithms should be effectively identical.
However, bringing these two over to quick-bench, I found that was not the case. Both in GCC 10.1 and Clang 10.0, with -O3, I found that runtime doubled between the integer version, and the generic version. It's hard for me to believe that Clang and GCC have a bug, so I'm left wondering why my generic performance is abysmal.
What are some recommendations to improve the speed of the generic version?
My Quick-Bench code:
#include <vector>
#include <algorithm>
#include <numeric>
// Functions definitions removed for brevity
std::vector<int> uut = {1,2,4,1,3,5,2,5,7,9,3,4,5,5,5,7,9,9,4,2};
static void Maxprofit_Normal(benchmark::State& state) {
// Code inside this loop is measured repeatedly
for (auto _ : state) {
auto res = maxprofit(uut);
benchmark::DoNotOptimize(res);
}
}
// Register the function as a benchmark
BENCHMARK(Maxprofit_Normal);
static void Maxprofit_Generic(benchmark::State& state) {
// Code inside this loop is measured repeatedly
for (auto _ : state) {
auto res = maxprofit(uut.cbegin(),uut.cend());
benchmark::DoNotOptimize(res);
}
}
BENCHMARK(Maxprofit_Generic);
