• Post Reply Bookmark Topic Watch Topic
  • New Topic

Set vs List  RSS feed

 
Ali Khalfan
Ranch Hand
Posts: 129
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I writing a module that requires a unique data structure, but I'm debating whether I should use a TreeSet or an ArrayList. Currently, performance isn't really an issue, since the list carries less than 500 elements.
Naturally, I should go for a Set since it contains unique elements. But I realized a few issues with Sets if I wanted to do a comparison.

E.g. With an ArrayList I can simply implement a new comparator and one I desire a sort I simply do a anytime I update a list. On the other hand, doing this after updating any values in a set seems to be a complicated task, since TreeSet will not automatically update the sorting structure after I update a value in the set.

Also, I can prevent duplicates in the ArrayList by simply checking if the object is contained in the list and by overriding the equals of T.

Wonder if anyone had any opinion about this? I'm inclined more to go with lists at this stage.


 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You want the entries to be unique? That screams Set. You want them sorted too? That screams TreeSet. I don't see why you're even considering a List.

But I realized a few issues with Sets if I wanted to do a comparison


Such as?
 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you need the collection sorted in different ways to perform various task, you could start with a TreeSet using the comparator that would be used the most often, and when needing different order, create an ArrayList from the set and resort when needed. With around 500 elements, that should be good even from a performance perspective.

Another possibility would be to create a class that would keep your items in several TreeSets with various comparators, making sure items are always added/removed to/from all sets, and providing ways to access the set with desired ordering by the clients of your class.
 
Ali Khalfan
Ranch Hand
Posts: 129
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeff Verdegan wrote:You want the entries to be unique? That screams Set. You want them sorted too? That screams TreeSet. I don't see why you're even considering a List.

But I realized a few issues with Sets if I wanted to do a comparison


Such as?


updating the TreeSet everytime one of the elements in the Set is changed is an issue. E.g. if you have a TreeSet with object E sorted by a double value in the object. When you add different elements of type E in the set, they will be sorted. However, when you change any of those elements the TreeSet will not update the order, which introduces complexities. One way I think this could be done is every time I do an update, copy the entire set into another using an iterator then point the reference to the new TreeSet, but that also sounds complicated.

 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ali Khalfan wrote:
Jeff Verdegan wrote:You want the entries to be unique? That screams Set. You want them sorted too? That screams TreeSet. I don't see why you're even considering a List.

But I realized a few issues with Sets if I wanted to do a comparison


Such as?


updating the TreeSet everytime one of the elements in the Set is changed is an issue. E.g. if you have a TreeSet with object E sorted by a double value in the object. When you add different elements of type E in the set, they will be sorted. However, when you change any of those elements the TreeSet will not update the order, which introduces complexities. One way I think this could be done is every time I do an update, copy the entire set into another using an iterator then point the reference to the new TreeSet, but that also sounds complicated.



Remove, update, re-add.

Since you want the elements to be unique, I'd stick with a Set, but whether you use a TreeSet or simply use a HashSet, and then dump it out to a List and sort it when you need the sorted order really depends on the overall usage profile.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ali Khalfan wrote:updating the TreeSet everytime one of the elements in the Set is changed is an issue. E.g. if you have a TreeSet with object E sorted by a double value in the object. When you add different elements of type E in the set, they will be sorted. However, when you change any of those elements the TreeSet will not update the order, which introduces complexities.

First, updating a value used to order an object will always cause you problems, regardless of what structure you use. In the case of a List you'll have to re-sort; in the case of a TreeSet, as Jeff says, the best is to delete, change, and re-add.

In your case, it's also quite dangerous, because you're changing something that is used to determine uniqueness, and that's usually very bad news.

Winston
 
Ali Khalfan
Ranch Hand
Posts: 129
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Winston,
In your case, it's also quite dangerous, because you're changing something that is used to determine uniqueness, and that's usually very bad news


I agree changing something that determines uniqueness is dangerous, but I'm actually changing one of the attributes (e..g. in an object Student with attributes studentId and overallGpa, I'm sorting by overallGpa but the uniqueness is the studentId.

One of the other things I'd like to point is with a list I could do a

Collections.sort(List, Compatator), and choose any kind of comparator (e.g. sort by gpa, or studentId), with a TreeSet I'd have to instantiate a new object and re-populate it
appreciate all the replies.

 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ali Khalfan wrote:I agree changing something that determines uniqueness is dangerous, but I'm actually changing one of the attributes (e..g. in an object Student with attributes studentId and overallGpa, I'm sorting by overallGpa but the uniqueness is the studentId.

When you use a TreeSet, the Comparator you give to it is used to determine the identity of objects. This is part of TreeSet's contract. So what you say might be true in some contexts, but it does not apply to your case.

I don't know of any way other from the ones that were already mentioned (and which you summed up). Collection Framework does not have a collection which would automatically do what you need.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My thought would be to use a TreeSet sorted by StudentID to store the Students, then create different views for the Collection based on Comparator that you want. You could probably use an enum to do the work... for example:

 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Luke wrote:My thought would be to use a TreeSet sorted by StudentID to store the Students, then create different views for the Collection based on Comparator that you want. You could probably use an enum to do the work...

Glad I'm not the only one to use enums in this context. I've created a very useful class called Index for producing compound orderings, and it works especially well with enums (partly because they have names).

@Ali: Most Collections also have fast methods to convert to arrays, so you might find it a bit faster to use a HashSet<Student> for the 'base' Set that Steve suggests, and then create your sorted sets with something like:
Student[] studentsByName = Arrays.sort(baseSet.toArray(new Student[0]), StudentViews.Name);

TreeSet is generally only useful if you want a sorted Set, whereas in your case you really only want it to ensure no duplicate IDs, so a HashSet is likely to be quicker and more compact.

Winston
 
Vinod Vijay
Ranch Hand
Posts: 165
Java Tomcat Server Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ali Khalfan wrote:I writing a module that requires a unique data structure, but I'm debating whether I should use a TreeSet or an ArrayList. Currently, performance isn't really an issue, since the list carries less than 500 elements.
Naturally, I should go for a Set since it contains unique elements. But I realized a few issues with Sets if I wanted to do a comparison.

E.g. With an ArrayList I can simply implement a new comparator and one I desire a sort I simply do a anytime I update a list. On the other hand, doing this after updating any values in a set seems to be a complicated task, since TreeSet will not automatically update the sorting structure after I update a value in the set.

Also, I can prevent duplicates in the ArrayList by simply checking if the object is contained in the list and by overriding the equals of T.

Wonder if anyone had any opinion about this? I'm inclined more to go with lists at this stage.




Go for TreeSet if you want unique and ordered collection of elements
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Vinod Vijay wrote:Go for TreeSet if you want unique and ordered collection of elements

I think we've got a bit past that. My suggestion would be to read the whole thread.

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!