Win a copy of Beginning Java 17 Fundamentals: Object-Oriented Programming in Java 17 this week in the Java in General forum!
  • 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:
  • Tim Cooke
  • Campbell Ritchie
  • Ron McLeod
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Rob Spoor
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Tim Moores
  • Jesse Silverman
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Frits Walraven

How to Retrieve all Equal Objects from a List ?

 
Ranch Hand
Posts: 339
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Ranch Hand
Posts: 385
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
try this
 
Embla Tingeling
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
WHAT is your favorite color? Blue, no yellow, ahhhhhhh! Tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic