posted 1 year ago

Hi,

I am trying to learn code optimization. I have a simple problem. The objective is to find the maximum product value for a set of positive numbers in an array.

Here is the code:

The surprising part is the time complexity. Here is the output:

What I do not understand is why the single loop solution is 10 times slower than the nested for loop

I am trying to learn code optimization. I have a simple problem. The objective is to find the maximum product value for a set of positive numbers in an array.

Here is the code:

The surprising part is the time complexity. Here is the output:

What I do not understand is why the single loop solution is 10 times slower than the nested for loop

posted 1 year ago

The bulk of your time lies in creating the BigInteger objects. I've put some

startTime to just after creating the 0 BigInteger: 1206578 First loop: 2933 Second loop: 2445 Creating the resulting BigInteger: 91911

So the bulk of the work lies in creating the first BigInteger, which is probably caused by class loading. If I turn the 0 BigInteger into a static final field (using BigInteger.ZERO as well), the total time drops to 168178; the bulk again lying in the creating of the resulting BigInteger.

If I change the second method to also use longs (changing

`System.nanoTime()`calls in between, and I got the following result:So the bulk of the work lies in creating the first BigInteger, which is probably caused by class loading. If I turn the 0 BigInteger into a static final field (using BigInteger.ZERO as well), the total time drops to 168178; the bulk again lying in the creating of the resulting BigInteger.

If I change the second method to also use longs (changing

`secondLargestNum`into a long to prevent overflow issues) the second method is faster than the second.SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

posted 1 year ago

Notice that your normal and fast results are not the same, so you have an error. In normal your multiply is overflowing an int.

In fast: because your array length is short, the BigInteger and String manipulation is killing your time.

In fast: because your array length is short, the BigInteger and String manipulation is killing your time.

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 1 year ago

If you're calculating the product of two ints, then long should be big enough already. I suspect that the problem is that you're getting int overflow in the multiplication before it gets converted to int. (As Carey noted earlier, I see.) Take a look at the output of the following, and see if you can understand what's happening in each case:

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 1 year ago

Also: is it really necessary to multiply all those numbers? Couldn't you also just find the two biggest numbers, and the product of those two should be the biggest, overall?

That gets a bit more complicated if there are also negative numbers in the list - the two most negative numbers might have a bigger product than the two most positive numbers.

Edited to add: OK, I now see that's what the intent of the "optimized" code was. Good, keep this idea.

That gets a bit more complicated if there are also negative numbers in the list - the two most negative numbers might have a bigger product than the two most positive numbers.

Edited to add: OK, I now see that's what the intent of the "optimized" code was. Good, keep this idea.

posted 1 year ago

Well the problem statement states that for an array with numbers of value 0< n < 10^5. Find the max pair product. Now that range is huge. I needed something that will fit the result.

Using the long cast, I was able to get the result. But I would really like to know how is it different from using two long values instead of int? It should hold the max values with long right?

Using the long cast, I was able to get the result. But I would really like to know how is it different from using two long values instead of int? It should hold the max values with long right?

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |