File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Performance and the fly likes Collection Class ArrayListMap Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "Collection Class ArrayListMap" Watch "Collection Class ArrayListMap" New topic
Author

Collection Class ArrayListMap

Jeff Gent
Ranch Hand

Joined: Mar 24, 2011
Posts: 44

I'm in the transition from a beginner to a intermediate in my Java Foo, so I lack confidence in some of this. Wanted to get some advice from the masters.

I know to try and choose the best collection for the task, but I find sometimes that I need a collection to do a couple things quickly - mainly I want to know the index and value. Primarily, I need something fast on get(), indexOf, contains(). So here is my attempt to increase performance over an ArrayList by optimizing the return for the type of call by complementing it with a HashMap. It is a little slower on add() of an ArrayList and takes a little more memory for the map, but the trade off is fast returns when using indexOf() and contains(). I'm thinking the additional memory consumption is minor since it's using Objects, so it shouldn't have to store it twice... correct?

So looking for any advice, suggestions, comments.

Anyway, here are my quick benchmarks in ms running a 50,000 loop.

add()
50.0 ArrayList
90.0 HashMap
55.0 ArrayListMap

contains()
13790.0 ArrayList
61934.0 HashMap containsValue()
41.0 HashMap containsKey() using value as key
41.0 ArrayListMap

get()
1.0 ArrayList
1.0 ArrayListMap
3.0 HashMap

indexOf()
13639.0 ArrayList
19.0 ArrayListMap
19.0 HashMap using value as key


Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7029
    
  16

Jeff Gent wrote:So looking for any advice, suggestions, comments.

A few:
1. In order to be most useful, I reckon your class should implement at least one of the collection interfaces. List<E> seems the most obvious, although in fact your class is closer to a Set (see below). You could even implement both.
2. Because you are storing your elements in a HashMap, you will not be able to store duplicates. If that's OK, great; but you should be aware of it.
3. If you want your set() method to replicate ArrayList's, then it needs to return an element. Also, you don't strictly need to do a remove() before you do the put().

But otherwise, congratulations - your first collection wrapper class. Fun, aren't they?

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Artlicles by Winston can be found here
Jeff Gent
Ranch Hand

Joined: Mar 24, 2011
Posts: 44

Thanks! I think for that Set, I meant to do the following. Since the value is what is being changed, it may not be there in the HashMap to change.
Also, thanks for the reminder that it doesn't support duplicates - I ran some checks and verified I'm not adding any in my overall program. I'll look into the implements - that's not something I've done yet. The whole implements, extends, abstract stuff is still something I'm learning and I find a bit confusing.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Winston Gutkowski wrote:
Jeff Gent wrote:So looking for any advice, suggestions, comments.

A few:
1. In order to be most useful, I reckon your class should implement at least one of the collection interfaces. List<E> seems the most obvious, although in fact your class is closer to a Set (see below). You could even implement both.


No class can fulfill both contracts. Equality pops to mind. There may be other incompatibilities, but nothing that I can think of at the moment.

He can of course still choose to implement both and document the deviations from the contracts, but I wouldn't advise it without a really pressing need.

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7029
    
  16

Jeff Verdegan wrote:No class can fulfill both contracts. Equality pops to mind.

Yes, that's true; although the basic contract for both interfaces can be overriden (and is in some subclasses). It's often seemed a little odd to me that there is no hybrid of the two - ie, a List that can't contain duplicate values, or a Set that offers randomized access.

Winston
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

Winston Gutkowski wrote:It's often seemed a little odd to me that there is no hybrid of the two - ie, a List that can't contain duplicate values, or a Set that offers randomized access.

It doesn't provide random access, but a LinkedHashSet is a set with an order, which is a hybrid of List and Set to some extent.
Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3433
    
  47

Correct me if I'm wrong, but I'd say that removing an item should cause the indexes of subsequent items to be adjusted, which is not happening at the moment. Straightforward correction of this deficiency will make item removal an O(n) operation. Of course, depending on the need this might not pose a problem.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7029
    
  16

Martin Vajsar wrote:Correct me if I'm wrong, but I'd say that removing an item should cause the indexes of subsequent items to be adjusted...

Ah yes. Well spotted that man. I suppose you could define an interface of your own (SparseList?) that extends java.util.List but redefines some of the operations. It also tends to suggest that null values should be disallowed.

Winston
Jeff Gent
Ranch Hand

Joined: Mar 24, 2011
Posts: 44

Martin Vajsar wrote:Correct me if I'm wrong, but I'd say that removing an item should cause the indexes of subsequent items to be adjusted, which is not happening at the moment. Straightforward correction of this deficiency will make item removal an O(n) operation. Of course, depending on the need this might not pose a problem.


Thanks, I've adjusted it as the following to update the hash values, so the index lines up after a removal.

Jeff Gent
Ranch Hand

Joined: Mar 24, 2011
Posts: 44

Just wanted to post this in case anyone else happen to use it. I made a change to the indexOf to better conform to the ArrayList return of -1 instead of a Null.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Collection Class ArrayListMap
 
Similar Threads
Iterator Pattern
proble in converting ArrayList<String> to ArrayList<Object>
To print MAX and MIN line from a text file
Sorting HashMap by values