wood burning stoves 2.0*
The moose likes Performance and the fly likes Quickest way to convert a map to a list Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "Quickest way to convert a map to a list" Watch "Quickest way to convert a map to a list" New topic
Author

Quickest way to convert a map to a list

Luke Murphy
Ranch Hand

Joined: May 12, 2010
Posts: 300
Anyone know a quickway to convert a map to a list that is quicker than this...

fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11246
    
  16

and is that too slow for some reason?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Luke Murphy
Ranch Hand

Joined: May 12, 2010
Posts: 300
fred rosenberger wrote:and is that too slow for some reason?


Well this is the performance forum :-)
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11246
    
  16

it is indeed the performance forum. And the first rule of performance is "don't worry about it until it is a problem". or as Knuth put it, "Premature optimization is the root of all evil".
Luke Murphy
Ranch Hand

Joined: May 12, 2010
Posts: 300
fred rosenberger wrote:it is indeed the performance forum. And the first rule of performance is "don't worry about it until it is a problem". or as Knuth put it, "Premature optimization is the root of all evil".


Yes it is a problem. I need to be able to convert a map to a list as fast as possible. I am wondering is this the fastest way.

Cheers.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11246
    
  16

"As fast as possible" is not really a spec - but if that is your requirement, my answer would be "buy a faster machine".
Luke Murphy
Ranch Hand

Joined: May 12, 2010
Posts: 300
fred rosenberger wrote:"As fast as possible" is not really a spec - but if that is your requirement, my answer would be "buy a faster machine".

I have a use case which takes one hour approx, I have JProbed it and noticed a huge bottleneck on list.contains() calls. I have sped it up by replacing some of these with maps.

But in some cases I need to convert these maps back to lists.

There are several ways to convert maps to lists.

For example:



Which is abot 50% slower than the first way I pointed out.

I was wondering if someone knows of a faster way than I pointed out.

Pretty simple question.





Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

So you identified the contains() methods as a performance bottleneck, and did something to deal with it. That's a good thing. But as far as I know you haven't identified converting maps to lists as the new performance bottleneck; at least, you haven't said that. And you have a reasonable-looking way to do it, too. So I'm with Fred, I don't see a reason to be looking at that for performance improvements. Go with the reasonable-looking way and see if it's worth improving.
Luke Murphy
Ranch Hand

Joined: May 12, 2010
Posts: 300
Paul Clapham wrote:So you identified the contains() methods as a performance bottleneck, and did something to deal with it. That's a good thing. But as far as I know you haven't identified converting maps to lists as the new performance bottleneck; at least, you haven't said that. And you have a reasonable-looking way to do it, too. So I'm with Fred, I don't see a reason to be looking at that for performance improvements. Go with the reasonable-looking way and see if it's worth improving.


It is a bottleneck. But it is not as bad as having everything as lists.

Look no worries if no-one can answer the question. It probably is the fastest way to do it.


Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

I would assume that something from the standard API would normally be at least as something that I threw together, if only because it has direct access to internal structures which I don't. But that's just an assumption, of course.

It's also possible there's something as simple as the standard API preallocating the full array for the ArrayList instead of having to recopy it several times as the list grows. (You must be creating a large list since you say this is a bottleneck.)

It might also make a difference if you created some other kind of list, say a LinkedList. Or there might be a difference depending on the kind of Map you're using.

Or you could design some new data structure which had the features of a Map and of a List at the same time, so you didn't have to do the copying at all.

Lots of possibilities, then. Just because it's a simple question doesn't mean it has a simple answer.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: Quickest way to convert a map to a list