Comparing two ArrayList of Objects to find differences

Processing Coding Questions
#1

Hello! I am working with two ArrayList of objects with more than 6000 elements for each ArrayList. Most of these objects are the same but I need to find what are the differences between the two lists.

Is there a quick way to compare two ArrayList of objects?

As a reference this is my object:

class Follower {
  String id;
  String name;
  String username;
  
  Follower(String id, String name, String username) {
    this.id = id;
    this.name = name;
    this.username = username;
  }
}

I need to find which “Follower” (searching by ids or username) is different between the two lists.

I already tried with a nested loops but it takes ages.

Thanks

#2

If the elements in both lists are unordered then comparing 2 lists with 6000 elements in each requires 3.6 million comparisons.

The solution is challenging but we can get that down to a maximum of 12000 comparisons.

The algorithm to do this requires that both lists are sorted on the search value. In this case you have two possible search parameters either id or username. To do this you would need to create a class for each search value that implements the java.util.Comparator class here is an example for id

class CompareID implements Comparator<Follower> {

    public int compare(Follower f1, Follower f2){
      return f1.id.compareTo(f2.id);
    }
}

Assuming that you have two lists of followers called listA and listB declared and created with

ArrayList<Follower> listA = new ArrayList<Follower>();
ArrayList<Follower> listB = new ArrayList<Follower>();

Both lists can be sorted with -

  Collections.sort(listA, new CompareID());
  Collections.sort(listB, new CompareID());

Once both lists are sorted we get to the hard bit. :slightly_smiling_face:

More to follow

#3

I am assuming that you want a list that contains both

  1. any Follower in list A that is not in list B
  2. any Follower in list B that is not in list A

So decalre and create a list to hold these followers

ArrayList<Follower> difference = new ArrayList<Follower>();

then call this method

void findDifferenceOnId(ArrayList<Follower> list) {
  list .clear();  //  make sure we start with an empty list
  int idxA = 0, idxB = 0; // indexes into lists
  while (idxA < listA.size() && idxB < size()) {
    Follower fa = listA.get(idxA);
    Follower fb = listB.get(idxB);
    int v = fa.id.compareTo(fb.id);
    if (v < 0) { 
      list.add(fa);
      idxA++;
    } else if (v > 0) {
      list.add(fb);
      idxB++;
    } else { // same
      idxA++;
      idxB++;
    }
  }
  // At least one list is exhausted so get reamining followers
  while (idxA < listA.size()) list.add(listA.get(idxA++));
  while (idxB < listB.size()) list.add(listB.get(idxB++));
}

Since each follower is visited once only then the maximum number of comparisons is the sum of the Followers in both lists.

Although there are no syntax errors in this code I have not tested for logical errors. Have to leave something for you to do LOL

#4

Hi @quark, thank you very much for your reply.
After posting here on the forum I googled for other solutions and I found out that Lists have a removeAll function. So when I created the objects I also created an ArrayList of strings with just the username.

Here’s the part of the code for the comparison between the two lists:

ArrayList<String> oldF = new ArrayList<String>();
ArrayList<String> newF = new ArrayList<String>();
/* Here I fill the ArrayList with data */
List<String> sourceList = new ArrayList<String>(oldF);
List<String> destinationList = new ArrayList<String>(newF);
  
sourceList.removeAll(newF);  
destinationList.removeAll(oldF);
#5

It is difficult, if not impossible to see how the answer you have just provided has any relationship to the question as posted.

It’s a shame that you didn’t google the problem before posting in this forum as it would have saved me a lot of effort. My only consolation is that others might find the information useful.

1 Like
#6

I typed my reply too quickly so I’ll try to explain myself a little better. When I write some code I’m always looking for the best solution (as I think everybody does) in term of code, performance and results. I started with the idea of having objects because I though it would be easier comparing objects instead of other data types. I was wrong and that’s why I posted my first message (I thought I was missing something easy but, your answer confirmed that comparing two objects is hard). I saw your answer and applied it to my program but although it worked I didn’t like my code so I refactored everything and then realised that I didn’t need to have those objects.

Probably my question in the forum would’ve been more helpful if I asked: “I have this set of data, what’s the best way to compare them” but I think nobody wasted time: here we have the solution of my first question and also some consideration on the overall approach of this problem.

#7

if you are trying to do this:
image
then the program

ArrayList<Float> a = new ArrayList<Float>(), b = new ArrayList<Float>();
void setup() {
  float aa[] = {1,2,3,6,7,8};
  float bb[] = {2,3,4,8,9,11};
  addTo(aa, bb);
  printArray(compare(a,b));
}
void draw() {
  
}
void addTo(float[] aa, float[] bb) {
  for(int i = 0; i < aa.length; i++) a.add(aa[i]);
  for(int i = 0; i < bb.length; i++) b.add(bb[i]);
}
ArrayList<Float> compare(ArrayList<Float> input1, ArrayList<Float> input2) {
  ArrayList<Float> result = new ArrayList<Float>();
  for(int i = 0; i < input1.size() && i < input2.size(); i++) {
    if(input1.contains(input2.get(i))) {
      result.add(input2.get(i));
    }
  }
  return (result);
}

image
should work