opinions? re: optimal choice of Collection-implementation? ...
2 posts in topic
Flat View  Flat View
TOPIC ACTIONS:
 

Posted By:   Larry_LeFever
Posted On:   Wednesday, August 8, 2001 03:46 PM

I plan to avoid any Map implementations, since I do not have name-value pairs, though I would like the constant-time of hashing. Also, I want to avoid the linear time of sequential search. It seems a worthwhile compromise is a Vector (or ArrayList), using Collections.binarySearch() (log n, if I understand correctly) to get the index at which to insert in sorted order (as opposed to Collections.sort()-ing just before each search), and then that same method (binarySearch()) for retrieval, instead of contains(), unless contains uses binarySearch (does it?). I presume binarySearch is used by contains() in Tree implementations, but I don't see a Tree implementation that does not use a Map (e.g., TreeSet apparently "uses" a TreeMap, per the docs). I want to avo   More>>

I plan to avoid any Map implementations, since I do not have name-value pairs, though I would like the constant-time of hashing. Also, I want to avoid the linear time of sequential search. It seems a worthwhile compromise is a Vector (or ArrayList), using Collections.binarySearch() (log n, if I understand correctly) to get the index at which to insert in sorted order (as opposed to Collections.sort()-ing just before each search), and then that same method (binarySearch()) for retrieval, instead of contains(), unless contains uses binarySearch (does it?). I presume binarySearch is used by contains() in Tree implementations, but I don't see a Tree implementation that does not use a Map (e.g., TreeSet apparently "uses" a TreeMap, per the docs). I want to avoid the memory-demand (and unnecessary instantiations) involved in using a Map (of whatever type) in this case. Any advice?

   <<Less

Re: opinions? re: optimal choice of Collection-implementation? ...

Posted By:   Christopher_Schultz  
Posted On:   Friday, August 10, 2001 11:34 AM

Don't forget that you'll have to sort your collection before you binarySearch it, since the binary search algorithm only works on sorted data.



If you find that your data set changes a lot, forget sorting and then searching every time. Just perform a linear search.



Do you have hard performence demands? If not, just write whatever code is easiest to write/read/maintain.



-chris

Re: opinions? re: optimal choice of Collection-implementation? ...

Posted By:   John_Zukowski  
Posted On:   Wednesday, August 8, 2001 06:30 PM

If you are constantly inserting and removing elements, the cost involved in maintaining the ARRAY in sorted order is not worth the hassle.


Since you obviously feel that Sun made the wrong choice in implementing a Set by having it backed by a Map, create your own implementation that does things differerntly.

About | Sitemap | Contact