reducing run-time example

[memepapa]

I'm starting to pay attention to run-time and thinking about how to write more efficient codes.

when I run the example code below, run time is about 5ms using a online compiler (the one provided by leetcode)

when i remove
a) n=prices.size()
and wrote
b) for (int j=0; j<n; j++){

... the runtime became faster, i was surprised. i expected it to be slower.

obviously, my fundamentals are not strong enough to understand why. I tried reading the books again and couldn't find a direct explanation.

i thought by writing
n=prices.size(), we execute prices.size() only once

and to include it in for (int j=0; j<prices.size(); j++), it gets calculated a few times. apparently i was wrong.
now trying to understand the WHY?

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int temp, maxp=0;
        int i=0, n=prices.size();
        
        for (int j=0; j<prices.size(); j++){
            temp=prices[j]-prices[i];
            if (temp>maxp) maxp=temp;
            else if(temp<0){
                i++;
                j--;
            }
        }
        return maxp;
    }
};

[salem c]

> b) for (int j=0; j<n; j++){
But your code still reads the member function every time.

        int i=0, n=prices.size();
        
        for (int j=0; j<prices.size(); j++){

You also need to be mindful of "debug" vs "release" builds.
In debug builds, the compiler pretty much does what you ask, and j<prices.size() is likely to be evaluated in its entirety every time.

In release builds, the compiler will easily see that the size of prices is invariant, compute prices.size() only once, and produce much better code.

Be wary of second guessing how the compiler works to chase that last mS.

        int i=0, n=prices.size();
        
        for (int j=0; j<n; j++){
            //  code

            // then in a later edit, you add this
            prices.push_back(somevalue);  //!! oops, you broke the invariant.
        }

Now your 'carefully' optimised code is suddenly broken, but it could be a while before you figure out why.

> I'm starting to pay attention to run-time and thinking about how to write more efficient codes.
The really big efficiencies come from choosing the best algorithms, not micro-managing the source code.

[memepapa]

thanks. it was enlightening.

[thmm]

The really big efficiencies come from choosing the best algorithms

and choosing the right data structures.

@OP,
as a beginner you need not to worry about performance. Scott Meyers wrote a few books about Effective C++, but the are not for beginners.
Marc Gregoire wrote a chapter about profiling and optimizing code in his book "Professional C++"

[seeplus]

run time is about 5ms using a online compiler (the one provided by leetcode)

Which compiler? Note that run 'timings' can vary from one run to the next! Unless you're doing real-time programming, a few ms difference in run-time isn't going to be noticed and almost certainly doesn't matter. Concentrate on the algorithm and usage of C++ constructs (ref, move etc) rather than micro-optimising and trying to 'better' the compiler. Modern C++ compilers when compiling in release mode with optimisation turned on are very, very efficient in their code production - and get better.

[jonnin]

n isnt used.
j-- is an undo of j++ ... can you rewrite it to avoid that so j++ only happens when it needs to and you never need to undo it?

none of that likely has much effect, but you can poke at it.

making code faster by making little adjustments and timing it over and over can result in code that has to be rewritten every time you change something {driver update, OS update, library update, compiler update, .. etc}. At some point you need to set it down and accept that there are ghouls in the machine that you cannot control.

[seeplus]

As C++17 possibly:

int maxProfit(const vector<int>& prices) {
	int maxp {};

	for (size_t j {}, i {}; j < prices.size(); ) {
		if (const auto temp {prices[j] - prices[i]}; temp > maxp)
			maxp = temp;
		else if (temp < 0) {
			++i;
			continue;
		}

		++j;
	}

	return maxp;
}

[seeplus]

However, if I'm reading the code right what you're after is the maximum difference between any 2 elements? If so, then consider:

#include <vector>
#include <iostream>

int maxProfit(const std::vector<int>& prices) {
	if (prices.size() < 2)
		return 0;

	int max_diff {prices[1] - prices[0]};
	int min_element {prices[0]};

	for (size_t i = 1; i < prices.size(); ++i) {
		if (prices[i] - min_element > max_diff)
			max_diff = prices[i] - min_element;

		if (prices[i] < min_element)
			min_element = prices[i];
	}

	return max_diff;
}

int main() {
	const std::vector<int> arr {1, 2, 90, 10, 110};

	std::cout << "Maximum profit is " << maxProfit(arr) << '\n';
}

Maximum profit is 109

[salem c]

Perhaps it's then

#include <vector>
#include <iostream>
#include <algorithm>

int maxProfit(const std::vector<int>& prices) {
	if (prices.size() < 2)
		return 0;
    std::vector<int>::const_iterator lmax = std::max_element(prices.begin(),prices.end());
    std::vector<int>::const_iterator lmin = std::min_element(prices.begin(),prices.end());
    return *lmax - *lmin;
}

int main() {
	const std::vector<int> arr {1, 2, 90, 10, 110};

	std::cout << "Maximum profit is " << maxProfit(arr) << '\n';
}

[seeplus]

but that iterates twice over the vector... Perhaps:

#include <vector>
#include <iostream>
#include <algorithm>

int maxProfit(const std::vector<int>& prices) {
	const auto mnmx {std::minmax_element(prices.begin(), prices.end())};

	return *mnmx.second - *mnmx.first;
}

int main() {
	const std::vector<int> arr {1, 2, 90, 10, 110};

	std::cout << "Maximum profit is " << maxProfit(arr) << '\n';
}

[jonnin]

^^^ nice circle back to the original post, which said that finding the better algorithm is the right way