How do I reduce the number of loop iterations needed to compare lists?

Question

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);
    }        
}

Answer 1

If, you override the equals() and the hashCode methods in your Team class, like this:

public class Team {
    final String name;

    public Team(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof Team
                && ((Team) o).name.equals(name);
    }

    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

You could use a HashMap, that you can use to aggregate the number of teams in all collections:

private static List<Team> getTeamsInAllLists(List<Team>[] teamList) {
    Map<Team, Integer> map = new HashMap<Team, Integer>();

    for (List<Team> teams : teamList) {
        for (Team team : teams) {
            if(map.containsKey(team)){
                map.put(team, map.get(team)+1);
            } else {
                map.put(team, 1);
            }
        }
    }

    List<Team> teamsInAllLists = new ArrayList<Team>();

    for (Map.Entry<Team, Integer> entry : map.entrySet()) {
        if(entry.getValue() == teamList.length){
            teamsInAllLists.add(entry.getKey());
        }
    }
    return teamsInAllLists;
}

Answer 2

How many comparisons is unimportant, clock time is what counts!

package com.stackoverflow;

import com.google.common.base.Function;
import com.google.common.base.Joiner;
import com.google.common.base.Predicate;
import com.google.common.collect.*;
import com.google.common.math.LongMath;

import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import java.math.BigInteger;
import java.util.*;

public class Q26321664
{
    private static final Set<Team> TL1;
    private static final Set<Team> TL2;
    private static final Set<Team> TL3;

    static
    {
        TL1 = Team.createTeams("bulls,lakers,suns,pistons,hornets".split(","));
        TL2 = Team.createTeams("suns,cletics,spurs,lakers,bulls".split(","));
        TL3 = Team.createTeams("heat,lakers,jazz,suns,wizards".split(","));
    }

    private static class Team implements Comparable<Team>
    {
        public static Set<Team> createTeams(@Nonnull final String ... names)
        {
            return Sets.newTreeSet(Lists.transform(Arrays.asList(names), new Function<String, Team>()
            {
                @Nullable
                @Override
                public Team apply(@Nullable final String name)
                {
                    return new Team(name);
                }
            }));
        }

        @Nonnull
        private final String name;

        private Team(@Nonnull final String name)
        {
            this.name = name;
        }

        @Override
        public boolean equals(@Nullable final Object o)
        {
            if (this == o) { return true; }
            final Team team = (Team) o;
            return team != null && name.equals(team.name);

        }

        @Override
        public int compareTo(final Team t) { return this.name.compareTo(t.name); }

        @Override
        public int hashCode() { return name.hashCode(); }
    }

    private static final Comparable[] findMatchingItems(Object[] collections)
    {
        final Set<Comparable> allTeams = new HashSet<>();
        allTeams.addAll(TL1);
        allTeams.addAll(TL2);
        allTeams.addAll(TL3);

        final Multiset<Team> ms = HashMultiset.create();
        for (final Object o : collections)
        {
            ms.addAll((Collection) o);
        }

        final List<Comparable> intersections = Lists.newArrayList(Iterables.filter(allTeams, new Predicate<Comparable>()
        {
            @Override
            public boolean apply(@Nullable final Comparable input)
            {
                return ms.count(input) > 1;
            }
        }));
        return intersections.toArray(new Comparable[intersections.size()]);
    }

    private static double mean(@Nonnull final long[] times)
    {
        double sum = 0;
        for (final long time : times)
        {
            sum = sum + time;
        }
        return sum / times.length;
    }

    private static double median(@Nonnull final long[] times)
    {
        final int midpoint = times.length / 2;
        final long mp1 = times[midpoint];
        final long mp2 = times[midpoint + 1];
        return (mp1 + mp2) / 2;
    }

    public static void main(final String[] args)
    {
        final ImmutableList<Set<Team>> of = ImmutableList.of(TL1, TL2, TL3);
        final Object[] collections = of.toArray(new Object[of.size()]);
        final int repetitions = 1000000;
        final long[] elapsedTimes = new long[repetitions]; // this is to limit impact on what goes on in the loop!
        for(int i =0; i < repetitions; i++)
        {
            final long s = System.nanoTime();
            findMatchingItems(collections);
            elapsedTimes[i] = System.nanoTime() - s;
        }
        Arrays.sort(elapsedTimes);
        System.out.println("All times in nano seconds!");
        System.out.println("elapsedTimes[0] = " + elapsedTimes[0]);
        System.out.println("elapsedTimes = " + elapsedTimes[elapsedTimes.length - 1]);
        System.out.println("mean(elapsedTimes) = " + mean(elapsedTimes));
        System.out.println("median(elapsedTimes) = " + median(elapsedTimes));
    }
}

Pentium Q9650 with 8GB RAM (JDK 1.7.0_67/OSX) results (All times in nano seconds)

elapsedTimes[0] = 1000  
elapsedTimes[elapsedTimes.length - 1] = 50435000  
mean(elapsedTimes) = 2653.372  
median(elapsedTimes) = 2000.0  

Answer 3

As others have indicated, creating a HashSet of the teams lets you compare teams in a more direct way. You avoid the m*n loop to compare each teams of one list to each teams of the other.

This requires implementing equals() and hashcode(). I have also moved the comparisonCount variable in the Team class, where it is more reliable.

public class Team
{
    public static int comparisonCount = 0;

    String teamName;

    public void setName(String n) {
        teamName = n;
    }

    public String getName() {
        return teamName;
    }

    public Team(String n) {
        setName(n);
    }


    @Override
    public boolean equals(Object o) {
        comparisonCount++;
        return o instanceof Team
                && ((Team) o).teamName.equals(teamName);
    }

    @Override
    public int hashCode() {
        return teamName.hashCode();
    }
}

But instead of dealing with sets directly, you can use Java's Collection methods to compute the intersection.

Note that I have changed the signature. It doesn't make sense to refer to a Team as a Comparable<Team>.

public testCommonElements() {

    ... (build team lists)

    Team.comparisonCount = 0;
    Team[] commonTeams = findMatchingItems(new List[]{teamList1, teamList2, teamList3});

    for(Team team : commonTeams){
        System.out.println(team.getName());
    }
    System.out.println(Team.comparisonCount + " comparisons were made.");          
}

public Team[] findMatchingItems(List<Team>[] collections)
{
    Set<Team> commonTeams = new HashSet<Team>(collections[0]);
    for( int i=1 ; i<collections.length ; i++ ){
        List<Team> list = new ArrayList<Team>(collections[i]);
        list.retainAll(commonTeams);
        commonTeams.retainAll(list);
    }
    return commonTeams.toArray(new Team[commonTeams.size()]);
}

It uses 22 comparisons.

You could also write

public Team[] findMatchingItems(List<Team>[] collections)
{
    Set<Team> commonTeams = new HashSet<Team>(collections[0]);
    for( int i=1 ; i<collections.length ; i++ ){
        commonTeams.retainAll(collections[i]);
    }
    return commonTeams.toArray(new Team[commonTeams.size()]);
}

But doing so is more expensive. You have to understand that set.retainAll(list) creates a HashSet from the list, and then compares each element of the set with the list. And building the HashSet requires to compare all elements of the list with each other. By reducing the list to only the elements in the commonTeams set, you can reduce the cost of building the HashSet in the second retainAll.