Efficient way to compare different types of List of Objects

Question

public class State{

String code;
int occurValue;
int name;

}

public class Equi{
String code;
int occurValue;
int macAddress;

}

Having 2 classes of different types. I'm having a List<State> and List<equi>. In these lists if code and occurValue is same, I need to move that to different List. How can I achieve this, googling gave me so many options line Comparable, Comparator. Let me know which is the most efficient way to achieve this. Thanks in advance.

Answer 1

If there is no additional information on the lists, then the most efficient algorithm is to compare each element of the one list with each element of the other:

for (State s : stateList) {
    for (equi e : equiList) {
        if (s.code.equals(e.code) && s.occurValue == e.occurValue) {
            // add to another list
        }
    }
}

This is O(n * m) (where n is the size of stateList and m is the size of equiList).

If the two lists are sorted, then more efficient algorithms can be used. For example, in pseudocode:

for (int i = 0; i < stateList.size(); i++) {
    int j = 0;
    State s = stateList.get(i);
    while (equiList.get(j) is smaller than s) {
        j++;
    }
    equi e = equiList.get(j);
    if (s.code.equals(e.code) && s.occurValue == e.occurValue) {
        // add to another list
    }
}

This is O(m + n). Of course, for this to work you will have to write comparison functions (one for comparing a State with a State, one for comparing an equi with an equi and one for comparing a State with an equi).

By the way, Java naming conventions dictate that classes start with a capital letter, so it should be Equi, not equi.

Answer 2

I would use an own defined method to do that, a Boolean <compare(State state, Equi equi)> or something like that with the given list items as parameters. And the code:

//You have to iterate the method with a for loop for example
//In different situations you need different iterating methods, for example you add 
//1 element to Equi:
//You compare all State element with the new Equi element, but just with that ONE
for (int i =0; i < stateList.size(); i++ {
  flag = compare(stateList.get(i),equiList.get(<indexOfNewElement>); // flag is a boolean value
  if (flag) {
    //moving metod and stuff...
  }
}
//this way you don't make unnecessary steps. It's one example, there are many other situation

Boolean compare(State state, Equi equi) { // You add List elements as parameters
  if (state.getCode().equals(equi.getCode())) { // I prefer to use getters, it depends on your code and preferences
    if (state.getOccurValue() == equi.getOccurValue()) { //same here
      return true; //If returns true, an other method move it.
    } else {
      return false;
    }
  } else { //if the first ones aren't equal needless to check the second values
    return false;
  }
}

This way you can use this method for all comparison, but every time you need to write an iterator. It means more coding, but less runtime. For example if the lists are ordered by code in ABC order, you can avoid to compare the "k*" with "a*" using a flag or anything.

Answer 3

It highly depends on your definition of "efficient".

If you are not interested in time you can just create a double foreach loop and compare each item with each other. This is brute-force and not time-efficient (as it is O(n^2)), but saves you a lot of programming time you can spend on something more useful. The same goes with a fairly small number of items (I suggest < 10.000), where time-optimizations usually don't pay of.

If you want it time-efficient you can use some abstract data structure to help you. For example if the "code"-field is unique in each set, create a HashMap where the key refers to "code" and the value is the Equi referenct. You can then iterate over your States and query the HashMap for a matching Equi. Ask the returned Equi for its occurValue. You may also introduce a second HashMap with the occurValues as keys. This should give you O(n) for the comparison part.

A more object-oriented approach you be to create an interface IHasCodeAndOccurValue and let State and Equi implement it. Then you implement equals(IHasCodeAndOccurValue other) methods in both classes. You insert both data sets in a List each and call stateList.retainAll(equiList). This might be the most elegant approach and - depending on your chosen List implementation - can also run in O(n).

As you can see, there are several ways of optimizing this code. Without knowing the details it is pure speculation how to proceed.