aspose file tools*
The moose likes Java in General and the fly likes Searching for a list element without having to iterate Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Searching for a list element without having to iterate" Watch "Searching for a list element without having to iterate" New topic
Author

Searching for a list element without having to iterate

Kjeld Sigtermans
Ranch Hand

Joined: Aug 10, 2006
Posts: 122
I have been trying to find an elegant solution to the following problem.
Let's say we have two Lists (java.util.List) that both solely contain objects of type Person. Person, in turn, has a property 'name' which can be retrieved by Person.getName().
I am interested in any Person from List A that matches the same name as any of the Persons in List B.
My first thought is to create some sort of iteration like
Iterator i = listA.iterator();
while(i.hasNext()) {
Person p = (Person) i.next();
String name = p.getName();
// ...and then do an inner iteration through listB, to compare
// each and every Person.getName() in listB to this name.
}

I don�t like this and I hope you agree. This is especially performance consuming when having large Lists. There must be some kind of comparison possible using some standard library?

Anyway, I made up an alternative which I am about to implement in a professional assignment. I�d like to know if this can be called a more elegant solution.

First, I create a Comparator called SearchComparator which has the mandatory method compare(Object o1, Object o2). Instead of using both attributes, I only use o1, cast it to Person and compare its name to the name I specify through the Comparator�s constructor. If the names are equal, the result of compare is -1, meaning the object will be moved forward in the Collection, otherwise it�s 1, meaning it will be moved backwards.

public class SearchComparator implements Comparator {
private String name;
public SearchComparator (String name) {
this.name = name;
}
public int compare(Object o1, Object o2) {
Person p1 = (Person) o1;
return p1.getName().equals(name) ? -1 : 1;
}
}

Just like in the first example, I�ll be iterating through listA using Iterator, and I retrieve the name of the Person provided by the next iteration. Nothing different.
But now, I pass this name to a new instance of my SearchComparator, and use it to sort listB using Collections.sort(). The effect is, that it the name occurs in listB, it is now at position 0 of listB. So, I test the name to the name of to person at listB.get(0) and if they�re equal, I have found a match. Then comes the next iteration.

Iterator i = listA.iterator();
while(i.hasNext()) {
Person p = (Person) i.next();
Collections.sort(listB, new SearchComparator( p.getName() ));
if ((Person)listB.get(0)).getName().equals( p.getName() ) {
// found a match�
}
}

It�s more code, and might be hard to comprehend at first glance, but I think it�s less performance expensive than using iterations within iterations.
I�d like to know if there are other solutions, perhaps standard framework API�s that solve this with one line of code, like Framework.match(listA, listB, �name�); :-)

Please let me know what you think. Thanks.


Kjeld Sigtermans - SCJP 1.4 - SCWCD 1.4
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
Why not just create a comparator that compares two Person instances by name


Then you can sort and search the list using the name comparator

[ August 10, 2006: Message edited by: Garrett Rowe ]

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Just for the finding and matching bit, see how long it takes to build Maps with name keys. One iteration through each list might pay off in avoiding many iterations later.


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Kjeld Sigtermans
Ranch Hand

Joined: Aug 10, 2006
Posts: 122
Thanks! I also discussed this yesterday with a colleague and he also came up with the second possibilty: create a Set of names from one of the lists (say listA), and then iterate through the other listB and check if the person's name retrieved simply occurs in that temporary name set using Set.contains(name) (I understand that's what you meant Stan?).

The first possibility by Garrett is what I was looking for at first: if I understand this correctly, you make sure listA is sorted alphabetically (which I forgot to mention, it already is) and then iterate through listB: for each Person object do the Collection.binarySearch(listA, thePerson, AlphabeticComparator).

Hmm, tough. I think the binarysearch option looks more elegant, but I think the nameSet option is indeed faster and probably easier to understand for the next guy (just thinking out loud here). I guess the size of the lists probably also plays a big role in such a choice.

Thanks guys.
William Brogden
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12678
    
    5
Personally I would just build maps - ensure that the hashCode and equals functions use all the information you want to compare and reuse the hashCode once it has been calculated.
I would bet that a solution based on existing Collections classes will be faster.
Bill


Java Resources at www.wbrogden.com
Ilja Preuss
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
Originally posted by Kjeld Sigtermans:

I�d like to know if there are other solutions, perhaps standard framework API�s that solve this with one line of code, like Framework.match(listA, listB, �name�); :-)


Well, if you have two Sets of Persons, with the Persons being compared by name,

set1.retainAll(set2);

would do the trick - set1 then contains exactly those persons that were both in set1 and set2.


The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
Mr. C Lamont Gilbert
Ranch Hand

Joined: Oct 05, 2001
Posts: 1170

Just what I was thinking Ilja. You would have to make person use name for equals and hashcode and your set

Be sure to use a List and not a Set to hold the Persons unless no two persons can have the same name;
Kjeld Sigtermans
Ranch Hand

Joined: Aug 10, 2006
Posts: 122
Aha! I wondered if there would be such a simple and elegant solution.
My 'Person' class (the name Person is just an example) is actually a Hibernate domain object mapped to a table. Can I still freely override the equals and hascode methods without any consequences?
(Let alone that I could use hibernate/hql to make the desired intersection in the first place, still I'd like to know).
Ilja Preuss
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
I think if you use TreeSets, you can give it an individual comparator, so that you don't need to change your business objects.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Searching for a list element without having to iterate
 
Similar Threads
How do u access the classes in interfaces ?
Sorting a Hashtable by values & retriving kay-value pair
How to sort a list of things (string, float)?
Use of comparator and comparable interface
Comparable/Comparator query