Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

How to Retrieve all Equal Objects from a List ?

 
Jose Campana
Ranch Hand
Posts: 339
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello there,

I was wondering if there's an easier way to do what i'm trying to code...

If I have an Ordered list, whose Contained objects correctly implement the Comparable interface's compareTo method, in such a way that after sorting (by using the Collections.sort() method) you get
an ordered list like the one below:

{ "AA", "AA", "AA", "CC", "CC", "DD" }

Is there a way to easily create sub-lists for each of the objects that are common between one-another ?

in other words: For the List above, I should get 3 sub-Lists:

{"AA", "AA", "AA"}
{"CC", "CC"}
{"DD"}

Is there an easy way to do this by using the Collections framework ?

I've just spent more than the adequate time trying to do this, and probably there's an easier way,

I hope to read your comments soon to see If I can fix my algorithm.

How would you guys do it?

Best Regards,

Jose
 
Embla Tingeling
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jose Campana wrote:How would you guys do it?


If the list is ordered you only need to iterate through it once to split it up in sublists like that.

It's because all equal items appear in groups. When you iterate the list and find a new item you create a sublist and fill it with items as long as they're equal. Then you create a new sublist filling it, etcetera.
 
Embla Tingeling
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There's another algorithm which doesn't require the list to be sorted.

This solution uses a HashMap. The HashMap keys are the list items and the HashMap values are the sublists.

You scan the list once and consider each item. If an item is not in the HashMap you enter it together with a sublist containing the item. If the item is already in the HashMap you just add it to the corresponding sublist. Afterwards the HashMap values are the sublists.
 
Siva Masilamani
Ranch Hand
Posts: 385
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
try this
 
Embla Tingeling
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Siva Masilamani wrote:try this


Note that although this algorith may work it's unnecessarily complex. It's a quadratic solution to a linear problem.

 
Siva Masilamani
Ranch Hand
Posts: 385
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
why?

Don;t take it offensively but could you tell me why it is complex?

 
Embla Tingeling
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Siva Masilamani wrote:why?

Don;t take it offensively but could you tell me why it is complex?



Your solution is complex in the algorithmic sense. It's O(N*N) when it only needs to be O(N) (where N is the number of items in the list).

In princple it's because for each unique item in the list you scan the list from the beginning.
 
Jose Campana
Ranch Hand
Posts: 339
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Embla Tingeling wrote:There's another algorithm which doesn't require the list to be sorted.

This solution uses a HashMap. The HashMap keys are the list items and the HashMap values are the sublists.

You scan the list once and consider each item. If an item is not in the HashMap you enter it together with a sublist containing the item. If the item is already in the HashMap you just add it to the corresponding sublist. Afterwards the HashMap values are the sublists.


Good day !

This solution you have just mentioned, which uses a HashMap sounds totally appealing to me, mostly because I was considering HashMap myself.
Embla could you clarify with a little example how would you implement this solution. I really want to see it, an image(in this case some code) is worth a thousand words.

I'd love to see it, and hope it's not much of a trouble.

Sincerely, Jose.
 
Embla Tingeling
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jose Campana wrote:I'd love to see it, and hope it's not much of a trouble.


It's a standard solution to all sorts of counting problems. It goes like this in this particular case,


 
Jose Campana
Ranch Hand
Posts: 339
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Embla,

Let me just say this,

It's Magnificent. Thanks for the contribution. Wow... amazing.

It's good to know that there's always room for learning, I'm glad for it !

I can't help but asking, Where did you learn this technique ?

I'm so curious,

Jose
 
Embla Tingeling
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jose Campana wrote:I can't help but asking, Where did you learn this technique ?


I don't remember anymore but it's a standard algorithm really.

The most common use is for frequency counting I think. For example when you have a textfile and need to count how many times each word occurs in the text. In that case the HashMap would hold a counter for each word.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic