• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Efficiency of two methods for array rotation

 
Greenhorn
Posts: 27
Eclipse IDE Oracle Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have started learning Java and was trying to solve some easy problems from different websites like HackerRank and leetcode.I am relatively new to programming so please don't mind if this is too naive. I found a problem in LeetCode to rotate array.The problem can be found here

I have implemented the solution using two different methods:

The first method(my initial solution) rotateArray1 is very straightforward where we divide the array into two parts and then copy the elements back into the main array.

I found the logic for the second method in programcreek which says :

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].



have implemented the solution using two different methods:

The first method(my initial solution) rotateArray1 is very straightforward where we divide the array into two parts and then copy the elements back into the main array.

I found the logic for the second method in programcreek which says :


1. Divide the array two parts: 1,2,3,4 and 5, 6
2. Reverse first part: 4,3,2,1,5,6
3. Reverse second part: 4,3,2,1,6,5
4. Reverse the whole array: 5,6,1,2,3,4



This is my solution where I implemented both the methods.I am trying to get better at writing good code for my solutions. Please give me your suggestions and also can anyone please tell me which one of these two methods is more efficiant in terms of time complexity.




 
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Any time you want to test how long something takes you can surround it like this:

Note that if your "do something" is very quick it may not register enough milli-seconds. In that case, put your do-something inside a loop that iterates thousands of times, or maybe even a million.
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am sure you are right about the millisecond method not having the precision to time that loop. Run the loop 50000× before starting the timing, so as to get the JiT compiler to make any optimisations, then time it for 1000000× I usually use the timing methods thrice.start2 - start gives you the time taken for a method call, so you subtract that from the timings.
Time = end − start2 − (start2 − start1) =
end + start − start2 × 2
\u00f7 = ÷
If you are getting small results from the millisecond method, try this instead.
 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A couple of comments on this:
  • It seems that "end-start2-(start2-start1)" would be less inclined to overflow than "end+start-start2*2".
  • I like the addition of the JiT code.
  • Have you ever really seen the cost of the currentTimeMillis() call significantly impact the results? Or are you trying to capture the overhead of calling the doSomething() method? If it's the later, then why not go to the trouble of working out the cost of the for() loop? (Not sure how you'd do that.)
  •  
    Campbell Ritchie
    Marshal
    Posts: 79177
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Since there are enough milliseconds in a long to last something like 300000000 years, I don't think there is much risk of an overflow. I have never tried an empty for loop, but I suspect the JiT compiler may optimise it away to nothing.

    I have tried an empty loop now:

    java EmptyDemo
    1461336494758
    1461336494759
    1461336494764

    Only 12 digits and a long goes up to about 19 digits.
    Calling current time millis: 1ms. 1000000 iterations of empty loop: 5ms. Take off time for milliseconds call, and you get 4ms per 1000000 loops. That is 4ns per iteration. Isn't your life enriched by knowing that
     
    Campbell Ritchie
    Marshal
    Posts: 79177
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Sorry; I didn't mean to be rude.
     
    Carey Brown
    Saloon Keeper
    Posts: 10705
    86
    Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:Calling current time millis: 1ms. 1000000 iterations of empty loop: 5ms. Take off time for milliseconds call, and you get 4ms per 1000000 loops. That is 4ns per iteration. Isn't your life enriched by knowing that


    Yes. Confirms that it is well withing the "noise" level of measurement.
     
    Bartender
    Posts: 10780
    71
    Hibernate Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    dhrubo bhattacharjee wrote:I have implemented the solution using two different methods:
    The first method(my initial solution) rotateArray1 is very straightforward where we divide the array into two parts and then copy the elements back into the main array.
    I found the logic for the second method in programcreek which says :


    1. Divide the array two parts: 1,2,3,4 and 5, 6
    2. Reverse first part: 4,3,2,1,5,6
    3. Reverse second part: 4,3,2,1,6,5
    4. Reverse the whole array: 5,6,1,2,3,4


    I'd say that the two styles are likely to be about the same in terms of speed (O(2n)), but the second is better in terms of space, since it can be done in place.

    There is a third one which, for n = 7 and k = 3, and the array [1,2,3,4,5,6,7], would be as follows:
    1. Copy [5,6,7] to a new array.
    2. Shift [1,2,3,4] 3 places to the right.
    3. Copy [5,6,7] to the start.
    This takes O(2k + n - k) == O(k + n) time, which is marginally faster than O(2n), but it does need a bit of extra storage as well.

    It's probably also worth mentioning that if k > n/2, you can achieve the same result by rotating n-k elements the other way.

    HIH

    Winston
     
    Winston Gutkowski
    Bartender
    Posts: 10780
    71
    Hibernate Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Winston Gutkowski wrote:I'd say that the two styles are likely to be about the same in terms of speed (O(2n)), but the second is better in terms of space, since it can be done in place.


    Actually, that's not quite right. A "reverse" can be done in place, but It takes O(3n/2) time to do it (worst case) because it has to "swap" elements; so an in-place version of your #2 algorithm would take O(3n) time.

    Winston
     
    Bartender
    Posts: 5465
    212
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    O(n) and O(2n) are both O(n).

    Well in fact there are many methods. The easiest I can think of is:

     
    Winston Gutkowski
    Bartender
    Posts: 10780
    71
    Hibernate Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Piet Souris wrote:O(n) and O(2n) are both O(n).


    Only if you're interested in scalability. Sometimes the difference between O(n) and O(3n) is a deal-breaker - and the question was about "efficiency".

    Well in fact there are many methods. The easiest I can think of is:...


    Luscious. Deserves a cow for making me feel like a fool for not spotting it myself.

    Winston
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    reply
      Bookmark Topic Watch Topic
    • New Topic