• Post Reply Bookmark Topic Watch Topic
  • New Topic

Collections.reverse under the hood  RSS feed

 
Daniel Gurianov
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All.

Does anyone know what approach Collections.reverse() uses to reverse list?
My task is to implement and compare reverse methods from list and i already did reveres with Recursion, Swap, Reading backward with creating reversed copy.
Does Collections.reverse() use different approach from those i already did?

Thank you.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Daniel Gurianov wrote:Does anyone know what approach Collections.reverse() uses to reverse list?
My task is to implement and compare reverse methods from list and i already did reveres with Recursion, Swap, Reading backward with creating reversed copy.
Does Collections.reverse() use different approach from those i already did?

The answer to your first question: Nope.
The answer to your last one: Probably not; but since we don't know the details of your various implementations, again we can't know.

The fact is that there aren't that many ways to "reverse" a collection; and the method you choose will almost certainly depend on whether you need to reverse it "in place" or not.

One possibility that might be worth considering is a "reversed wrapper" - ie, a List that "wraps" an existing one, but has methods that convert all supplied indexes to "reversed" ones, and returns an Iterator that traverses in reverse order. That way, you don't need to "change" anything to get a "reversed" version of an existing List.

HIH

Winston
 
Tim Cooke
Marshal
Posts: 4041
239
Clojure IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can see the implementation of the OpenJDK Collections.reverse(List). There's no guarantee that the same implementation will be used in the Oracle Java JDK, or any other JDK for that matter, but in the case of OpenJDK it's highly likely (as far as I understand it, the Oracle JDK developers are the primary contributors to OpenJDK)
 
Campbell Ritchie
Marshal
Posts: 56533
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote: . . .
One possibility that might be worth considering is a "reversed wrapper" - . . .
Since Collections#reverse has void return type, it cannot produce a wrapper.

The method does not reverse a Collection, but a List, because Lists encapsulate an order which Collections might not specify. Is mentions the set method in the documentation, so it obviously uses set. The correct answer is:
You don't need to know that
… but there is a file in your Java® installation folder called src.zip. If you unzip that, you can find the source code and read it.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Since Collections#reverse has void return type, it cannot produce a wrapper.

True, but that's not what Daniel said his task was. If the "methods" that he's been asked to implement must return void, then plainly they must do the "reversal" in-place, but I didn't see anything about that in the OP.

Winston
 
Knute Snortum
Sheriff
Posts: 4276
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's a good article about reversing in place.
 
Daniel Gurianov
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you all for the replies.

Tim Cooke, thanks for OpenJDK link. I do not think there is a high chances that Oracle would change reverse in their JDK to something else.
Yes, from OpenJDK it looks that for Collections.reverse() , in any case, it finally boils down to swap elements.


Knute Snortum, thanks for in-place link. It is actually what i ment by "swap reverse", except i did one additional step to control for loop . Now i see that it is actually rudimental and i can get rid from it. Also i will know that it should be called in-place reverse.
 
Campbell Ritchie
Marshal
Posts: 56533
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not an in‑place technique, but have you ever tried a stack?
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Not an in‑place technique, but have you ever tried a stack?

Oh yer, I'd forgotten about that one. Good thinking, Batman.

Winston
 
Daniel Gurianov
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Not an in‑place technique, but have you ever tried a stack?


As i understood , recursive reverse is kinda stack approach, cause you put elemtns in memory one by one in forward order , and the put them back into object in reverse order, when you reached end of the object.
Also i`m trying to avoid involvement other data structures , assuming that unnecesarry allocating and deallocating will degrade overall performance.
In case stack , i need +1 stack object where to put elements and then get it back as soon as i hit the bottom of Array- or LinkedList.
 
Campbell Ritchie
Marshal
Posts: 56533
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A recursion actually creates a sort of stack. It uses the standard JVM stack.
No, you will not find using a stack at all slow. You may do well to give the stack a predefined size (same as the List) for quicker execution. You can create a stack object with a capacity of 100000000 if you wish whereas most recursions run out of stack space between 5000 and 10000 levels. And avoid this. Use an implementation of this (e.g. this) (or write your own stack class). You only need one stack object.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!