aspose file tools*
The moose likes Performance and the fly likes Vector or ArrayList ? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "Vector or ArrayList ?" Watch "Vector or ArrayList ?" New topic
Author

Vector or ArrayList ?

Aditya Kanitkar
Ranch Hand

Joined: Aug 08, 2009
Posts: 72
Hi,

I was thinking about asking this in my recent post, But decided to
make it new......

As my code is using So many Vectors here & there,
I was thinking about replacing them with some other Collection (Like ArrayList) which
would increase my performance.

Will it work for me...?? Because i have to handle the Vectors after every few Statements...


Note: Currently, I do not have any Synchronized method in my code.

Thanks.
William Brogden
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12835
    
    5
If only one Thread is accessing these Vector collections, sure. Replacing with ArrayList will not cause a problem, but it would surprise me if you could measure any difference in execution time.

Bill
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Aditya Kanitkar wrote:
Currently, I do not have any Synchronized method in my code.


It may be because of Vector methods are synchronized . Sure you can replace Vector by ArrayList. but again, you need to test your code thoroughly whether concurrent threads affect your mutable objects or not. if it affects then, consider java.util.concurrent.CopyOnWriteArrayList

hth
Aditya Kanitkar
Ranch Hand

Joined: Aug 08, 2009
Posts: 72
OK.

But does it mean that, if i change all Vectors into ArrayList, there will be 0% change in
my code performance...?? Or some % change atleast...??
Thomas Kiersted
Greenhorn

Joined: Feb 24, 2007
Posts: 22

There will be some decrease in execution time. But unless you are using your vectors quite heavily, it is unlikely that you will be able to notice the difference. Even if the vectors are by far the bottleneck of your code, expect modest gains - it wouldn't halve your execution time even if the only thing you do is modify Vectors.
ganesh roti
Greenhorn

Joined: May 16, 2010
Posts: 17
it depends on how are you using your vectors/arraylist..Note that ArrayList is position based while vector is both position and hash based. So you can conside Vectoris made up of both the features of a LinkedList and ArrayList.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
ganesh roti wrote:Note that ArrayList is position based while vector is both position and hash based. So you can conside Vectoris made up of both the features of a LinkedList and ArrayList.

I'm sorry, but that's not remotely true. Vector and ArrayList are very similar to each other, but not to the other classes mentioned; Vector is not hash based, and no more similar to LinkedList than ArrayList is. Yes, they're all lists, but neither Vector nor ArrayList has links like LinkedList has. Also, hashes are not present in LinkedList, so your erroneous assertion that Vector is "hash based" would not have anything to do with your equally erroneous assertion that "Vector is made up of both the features of a LinkedList and ArrayList".
ganesh roti
Greenhorn

Joined: May 16, 2010
Posts: 17
I guess you are misleading others. If Vector is not hasing based on its key then it would have not provided Vector.get(int index)? From where does this index came from then if it is not key-hashing based. I never said it is full of features but to identify the key difference that you can remove or get the element directly on the index in case of Vector while this is not true in case of arraylist.
Tim Holloway
Saloon Keeper

Joined: Jun 25, 2001
Posts: 16303
    
  21

Vectors do not use hashing. If you tell a vector to remove object "xyz" from itself, it will do something a lot like the following:


"get" is simply the same thing as array indexing in the underlying object array inside the Vector. "remove" moves all higher elements in the Vector down one slot, and shortens the internal array by 1.

You can do all of this and more without hashing, although the time it takes is proportional to the size of the Vector.


Customer surveys are for companies who didn't pay proper attention to begin with.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
ganesh roti wrote:to identify the key difference that you can remove or get the element directly on the index in case of Vector while this is not true in case of arraylist.

You can remove or get an element directly in an ArrayList, almost exactly the same way you can in a Vector. There is no substantial difference between the two, except that Vector is synchronized and ArrayList isn't. Both use an internal array, and resize it when necessary. Neither uses hashing. They both have an extremely fast get() method (faster even than hashing) and a comparatively slow remove() method. You can look at the source code for both to see for yourself in the file src.zip, or using whatever IDE you prefer.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
Tim Holloway wrote:You can do all of this and more without hashing, although the time it takes is proportional to the size of the Vector.

To clarify, that's true for the remove(), but not the get(). For get() the time is O(1) in a Vector or ArrayList.
Aditya Kanitkar
Ranch Hand

Joined: Aug 08, 2009
Posts: 72
Mike Simmons wrote:
You can remove or get an element directly in an ArrayList, almost exactly the same way you can in a Vector. There is no substantial difference between the two, except that Vector is synchronized and ArrayList isn't. Both use an internal array, and resize it when necessary. Neither uses hashing. They both have an extremely fast get() method (faster even than hashing) and a comparatively slow remove() method. You can look at the source code for both to see for yourself in the file src.zip, or using whatever IDE you prefer.


That is correct...

But didn't get you on this one...

Mike Simmons wrote:To clarify, that's true for the remove(), but not the get(). For get() the time is O(1) in a Vector or ArrayList.

Alpesh Padra
Ranch Hand

Joined: Jan 10, 2010
Posts: 41
It's always make a sense when you are using a data structure in your application.

Use non-syncronization DS when there is no scope for multiple thread access DS.

Moreover, it doesnt make sense for 10-100 elements but it make lot of sense for 10000-100000 elements.

You will get performance hit after your application is growing.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
Aditya Kanitkar wrote:But didn't get you on this one...

Mike Simmons wrote:
Tim Holloway wrote:"get" is simply the same thing as array indexing in the underlying object array inside the Vector. "remove" moves all higher elements in the Vector down one slot, and shortens the internal array by 1.

You can do all of this and more without hashing, although the time it takes is proportional to the size of the Vector.

To clarify, that's true for the remove(), but not the get(). For get() the time is O(1) in a Vector or ArrayList.

I've gone back and added more of the original quotes, to make it clearer. Tim was talking about "get", and then about "remove". Then he said that "the time it takes is proportional to the size of the Vector". It's not clear whether that last part is referring to get() and remove(), or just remove(). So I was trying to clarify - it's not true that get() takes time proportional to the size of a Vector. It is true that remove() takes time proportional to the size of the Vector. For a Vector, remove() is slow (O(N)) and get() is fast (O(1)).

Well, actually time for remove() is proportional to the distance from the end of the Vector, which is often proportional to and limited by the size. But not always.
ganesh roti
Greenhorn

Joined: May 16, 2010
Posts: 17
I am not getting why you are insiting that ArrayList is also not hash based. If it is not hash based then why ArrayList is faster than LinkedList in case of retrival? To make its object postion based, ArrayList has to create something like a map inside to keep the pointers for the positions. So isn't that similar to hashing(Key, value)?
ganesh roti
Greenhorn

Joined: May 16, 2010
Posts: 17
I m sorry yesterday i was telling Vector as combination of ArrayList and LinkedList. I guess it was a type mistake. But that is wrong. Actually i want to say it is a mbination feature of ArrayList and HashMap. Why? Because in vector you can add values based on positions and as well as based on keys. And dont mind if i add as i have seen sometimes vectors run fast than Hashmap if you are using Vector as a key value like we do in Hashmap
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
ganesh roti wrote:I am not getting why you are insiting that ArrayList is also not hash based.

You haven't actually looked at the source code yet, have you?

ganesh roti wrote:If it is not hash based then why ArrayList is faster than LinkedList in case of retrival?

Because hashing is not the only way to retrieve something quickly. There are other ways. Such as, oh I don't know... using arrays, maybe?

ganesh roti wrote:To make its object postion based, ArrayList has to create something like a map inside to keep the pointers for the positions. So isn't that similar to hashing(Key, value)?

Well, it's kind of similar, in the sense that both are fast compared to using get() on a LinkedList. But kind of different, in the sense that "hash" refers to a specific technique, which in Java means calling the hashCode() method, used in hash table implementations such as Hashtable and HashMap. But hashing is not used in Vector or ArrayList. Ever. At all. In any way. Period. End of story. Really.

It sounds like maybe you've learned a little bit about one particular technique for retrieving data from a data structure: hashing. That's cool - hashing is a very good technique. But it's not the only one out there. (Hint: arrays.) And it's not helpful to talk about hashing as if it's the only way one could possibly retrieve data quickly using a key. It isn't. (Hint: arrays.) Especially if the key is an integer with nice sequential values like 0, 1, 2, 3, etc. (Hint: arrays.)

By the way, have you learned about arrays yet? It really would be helpful here. Arrays are very useful things. I don't know why I felt like mentioning that, but I did.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
ganesh roti wrote:And dont mind if i add as i have seen sometimes vectors run fast than Hashmap if you are using Vector as a key value like we do in Hashmap

Wait - you're saying that there is some other technique that can sometimes give faster results than hashing? No!!! I am shocked - SHOCKED!!! - at this suggestion.
ganesh roti
Greenhorn

Joined: May 16, 2010
Posts: 17
But that is reality i have seen. Try using Vector<int, objects> and HashMap<Integer, Objects>. For me vector gave a significant performance.
ganesh roti
Greenhorn

Joined: May 16, 2010
Posts: 17
I am still not convinced
Because for me, whenever you talk about the word "index", it means hashing by default because you can create index only by hashing . Sounds complicated.
Andrew Monkhouse
author and jackaroo
Marshal Commander

Joined: Mar 28, 2003
Posts: 11523
    
100

As has been hinted several times, you can benefit by looking at the source code. You should have the Sun source code available to you, but in case you don't, you can also look at source code online. For example, the first link on Google when I searched was for the Apache Harmony version of java.html. (In case you are unaware of it, Apache Harmony is an open source implementation of Java - so if you wanted Java on a computer that Sun does not support, you could install it yourself as an open source application.) You might want to look at the get() method. Notice the complete and utter lack of hashing in that method (or in the entire class for that matter).


The Sun Certified Java Developer Exam with J2SE 5: paper version from Amazon, PDF from Apress, Online reference: Books 24x7 Personal blog
William Brogden
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12835
    
    5


From the Java 6 source code for java.util.Vector class.

Every serious student of Java should have the source available in his/her working environment to answer questions like this and to educate themselves on good Java practice.

Bill
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Vector or ArrayList ?