• 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

Vector or ArrayList ?

 
Ranch Hand
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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...??
 
Greenhorn
Posts: 22
Opera Windows XP
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Saloon Keeper
Posts: 27762
196
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.


 
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
author and jackaroo
Posts: 12200
280
Mac IntelliJ IDE Firefox Browser Oracle C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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).
 
William Brogden
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


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'm doing laundry! Look how clean this tiny ad is:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic