I have a functional program that compares multiple collections of basketball team name objects. It creates a new array of objects that the input collections share in common, and simultaneously prints it out to the console. I am not allowed to change the findMatchingItems method signature that you see in the code. It has to stay as is. Also important to note, duplicate team names are allowed to show up in the list of matching items.
I noticed that my program is inefficient, and makes over 30 comparisons for the sample inputs below. The number of comparisons grow exponentially as the inputs grow incrementally (especially if the lists share many items in common). Is there a way to modify the algorithm so that it operates with a more linear efficiency?
import java.util.*;
public class CommonElements {
List<Comparable> teamList1 = new ArrayList<Comparable>();
List<Comparable> teamList2 = new ArrayList<Comparable>();
List<Comparable> teamList3 = new ArrayList<Comparable>();
public static int listCount = 1;
public static int originalCollectionCount = 0;
Object[] originalCollections;
int comparisonCount;
public static void main(String[] args) {
new CommonElements();
}
public CommonElements() {
comparisonCount = 0;
teamList1.add(new Team("bulls"));
teamList1.add(new Team("lakers"));
teamList1.add(new Team("suns"));
teamList1.add(new Team("pistons"));
teamList1.add(new Team("hornets"));
teamList2.add(new Team("suns"));
teamList2.add(new Team("celtics"));
teamList2.add(new Team("spurs"));
teamList2.add(new Team("lakers"));
teamList2.add(new Team("bulls"));
teamList3.add(new Team("heat"));
teamList3.add(new Team("lakers"));
teamList3.add(new Team("jazz"));
teamList3.add(new Team("suns"));
teamList3.add(new Team("wizards"));
findMatchingItems(new Object[] {teamList1,teamList2,teamList3});
System.out.println(comparisonCount + " comparisons were made.");
}
public Comparable[] findMatchingItems(Object[] collections)
{
ArrayList<Team> queryList = (ArrayList<Team>)collections[0];
ArrayList<Team> secondaryList = (ArrayList<Team>)collections[1];
int matchCount = 0;
int i = 0;
if(listCount == 1){
originalCollectionCount = collections.length;
originalCollections = collections;}
listCount ++;
for(Team x:queryList)
{
for(Team y:secondaryList)
{
if(x.compareTo(y) == 0)
matchCount++;
}
}
Team[] commonList = new Team[matchCount];
for(Team x:queryList)
{
for(Team y:secondaryList)
{
comparisonCount++;
if(x.compareTo(y) == 0)
{
commonList[i] = x;
if(originalCollectionCount == listCount)
{
System.out.println(commonList[i].getName());
}
i++;
break;
}
}
}
if(originalCollectionCount > listCount)
{
findMatchingItems(new Object[] {new ArrayList<Comparable>(Arrays.asList(commonList)),originalCollections[listCount]});
}
return commonList;
}
public int getComparisons()
{
return comparisonCount;
}
}
public class Team implements Comparable<Team> {
String teamName;
public void setName ( String n ) {
teamName = n;
}
public String getName() {
return teamName;
}
public Team(String n) {
setName(n);
}
public int compareTo(Team x)
{
return this.teamName.compareTo(x.teamName);
}
}
x.compareTo(y) == 0
almost always should bex.equals(y);
wherex
is guaranteed to benot null
.Comparable
is almost exclusively idiomatic forsorting
. \$\endgroup\$