• Post Reply Bookmark Topic Watch Topic
  • New Topic

Nested for loop execution time lower than a for loop  RSS feed

 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your "optimized" is not really optimized. BigInteger is much slower than int or long math.
 
Rob Spoor
Sheriff
Posts: 21135
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The bulk of your time lies in creating the BigInteger objects. I've put some System.nanoTime() calls in between, and I got the following result:
  • 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 secondLargestNum into a long to prevent overflow issues) the second method is faster than the second.
     
    Carey Brown
    Saloon Keeper
    Posts: 3328
    46
    Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    How to hold large values then? I replaced all long types to BigInteger when I saw number overflow. 
     
    Mike Simmons
    Ranch Hand
    Posts: 3090
    14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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?
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!